Çfarë janë algoritmet grabitëse dhe kur funksionojnë?

Question

Accepted Answer

Një **algoritëm grabitës** bën **zgjedhjen lokalisht optimale** në secilin hap, shpresojmë se çon në një optimum global. Është i thjeshtë dhe i shpejtë, por vetëm i saktë kur problemi ka **vetinë e zgjedhjes grabitëse** dhe **struktura optimale**.

## Ideja

Asnjë herë nuk duhet të rimendosh zgjedhje të kaluara — përpiqu të zgjedhësh alternativën më të mirë të menjëhershme dhe vazhdo.

## Shembull: ndërrim monedhash me monedha kanonike

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

Kjo është optimale për monedhën amerikane, por **dështon** për grupet si {1, 3, 4} ku grabitja jep 4+1+1 për 6 në vend të 3+3.

## Kur funksionon grabitja

- **Struktura optimale:** një zgjidhje optimale përmban nën-zgjidhje optimale.
- **Vetia e zgjedhjes grabitëse:** një optimum lokal është pjesë e një optimumi global.

Shembujt që funksionojnë: Dijkstra, Kruskal/Prim (MST), kodimi Huffman, planifikimi i intervaleve.

## Kompleksiteti

Zakonisht i shpejtë — shpesh O(n log n) pas renditjes.

## Kurthët

Grabitja **nuk është gjithmonë e saktë**. Vërteto vetinë e zgjedhjes grabitëse ose testo kundër një bazeline brute-force/DP përpara se ta besosh.

## Pse është e rëndësishme

Kur grabitja është e zbatueshme, ajo është shumë më e thjeshtë dhe më e shpejtë sesa DP ose brute force.

Dija *kur* është e vlefshme — dhe kur në heshtje jep përgjigje të gabuara — është shenjë e pjekurisë algoritmike.

Shumë algoritme themelore të grafikut kanë grabitjen në zemër.