Kaj so pohlepni algoritmi in kdaj delujejo?

Question

Accepted Answer

**Pohlepni algoritem** naredi **lokalno optimalno izbiro** pri vsakem koraku, v upanju, da vodi do globalnega optimuma. Je preprost in hiter, a le pravilen, ko ima problem **pohlepno-izbiro lastnost** in **optimalno podstrukturi**.

## Ideja

Nikoli ne prerazmisli preteklih izbir — zavezani se k najboljši neposredni možnosti in nadaljuj.

## Primer: izmenjava kovancev s kanoničnimi kovanci

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

To je optimalno za ameriške kovance, vendar **ne deluje** za nabore kot {1, 3, 4}, kjer pohlepni daje 4+1+1 za 6 namesto 3+3.

## Kdaj pohlepni deluje

- **Optimalna podstruktura:** optimalna rešitev vsebuje optimalne pod-rešitve.
- **Pohlepno-izbiro lastnost:** lokalni optimum je del globalnega optimuma.

Primeri, ki delujejo: Dijkstrin algoritem, Kruskalov/Primov (MST), Huffmanov kod, razporeditev intervalov.

## Kompleksnost

Navadno hiter — pogosto O(n log n) po sortiranju.

## Pasti

Pohlepni **ni vedno pravilen**. Dokaži pohlepno-izbiro lastnost ali testiraj zoper brute-force/DP osnovo preden mu zaupam.

## Zakaj je to pomembno

Ko je pohlepni primeren, je daleč enostavnejši in hitrejši od DP ali brute force.

Znanje *kdaj* je veljaven — in kdaj tiho daje napačne odgovore — je znak algoritmske zrelosti.

Mnogi temeljni grafovski algoritmi so v srcu pohlepni.