X'inhuma algoritmi greed u meta jaħdmu?

Question

Accepted Answer

**Algoritmu greed** jagħmel **għażla lokalment ottimali** f'kull pass, bi speranza li twassal għal optimu globali. Hija sempliċi u veloċi, iżda korrett biss meta l-problema għandha **proprjetà greedy-choice** u **struttura ottimali**.

## L-idea

Magħaddiesx tabbula għar-riċerka ta' għażliet antiki — iltiżam għall-aħjar għażla immedjata u mur quddiem.

## Eżempju: bidla ta' muniti b'muniti kanonika

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

Dan huwa ottimali għal muniti tal-ISTATI, imma **nuqqas** għal settijiet bħal {1, 3, 4} fejn greed jagħti 4+1+1 għal 6 minflok 3+3.

## Meta jaħdmu algoritmi greed

- **Struttura ottimali:** soluzzjoni ottimali fiha sottusoluq-ionidek ottimali.
- **Proprjetà greedy-choice:** optimu lokali hija parti ta' optimu globali.

Eżempji li jaħdmu: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.

## Kumplessità

Bħal regola veloċi — ħafna drabi O(n log n) wara s-sorting.

## Tħattiġiet

Greed **mhux dejjem korrett**. Ipprova l-proprjetà greedy-choice jew test kontra baseline brute-force/DP qabel ma takkwista filwaqt.

## Għaliex importanti

Meta greed tapplika, hija ħafna iktar sempliċi u veloċi minn DP jew brute force.

Il-għarfien *meta* huwa validu — u meta b'mod taċitu tagħti risposti ħamsin — hija sinjal ta' maturità algoritnika.

Bħala algoritmi grafiku fundamentali għandhom qalb greed.