Diskussion:Greedy-Algorithmus

Ist der Kruskal-Algorithmus ein Greedy-Algorithmus?

der Kruskal-Algorithmus geht meines Erachtens nach gerade nicht nach dem Greedy-Prinzip vor. Daher nehme ich ihn aus der Liste.

WhiteCrow 24.6.2005

Antwort: Der Kruskal-Algorithmus wählt aus den verbliebenen Knoten einen mit minimalem Gewicht. Dies ist eindeutig eine Greedy-Strategie. Auch in „Introduction to Algorithms“ ist er im Stichwortverzeichnis unter „greedy algorithm“ aufgelistet. Was veranlasst dich dazu hierin keine Greedy-Strategie zu sehen?

--Squizzz 14:32, 30. Jun 2005 (CEST)

Der folgende Diskussionsbeitrag stammt von der Diskussions-Seite des Benutzers Squizz.

Hast Du Dir die Diskussionsseite angesehen? Wenn der Kruskal-Algorithmus nach dem Greedy-Prinzip arbeiten soll, dann hieße das, von einer Kante ausgehend wird eine anliegende Kante mit nächstkleinem Gewicht gewählt. Die Idee bei Greedy ist das lokale, sukzessive Vorgehen. Kruskal setzt voraus, dass man ALLE Gewichte kennt und global aus ALLEN Gewichten das beste auswählen kann.

Antwort: Das widerspricht nicht der Greedy-Strategie, die allein fordert aus einer Menge von Möglichkeiten die im Moment beste zu wählen. Lokales Vorgehen bedeutet hier nur, dass man sozusagen nicht einen Schritt vorausschaut, sondern nur den nächsten Schritt betrachtet. Ansonsten habe ich auch auf der Diskussionsseite geantwortet. --Squizzz 14:36, 30. Jun 2005 (CEST)

[...] Greedy-Strategie, die allein fordert aus einer Menge von Möglichkeiten die im Moment beste zu wählen. – Gibt es einen Algorithmus, der die beste Lösung finden will, und der aus einer Menge von Möglichkeiten nicht die im Moment Beste auswählt? Ich bestreite nicht, dass Kruskal ein Greedy-Algorithmus ist, aber mit der Begründung ist so ziemlich jeder Algorithmus abgedeckt. Hier fehlt, dass bei einem Greedy-Algorithmus die Lösung inkrementell zusammengebaut wird. --Sargeras 01:51, 5. Feb. 2008 (CET)

Natürlich gibt es solche, z.B. beim Schachspiel - wenn der Algorithmus mehr als 1 (Halb-)Zug vorausrechnet, wählt er evtl. einen Zug, der erst nach n Halbzügen besser wird als ein anderer. Der Zug ist im Moment also nicht der "beste nächste Schritt", sondern wird erst zum "besten", wenn man (n-1) Schritte weiter plant/betrachtet.

Und auch genetische Algorithmen, insbesondere gekoppelt mit Verinselung, wählen durchaus immer wieder nicht-optimale nächste Schritte.

--arilou (Diskussion) 09:26, 30. Sep. 2014 (CEST)

Einleitung

Da Du meine Änderung der Einleitung revertiert hast, hast Du Dir dabei wohl etwas gedacht. Der neue und alte Satz "Greedy-Algorithmen (gierige Algorithmen) bilden in der Informatik eine spezielle Klasse von Algorithmen." ist aber m.E. sprachlich unschön: Zunächst ist die in der Wikipedia leider übliche Formulierung "[Begriff] ist/bildet in [Fachbereich] [Definition]" ungenau, denn der Begriff ist überall das, als was er definiert wurde (deshalb habe ich das Verb "bezeichnen" verwendet). Die Verdopplung des Worts "Algorithmus" finde ich etwas schwerfällig. Außerdem ist der Satz in dieser Form bis auf die Zuordnung zur Informatik nicht sehr gehaltvoll, denn daß gierige Algorithmen Algorithmen sind, überrascht kaum. Sehe ich das falsch? --FRR 15:54, 6. Aug 2006 (CEST)

Für den unbedarften Benutzer ist klarzustellen, dass es sich um eine Algorithmen-Klasse handelt. Es ist mir schon passiert, dass Leute dachten der Greedy-Algorithmus wäre ein bestimmter Algorithmus (nämlich der erste Greedy-Algorithmus, den sie kennengelernt haben). Den Einleitungssatz habe ich nochmal ein klein wenig geändert. Das du den Satz sprachlich nicht schön findest ist deine Ansicht. Ich bin hier anderer Meinung ;-) Insbesondere die Wortdopplung sehe ich nicht als Problem an. Es handelt sich hier nunmal um einen Enzyklopädie-Eintrag und nicht um ein Kapitel in einem Lehrbuch. --Squizzz 16:03, 6. Aug 2006 (CEST)

Irgendwie fehlt mir in der Einleitung der Fakt, dass ein Greedy Algorithmus sich in erster Linie dadurch definiert, dass er einmal gelöste Teilprobleme im Laufe des Algorithmus nicht mehr aktiv betrachtet. Sprich, für Graphen, betrachtete Knoten/Kanten die in die Lösungsmenge aufgenommen wurden, werden nicht nocheinmal betrachtet. Deswegen kann man auch den Bellman/Ford nicht greedy nennen, weil es jederzeit sein kann, dass sich während eines Durchlaufs erhaltene Lösungen ändern, und auch dass der Algorithmus mehrmals global durchläuft spricht nicht für Greedy. --F GX 11:20, 6. Feb. 2009 (CET)

