Was ist ein Greedy-Algorithmus

Ein Greedy-Algorithmus ist ein Algorithmus, der eine Lösung eines Optimierungsproblems dadurch erzeugt, dass er in jedem Schritt die „beste“ zur Verfügung stehende Auswahl aus einer Menge von Entscheidungsoptionen wählt.

Ein sehr bekannter Greedy-Algorithmus ist der Nearest-Neighbour-Algorithmus zur Lösung von Tourenplanungsproblemen: Man baut die Touren auf, indem man im Depot startet und in jedem Schritt den nächstgelegenen Ort/Kunden besucht, der noch nicht besucht wurde, und dessen Hinzunahme zur Tour zulässig ist. Kann kein weiterer Ort hinzugefügt werden, fährt man zum Depot zurück, schließt die aktuelle Tour ab und beginnt mit einer neuen Tour. Der Algorithmus endet, wenn alle Orte/Kunden in Touren aufgenommen wurden.

Leider liefern Greedy-Algorithmen in der Regel sehr schlechte Ergebnisse, weil am Ende nur sehr ungünstige Entscheidungsmöglichkeiten zur Verfügung stehen. Eine Ausnahme ist die Bestimmung eines minimal spannenden Baums in einem Graphen. In diesem Sonderfall findet der Greedy-Algorithmus (sog. „Algorithmus von Kruskal“) tatsächlich eine garantiert optimale Lösung.

Was ist ein Greedy-Algorithmus - gts systems
Cookie Consent with Real Cookie Banner