Wat zijn hebzuchtige algoritmen en wanneer werken ze?

Question

Accepted Answer

Een **hebzuchtig algoritme** maakt bij elke stap de **lokaal optimale keuze**, hopende dat dit tot een globaal optimum leidt. Het is eenvoudig en snel, maar alleen correct wanneer het probleem de **hebzuchtige-keuzeeigenschap** en **optimale substructuur** bezit.

## Het idee

Overwegen eerdere keuzen nooit opnieuw — zeg ja tegen de beste onmiddellijke optie en ga verder.

## Voorbeeld: muntuitwisseling met canonieke munten

```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]
```

Dit is optimaal voor Amerikaanse munten, maar **faalt** voor verzamelingen zoals {1, 3, 4} waar hebzuchtig 4+1+1 geeft voor 6 in plaats van 3+3.

## Wanneer hebzuchtig werkt

- **Optimale substructuur:** een optimale oplossing bevat optimale deel-oplossingen.
- **Hebzuchtige-keuzeeigenschap:** een lokaal optimum is onderdeel van een globaal optimum.

Voorbeelden die werken: Dijkstra, Kruskal/Prim (MST), Huffman-codering, intervalplanning.

## Complexiteit

Usually snel — vaak O(n log n) na sorteren.

## Valkuilen

Hebzuchtig is **niet altijd correct**. Bewijs de hebzuchtige-keuzeeigenschap of test tegen een brute-force/DP baseline voordat je het vertrouwt.

## Waarom het belangrijk is

Wanneer hebzuchtig van toepassing is, is het veel eenvoudiger en sneller dan DP of brute force.

Weten *wanneer* het geldig is — en wanneer het stilzwijgend verkeerde antwoorden geeft — is een teken van algoritmische volwassenheid.

Veel hoeksteen-grafiekalgoritmen hebben hebzucht in hun hart.