Informatik Algorithmen – Greedy-Algorithmen

Eine global optimale Lösung kann durch eine lokal optimale (gierige) Wahl erreicht werden; die erste Entscheidung hängt nicht von späteren Teilproblemen ab.

Eine optimale Lösung des Gesamtproblems enthält optimale Lösungen der Teilprobleme, die nach der gierigen Wahl übrig bleiben.

Greedy trifft irrevocable Entscheidungen ohne Rückblick; DP löst alle Teilprobleme und kombiniert sie, oft mit Memoisierung oder Bottom-Up.

Sortiert alle Kanten nach Gewicht, fügt sie aufsteigend hinzu, wenn sie keinen Zyklus erzeugen (Union-Find), bis n-1 Kanten erreicht sind.

Startet mit einem Knoten, erweitert den Baum iterativ um die leichteste Kante, die einen neuen Knoten verbindet (Priority Queue).

Wählt in jedem Schritt den unerreichten Knoten mit minimalem Tentativabstand (gierige Wahl) und finalisiert dessen kürzesten Pfad.

Baut einen binären Baum bottom-up: vereint stets die zwei seltensten Symbole zu einem Knoten, dessen Gewicht die Summe ist; ergibt präfixfreie optimale Codes.

Sortiert Aktivitäten nach Endzeit, wählt stets die frühest endende, die mit der letzten gewählten nicht kollidiert – liefert optimale maximale Menge.

Bruchteilbar: Wert-Gewicht-Verhältnis sortieren, nehmen was passt – optimal. 0/1: Gegenbeispiel zeigt, dass lokale Optimalität (höchster Wert/kg) nicht global optimal ist.

Bei kanonischen Münzsystemen (z. B. Euro: 1,2,5,10,20,50,100,200), wo jede Münze ein Vielfaches der vorherigen ist oder bestimmte Bedingungen erfüllt.

Eine Struktur (Menge + unabhängige Teilmengen), die Vererbbarkeit und Austauscheigenschaft erfüllt; Greedy findet darauf für Gewichtsfunktionen immer ein Optimum.

Keine Garantie für globales Optimum bei beliebigen Problemen; ohne Beweis von Greedy-Choice-Property und optimaler Substruktur kann die Lösung willkürlich schlecht sein.

0/1-Rucksack: Gegenstände (Wert/Gewicht): A(60/10), B(100/20), C(120/30), Kapazität 50. Greedy nimmt A+B (160), Optimum ist B+C (220).