Mitkä ovat ahneita algoritmeja ja milloin ne toimivat?

Question

Accepted Answer

**Ahne algoritmi** tekee **paikallisesti optimaalisen valinnan** jokaisessa vaiheessa toivoen, että se johtaa globaaliin optimiin. Se on yksinkertainen ja nopea, mutta vain oikea, kun ongelmalla on **ahne-choice-ominaisuus** ja **optimaalinen alirakenne**.

## Idea

Älä harkitse aiempia valintoja uudelleen — sitoudu parhaaseen välittömään vaihtoehtoon ja siirry eteenpäin.

## Esimerkki: kolikkojen vaihto kanonisilla kolikoilla

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

Tämä on optimaalinen Yhdysvaltain kolikoille, mutta **epäonnistuu** joukoille kuten {1, 3, 4}, joissa ahne antaa 4+1+1 luvulle 6 3+3:n sijaan.

## Milloin ahne toimii

- **Optimaalinen alirakenne:** optimaalinen ratkaisu sisältää optimaaliset osaratkaisut.
- **Ahne-choice-ominaisuus:** paikallinen optimi on osa globaalia optimia.

Esimerkki, jotka toimivat: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.

## Monimutkaisuus

Yleensä nopea — usein O(n log n) lajittelun jälkeen.

## Ansiot

Ahne **ei ole aina oikea**. Todista ahne-choice-ominaisuus tai testaa sitä brute-force/DP-lähtöviivaa vastaan ennen kuin luotat siihen.

## Miksi se on tärkeää

Kun ahne pätee, se on paljon yksinkertaisempi ja nopeampi kuin DP tai brute force.

Tietää *milloin* se on voimassa — ja milloin se hiljaa antaa väärät vastaukset — on algoritmisen kypsyyden merkki.

Monet periaatteen graafialgoritmi ovat ahneen ytimessä.