Zufällige topologische Sortierung mit gleichmäßiger Verteilung in nahezu linearer Zeit

Question

Ich möchte einen Algorithmus für die topologische Sortierung, der nicht jedes Mal die gleiche Sortierung liefert, sondern eine zufällige, wobei jede Sortierung für alle anderen gleich wahrscheinlich ist.

Die Erzeugung aller möglichen topologischen Sortierungen und die zufällige Auswahl ist korrekt, aber viel zu langsam. Das Generieren aller Permutationen und das Filtern der ungültigen topologischen Sortierungen ist ebenfalls sehr langsam; der erste zerfällt in den zweiten, wenn der Baum/Wald breit genug ist.

Das Einfügen neuer Knoten in eine zufällige Position in der Warteschlange der zu überprüfenden Knoten scheint ein verzerrtes Ergebnis zu erzeugen, und das Anordnen am Ende und das Ausführen eines fisher-yates-Shuffle scheint ebenfalls verzerrt zu sein, da beide nicht berücksichtigen für die Anzahl der Knoten "versteckt" unter jedem Knoten, dh wie viele Knoten sind abhängig von a oder b geplant. a konnte keine Kinder haben, während b den Rest des Baumes hält.

Wie kann ich eine zufällige topologische Sortierung erzeugen, wobei jede gültige Sortierung in nahezu linearer Zeit gleich wahrscheinlich ist?

Answer 1

Bearbeiten: Dieses Problem so zu lösen, wie Sie es möchten, ist in keiner vernünftigen Zeitspanne möglich. Um dies zu tun, muss ein # P-vollständiges Problem gelöst werden. Ihre beste Wette ist es, einen probabilistischen Ansatz zu verwenden.

https://mathoverflow.net/questions/45875/how-can-you-compute-the-number-of-topological-sorts-in-a-dag

1. Kommen Sie mit einer Liste aller Kanten bis
2. bestimmen, welche Knoten "Start" Knoten sind. Startknoten haben keine gerichteten Kanten, die in sie kommen
3. Für jeden Startknoten, wählen Sie ihn aus, entfernen Sie alle gerichteten Kanten, die ihm entsprechen, und überlegen Sie dann die Anzahl der möglichen nächsten Bewegungen. Sobald Sie die Anzahl der möglichen Züge für jeden Startknoten gefunden haben, wählen Sie einen Knoten zufällig basierend auf seiner Wahrscheinlichkeit (ein Beispiel ist unten angegeben).
4. Entfernen Sie die Kanten, auf die der Startknoten zeigt.
5. Wiederholen Sie die Schritte 2 bis 4.

Dies zu Kahns Algorithmus ähnlich ist.

https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm

Solange Sie jeder Startknoten zufällig von allen anderen Startknoten werden Kommissionierung, sollten Sie eine zufällige gültige topologische Sortierung erhalten, die die gleiche Wahrscheinlichkeit wie jeder andere zufällige topologische Sortierung hat.

Zum Beispiel, wenn ich ein Diagramm habe {(5, 11) (7, 8) (7, 11) (3, 8) (3, 10) (8, 9) (11, 2) (11 , 9) (11, 10)} wo (a, b) eine gerichtete Kante von a nach b ist, würde ich zuerst bestimmen, dass 5, 7 und 3 Startknoten sind. Ich würde nach dem Zufallsprinzip eine (3) auswählen und dann alle Kanten entfernen, die mit 3 beginnen, was (3,8) und (3, 10) einschließt. Ich würde prüfen, ob Knoten 8 und 10 jetzt Startknoten sind. Sie sind nicht. Meine Startknoten sind jetzt 5 und 7. Ich würde einen anderen zufälligen Startknoten (7) auswählen und dann alle Kanten mit 7 entfernen, die (7, 8) und (7, 11) sind. Ich würde prüfen, ob einige von diesen Startknoten sind. 8 ist ein Startknoten. Meine Startknoten sind jetzt 5 und 8. Ich wähle zufällig 8, entferne Kanten mit 8, was (8, 9) beinhaltet. Ich überprüfe, ob 9 ein Startknoten ist. Mein einziger Startknoten ist 5. Ich wähle 5, entferne die Kanten (5, 11). 11 ist jetzt mein einziger Startknoten. Ich nehme 11, entferne die Kanten (11, 2), (11, 9) und (11, 10). 2, 9 und 10 sind jetzt Startknoten. Ich wähle 2 zufällig, alle Kanten entfernen. 9 und 10 sind meine Startknoten. Ich wähle 10, dann 9.

Meine topologische Sortierung ist jetzt {3, 7, 8, 5 11, 2, 10, 9}

Edit: Es scheint, dass die Anzahl der gültigen topologischen Art zu finden, ist # P-complete, die Das bedeutet, dass es am besten ist, einen probabilistischen Algorithmus zu verwenden, um die Anzahl der möglichen Sortierungen für jedes Element zu bestimmen, und dann die Wahrscheinlichkeit basierend auf der Gesamtzahl der topologischen Sortierungen aller Startknoten anzupassen.

https://mathoverflow.net/questions/45875/how-can-you-compute-the-number-of-topological-sorts-in-a-dag

https://en.wikipedia.org/wiki/Sharp-P-complete

Edit: Sie könnten den Anteil der topologischen Art erraten mit einem Knoten spezifischen Start beginnend von diesen Startknoten wählen, und entfernen Sie alle gerichteten Kanten von ihm geht, dann ist die Berechnung Anzahl aller möglichen nächsten Züge, und dann eine gute Funktion zu finden, um es zu modellieren. Wenn ich zum Beispiel in meinem Beispiel 5 auswähle, hätte ich als nächstes zwei mögliche Züge, 3 und 7. Wenn ich 3 oder 7 auswähle, hätte ich auch noch zwei mögliche Züge übrig. Ich würde dann herausfinden, welchen Bruchteil möglicher Züge ich noch habe, und dann probabilistisch auswählen. In diesem Fall haben alle drei gleiche Chancen, also wähle ich einfach eine zufällig aus. In diesem Fall wähle ich 3. Dann kann ich entweder 5 oder 7 wählen. Wenn ich 5 wähle, habe ich nur eine mögliche Bewegung übrig, 7, und wenn ich 7 wähle, hätte ich noch zwei mögliche Züge übrig. 7 hat daher eine Chance von 2/3, ausgewählt zu werden, und 5 hat eine Chance von 1/3. Dieser Prozess wird fortgesetzt, bis Sie das Ende erreicht haben. Dies ist nur eine Heuristik, aber es sollte Ihnen eine gute Annäherung an die Auswahl einer völlig zufälligen gültigen topologischen Sortierung geben. Auch in dem Gegenbeispiel, das Sie gegeben haben, schien es, als ob man einen zu der Anzahl der möglichen Züge für jeden Startknoten hinzufügen würde, um eine bessere Annäherung zu erhalten.