Greedy Algorithm

Beispiel: Wechselgeld. Du sollst 67 Cent herausgeben mit möglichst wenig Münzen. Greedy-Strategie:

1. Nimm die größte Münze, die passt: 50 Cent. (Rest: 17).
2. Nimm die größte Münze, die passt: 10 Cent. (Rest: 7).
3. Nimm die größte Münze, die passt: 5 Cent. (Rest: 2).
4. Nimm 2 Cent. Fertig. 4 Münzen. Perfekt. Greedy funktioniert hier super!

1. Wann Greedy scheitert

Stell dir ein Währungssystem vor mit Münzen: 1, 3, 4. Du sollst 6 Cent geben. Greedy nimmt die größte (4). Rest: 2. Dann zwei 1er. Ergebnis: 4 + 1 + 1 (3 Münzen). Optimal wäre aber: 3 + 3 (2 Münzen)! Hier versagt Greedy, weil er zu kurzsichtig war. Hier bräuchte man Dynamic Programming.

2. Dijkstra & Huffman

Berühmte Algorithmen sind greedy:

• Dijkstra (Kürzester Pfad): Gehe immer zum nächsten Knoten, der am dichtesten dran ist.
• Huffman-Kodierung (ZIP-Komprimierung): Fasse immer die zwei seltensten Zeichen zusammen. Hier ist mathematisch bewiesen, dass Gier immer zum optimalen Ziel führt (Matroid-Theorie).

1. Lokale Optima vs. Globale Optima

Der mathematische Archillesfersen von der puren Gier (Greedy Choice Property). In Systemen, in denen Subentscheidungen strikte Subsumptionsstrukturen unterliegen (Optimal Substructure), dominiert Greedy (siehe Kruskals Minimum Spanning Tree). Treten im Entscheidungsbaum asymmetrische Bestrafungen (Knapsack-Problem, Traveling Sales Person) auf, landet der Algorithmus irreparabel blinden Auges in einem Lokalen Optimum. Das System findet den Gipfel eines kleinen Hügels, anstatt in das düstere Tal des Verzichtes abzusteigen, um drei Meilen weiter den eigentlichen majestätischen Berg Everest (Global Optima) bezwingen zu können.

2. Matroide Kombinatorik (Das Greedy-Theorem)

Wie beweist man vorab, dass ein gieriger Hacker Code korrekt ist, ohne ihn für Milliarden Test-Eingaben laufen zu lassen? Die Matroid-Theorie ist das formale Rückgrat in Diskreter Mathematik, um die Richtigkeit von Greedy-Strukuren wasserdicht zu verifizieren. Ein Matroid ist ein Paar auf der Menge kombinatorisch unabhängiger Graphenmengen ($I, E$). Wenn die Problem-Datenstruktur das "Augmentation-Axiom" (Austauscheigenschaft / Independence Property) eines formellen Matroids erfüllt, garantiert das Rado-Edmonds-Theorem rigoros mathematisch, dass ein trivial designter Greedy-Algorithmus garantiert das perfekte Welt-Maximum liefert und Dynamic Programming Code reine Verschwendung an Developer-Time wäre.

3. Gradient Descent als Continuous Greedy Process

In der künstlichen Intelligenz basiert der elementare Deep Learning Kern auf Gradient Descent – es ist de facto ein Algorithmus der Greedy-Klasse im Multi-Dimensionalen, kontinuierlichen Vektorraum. Um das $Loss$ Netzwerk (Fehler) stetig zu minimieren, errechnet die KI den steilsten partiellen Neigungswinkel im Terrain. Sie schreitet "gierig" stumpf exakt bergab entgegen des Gradienten, ohne zu wissen wo ihr Schritt hingeht. Da gigantische Multi-Billion-Dim Räume kraterhaft zerklüftet sind, stolpern simple SGD-Gradients hier erbärmlich und stecken in Tälern (Lokale Minima) fest. Komplexe Optimizer wie AdamW fügen daher "Momentum" in den Gier-Prozess hinzu, was den Abroll-Kugeln physische Trägheit verleiht, um kurzzeittige Berg-Widerstände zu überrollen, ohne den Greedy Flow abzubrechen.