Greedy-Algorithmen

Kurz: Ein Greedy-Algorithmus („gierig”) trifft in jedem Schritt die Entscheidung, die gerade am besten aussieht, ohne sie später zu bereuen.

Genauer: Das ist schnell und einfach, führt aber nicht immer zum besten Gesamtergebnis. Bei manchen Problemen ist es beweisbar optimal, bei anderen nur eine gute Näherung.

Im Detail

• Optimal: Münzwechsel mit Euro-Münzen (immer die größte passende Münze), Huffman-Kodierung, Dijkstra, minimale Spannbäume (Kruskal, Prim).
• Nicht optimal: Münzwechsel mit Münzen 1, 3, 4 für 6: Greedy nimmt 4+1+1 (3 Münzen), optimal wäre 3+3 (2 Münzen).
• Vergleich: Dynamische Programmierung betrachtet alle Teilprobleme und findet die optimale Lösung, braucht aber mehr Aufwand.
• Eigenschaft: Es muss gelten, dass lokal beste Entscheidungen zur globalen Lösung führen (Greedy-Choice-Eigenschaft).

Siehe auch: Dijkstra-Algorithmus, Dynamische Programmierung