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)?