Greedy-Algorithmen
Greedy-Algorithmus Definition
Ein Greedy-Algorithmus ist gierig (greedy) und kurzsichtig: er wählt in der jeweils aktuellen Situation / auf der aktuellen Stufe die Lösung aus, die ihn an dieser Stelle den größten Schritt dem Ziel näher bringt (gierig) – ohne weiter nach vorn oder nach hinten zu schauen (kurzsichtig).
Greedy-Algorithmen sind einfach und schnell, garantieren aber nicht immer eine optimale Lösung.
Der Dijkstra-Algorithmus (sucht den kürzesten Weg in einem Graphen, z. B. einem Straßennetz) ist beispielsweise ein Greedy-Algorithmus (und führt zu einer optimalen Lösung).
Beispiel
Beispiel (zum Verständnis des Prinzips)
Sie wollen mit möglichst wenig Produkten 1.900 Kalorien zu sich nehmen.
Vor Ihnen liegen 2 Burger mit jeweils 600 Kalorien, 3 Tüten Pommes mit jeweils 300 Kalorien, 3 Schokoriegel mit jeweils 233 Kalorien und 2 Äpfel mit jeweils 100 Kalorien.
Was bringt Sie Ihrem Ziel (1.900 Kalorien) jeweils den größten Schritt entgegen?
1) Burger 1 (600, kumuliert 600; verbleibende Kalorienlücke: 1.300)
2) Burger 2 (600, kumuliert 1.200; verbleibende Kalorienlücke: 700)
3) Pommes 1 (300, kumuliert 1.500; verbleibende Kalorienlücke: 400)
4) Pommes 2 (300, kumuliert 1.800; verbleibende Kalorienlücke: 100)
5) Apfel 1 (100, kumuliert 1.900; verbleibende Kalorienlücke: 0)
Sie müssen also 5 Produkte essen. Der hier angewandte Algorithmus ging so vor, dass jeweils das Produkt mit den höchsten Kalorien gewählt wurde, das noch in die verbliebene Kalorienlücke hineinpasste.
Das gleiche Ergebnis (1.900 Kalorien mit 5 Produkten) hätten Sie auch erreicht mit 2 Burgern (2 x 600 = 1.200) und 3 Schokoriegeln (3 x 233 = 699, gerundet 700). Diese Alternative findet aber der Greedy-Algorithmus nicht, weil er auf jeder einzelnen Stufe gierig ist und aufgrund der höheren Kalorienzahl nach den 2 Burgern die Pommes wählt und nicht "weiterdenkt".