Diskussion:Algorithmus von Prim

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 9 Jahren von V4len in Abschnitt MinHeap
Zur Navigation springen Zur Suche springen

Verwandtschaft zum Algorithmus von Dijkstra

[Quelltext bearbeiten]

Ein sehr ähnlicher Algorithmus für sehr ähnliche gelagerte Probleme ist der Algorithmus von Dijkstra.

Habe diesen Satz entfernt, da er schlicht und einfach doof klingt. Wieso sind die Suche nach einem MST sehr ähnlich zur Suche nach kürzesten Wegen? --zeno 19:36, 7. Apr 2004 (CEST)
Ich wollte gerade fragen, wo im Artikel am besten erwähnt werden sollte, dass die beiden Algorithmen ähnlich arbeiten. Die beiden Algorithmen haben so ziemlich die gleiche Struktur. Der einzige Unterschied ist das Auswahlkriterium, nach dem die Kanten relaxiert werden. --Daniel Mex 20:00, 13. Sep. 2007 (CEST)Beantworten
Ich glaube es gibt viele Algorithmen, die auf der obersten Ebene aus einer For-Schleife bestehen! Und: jeden Alg. kann man als While-Schleife implementieren. Sind also alle Algorithmen ähnlich?! Glaub mir, so eine Bermerkung ist Blödsinn! --Koethnig 22:44, 19. Sep. 2007 (CEST)Beantworten
Ich sehe zwar mehr Gemeinsamkeiten zwischen den beiden Algorithmen als nur, dass man sie beide so implementieren kann, dass sie eine while-Schleife enthalten, aber nach einigem Nachdenken halte ich eine solche Bemerkung auch nicht mehr für so gut. Dass der Dijkstra-Algorithmus einen Spannbaum erzeugt, ist ja im entsprechenden Artikel schon vermerkt. --Daniel Mex 21:21, 29. Sep. 2007 (CEST)Beantworten

kürzeste Wege und MST

[Quelltext bearbeiten]

weil man aus einem MST die kürzesten Wege von der Wurzel zum Blatt ablesen kann

DWay 12:58, 30. Aug 2004 (CEST)

Greedy-Algorithmus

[Quelltext bearbeiten]

Es wurde folgende Behauptung aufgestellt: Im Gegensatz zum Algorithmus von Kruskal ist der Algorithmus von Prim KEIN Greedy-Algorithmus!

In "Introduction to Algorithms" wird im entsprechenden Kapitel 24.2 explizit erläutert, dass der Algorithmus von Prim greedy ist. --Squizzz 21:30, 1. Nov 2004 (CET)

In der Tat sehen die meisten Autoren diesen Algorithmus als greedy an. Ich habe aber auch ein Gegenargument gefunden: Die jeweils minimale Kante wird immer nur aus den zum bisherigen Minimalgerüst adjazenten Kanten ausgewählt. Ein typischer Greedy-Algorithmus würde jedoch immer das nächste Element aus der Gesamtheit aller Kanten auswählen. Der Algorithmus von Prim kann also nicht einfach die "nächste minimale Kante" gehen, sondern er muss immer überhaupt ersteinmal prüfen, welche Kanten in Betracht kommen. Das macht den Algorithmus freilich weniger effizient, und es ist auch eine Zusatzbedingung zum Greedy-Verhalten, das ja eigentlich immer nur das nächste Element gemäß seiner Minimalität/Maximalität auswählt und daher auch idR sehr schnell abläuft. Wie seht ihr das? --Mkleine 13:47, 7. Okt. 2007 (CEST)Beantworten
Wie kommst du darauf, dass „ein typischer Greedy-Algorithmus immer das nächste Element aus der Gesamtheit aller Kanten auswählen“ würde? Diese Annahme ist falsch. --Stefan Birkner 00:11, 12. Okt. 2007 (CEST)Beantworten
Wenn man sich die Sache näher ansieht, geht Prim tatsächlich geringfügig anders zu Werke. Er ist kein globaler dummer Greedy-Alg., sondern geht bei der Auswahl der Kandidatenmenge für den Greedy-Schritt differenzierter vor. Prim nicht zu den Greedy-Algorithmen zu zählen, wäre aber m.E. verfehlt. In Algorithmen-Büchern wird er oft als einer der Greedys aufgeführt, die Erfolg haben ... (im Gegensatz z.B. zu Knapsack, TSP, ...). --MWinckler 09:26, 9. Mai 2008 (CEST)Beantworten


Abschnitt „Vergleich mit dem Algorithmus von Kruskal“

[Quelltext bearbeiten]

