Kas yra greedy algoritmai ir kada jie veikia?

Question

Accepted Answer

**Greedy algoritmas** kiekviename žingsnyje daro **lokaliai optimalų pasirinkimą**, tikėdamasis, kad tai veda prie globalaus optimumo. Jis paprastas ir greitas, tačiau teisingas tik tada, kai problema turi **greedy-choice savybę** ir **optimalią substruktūrą**.

## Idėja

Niekada nepersvarstyk ankstesnių pasirinkimų — pasitikėk geriausiu turimu variantu ir eik toliau.

## Pavyzdys: monetų keitimas su kanoninėmis monetomis

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

Tai optimalu JAV monetoms, bet **nepavyksta** tokiems rinkiniams kaip {1, 3, 4}, kur greedy duoda 4+1+1 skaičiui 6 vietoje 3+3.

## Kada greedy veikia

- **Optimali substruktūra:** optimalus sprendimas yra optimalūs podsprendimų rinkinys.
- **Greedy-choice savybė:** lokalus optimumas yra globalaus optimumo dalis.

Pavyzdžiai, kurie veikia: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.

## Sudėtingumas

Paprastai greitas — dažnai O(n log n) po rūšiavimo.

## Klaidos

Greedy **ne visada teisingas**. Įrodyk greedy-choice savybę arba testuok prieš brute-force/DP pamatą prieš juo pasitikėdamas.

## Kodėl tai svarbu

Kai greedy tinka, tai yra daug paprastesnis ir greitesnis nei DP arba brute force.

Žinojimas *kada* jis galioja — ir kada nutilpus duoda klaidingus atsakymus — yra algoritminės brandos ženklas.

Daug pagrindinių grafų algoritmų širdyje yra greedy.