Eine konstruktive Methode, die eine Lösung schrittweise aufbaut, indem in jeder Stufe eine lokal optimale Wahl getroffen wird, verwendet in kombinatorischer Optimierung, Approximationsalgorithmen und Existenzbeweisen, wenn lokale Entscheidungen zu einer global akzeptablen Lösung führen.

Prinzip

In jeder Iteration wähle die Option, die nach einem lokalen Kriterium am besten erscheint (z. B. größter unmittelbarer Gewinn oder geringste unmittelbare Kosten), und verlasse dich auf einen Beweis — oft durch Austauschargumente oder Matroidstruktur — dass diese lokalen Entscheidungen zu einer optimalen oder nachweislich guten globalen Lösung aggregieren.

Demonstration

Kruskals Algorithmus für minimale Spannbäume fügt wiederholt die kleinstgewichtige Kante hinzu, die keinen Zyklus erzeugt; lokale minimale Kantenauswahlen ergeben global einen minimalen Spannbaum aufgrund eines Austauscharguments, das an Matroid- oder Schnitt-Eigenschaften von Graphen anknüpft.

Fehlanwendung

Die Anwendung einer gierigen Regel ohne zugrundeliegenden Korrektheitsbeweis kann beliebig schlechte Lösungen erzeugen; etwa führt gierige Auswahl nach unmittelbarem Profit im Rucksackproblem ohne Berücksichtigung der Kapazität zu suboptimalen Ergebnissen, sofern nicht der fraktionale Fall oder eine spezielle Struktur vorliegt.

Konsequenz

Richtig begründet sind gierige Algorithmen einfach, schnell und liefern oft optimale oder konstantfaktorige Approximationslösungen mit transparenten Korrektheitsbeweisen; sie liefern auch konstruktive Existenzbeweise in der Kombinatorik.

Umkehrung

Die Umkehrung sucht zuerst globale Optimalität und leitet daraus eine lokale Auswahlregel ab, die eine optimale Lösung reproduzieren würde, und nutzt dies zur Gestaltung gieriger Strategien durch Charakterisierung notwendiger lokaler Bedingungen des Optimums.

Abgrenzung

Wirksam, wenn das Problem eine matroidale Eigenschaft, eine greedy-choice-Eigenschaft oder ein anwendbares Austauschargument besitzt; versagt bei vielen NP-schweren Problemen ohne solche Struktur oder wenn zukünftige Interaktionen lokale Entscheidungen kurzsichtig machen.

Semantische Spannung

Im Spannungsfeld zu dynamischer Programmierung und globaler Optimierung: gierig ist lokal und schnell, kann aber globale Optima verpassen, die dynamische Programmierung oder Branch-and-Bound finden würden; wenn beide anwendbar sind, bietet gierig meist größere Einfachheit und geringeren Overhead.

Synthese

Gierige Algorithmen treffen wiederholt lokal optimale Entscheidungen und sind gerechtfertigt, wenn die Problemstruktur (Matroid, Austausch-Eigenschaft oder nachweisbare Approximationsgrenze) sicherstellt, dass diese Entscheidungen zu einer nahezu optimalen oder optimalen globalen Lösung führen; fehlt diese Struktur, droht schlechte Leistung.