Vad är giriga algoritmer och när fungerar de?

Question

Accepted Answer

En **girig algoritm** gör det **lokalt optimala valet** vid varje steg, i hopp om att det leder till ett globalt optimum. Det är enkelt och snabbt, men endast korrekt när problemet har **egenskapen för girigar val** och **optimal substruktur**.

## Idén

Ömvärdera aldrig tidigare val — åta dig det bästa omedelbar alternativet och gå vidare.

## Exempel: myntvexling med kanoniska mynt

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

Detta är optimalt för amerikanska mynt, men **misslyckas** för uppsättningar som {1, 3, 4} där girig ger 4+1+1 för 6 istället för 3+3.

## När girig fungerar

- **Optimal substruktur:** en optimal lösning innehåller optimala dellösningar.
- **Egenskapen för girigar val:** ett lokalt optimum är en del av ett globalt optimum.

Exempel som fungerar: Dijkstra, Kruskal/Prim (MST), Huffman-kodning, intervallschemaläggning.

## Komplexitet

Oftast snabb — ofta O(n log n) efter sortering.

## Fallgropar

Girig är **inte alltid korrekt**. Bevisa egenskapen för girigar val eller testa mot en brute-force/DP-baslinje innan du litar på det.

## Varför det är viktigt

När girig tillämpbar, är det långt enklare och snabbare än DP eller brute force.

Att veta *när* den är giltig — och när den tyst ger fel svar — är ett tecken på algoritmisk mognad.

Många grundläggande grafalgoritmer är giriga i hjärtat.