Greedy-Algorithmus (englisch greedy = gierig) ist ein Algorithmus-Paradigma: Ein Problem wird Schritt für Schritt gelöst, wobei in jedem Schritt die aktuell lokal beste Entscheidung getroffen wird — ohne Zurückrollen und ohne die späteren Konsequenzen neu zu bewerten. Der Name stammt vom Prinzip „Nimm immer das, was jetzt am besten aussieht“.
Typische Beispiele
- Dijkstra wählt immer den aktuell nächstgelegenen Knoten und findet so die kürzesten Wege.
- Der minimale Spannbaum nach Kruskal oder Prim fügt immer die günstigste verträgliche Kante hinzu.
- Die Huffman-Kodierung kombiniert stets die beiden seltensten Zeichen zu einem Baum — das Ergebnis ist eine optimale verlustfreie Kompression.
- Beim Münzwechsel mit üblichen Währungen liefert „immer die größte passende Münze“ die minimale Anzahl.
Wann funktioniert Greedy?
Ein Greedy-Verfahren ist nur dann garantiert optimal, wenn das Problem die Greedy-Eigenschaft besitzt: Lokal optimale Entscheidungen führen auch global zum Optimum, und einmal getroffene Entscheidungen müssen nie revidiert werden. Bei vielen realen Problemen ist das nicht der Fall — dann liefert Greedy lediglich eine schnelle Näherungslösung. Die dynamische Programmierung ist das Gegenstück: Sie untersucht alle Teilprobleme systematisch und findet auch dort das Optimum, wo Greedy scheitert. Beide Paradigmen bauen auf dem Algorithmus-Begriff auf.
Kurz zusammengefasst
- Paradigma: pro Schritt die lokal beste Wahl, kein Backtracking
- Sehr effizient, aber nur bei Greedy-Eigenschaft garantiert optimal
- Klassiker: Dijkstra, Kruskal, Prim, Huffman, Münzwechsel
- Abgrenzung: dynamische Programmierung wägt alle Teilprobleme ab