Hvad er grådige algoritmer, og hvornår virker de?

Question

Accepted Answer

En **grrådig algoritme** foretager det **lokalt optimale valg** ved hvert trin i håb om, at det fører til et globalt optimum. Den er enkel og hurtig, men kun korrekt når problemet har **greedy-choice egenskab** og **optimal substruktur**.

## Ideen

Genvurdér aldrig tidligere valg — forpligt dig til det bedste øjeblikkelige valg og gå videre.

## Eksempel: møntveksling med kanoniske mønter

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

Dette er optimalt for amerikanske mønter, men **fejler** for sæt som {1, 3, 4} hvor grådigt giver 4+1+1 for 6 i stedet for 3+3.

## Hvornår virker grådigt

- **Optimal substruktur:** en optimal løsning indeholder optimale dellinger.
- **Greedy-choice egenskab:** et lokalt optimum er del af et globalt optimum.

Eksempler der virker: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.

## Kompleksitet

Gewalt hurtig — ofte O(n log n) efter sortering.

## Faldgruber

Grådigt er **ikke altid korrekt**. Bevis greedy-choice egenskaben eller test mod en brute-force/DP baseline før du stoler på det.

## Hvorfor det betyder noget

Når grådigt gælder, er det langt enklere og hurtigere end DP eller brute force.

At vide *hvornår* det er gyldigt — og hvornår det stille giver forkerte svar — er et tegn på algoritmisk modenhed.

Mange hjørnesten grafalgoritmer er grådige i hjertet.