Ich habe ein klassisches Abhängigkeitslösungsproblem. Ich dachte, ich würde in die richtige Richtung gehen, aber jetzt bin ich auf eine Straßensperre gestoßen und weiß nicht, wie ich vorgehen soll.

Hintergrund

In dem bekannten Universum (dem Cache aller Artefakte und ihrer Abhängigkeiten) besteht jeweils eine 1-> n-Beziehung zwischen Artefakten und Versionen, und jede Version kann einen unterschiedlichen Satz von Abhängigkeiten enthalten. Zum Beispiel:

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

Angesichts einer Reihe von "Nachfrageeinschränkungen" würde ich gerne die bestmögliche Lösung finden (wobei "best" die höchstmögliche Version ist, die noch alle Einschränkungen erfüllt). Hier ist ein Beispiel für "Nachfragebeschränkungen" mit der Lösung:

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

In Wirklichkeit gibt es deutlich mehr Anforderungen:

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

(Die Fassungen folgen demsemantische Versionierung Standard)

Ich habe es versucht

Die aktuelle Lösung verwendet die Rückverfolgung und ist nicht sehr leistungsfähig. Ich habe ein bisschen gegraben und festgestellt, dass die Leistungsprobleme auf die Größe des Universums zurückzuführen sind. Ich habe mich entschlossen, einen alternativen Ansatz zu versuchen und ein "Möglichkeit" -DAG-Diagramm für zu konstruierengerade die Forderungen:

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

Ich konstruiere dann eine DAG aller möglichen Lösungen aus dem Universum. Dies reduziert die Anzahl der Möglichkeiten drastisch und gibt mir einen tatsächlichen Graphen mit echten Artefaktmöglichkeiten zum Arbeiten.

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

Also, aus dem früheren Beispielgraphen, wenn ich die Anforderungen hätte'A', '>= 0.0.0'würde meine DAG so aussehen:

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

Da die möglichen Werte für A-1.0.0 "ein beliebiger Wert von B" sind, lauten die Einschränkungen für A-1.0.1 "ein beliebiges B in der 0,1-Serie". Dies funktioniert derzeit (mit einer vollständigen Testsuite) wie erwartet.

Mit anderen Worten, die DAG verwendet die abstrakten Abhängigkeitsbedingungen und erstellt einen "echten" Graphen, in dem jede Kante eine Abhängigkeit und jeder Scheitelpunkt ist (ich habe es eine genannt)node) ist ein tatsächliches Artefakt. Wenn es eine Lösung gibt, befindet sie sich irgendwo in diesem Diagramm.

Und leider stecke ich hier fest. Ich bin nicht in der Lage, einen Algorithmus oder eine Prozedur zu finden, um den "besten" Weg durch dieses Diagramm zu finden. Ich bin mir auch nicht sicher, wie ich feststellen kann, ob das Diagramm nicht lösbar ist.

Ich habe ein bisschen recherchiert und dachte, topologische Sortierung (Tsort) wäre der Prozess, den ich brauchte. Dieser Algorithmus bestimmt jedoch die Einfügereihenfolge für Abhängigkeiten und nicht die beste Lösung.

Ich bin mir ziemlich sicher, dass dies ein np-hartes Problem ist und wahrscheinlich eine ineffiziente Laufzeit haben wird. Ich würde jedoch mit einer DAG weniger Vergleiche anstellen müssen. Irre ich mich in dieser Annahme? Gibt es eine bessere Datenstruktur?

Abschließende GedankenIch habe diese Frage mit "Ruby" markiert, weil ich Ruby verwende, aber ich suche nach Pseudocode / Richtung. Dies ist kein Problem mit den Hausaufgaben - ich versuche wirklich zu lernen.Ich habe versucht, so viel Hintergrund wie möglich zu geben, aber bitte hinterlassen Sie einen Kommentar, wenn Sie mehr Details zu einem bestimmten Thema wünschen. Dies ist bereits ein langer Beitrag, aber ich habe mehr Code, den ich teilen kann.