Greedy Algorithm
Ein Greedy-Algorithmus trifft in jedem Schritt die lokal optimale Wahl ohne Backtracking; er ist einfach und effizient, garantiert aber kein globales Optimum.
Zweck
Optimierungsprobleme schnell und approximativ lösen, wobei die Greedy-Choice-Eigenschaft bewiesen werden muss.
Mechanismus
Jeder Schritt nimmt das lokale Optimum in Erwartung eines globalen. Die Anwendbarkeit erfordert die Greedy-Choice-Eigenschaft (ein lokales Optimum lässt sich zu einem globalen erweitern) plus optimale Substruktur. Klassiker: Huffman-Kodierung, Dijkstra, Kruskal, fraktionaler Rucksack.
Anwendungsfälle
- Algorithmendesign
- Approximative Optimierung
- Scheduling-Probleme