Toll, wie sich der Artikel entwickelt hat. Die Darstellung des Algorithmus ist m.E. durch die neuen Bilder deutlich besser geworden. Trotzdem habe ich noch einen weiteren Kritikpunkt: Im Abschnitt zum Vergleich mit Kruskal wird weiterhin deutlich auf das Vermeiden von Kreisen hingewiesen. Diese Passage scheint mir aus dem englischen Artikel zu stammen, mit dem ich sowieso alles andere als glücklich bin ;-( (An Adrichel: Die englische Darstellung ist wohl aus dem Kruskal-Artikel abgeleitet und geht eben nicht auf die prinzipiellen Unterschiede ein)

Meiner Meinung nach ist der zentrale Vorteil (den man übrigens beim Programmieren auch merkt!!) von Prims Algorithmus die Tatsache, dass er Aufgrund der Kantenvorauswahl garkein Problem mti Kreisbildung hat. Prim ist eben ein lokaler Algorithmus in dem Sinne, dass er stets nur eine Zusammenhangskomponente und die freien Knoten betrachtet. Kruskal dagegegn arbeitet global bei der Suche nach kurzen Kanten ... und muss daher immer alle einzelnen Zusammenhangskomponenten im Auge haben, damit sich kein Kreis bildet.

Ich würde gerne den Abschnitt über den Vergleich neu Schreiben - aber das dauert noch 2-3 Tage. Ich bin im Augenblick an einem anderen sehr zeitraubenden Projekt beteiligt. (nicht signierter Beitrag von MWinckler (Diskussion | Beiträge) 08:26, 9. Mai 2008)

Ich finde den Vergleich zu Kruskal in diesem Artikel überflüssig. Mir erschließt sich nicht der Sinn. Wer beide Algorithmen versteht, erkennt die Unterschiede. Wer einen der beiden Algorithmen nicht versteht, kommt auch durch die Unterschiede nicht weiter. Und neben den beiden erwähnten Algorithmen gibt es auch noch andere MST-Algorithmen. Statt eines zweiseitigen Vergleichs sollte man meines Erachtens den Abschnitt zu den Algorithmen im Artikel minimaler Spannbaum ausbauen. Wenn man dort jedem Algorithmus ein oder zwei Abschnitte gönnt, sollten die Unterschiede auch klar werden. --Stefan Birkner 10:16, 9. Mai 2008 (CEST)Beantworten
Ich finde den Vergleich sehr nützlich! Wieso denn nicht? Man hat einen schnellen Überblick. Bin nur mit einem Satz nicht einverstanden: "Da aus dieser (lokalen) Kantenmenge die leichteste Kante ausgewählt wird, vermeidet der Algorithmus per Konstruktion das Auftreten von Kreisen.". Es stimmt doch gar nicht! Der Algo vermeidet das Auftretten von Kreisen, in dem er immer einen neuen Knoten auswählt. Es hat nichts mit dem Auswählen von leichtesten Kanten zu tun. Als Beispiel siehe den vorletzten Schritt im Ablauf: da hätte er nach der Logik des Verfassers EF auswählen sollen. --Roman tum 01:34, 10. Jul. 2008 (CEST)Beantworten
Prims und Kruskals Algorithmus zu vergleichen finde ich deshalb sinnvoll, weil beide sich in der Anlage sehr ähneln, aber durch die Strategie zur Vermeidung der Kreise unterscheiden. Vom abstrakten Standpunkt aus gesehen ist Kruskal = Greedy und Kreise explizit vermeiden und Prim = Greedy mit impliziter Kreisvermeidung. Daher sind sie als Instanzen abstrakter Lösungskonzepte interessant und vergleichbar. Bei Vergleichen zwischen mehr als zwei Konzepten tun sich allerdings Leser recht schwer. Hier könnte eine Tabelle helfen, aber das halte ich dann doch für zu unübersichtlich.--MWinckler 17:46, 10. Sep. 2008 (CEST)Beantworten
Was spricht den dagegen, im Artikel minimaler Spannbaum den Abschnitt zu Algorithmen zu erweitern und dort die entsprechenden Vergleiche unterzubringen? --Stefan Birkner 14:28, 13. Sep. 2008 (CEST)Beantworten

Zur aktuellen Textform habe ich noch einen Kritikpunkt: Der Satz Da aus dieser (lokalen) Kantenmenge die leichteste Kante ausgewählt wird, vermeidet der Algorithmus per Konstruktion das Auftreten von Kreisen. suggeriert, dass die Kreisbildung dadurch implizit vermieden wird, dass man die leichteste Kante wählt. Das ist natürlich nicht richtig: Jede Wahl einer Kante zwischen Teilgraf und Komplementärmenge vermeidet die Kreisbildung. Ich bin deshlab dafür, die Worte die leichteste schlicht durch eine zu ersetzen und werde das auf der Seite auch gleich tun ;-) --MWinckler 17:46, 10. Sep. 2008 (CEST)Beantworten

"Fehler" im Bild 3 (Prim Algorithm 2.svg)

[Quelltext bearbeiten]

Damit hab ich' sverstanden - DANKE! Ein kleiner "Fehler" ist mir jedoch aufgefallen: Beim 3-ten Bild ist die Kante DB nicht blau eingefärbt. Muss das so sein, weil diese Kante denselben Endpunkt hat wie die Kante AB und deshalb früzeitig entfernt wird?

Gruss Ein neuer Wikianer (nicht signierter Beitrag von Wikianer999 (Diskussion | Beiträge) 17:49, 1. Jul 2010 (CEST))

Vermutlich ist das der Grund, ja. Das würde zumindest auch erklären, warum DE im 4. Bild fehlt, oder FE im 5. -- Pberndt (DS) 18:59, 1. Jul. 2010 (CEST)Beantworten

MinHeap

[Quelltext bearbeiten]

Die Worst-Time-Komplexität scheint sich m.E. nicht zu ändern, wenn man statt eines Fibonacci-Heaps einen Min-Heap benutzt. Oder sehe ich das falsch? --V4len (Diskussion) 16:15, 28. Nov. 2015 (CET)Beantworten