Wie man von einem gerichteten azyklischen Graphen mit exklusiven Teilmengen abfragt - Algorithmus, Graphentheorie, Abhängigkeitsverwaltung, gerichtete azyklische Graphen

Frage in abstrakten Begriffen:

Ich habe einen gerichteten azyklischen Graphen (DAG), derenthält Teilmengen von Vertices, die exklusiv sind, wenn sie abgefragt werden (nur ein Element pro Teilmenge sollte in den Ergebnissen der Abfrage vorhanden sein). Wenn ich die Graphenstruktur abfrage, möchte ich die Menge der Scheitelpunkte erhalten, die von einem gegebenen Eckpunkt fließen ein einzelnes Element aus bekannten Teilmengen der Scheitelpunkte im Diagramm.

Frage konkret:

Ich habe eine DAG, die meine Assemblies (Vertices) speichertund ihre Abhängigkeiten (Kanten). Bei einer Assembly oder einer Gruppe von Assemblys muss ich abfragen, um die Menge aller beteiligten Assemblys und ihrer Abhängigkeiten zu erhalten. Der schwierige Teil besteht darin, dass jede Assembly mehrere Versionen hat und nur eine Instanz einer Assembly in einen Prozess geladen werden kann. Die Abhängigkeiten für eine bestimmte Assembly ändern sich zwischen den verschiedenen Versionen der Assembly.

Gibt es einen Namen für dieses Problem oder diese Problemgruppe? Ein Standardalgorithmus, den ich erforschen kann, um eine Lösung zu finden?

Mögliche Lösungsbereiche:

EIN Transitive Schließung scheint nahe an einer guten Lösung, aber das Elementaus der Teilmenge (Assembly-Version) ausgewählt wird, ändert sich abhängig von dem Pfad, der durch den Graph genommen wird, möglicherweise durch mehrere Zweige, so dass Sie fast den Pfad durch den Graphen verfolgen müssten, um den transitiven Abschluss zu erzeugen.

EIN Graphdatenbank Vielleicht können wir hier ein bisschen helfen, aber wir wollen vermeiden, dass wir diesen Weg jetzt gehen, es sei denn, wir müssen es unbedingt tun.

Antworten:

Ich denke, dass die Menge der Ecken, die von einem fließenDie gegebene Wahl erscheint verwirrend, weil es tatsächlich ein zugrunde liegendes Optimierungs- oder Zufriedenheitsproblem gibt: Bei einer Baugruppe A können Sie ihre Abhängigkeiten über B1 oder B2 oder B3 erfüllen, und jede dieser Entscheidungen hat dann ihre eigenen Konsequenzen.

Wenn wir dies als logisches Zufriedenheitsproblem betrachten,Dann könnten wir ein Problem betrachten, bei dem Baugruppen nur in zwei Versionen vorliegen, z. A1 oder A2. Dann würde eine Klausel wie (a oder b oder nicht c) zu einer übergeordneten Baugruppe übersetzen, die A1 oder B1 oder C2 - möglicherweise indirekt über X1, X2 und X3 - benötigt, und eine Konjunktion von Klauseln würde in ein oberes Upper übergehen Level-Assembly, die alle übergeordneten Baugruppen benötigt. Ich denke also, wenn Sie das allgemeine Problem effizient lösen könnten, könnten Sie 3-SAT effizient lösen und dann P = NP.

Seltsamerweise, wenn Sie nicht die Einschränkung haben, dassWenn man nur eine Anordnung von jedem Typ zulässt (A1 oder A2 oder A3, aber mehr als eine), dann kann das Problem sehr leicht in Hornsätze (Knuth Vol. 4 Abschnitt 7.1.1 P 57) übersetzt werden, für die das Erfüllbarkeitsproblem sein kann effizient gelöst. Um dies zu tun, arbeiten Sie mit der Umkehrung der natürlichen Variablen, so dass X1 bedeutet, dass A1 nicht enthalten ist. Wenn Sie dann die Horn-Klausel-Version als eine Möglichkeit behandeln, Ihr Problem zu lösen, indem Sie die Einschränkung ignorieren, dass höchstens eine Version jeder Assembly unterstützt werden kann, erhalten Sie einen Mechanismus, der Ihnen die Assemblyversion A1 mitteilt kann nicht Sei in der Lösung, weil X1 = nicht A1 im Kern der Horn-Lösung wahr ist und daher in jeder erfüllenden Aufgabe wahr ist.