Was sind Greedy-Algorithmen, und wann funktionieren sie?

Question

Accepted Answer

Ein **Greedy-Algorithmus** trifft bei jedem Schritt die **lokal optimale Wahl** in der Hoffnung, dass dies zum globalen Optimum führt. Er ist einfach und schnell, aber nur korrekt, wenn das Problem die **Greedy-Choice-Eigenschaft** und **optimale Substruktur** besitzt.

## Die Idee

Überdenken Sie frühere Entscheidungen nie — verpflichten Sie sich zur besten sofortigen Option und fahren Sie fort.

## Beispiel: Münzwechsel mit kanonischen Münzen

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # largest first
        while amount >= coin:
            amount -= coin             # take as many as possible
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

Dies ist optimal für US-Münzen, aber **schlägt fehl** für Mengen wie {1, 3, 4}, wobei Greedy 4+1+1 für 6 statt 3+3 ergibt.

## Warum es wichtig ist

- **Optimale Substruktur:** eine optimale Lösung enthält optimale Teillösungen.
- **Greedy-Choice-Eigenschaft:** ein lokales Optimum ist Teil eines globalen Optimums.

Beispiele, die funktionieren: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.

## Komplexität

Gewöhnlich schnell — oft O(n log n) nach dem Sortieren.

## Fallstricke

Greedy ist **nicht immer korrekt**. Beweisen Sie die Greedy-Choice-Eigenschaft oder testen Sie gegen einen Brute-Force/DP-Baseline, bevor Sie sich darauf verlassen.

## Warum es wichtig ist

Wenn Greedy zutrifft, ist es far einfacher und schneller als DP oder Brute Force.

Zu wissen, *wann* es gültig ist — und wann es heimlich falsche Antworten liefert — ist ein Zeichen algorithmischer Reife.

Viele grundlegende Graph-Algorithmen sind im Kern Greedy-Algorithmen.