Greedy-Algorithmen

ein Such-Algorithmus heißt greedy (gierig), falls er in jedem Knoten des Suchbaums die lokal beste Entscheidung trifft und nie ändert.

(backtracking ohne back: der Suchbaum ist nur ein Pfad.)

Greedy-Algorithmen sind schnell, aber nicht immer optimal.


Beispiel: Münzsysteme: benutze zur Herausgabe eines Betrages immer zunächst das größte passende Geldstück.

Ist dieser Algorithmus für das Euro-System optimal (d. h. benutzt immer die geringste mögliche Anzahl von Münzen)?

Für welches System nicht (Beispiele)?



Johannes Waldmann 2005-01-25