Greedy-Algorithmus

Ein Greedy-Algorithmus ist eine Klasse konstruktiver Algorithmen, die in jedem Schritt die lokal optimal erscheinende Entscheidung trifft und nie zurückverfolgt. Die Wurzeln liegen in klassischer kombinatorischer Arbeit (Kruskal 1956 und Prim 1957 für minimal aufspannende Bäume; Dijkstra 1959 für kürzeste Wege). Wann der Greedy-Ansatz das globale Optimum liefert, charakterisiert die Matroidtheorie: der Satz von Rado-Edmonds (Edmonds 1971) besagt, dass ein Mengensystem genau dann für alle Gewichtsfunktionen durch den Greedy-Algorithmus optimal gelöst wird, wenn es ein Matroid ist. Daher lösen sich minimal aufspannende Bäume (Kruskal/Prim), Huffman-Codierung (Huffman 1952) und gewichtete Fertigstellungszeit auf einer Einzelmaschine (SPT/EDD-Regel, Smith 1956) greedy optimal. Hingegen liefern Rucksackproblem, Bin Packing, Set Covering und VRP nur Greedy-Lösungen mit bekanntem Approximationsfaktor (z. B. Chvátal 1979 ln(n)+1 für Set Covering) und sind nicht global optimal. Praktisch spielen Greedy-Algorithmen drei Rollen: (1) schnelle konstruktive Heuristik (Warmstart), (2) Approximationsalgorithmus mit Gütegarantie, (3) Anfangslösung für lokale Suche oder Metaheuristiken. Heuristisch sind Greedy-TSP (Nächster Nachbar), Clarke-Wright-Savings-Methode (1964) für VRP und die LPT/SPT-Familie im Scheduling industrielle Standardbeispiele. Cormen, Leiserson, Rivest und Stein (CLRS, 2009), Kapitel 16, ist die Referenzdarstellung.