Решение ограничений зависимости

У меня есть классическая проблема решения зависимостей. Я думал, что я направился в правильном направлении, но теперь я попал в блокпост, и я не уверен, как действовать дальше.

Фон

В известном юниверсе (кеше всех артефактов и их зависимостях) каждая взаимосвязь между артефактами и версиями имеет 1- > n, и каждая версия может содержать другой набор зависимостей. Например:

A
  1.0.0
    B (>= 0.0.0)
  1.0.1
    B (~> 0.1)
B
  0.1.0
  1.0.0

Учитывая набор "ограничений спроса", я хотел бы найти наилучшее возможное решение (где "наилучшим" является наивысшая возможная версия, которая все еще удовлетворяет всем ограничениям). Здесь пример "ограничений спроса" с решением:

solve!('A' => '~> 1.0') #=> {"A" => "1.0.1", "B" => "0.1.0"}

В действительности, есть значительно больше требований:

solve!('A' => '~> 1.0', 'B' => '>= 0.0.0', 'C' => '...', 'D' => '...')

(Версии следуют стандарту семантическое исполнение версии)

Я пробовал

В текущем решении используется обратная трассировка и не очень эффективна. Я немного поработал и нашел проблемы с производительностью, связанные с размером Вселенной. Я решил попробовать альтернативный подход и построить график "возможности" DAG для всего набора требований:

class Graph
  def initialize
    @nodes = {}
    @edges = {}
  end

  def node(object)
    @nodes[object] ||= Set.new
    self
  end

  def edge(a, b)
    node(a)
    node(b)

    @nodes[a].add(b)

    self
  end

  def nodes
    @nodes.keys
  end

  def edges
    @nodes.values
  end

  def adjacencies(node)
    @nodes[node]
  end
end

Затем я создаю DAG всех возможных решений из вселенной. Это значительно уменьшает количество возможностей и дает мне фактический график с реальными возможностями артефакта для работы.

def populate(artifact)
  return if loaded?(artifact)

  @graph.node(artifact)

  artifact.dependencies.each do |dependency|
    versions_for(dependency).each do |dependent_artifact|
      @graph.edge(artifact, dependent_artifact)
      populate(dependent_artifact)
    end
  end
end

private

def versions_for(dependency)
  possibles = @universe.versions(dependency.name, dependency.constraint)

  # Short-circuit if there are no versions for this dependency,
  # since we know the graph won't be solvable.
  raise "No solution for #{dependency}!" if possibles.empty?

  possibles
end

Итак, из предыдущего примера графика, если бы у меня были требования 'A', '>= 0.0.0', моя DAG выглядела бы так:

+---------+   +---------+
| A-1.0.0 |   | A-1.0.1 |
+---------+   +---------+
       /  \        |
      /    \       |
     /      \      |
    /        \     |
+---------+   +---------+
| B-1.0.0 |   | B-0.1.0 |
+---------+   +---------+

Так как возможными значениями для A-1.0.0 являются "любое значение B", но ограничения для A-1.0.1 являются "любыми B в серии 0.1". В настоящее время он работает (с полным набором тестов), как ожидалось.

Другими словами, DAG берет абстрактные ограничения зависимостей и создает "реальный" график, где каждое ребро является зависимостью, и каждая вершина (я называл ее a node) является фактическим артефактом. Если решение существует, оно находится где-то на этом графике.

И, к сожалению, здесь я застреваю. Я не могу придумать алгоритм или процедуру, чтобы найти "лучший" путь через этот граф. Я также не знаю, как определить, разрешен ли граф.

Я провел некоторое исследование, и я думал, что топологическая сортировка (tsort) - это тот процесс, который мне нужен. Однако этот алгоритм определяет порядок вставки для зависимостей, а не лучшее решение.

Я уверен, что это проблема np-hard и, вероятно, будет иметь неэффективное время выполнения. Я, хотя использование DAG уменьшит количество сравнений, которые я должен выполнить. Неужели я ошибаюсь в этом предположении? Есть ли лучшая структура данных для использования?

Заключительные мысли

  • Я отметил этот вопрос "Ruby", потому что я использую Ruby, но я ищу psuedo-code/direction. Это не проблема домашних заданий - я искренне пытаюсь учиться.
  • Я попытался дать как можно больше фона, но, пожалуйста, оставьте комментарий, если вы хотите получить более подробную информацию по определенной теме. Это уже длинный пост, но у меня есть больше кода, который я могу предоставить.

Ответы

Ответ 1

Я не эксперт в этой проблеме, я предлагаю полное решение, которое не является оптимальным, поскольку есть много вещей, которые можно оптимизировать.

Алгоритм прост, он идеально рекурсивный набор . пересечение DFS :

Алгоритм

Защита

Define: Name as String on format [ .* ]
Define: Version as String on format [ dd.dd.dd ]
Define: Revision as { Name, Version, Requirement }
Define: Range<T> as { min<T>, max<T> }
Define: Condition as { Name, Range<Version> }
Define: Requirement as Set<Revision> OR as Set<Condition>
Define: Component as { Name, Range<Version>, Requirement }
Define: System as Set<Component>

Ввод

Input: T as System aka basis
Input: C as Set<Condition> aka conditions to apply

Инициализация

Init: S as Set<Condition> = { S[i] as Condition | S[i] = {T[i].Name,T[i].Range} }
Init: Q as Stack<Condition> = { push(q) | q[i] = C[i] }

Процесс

for (Condition c in C)
{
    S.find(c.Name).apply(c)
}

While (Q.size > 0)
{
    Condition q = Q.pop()

    switch (T.assert(S.find(q.Name),q))
    {
      case VALID:
        S.find(q.Name).apply(q)
        q.push(S.find(q.Name).Requirement)

      case INVALID:
        S.find(q.Name).set(INVALID)

      case IDENTICAL:
      case SKIP:
    }
}

return S aka Solution

Операция

Stack.push вставить элемент в начале стека

Stack.pop удалить элемент из передней части стека

System.assert(Condition a, Condition b):
    if (a is INVALID) then return SKIP
    else if (b.Range = a.Range) then IDENTICAL
    else if (b.Range - a.Range = {}) then VALID
    else INVALID

Set.find(x) искать элемент на основе условия x

Condition.apply(Condition b) = { this.Name, intersection(this.Range,b.Range) }