Menene algorithms na greedy, kuma yaushe suke aiki?

Question

Accepted Answer

Algorithin **greedy** yana yin **zabon da suka dace a gida** a kowane mataki, tare da baki cewa zai haifar da cikakke gaske. Yana da sauƙi da sauri, amma yana daidai ne kawai idan matsala ta kasance da **greedy-choice property** da **optimal substructure**.

## Tunani

Kadai maimaita zakonin da aka yi - kulayi kan mafi kyau nan-nan kuma ci gaba.

## Misali: jiya saude tare da kudin gida

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

Hakan ya cancane domin kudin Amurka, amma **ya kasa** domin saiti kamar {1, 3, 4} inda greedy ba ya ba da 4+1+1 gida 6 maimakon 3+3.

## Yaushe greedy aiki

- **Optimal substructure:** cikakken yarjejeniya ya ƙunshi babbar yarjejeniya.
- **Greedy-choice property:** gidan gida shine gida na jijiya gaske.

Misalai da ke aiki: Dijkstra, Kruskal/Prim (MST), Huffman coding, jerin sakowa.

## Hadaddiyar yada

Yawanci sauri — sau da yawa O(n log n) bayan warewa.

## Abubuwan takada

Greedy ba **koyaushe daidai ba**. Tabbata greedy-choice property ko gwaji daga gida-jiya/DP tunani kafin kuna dogara dashi.

## Menene ake ji a gida

LokaciVi greedy ke aiki, yana da kusada da sauri fiye da DP ko tsoma baki.

Sanin *yaushe* yana aiki — da kuma yaushe yana ba da sakaci ba a babare — alamar girma-girman algorithm.

Yawancin mahimman algorithms na grafu suna da greedy a zuki.