Gieriger Algorithmus - Greedy algorithm
Ein Greedy-Algorithmus ist jeder Algorithmus , der der Problemlösungsheuristik folgt, um in jeder Stufe die lokal optimale Wahl zu treffen. Bei vielen Problemen erzeugt eine Greedy-Strategie keine optimale Lösung, aber eine Greedy-Heuristik kann lokal optimale Lösungen liefern, die sich in angemessener Zeit einer global optimalen Lösung annähern.
Eine gierige Strategie für das Problem des Handlungsreisenden (das eine hohe Rechenkomplexität hat) ist beispielsweise die folgende Heuristik: "Besuchen Sie bei jedem Schritt der Reise die nächste nicht besuchte Stadt." Diese Heuristik beabsichtigt nicht, die beste Lösung zu finden, aber sie endet in einer vernünftigen Anzahl von Schritten; Das Finden einer optimalen Lösung für ein so komplexes Problem erfordert normalerweise unangemessen viele Schritte. Bei der mathematischen Optimierung lösen Greedy-Algorithmen kombinatorische Probleme mit den Eigenschaften von Matroiden optimal und geben Optimierungsproblemen mit der submodularen Struktur konstante Näherungen.
Besonderheiten
Im Allgemeinen haben gierige Algorithmen fünf Komponenten:
- Eine Kandidatenmenge, aus der eine Lösung erstellt wird
- Eine Auswahlfunktion, die den besten Kandidaten für die Lösung auswählt
- Eine Machbarkeitsfunktion, die verwendet wird, um zu bestimmen, ob ein Kandidat verwendet werden kann, um zu einer Lösung beizutragen
- Eine Zielfunktion, die einer Lösung oder einer Teillösung einen Wert zuweist, und
- Eine Lösungsfunktion, die anzeigt, wenn wir eine vollständige Lösung gefunden haben
Gierige Algorithmen liefern gute Lösungen für einige mathematische Probleme , aber nicht für andere. Die meisten Probleme, für die sie funktionieren, haben zwei Eigenschaften:
- Gierige Wahl Eigentum
- Wir können die Wahl treffen, die im Moment am besten erscheint, und dann die Teilprobleme lösen, die später auftreten. Die von einem gierigen Algorithmus getroffene Wahl kann von den bisher getroffenen Entscheidungen abhängen, aber nicht von zukünftigen Entscheidungen oder allen Lösungen des Teilproblems. Es trifft iterativ eine gierige Wahl nach der anderen und reduziert jedes gegebene Problem in ein kleineres. Mit anderen Worten, ein gieriger Algorithmus überdenkt seine Entscheidungen nie. Dies ist der Hauptunterschied zur dynamischen Programmierung , die erschöpfend ist und garantiert die Lösung findet. Nach jeder Phase trifft die dynamische Programmierung Entscheidungen basierend auf allen Entscheidungen, die in der vorherigen Phase getroffen wurden, und kann den algorithmischen Weg der vorherigen Phase zur Lösung überdenken.
- Optimale Unterkonstruktion
- "Ein Problem weist eine optimale Unterstruktur auf, wenn eine optimale Lösung des Problems optimale Lösungen der Teilprobleme enthält."
Fehlerfälle
Greedy-Algorithmen liefern für viele andere Probleme nicht die optimale Lösung und können sogar die einzige schlechtestmögliche Lösung liefern . Ein Beispiel ist das oben erwähnte Travelling-Salesman-Problem : Für jede Anzahl von Städten gibt es eine Zuordnung von Entfernungen zwischen den Städten, für die die Nearest-Neighbour-Heuristik die eindeutig schlechtestmögliche Tour ergibt. Weitere mögliche Beispiele finden Sie unter Horizonteffekt .
Typen
Gierige Algorithmen können als „kurzsichtig“ und auch als „nicht wiederherstellbar“ bezeichnet werden. Sie eignen sich nur für Probleme, die einen „optimalen Unterbau“ haben. Trotzdem sind für viele einfache Probleme die am besten geeigneten Algorithmen gierig. Es ist jedoch wichtig zu beachten, dass der Greedy-Algorithmus als Auswahlalgorithmus verwendet werden kann, um Optionen innerhalb einer Suche oder eines Branch-and-Bound-Algorithmus zu priorisieren. Es gibt einige Variationen des Greedy-Algorithmus:
- Reine gierige Algorithmen
- Orthogonale gierige Algorithmen
- Entspannte gierige Algorithmen
Theorie
Gierige Algorithmen haben eine lange Geschichte in der kombinatorischen Optimierung und der theoretischen Informatik . Gierige Heuristiken sind dafür bekannt, bei vielen Problemen suboptimale Ergebnisse zu erzielen, und daher sind natürliche Fragen:
- Für welche Probleme funktionieren gierige Algorithmen optimal?
- Für welche Probleme garantieren gierige Algorithmen eine annähernd optimale Lösung?
- Für welche Probleme liefert der Greedy-Algorithmus garantiert keine optimale Lösung?
Es existiert eine große Menge an Literatur, die diese Fragen sowohl für allgemeine Problemklassen wie Matroide als auch für spezifische Probleme wie Set Cover beantwortet .
Matroiden
Ein Matroid ist eine mathematische Struktur, die den Begriff der linearen Unabhängigkeit von Vektorräumen auf beliebige Mengen verallgemeinert . Hat ein Optimierungsproblem die Struktur eines Matroids, wird es der entsprechende Greedy-Algorithmus optimal lösen.
Submodulare Funktionen
Eine Funktion, die auf Teilmengen einer Menge definiert ist, heißt submodular, wenn wir das für alle haben .
Angenommen, man möchte eine Menge finden, die maximiert . Der Greedy-Algorithmus, der eine Menge aufbaut, indem inkrementell das Element hinzugefügt wird, das bei jedem Schritt am stärksten zunimmt , erzeugt als Ausgabe eine Menge von mindestens . Das heißt, gierig arbeitet innerhalb eines konstanten Faktors von so gut wie die optimale Lösung.
Ähnliche Garantien sind nachweisbar, wenn der Ausgabe zusätzliche Beschränkungen, wie Kardinalitätsbeschränkungen, auferlegt werden, obwohl häufig geringfügige Variationen des Greedy-Algorithmus erforderlich sind. Siehe für eine Übersicht.
Andere Probleme mit Garantien
Andere Probleme, für die der Greedy-Algorithmus eine starke Garantie, aber keine optimale Lösung bietet, umfassen
Viele dieser Probleme haben übereinstimmende untere Schranken; dh der Greedy-Algorithmus schneidet im schlimmsten Fall nicht besser ab als die Garantie.
Anwendungen
Gierige Algorithmen finden typischerweise (aber nicht immer) die global optimale Lösung nicht, weil sie normalerweise nicht alle Daten erschöpfend verarbeiten. Sie können sich zu früh auf bestimmte Entscheidungen festlegen, was sie daran hindert, später die beste Gesamtlösung zu finden. Zum Beispiel finden alle bekannten Greedy-Coloring- Algorithmen für das Graph-Coloring-Problem und alle anderen NP-vollständigen Probleme nicht konsistent optimale Lösungen. Dennoch sind sie nützlich, weil sie schnell zu denken sind und oft gute Annäherungen an das Optimum liefern.
Wenn nachgewiesen werden kann, dass ein Greedy-Algorithmus das globale Optimum für eine gegebene Problemklasse liefert, wird er in der Regel zur Methode der Wahl, da er schneller ist als andere Optimierungsmethoden wie die dynamische Programmierung . Beispiele für solche gierigen Algorithmen sind Kruskals Algorithmus und Prim-Algorithmus für die Suche nach MST-Heuristik und der Algorithmus für die Suche nach optimalen Huffman Bäume .
Auch im Netzwerk- Routing tauchen gierige Algorithmen auf . Beim Greedy-Routing wird eine Nachricht an den Nachbarknoten weitergeleitet, der dem Ziel "am nächsten" liegt. Der Begriff des Standorts eines Knotens (und damit der "Nähe") kann durch seinen physischen Standort bestimmt werden, wie bei der geografischen Leitweglenkung, die von Ad-hoc-Netzwerken verwendet wird . Der Standort kann auch ein völlig künstliches Konstrukt sein, wie beim Small-World-Routing und der verteilten Hash-Tabelle .
Beispiele
- Das Aktivitätsauswahlproblem ist charakteristisch für diese Klasse von Problemen, bei denen das Ziel darin besteht, die maximale Anzahl von Aktivitäten auszuwählen, die nicht miteinander kollidieren.
- In dem Macintosh - Computer - Spiel Kristall Quest - das Ziel ist , zu sammeln Kristalle, in ähnlicher Weise wie das Reiseproblem . Das Spiel hat einen Demo-Modus, in dem das Spiel einen gierigen Algorithmus verwendet, um zu jedem Kristall zu gelangen. Die künstliche Intelligenz berücksichtigt keine Hindernisse, sodass der Demo-Modus oft schnell endet.
- Die Anpassungsverfolgung ist ein Beispiel für einen Greedy-Algorithmus, der auf die Signalannäherung angewendet wird.
- Ein gieriger Algorithmus findet die optimale Lösung für Malfattis Problem , drei disjunkte Kreise innerhalb eines gegebenen Dreiecks zu finden, die die Gesamtfläche der Kreise maximieren; Es wird vermutet, dass derselbe Greedy-Algorithmus für eine beliebige Anzahl von Kreisen optimal ist.
- Ein Greedy-Algorithmus wird verwendet, um während der Huffman-Codierung einen Huffman-Baum zu konstruieren, wo er eine optimale Lösung findet.
- Beim Lernen von Entscheidungsbäumen werden häufig gierige Algorithmen verwendet, die jedoch nicht garantiert die optimale Lösung finden.
- Ein beliebter solcher Algorithmus ist der ID3-Algorithmus zur Konstruktion von Entscheidungsbäumen.
-
Der Dijkstra-Algorithmus und der zugehörige A*-Suchalgorithmus sind nachweislich optimale Greedy-Algorithmen für die Graphensuche und die Suche nach dem kürzesten Weg .
- Die A*-Suche ist bedingt optimal und erfordert eine " zulässige Heuristik ", die die Pfadkosten nicht überschätzt.
- Kruskals Algorithmus und Prim-Algorithmus sind gierige Algorithmen für die Konstruktion von MST-Heuristik eines bestimmten zusammenhängenden Graphen . Sie finden immer eine optimale Lösung, die im Allgemeinen nicht eindeutig ist.
Siehe auch
Verweise
Quellen
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "16 gierige Algorithmen" . Einführung in Algorithmen . MIT-Presse. S. 370–. ISBN 978-0-262-03293-3.
- Gutin, Gregory; Ja, Anders; Zverovich, Alexey (2002). "Handelnder Verkäufer sollte nicht gierig sein: Dominanzanalyse gieriger Heuristiken für den TSP" . Diskrete Angewandte Mathematik . 117 (1–3): 81–86. doi : 10.1016/S0166-218X(01)00195-0 .
- Bang-Jensen, Jørgen; Gutin, Gregory; Yeo, Anders (2004). "Wenn der gierige Algorithmus versagt" . Diskrete Optimierung . 1 (2): 121–127. doi : 10.1016/j.disopt.2004.03.007 .
- Bendall, Gareth; Margot, François (2006). "Gieriger Widerstand kombinatorischer Probleme" . Diskrete Optimierung . 3 (4): 288–298. doi : 10.1016/j.disopt.2006.03.001 .
- Feige, U. (1998). "Ein Schwellenwert von ln n für die Annäherung der Setdeckung" (PDF) . Zeitschrift der ACM . 45 (4): 634–652. doi : 10.1145/285055.285059 . S2CID 52827488 .
- Nemhäuser, G.; Wolsey, LA; Fisher, ML (1978). "Eine Analyse von Näherungen zur Maximierung submodularer Mengenfunktionen - I" . Mathematische Programmierung . 14 (1): 265–294. doi : 10.1007/BF01588971 . S2CID 206800425 .
- Buchbinder, Niv; Feldman, Moran; Naor, Joseph (Seffi); Schwartz, Roy (2014). "Submodulare Maximierung mit Kardinalitätsbeschränkungen" (PDF) . Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete algorithms . Gesellschaft für Industrielle und Angewandte Mathematik. doi : 10.1137/1.9781611973402.106 . ISBN 978-1-61197-340-2.
- Krause, A.; Golovin, D. (2014). "Submodulare Funktionsmaximierung" . In Bordeaux, L.; Hamadi, Y.; Kohli, P. (Hrsg.). Zugänglichkeit: Praktische Ansätze für schwierige Probleme . Cambridge University Press. S. 71–104. doi : 10.1017/CBO9781139177801.004 . ISBN 9781139177801.
Externe Links
- "Greedy algorithm" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- Geschenk, Noah. "Beispiel für gierige Python-Münzen" .