Greedy-Algorithmen.

Greedy heißt 'gierig': bei jeder Entscheidung nimmst du die lokal beste Option, ohne dich umzuschauen. Manchmal landet das beim globalen Optimum, manchmal nicht. Klausur-Pflicht in 13/17 WInf-Algo-Klausuren, wichtige Counterpart-Strategie zu DP.

Die Idee in einem Satz

Greedy-Algorithmus: Trifft an jeder Stelle eine lokal optimale Entscheidung in der Hoffnung, dass die Gesamtlösung global optimal wird.

Wann funktioniert Greedy?

Zwei Voraussetzungen (analog zu DP, aber stärker):

1. Greedy-Auswahl-Eigenschaft: Lokal beste Auswahl führt zur global besten Lösung
2. Optimale Substruktur: Restproblem nach Greedy-Schritt hat selbe Struktur

Klausur-Faustregel: Wenn beides gilt → Greedy ist optimal. Wenn nur (2) gilt → DP nötig.

Beispiel: Münzwechsel

Problem: Gib 20€ Wechselgeld mit den wenigsten Münzen.

Münzen Euro-System: {1, 2, 5, 10, 20, 50, 100, 200}

Greedy: nimm immer die größte Münze ≤ Rest.

• 20 → 1× 20€ Münze ✓

Bei Münzen \1, 6, 10\ für 12 Cent:

• Greedy: 10 + 1 + 1 = 3 Münzen
• Optimal: 6 + 6 = 2 Münzen ✗

Greedy ist im Euro-System optimal, in beliebigen Systemen NICHT.

Klassische Greedy-Probleme

1. Activity-Selection (Klausur-Klassiker)

Gegeben Events mit Start- und Endzeit. Wähle die maximale Anzahl nicht-überlappender Events.

Greedy-Regel: Sortiere nach Endzeit. Nimm erstes Event, dann das nächste, dessen Start ≥ vorherigem End ist.

Korrekt! Beweis durch Austauschargument: wenn du eine andere Lösung hättest, könntest du das erste Event durch das mit frühester Endzeit ersetzen, ohne schlechter zu werden.

2. Huffman-Codierung

Optimale Präfix-Codes für Datenkompression. Iterativ die zwei seltensten Symbole zu einem Knoten verschmelzen → Binärbaum mit optimaler durchschnittlicher Codewort-Länge.

3. Minimum Spanning Tree (Prim, Kruskal)

Greedy auf Kanten (Kruskal: nimm immer billigste Kante ohne Zyklus) oder Knoten (Prim: erweitere Baum mit billigster Außen-Kante). Beide finden den global minimalen Spannbaum.

4. Fractional Knapsack

Wie 0/1-Knapsack, aber Items teilbar. Greedy: nimm Items in absteigender Reihenfolge nach v_i / w_i (Wert pro Gewichtseinheit), nimm so viel wie passt.

Achtung: 0/1-Knapsack (Items unteilbar) ist NICHT Greedy-lösbar, braucht DP.

5. Dijkstra

Auch ein Greedy-Algorithmus! In jedem Schritt: extrahiere Knoten mit kleinster Distanz (= lokal beste Wahl). Bei nicht-negativen Gewichten optimal.

Greedy vs. DP

Faustregel: Erst Greedy probieren (einfacher). Wenn das nicht optimal ist (Gegenbeispiel finden!), DP nutzen.

Beweis-Strategien für Greedy-Optimalität

Austauschargument

Annahme: Es gibt eine bessere Lösung als die von Greedy. Zeige: Du kannst die Greedy-Entscheidung in die andere Lösung einbauen ohne Verschlechterung. Daraus folgt Greedy = optimal.

Greedy bleibt vorne

Bei jedem Schritt liegt die Greedy-Lösung mindestens so gut wie jede andere Teil-Lösung mit gleicher Anzahl Schritte.

Pseudocode-Schema

greedy_algorithm(input):
    sort/prepare input by greedy criterion
    solution = empty
    for each candidate in sorted order:
        if candidate is feasible:
            add candidate to solution
    return solution

Beispiel-Pseudocode: Activity-Selection

selectActivities(activities):
    sort activities by end time ascending
    selected = []
    lastEnd = -infinity
    for activity in activities:
        if activity.start >= lastEnd:
            selected.append(activity)
            lastEnd = activity.end
    return selected

Laufzeit: O(n log n) wegen Sortierung. Greedy-Loop selbst ist O(n).

Klausur-Faustregeln

1. Greedy = lokal beste Entscheidung. Nie zurück, nie umentscheiden.

2. Sortieren ist oft erster Schritt. Activity-Selection nach Endzeit, Knapsack nach v/w, Huffman nach Häufigkeit.

3. Greedy ist nicht immer optimal. Münzwechsel kann schiefgehen, 0/1-Knapsack braucht DP.

4. Beweise mit Austauschargument. Annehmen: andere Lösung besser → tausche greedy-Schritt rein → kein Schaden → Greedy ist optimal.

5. Greedy vs. DP: Greedy einfacher + schneller, DP optimal. Wenn unsicher: probiere Gegenbeispiele.

Häufige Stolpersteine

1. Greedy ohne Korrektheits-Beweis. Funktioniert manchmal "rein zufällig". Bei Klausur immer prüfen: gibt's ein Gegenbeispiel?

2. 0/1-Knapsack mit Greedy. Falsch! Nur Fractional Knapsack ist greedy-optimal. 0/1 (Items unteilbar) braucht DP.

3. Falsches Sortier-Kriterium. Activity-Selection nach Start-Zeit funktioniert NICHT. Muss nach Endzeit sein. Bei Knapsack: Wert pro Gewicht (v/w), nicht nur Wert.

4. Greedy für Probleme ohne Greedy-Auswahl-Eigenschaft. TSP (Traveling Salesman) ist NICHT greedy-lösbar (NP-schwer).

5. Greedy mit Backtracking verwechseln. Greedy macht eine Entscheidung pro Schritt und vergisst Alternativen. Backtracking probiert systematisch alle Möglichkeiten durch.

Activity-Selection-Lab

Du hast 8 Vorlesungen mit verschiedenen Start- und Endzeiten. Wähle die maximale Anzahl, die du besuchen kannst ohne Überlappung.

Vergleich:

• Greedy nach Endzeit (korrekt!)
• Greedy nach Startzeit (Lockmittel, funktioniert nicht!)
• Greedy nach Dauer (auch falsch!)

Beobachte, welche Strategie die meisten Vorlesungen auswählt.

Klausur-Tipp: Bei Klausur-Aufgaben zur Activity-Selection IMMER nach Endzeit sortieren. Das ist die einzige korrekte Greedy-Strategie. Begründung: nach Austauschargument.

Greedy-Algorithmen, Praxis-Übung

6 Aufgaben zu Greedy-Konzepten, klassischen Problemen, Korrektheit.