Coder Wiki | Algorithmen

Greedy-Algorithmen zeichnen sich dadurch aus, dass sie schrittweise denjenigen Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis verspricht. Um unter den Folgezuständen eine Auswahl zu treffen, wird oft eine Bewertungsfunktion verwendet.

Greedy-Algorithmen sind meist schnell, lösen viele Problemen sind aber nicht optimal.

Beispiel

Aufgabe ist die Herausgabe von Münzen bei Wechselgeld. Ziel ist es so wenige Münzen wie möglich zu verwenden

Test mit 15 Cent

Es gibt Münzen zu 1, 5 und 10 Cent

10 + 5 = optimale Lösung

Es gibt Münzen zu 1, 5 und 11 Cent

11 + 1 + 1 + 1 + 1 = suboptimale Lösung

Optimum wäre 5 + 5 + 5

Problem beim Greedy Verfahren ist, dass es die Probleme durch den Schritt löst, der das lokale Optimum ? darstellt. Das globale Optimum bleibt dabei auf der Strecke.