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

Фон

В известном юниверсе (кеше всех артефактов и их зависимостях) каждая взаимосвязь между артефактами и версиями имеет 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. Это не проблема домашних заданий - я искренне пытаюсь учиться.
• Я попытался дать как можно больше фона, но, пожалуйста, оставьте комментарий, если вы хотите получить более подробную информацию по определенной теме. Это уже длинный пост, но у меня есть больше кода, который я могу предоставить.