Dijkstra Algorithmus?

Nach meinem Verständnis ist der Dijkstra Algorithmus gerade kein Greedy Algorithmus. Er wählt nicht immer die schwerste (leichteste) Kante, sondern schränkt die Kandidaten erheblich ein.

Djikstra-Algorithmus wählt immer die leichteste Kante bzgl der schon ausgewählten Knoten. Es ist nicht verlangt, dass ein Greedy-Algorithmus eine möglichst einfache Auswahlmenge hat. --Squizzz 10:03, 21. Aug 2006 (CEST)

Damit der Dijkstra-Algorithmus als Beispiel in diesem Artikel gerechtfertigt ist, müsste mal jemand sagen, was denn in diesem Fall das Matroid und die Gewichtsfunktion sind. (Vgl. auch Diskussion:Matroid#Dijkstra-Algorithmus als Greedy-Algorithmus?) --HeikoTheissen 10:44, 11. Mai 2007 (CEST)

Ich glaube auch nicht, dass Dijkstra gierig ist. Das Verhalten von Dijkstra passt nicht zum (sehr allgemein gehaltenen) Beispiel: Dort werden der Lösungsmenge T immer nur Elemente hinzugefügt, aber nie schlechte Elemente entfernt. Die Lösung wird also schrittweise (inkrementell) gefunden. Dieses Verhalten entspricht einer informierten Tiefensuche. Bei Dijkstra existiert aber keine solche Menge T. Hier gibts ein Java-Applet, dass Wegsuche unter anderem mit Greedy und Dijkstra veranschaulicht. Die dargestellte Greedy-Strategie entspricht dabei der Beschreibung in Künstliche Intelligenz – Ein moderner Ansatz. --Sargeras 02:04, 5. Feb. 2008 (CET)

Nachtrag: Bei dem in meinem KI Buch vorgestellten Greedy-Algorithmus gibt es auch keine solche Menge T. --Sargeras 12:47, 5. Feb. 2008 (CET)

Ich habe nun eine Gegenüberstellung von A*, Dijkstra und einem Greedy-Algorithmus erstellt, die mein Verständnis eines Greedy-Algorithmus (in Bezug auf Suche in Graphen) aufzeigen soll. Außerdem sind für mich Greedy-Algorithmus und Dijkstra-Algorithmus wie dargestellt zwei verschiedene Dinge. --Sargeras 18:38, 5. Feb. 2008 (CET)

Bitte etwas Geduld. Ich werde noch den Matroid suchen und dann dürfte alles klar sein. --Stefan Birkner 07:58, 7. Feb. 2008 (CET)

Laufzeit doppelt?

Kann das sein, dass der Abschnitt 'Laufzeit' doppelt auftaucht??? --85.179.71.113 14:47, 25. Mär. 2009 (CET)

Naja Unabhängigkeitsprüfung und Basis-Obermengen-Prüfung sind schon unterschiedlich.--Schönen Gruß "Wohingenau" 12:00, 4. Apr. 2010 (CEST)

kardinalitätsmaximalen?

Kann man diesen Begriff im Artikel erläutern und/oder verlinken? --Schönen Gruß "Wohingenau" 12:45, 4. Apr. 2010 (CEST)

Kardinalitätsmaximale =Basis--Flegmon 13:33, 21. Jun. 2010 (CEST)

Bezeichnung der zwei Varianten des greedy Algorithmus

Also im Buch von Korte sind die Beiden Varianten als Best-in und Worst-out bezeichnet, die Bezeichnung der beiden Varianten mit Maximierung bzw. Minimierung ist eigentlich irreführend, da (wie auch Beschrieben) jede Variante das Max/Min-imierungs-Problem lösen kann... Wenn niemand Einwände hat, würd ich dass gerne ändern.--Flegmon 13:33, 21. Jun. 2010 (CEST)

Laufzeit

Im Artikel steht, dass der Algorithmus eine Laufzeit von ${\mathcal {O}}(|E|\cdot (\log(|E|+L)))$ hat. Dass ist meines erachten aber nicht korrekt:

Für das sortieren wird $|E|*log(|E|)$ Zeit benötigt. Die schleife wird $n=|E|$ mal ausgeführt. Ist L die Laufzeit der Prüfung einer Menge auf Unabhängigkeit, dann wären die Gesamtkosten ${\mathcal {O}}(|E|*log(|E|)+|E|*L)$. Unter der Annahme $L>log(|E|)$ folgt dann ${\mathcal {O}}(|E|*L)$ und ${\mathcal {O}}(|E|*log(|E|))$ sonst.

Wenn meine Annahme falsch ist, wäre es wohl trotzdem interessant wie dieses L aussehen kann. (Zum Beispiel im Falle der NP-Vollständigkeit eines Problems) (nicht signierter Beitrag von 85.180.133.218 (Diskussion) 21:00, 4. Apr. 2013 (CEST))