Co jsou greedy algoritmy a kdy fungují?

Question

Accepted Answer

**Greedy algoritmus** provádí **lokálně optimální volbu** v každém kroku s nadějí, že vede k globálnímu optimu. Je jednoduchý a rychlý, ale správný je pouze tehdy, když má problém **vlastnost greedy-choice** a **optimální substrukturu**.

## Myšlenka

Nikdy nezvažujte minulé volby — zavažte se nejlepší okamžitou možností a pokračujte.

## Příklad: výměna mincí s kanonickými mincemi

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

Toto je optimální pro americké mince, ale **selhává** pro sady jako {1, 3, 4}, kde greedy dává 4+1+1 pro 6 místo 3+3.

## Kdy greedy funguje

- **Optimální substruktura:** optimální řešení obsahuje optimální podřešení.
- **Vlastnost greedy-choice:** lokální optimum je součástí globálního optima.

Příklady, které fungují: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.

## Složitost

Zwykle rychlé — často O(n log n) po třídění.

## Úskalí

Greedy **není vždy správný**. Dokažte vlastnost greedy-choice nebo jej otestujte proti brute-force/DP baseline před tím, než se jej rozhodnete použít.

## Proč je to důležité

Když se greedy vztahuje, je to mnohem jednoduší a rychlejší než DP nebo brute force.

Vědět *kdy* je platný — a kdy tiše dává nesprávné odpovědi — je znakem algoritmické zralosti.

Mnohé základní grafové algoritmy jsou v srdci greedy.