Wie implementieren Sie den Algorithmus von Prim mit einem Fibonacci -Haufen?

Question

Ich weiss Prims Algorithmus Und ich kenne seine Implementierung, aber ich überspringe immer einen Teil, den ich jetzt fragen möchte. Es wurde geschrieben, dass Prims Algorithmus -Implementierung mit Fibonacci Heap ist O(E + V log(V)) und meine Frage ist:

• Was ist ein Fibonacci -Haufen in Kürze?
• Wie wird es implementiert? Und
• Wie können Sie den Algorithmus von Prim mit einem Fibonacci -Haufen implementieren?

Answer 1

Ein Fibonacci-Heap ist eine ziemlich komplexe Prioritätswarteschlange, die bei allen Operationen ein ausgezeichnetes amoritiertes asymptotisches Verhalten hat-Einfügen, Fund-min und abnimmt alle in O (1) abgeschriebene Zeit, während sie löschen und extrahiert werden, in Amortisation o in Amortised O. (lg n) Zeit. Wenn Sie eine gute Referenz zu diesem Thema wünschen, empfehle ich dringend, eine Kopie von "Einführung in Algorithmen, 2. Ausgabe" von CLRS zu finden und das Kapitel darüber zu lesen. Es ist bemerkenswert gut geschrieben und sehr illustrativ. Das Originalpapier auf Fibonacci Heaps von Fredman und Tarjan ist online verfügbar und Sie möchten es vielleicht ausprobieren. Es ist dicht, gibt aber eine gute Behandlung des Materials.

Wenn Sie eine Implementierung von Fibonacci Heaps und Prims Algorithmus sehen möchten, muss ich für meine eigenen Implementierungen einen schamlosen Stecker geben:

1. Meine Implementierung eines Fibonacci -Haufens.
2. Meine Implementierung des Prim -Algorithmus unter Verwendung eines Fibonacci -Haufens.

Die Kommentare in beiden Implementierungen sollten eine ziemlich gute Beschreibung der Funktionsweise der Funktionsweise entsprechen. Lassen Sie mich wissen, ob ich etwas tun kann, um zu klären!

Answer 2

Der Algorithmus von Prim Wählen Sie die Kante mit dem niedrigsten Gewicht zwischen der bereits ausgewählten Wirbelgruppe und dem Rest der Wirbel.
Um den Algorithmus von Prim zu implementieren, benötigen Sie einen Mindesthaufen. Jedes Mal, wenn Sie eine Kante auswählen, fügen Sie den neuen Wirbel zu der Gruppe der bereits ausgewählten Wirbel -Wirtschaft hinzu, und alle angrenzenden Kanten gehen in den Haufen.
Dann wählen Sie die Kante mit dem Mindestwert erneut vom Haufen.

Also die Zeiten, die wir bekommen, sind:
Fibonacci:
Mindestkante auswählen = o (Zeit des Minimums entfernt) = O (log (e)) = o (log (v))
Einfügen von Kanten in Heap = O (Zeit des Einfügen von Elementen in Heap) = 1

Min Haufen:
Auswahl der minimalen Kante = O (Zeit des Minimums aus dem Haufen) = O (log (e)) = o (log (v))
Einfügen von Kanten in Heap = O (Zeit des Einfügen von Elementen in Heap) = O (log (e)) = o (log (v))

(Denken Sie daran, dass e = ~ V^2 ... also log (e) == log (v^2) == 2log (v) = o (log (v))

Insgesamt haben Sie also E -Einsätze und V -Mindestausfälle (es ist am Ende ein Baum).

Also in Min Heap bekommen Sie:

O (Vlog (v) + ELOG (v)) == O (EG (V))

Und in Fibonacci Heap bekommen Sie:

O (Vlog (v) + e)

Answer 3

Ich habe Dijkstra vor einigen Jahren mit Fibonacci -Haufen implementiert, und das Problem ist ziemlich ähnlich. Grundsätzlich besteht der Vorteil von Fibonacci -Haufen darin, dass das Finden des Minimums eines Satzes eine konstante Operation ist. Das ist also sehr geeignet für Prim und Dijkstra, wo Sie bei jedem Schritt diese Operation ausführen müssen.

Warum ist es gut

Die Komplexität dieser Algorithmen unter Verwendung eines Binomialhaufen Der neue Scheitelpunkt zu Ihrem Binomialhaufen (log v) oder verringert seinen Schlüssel (log v) und muss dann das Minimum Ihres Heaps (ein weiteres Protokoll V) finden.

Wenn Sie stattdessen einen Fibonacci -Haufen verwenden, ist die Kosten für das Einsetzen eines Scheitelpunkts oder die Verringerung des Schlüssels in Ihrem Haufen konstant, sodass Sie dafür nur ein O (e) haben. Das Löschen eines Scheitelpunkts ist jedoch O (log v), da am Ende jeder Scheitelpunkt entfernt wird, der ein O (v * log v) für ein Gesamt -O (E + V * log v) hinzufügt.

Wenn Ihr Diagramm dicht genug ist (z. B. >> v), ist die Verwendung eines Fibonacci -Haufens besser als ein Binomialhaufen.

Wie man

Die Idee ist daher, den Fibonacci -Heap zu verwenden, um alle Scheitelpunkte zu speichern, die von dem bereits erstellten Teilbaum zugänglich sind, das durch das Gewicht der kleinsten Kante indiziert ist. Wenn Sie die Implementierung oder den Prim -Algorithmus unter Verwendung einer anderen Datenstruktur verstanden haben, gibt es keine wirkliche Schwierigkeiten, stattdessen einen Fibonacci -Heap zu verwenden - verwenden Sie einfach die Einfügung und Löschen Methoden des Haufens wie gewohnt und verwenden Sie die Abnahme Methode zum Aktualisieren eines Scheitelpunkts, wenn Sie eine Kante veröffentlichen, die dazu führt.

Der einzige schwierige Teil ist die Implementierung des tatsächlichen Fibonacci -Haufens.

Ich kann Ihnen hier nicht alle Implementierungsdetails geben (das würde Seiten dauern), aber als ich meine tat, habe ich mich stark verlassen Einführung in Algorithmen (Cormen et al.). Wenn Sie es noch nicht haben, aber an Algorithmen interessiert sind, empfehle ich Ihnen dringend, eine Kopie davon zu erhalten! Es ist agnostisch Sprache und liefert detaillierte Erklärungen zu allen Standardalgorithmen sowie zu ihren Beweisen und wird Ihr Wissen und Ihre Fähigkeit, alle zu verwenden, definitiv stärken, um alle zu verwenden und neue zu entwerfen und zu beweisen. Dieser PDF (Von der von Ihnen verlinkten Wikipedia -Seite) liefert einige der Implementierungsdetails, aber es ist definitiv nicht so klar wie Einführung in Algorithmen.

Ich habe ein Bericht und ein Präsentation Ich schrieb danach, das erklärt ein wenig, wie man vorgeht (für Dijkstra - siehe das Ende des PPT für die Fibonacci -Heap -Funktionen in Pseudo -Code), aber es ist alles auf Französisch ... und meine Code ist in CAML (und Französisch), also bin ich mir nicht sicher, ob das hilft !!! Und wenn Sie etwas davon verstehen können, seien Sie bitte nachsichtig, ich habe gerade erst mit der Programmierung begonnen, damit meine Codierungsfähigkeiten zu dieser Zeit ziemlich schlecht waren ...