¶ Greedy Algorithmus[1]
Der Begriff „Greedy Algorithmus“ fasst eine Klasse von Algorithmen zusammen, die in jedem Schritt die lokal optimale Entscheidung treffen. Das bedeutet, dass immer die nächst beste Option gewählt wird, ohne den Versuch vorausschauend zu handeln, und ohne eine getroffene Wahl neu zu überdenken.
Durch dieses Vorgehen ergeben sich oft viel kürzere Laufzeiten als bei der dynamischen Programmierung. Allerdings wird auch nicht zwingend die global optimale Lösung gefunden.
¶ Optimales Beispiel
Obwohl das sogenannte change making problem eigentlich NP-schwer ist, kann es für die meisten Währungssysteme mit einem Greedy Algorithmus optimal gelöst werden.
Betrachtet werde folgendes Beispiel:
Es sollen 73 Cent mit der minimalen Anzahl von Centmünzen ausgegeben werden. Es stehen also 50, 20, 10, 5, 2 und 1 Cent Münzen zur Verfügung.
Ein Greedy Algorithmus wird nun immer den größten, in den Restbetrag passenden Betrag wählen. Sprich, erst die 50ct Münze. Dann bleiben 23ct übrig. Als nächstes wird also die 20ct Münze gewählt. Der Rest beträgt 3ct. Der Algorithmus wählt erst die 2ct, dann die 1ct Münze.
Mit weniger als diesen vier Münzen lässt sich der gesuchte Betrag nicht darstellen. Das heißt, der Greedy Algorithmus hat die global beste Lösung gefunden.
¶ Suboptimales Beispiel
Auch wenn für einige Probleme ein Greedy Algorithmus ein guter und effizienter Ansatz ist, gibt es durchaus viele Anwendungen, bei denen diese Herangehensweise scheitert, beziehungsweise eine suboptimale Lösung liefert.
Ein simples Beispiel ist in Abb. 1 zu sehen.
Ziel ist es, den Pfad mit der größten Summe über den Knoten zu finden. Rot zeigt den Greedy Ansatz: Vom Wurzelknoten aus besteht die Wahl zwischen 3 und 12. Da nur auf das lokale Optimum geachtet wird und spätere Optionen nicht bekannt sind, entscheidet sich der Algorithmus für die 12, obwohl dies mit Blick auf den gesamten Suchbaum nicht die beste Lösung sein kann.
¶ Überblick
Bei komplizierteren Aufgaben mag ein Greedy Algorithmus nicht immer die beste Wahl treffen, aber wenn ein dynamischer Ansatz eine unausführbare Laufzeit zum Finden einer Lösung benötigt, kann ein Greedy Ansatz einen akzeptablen Weg in einer annehmbaren Zeit liefern. Insgesamt kommt es immer auf die Struktur des Problems an, ob sich diese Art von Algorithmus anbietet oder nicht.
Es gibt außerdem verschiedene Variationen von Greedy Algorithmen mit verschiedenen Stärken, wie beispielsweise orthogonal greedy algorithms oder relaxed greedy algorithms, auf die hier allerdings nicht weiter eingegangen werden soll.
¶ Bildquellen
Abb. 1: https://en.wikipedia.org/wiki/File:Greedy-search-path-example.gif
¶ Referenzen
https://en.wikipedia.org/wiki/Greedy_algorithm (Stand vom 14.06.2025) ↩︎