Šta je algoritam pohlepnosti i kako se primenjuje pri…

Heuristički pristup, koji u svakom koraku donosi lokalno optimalno rešenje u nadi da će to dovesti do globalno optimalnog rešenja.

Primena:

Problem izbora aktivnosti (Activity Selection Problem):

Zadatak: Izabrati maksimalan broj nepoklapanja u vremenu intervala iz datog skupa.
Heurističko rešenje: Sortirati intervale po rastućem vremenu završetka. U svakom koraku izabrati interval sa najmanjim vremenom završetka koji se ne preklapa sa već izabranim.

# Primer izbora aktivnosti
# activities = [(start_time, end_time)]

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
activities.sort(key=lambda x: x[1]) # Sortiranje po vremenu završetka

selected_activities = []
last_finish_time = -1

for activity in activities:
    if activity[0] >= last_finish_time:
        selected_activities.append(activity)
        last_finish_time = activity[1]

print(selected_activities) # [ (1, 4), (5, 7), (8, 11), (12, 16) ]

Problem razmene novčića (Coin Change Problem) za kanoničke setove novčića:
- Zadatak: Izdati zadatu sumu minimalnim brojem novčića.
- Heurističko rešenje: Koristiti maksimalan mogući broj najvećih nominalnih vrednosti novčića dok se suma ne isplati. Radi samo za određene setove novčića (npr. 1, 5, 10, 25).
```
# Primer razmene novčića (za kanoničke novčiće)
coins = [25, 10, 5, 1]
amount = 67
result = {}

for coin in coins:
    while amount >= coin:
        result[coin] = result.get(coin, 0) + 1
        amount -= coin

print(result) # {25: 2, 10: 1, 5: 1, 1: 2}
```
Kruskalov algoritam za pronalaženje minimalnog razapinjućeg stabla (Minimum Spanning Tree):
- Zadatak: Naći podskup grana koji povezuje sve vrhove sa minimalnom ukupnom težinom grana.
- Heurističko rešenje: Sortirati sve grane po težini rastuće. Postepeno dodavati grane ako ne formiraju ciklus sa već odabranim granama, dok se ne poveže n-1 grana (gde je n broj vrhova).

Heuristički algoritmi su jednostavni za implementaciju, ali ne uvek pronalaze globalno optimalno rešenje za proizvoljne zadatke. Za neke zadatke (npr. problem razmene novčića sa proizvoljnim setom, problem ranca u opštem slučaju) žedni pristup nije optimalan. Za garantovanje optimalnosti ili bolju približnost mogu biti potrebni dinamičko programiranje ili drugi metodi. Pre primene žednog algoritma, potrebno je proveriti da li je pogodan za dat zadatak.

Šta je algoritam pohlepnosti i kako se primenjuje pri rešavanju problema?