Wikipedia · einfach zusammengefasst · Stand
Greedy-Algorithmus
Greedy-Algorithmen sind oft schnell, lösen viele Probleme aber nicht optimal.
Inhalt5 Abschnitte
Grundidee und Grenzen
Greedy-Algorithmen (gierige Algorithmen) sind eine Klasse von Algorithmen in der Informatik. Sie wählen schrittweise jeweils den Folgezustand, der nach einer Bewertungsfunktion im Moment der Entscheidung den größten Gewinn oder das beste Ergebnis verspricht, zum Beispiel bei Gradientenverfahren.
Sie sind oft schnell, liefern aber bei vielen Problemen keine optimale Gesamtlösung. Entscheidungen werden anhand der aktuell verfügbaren Informationen getroffen und typischerweise nicht zurückgenommen. Daher kann ein lokales Optimum entstehen: eine in der unmittelbaren Umgebung beste, aber nicht unbedingt insgesamt beste Lösung.
Wanderer im Nebel
Ein Wanderer möchte möglichst hoch steigen, kann wegen Nebels aber nur 5 Meter weit sehen. Er geht immer zum höchsten Punkt in seiner sichtbaren Umgebung und wiederholt dies, bis kein höherer Punkt mehr sichtbar ist.
Das veranschaulicht Greedy-Algorithmen: Große Ziele werden in kleinen Schritten erreicht, pro Schritt sind nur begrenzte Informationen vorhanden, und bereits ausgeführte Schritte werden nicht zurückgenommen. Der Wanderer kann dadurch auf dem Gipfel eines kleinen Hügels statt auf dem eines großen Berges landen. Auch die Ausgangsposition kann das Ergebnis stark verändern.
Optimierung auf Matroiden
Bei Optimierungsproblemen auf Unabhängigkeitssystemen findet ein Greedy-Algorithmus für alle Bewertungsfunktionen genau dann stets eine optimale Lösung, wenn die zulässigen Lösungen die unabhängigen Mengen eines Matroids sind. Andernfalls führt er nur zu einem lokalen Optimum.
Beim Rucksackproblem und beim Problem des Handlungsreisenden ist die optimale Lösung wesentlich aufwändiger zu finden, weil diese Probleme NP-vollständig sind.
Schwerste unabhängige Menge
Für ein Matroid (E,U) und eine Gewichtsfunktion w\colon E\rightarrow \mathbb {R}^{+} werden zunächst alle Elemente absteigend nach Gewicht sortiert: w(e_1)\geq\ldots\geq w(e_n). Man beginnt mit T=\varnothing. Dann wird jedes e_k der Reihe nach zu T hinzugefügt, aber nur, falls T\cup\{e_k\}\in U gilt. Ausgegeben wird T.
So entsteht eine schwerste unabhängige Menge F\in U, welche w(F):=\sum_{e\in F}w(e) maximiert. Bei beliebigen Gewichtsfunktionen w\colon E\to\mathbb {R} können beim Maximieren Elemente mit negativem Gewicht ignoriert werden. Das Finden einer minimalen unabhängigen Menge lässt sich auf das Maximierungsproblem zurückführen, indem die Gewichte durch ihre additiven Inversen ersetzt werden.
Ist L die Laufzeit der Unabhängigkeitsprüfung, beträgt die Laufzeit {\mathcal {O}}(|E|\cdot(\log(|E|+L))). Im besten Fall dominiert das Sortieren; ist die Unabhängigkeitsprüfung NP-vollständig, ist der Algorithmus praktisch nutzlos.
Leichteste Basis und Anwendungen
Für ein Matroid (E,U) und w\colon E\rightarrow\mathbb {R}^{+} werden die Elemente wieder absteigend sortiert. Man setzt T:=E und versucht anschließend für jedes e_i, es zu entfernen. Enthält T\setminus e_i weiterhin eine Basis, wird T:=T\setminus e_i gesetzt. Das Ergebnis ist eine leichteste Basis: unter den kardinalitätsmaximalen B\in U wird ein B gewählt, das c(B):=\sum_{e\in B}c(e) minimiert.
Bei positiven Gewichten ist die Suche nach einer leichtesten Basis-Obermenge äquivalent. Sie ist dual zum Maximierungsproblem und lässt sich analog auf beliebige Gewichtsfunktionen sowie das entsprechende Minimierungsproblem verallgemeinern. Mit L als Laufzeit der Prüfung, ob eine Teilmenge von E Obermenge einer Basis ist, lautet die Laufzeit ebenfalls {\mathcal {O}}(|E|\cdot(\log(|E|+L))). Ist diese Prüfung NP-vollständig, ist der Algorithmus praktisch nutzlos.
Beispiele sind die Algorithmen von Kruskal und Prim für minimale Spannbäume, Dijkstra für kürzeste Wege, Huffman für optimale präfixfreie Codes sowie der Algorithmus der sukzessiven Einbeziehung als Heuristik für kombinatorische Optimierungsprobleme.
