Wie kann man effizient einen Abhängigkeitsgraphen von einer transitiven paarweisen Beziehung konstruieren?

Question

Der folgende Algorithmus ist in einem Codegenerierungsproblem erforderlich, das ich anwende. Mein aktueller Algorithmus ist O (n^2), aber ich habe das Gefühl, dass es einen besseren Weg dafür gibt.

Angenommen, ich habe eine Prädikatfunktion für die Berechnung, ob x < y.

less?: (x:T, y:T) -> True|False 

Ich weiß a priori, dass diese Beziehung transitiv ist. So dass

less?(a, b) and less?(b, c) 

less?(a, c) 

impliziert eine Reihe von Objekten (x1, ..., xn) Ich möchte die Abhängigkeitsgraphen berechnen. Es soll wie folgt aussehen:?

x1 => (x2, x4, x5) 
x2 => (x3) 
x5 => (x7) 
x10 =>() 
etc... 

wobei jeder Knoten, xi, mit einer Liste von xj zugeordnet ist, so daß weniger (xj, xi) wahr ist. Der einfachste Weg, dieses Diagramm zu berechnen, besteht darin, weniger zu telefonieren. auf alle möglichen Paare von (xi, xj). Aber desto weniger? Beziehung ist teuer und ich möchte die Anrufe zu weniger minimieren?

Danke für Ihre Hilfe.

-Patrick

Answer 1

Wenn die < Beziehung ausreichend teuer ist, dass Sie durch die Aufrechterhaltung einer Matrix, in der gewinne den aktuellen Stand des Wissens über eine vs b zu speichern. Wir können eine < b,! (A < b) oder unbekannt haben. Wenn Sie dann einen Vergleich von a vs b berechnen, speichern Sie das in der Matrix und suchen Sie nach Abzügen über a vs c und b gegen c für jedes mögliche c, für das das Ergebnis noch unbekannt ist. Haben Sie auch eine < b =>! (B < a)?

Mit z.B. a vs b und b vs c gibt es nur eine endliche Anzahl von Möglichkeiten, um auf Kompatibilität und Inkompatibilität zu überprüfen, um zu sehen, wo Abzüge möglich sind, aber klar < b und b < c => a < c. Aus diesem Grund haben wir auch eine < b und! (A < c) =>! (B < c). Vielleicht, wenn Sie alle Möglichkeiten aufschreien, können Sie mehr finden.

Ich würde geneigt sein, langsam ein Quadrat von bekannten Werten zu wachsen, indem man neue Variablen zufallsmäßig in zufälliger Reihenfolge hinzufügt, so dass man im Stadium i den gesamten Inhalt der Matrix für die ersten zufällig ausgewählten Variablen kennt. Wenn Sie jede neue Variable hinzufügen, würde ich sie mit den bereits in zufälliger Reihenfolge bearbeiteten Variablen vergleichen. Sie machen jeden Abzug möglich. Wenn es eine sehr schlaue Variablenvergleichsreihenfolge gibt, können Sie hoffen, dass sie mit einer zufälligen Vergleichsreihenfolge nahe genug an der optimalen Reihenfolge ist, dass Sie nicht viel ineffizienter als diese sein werden.

Ich habe meine Zweifel im schlimmsten Fall daran. Wenn Sie nie eine < b für irgendwelche a, b finden, denke ich, dass Sie jede Möglichkeit überprüfen müssen.