Ist Prim's Algorithmus immer Greedy?
-
Hallo,
ich hatte letztens eine Diskussion mit einem Informatiker, bei der es um den Algorithmus von Prim geht.
Seine Behauptung ist, dass sobald man Fibonacci-Heaps für den Algorithmus nutzt, dieser nicht mehr Greedy ist. Mein Verständnis von Greedy Algorithmen sagt mir aber, dass das eine mit dem anderen nichts zu tun hat. Ich lasse mich natürlich eines Anderen belehren, leider konnten wir beide unsere Aussagen nicht sehr fundiert Begründen.
Kann jemand etwas Licht in diese Sache bringen?
-
Der algorithmus ist greedy, unabhaengig von der implementierung, esseiden die implementierung aendert den algorithmus
-
Ok, das heißt ich liege mit meiner Annahme richtig? Oder ändert die Nutzung von Fibonacci Heaps den Ablauf des Algorithmus? Das ist ja die Frage, die niemand so richtig beantworten konnte
-
Der Algorithmus benötigt irgendwie eine priority qeue. Wie diese implementiert ist, hat keinen Einfluss auf die Arbeitsweise des Algorithmus.
-
Greedy Prim schrieb:
Mein Verständnis von Greedy Algorithmen sagt mir aber, dass das eine mit dem anderen nichts zu tun hat.
Ist auch so.
Ein Greedy Algorithmus geht quasi Schritt für Schritt vor, und wenn er sich mal für einen Schritt entschieden hat, dann bleibt er dabei. Siehe auch
https://en.wikipedia.org/wiki/Greedy_algorithmDer Algorithmus von Prim macht genau das. Und an dieser Eigenschaft ändert sich natürlich nichts wenn man die Priority-Queue durch etwas anderes ersetzt.
BTW ist es auch egal ob ein Algorithmus immer das optimale Ergebnis liefert. Ein Greedy Algorithmus ist immer noch greedy, auch wenn das Ergebnis garantierterweise immer optimal sein sollte.
