Algorithmu za kushindi ni nini, na lini zimula?

Question

Accepted Answer

**Algorithmu wa kushindi** hufanya **chaguo finyu la ndani** katika kila hatua, la tumaini kwamba inasababisha digrii ya ulimwengu. Ni rahisi na haraka, lakini tu sahihi lini tatizo lina **mali ya chaguo la kushindi** na **muundo mwingine kamali**.

## Wazo

Usiwajibari chaguzi za zamani — jikamata chaguo bora la papo hapo na endelea.

## Mfano: ubadilishaji wa sarafu na sarafu za kimtamawala

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

Hii ni kamali kwa sarafu za Kiamerika, lakini **haidhani** kwa seti kama {1, 3, 4} ambapo kushindi inatoa 4+1+1 kwa 6 badala ya 3+3.

## Lini kushindi zimula

- **Muundo mwingine kamali:** suluhisho kamali lina suluhisho ndogo kamali.
- **Mali ya chaguo la kushindi:** digrii ya ndani ni sehemu ya digrii ya ulimwengu.

Miundo inayofanya kazi: Dijkstra, Kruskal/Prim (MST), Huffman coding, ratiba ya farala.

## Weledi

Kawaida haraka — kawaida O(n log n) baada ya kupanga.

## Tosheka

Kushindi **si kila wakati sahihi**. Thibitisha mali ya chaguo la kushindi au jaribu kwa heshima brute-force/DP kabla ya kuamini.

## Kwa nini ni muhimu

Lini kushindi iko, ni rahisi sana na haraka kuliko DP au brute force.

Kujua *lini* ni halali — na lini kimya inatoa majibu mabaya — ni alama ya kuzoea algorithmique.

Algoritmu nyingi za msingi wa grafu ni kushindi katika moyo.