Čo je to greedy algoritmus a ako sa používa pri riešení problémov?

Heuristický prístup, ktorý v každom kroku prijíma lokálne optimálne riešenie v nádeji, že to povedie k globálne optimálnemu riešeniu.

Použitie:

1. Problém výberu aktivít (Activity Selection Problem):

   • Úloha: Vybrať maximálne množstvo neprekrývajúcich sa časových intervalov z daného súboru.
   • Hladové riešenie: Usporiadať intervaly podľa rastúceho času ukončenia. V každom kroku vybrať interval s najmenším časom ukončenia, ktorý sa neprekrýva s už vybranými.

   # Príklad výberu aktivít
   # 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]) # Usporiadanie podľa času ukončenia
   
   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) ]
   

2. Problém výmeny mincí (Coin Change Problem) pre kanonické sady mincí:

   • Úloha: Vydať zadanú sumu minimálnym počtom mincí.
   • Hladové riešenie: Použiť maximálne možné množstvo najväčších nominálnych hodnôt mincí, kým suma nebude vyplatená. Funguje iba pre určité sady mincí (napríklad 1, 5, 10, 25).

   # Príklad výmeny mincí (pre kanonické mince)
   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}
   

3. Kruskalov algoritmus pre nájdenie minimálneho rozpinajúceho stromu (Minimum Spanning Tree):

   • Úloha: Nájsť podmnožinu hrán, ktorá spája všetky vrcholy s minimálnou celkovou váhou hrán.
   • Hladové riešenie: Usporiadať všetky hrany podľa váhy vzostupne. Postupne pridávať hrany, ak nevytvárajú cyklus s už vybranými hranami, kým nebude spojeno n-1 hrán (kde n je počet vrcholov).

Hladové algoritmy sú jednoduché na implementáciu, ale nie vždy nájdu globálne optimálne riešenie pre ľubovoľné úlohy. Pre niektoré úlohy (napríklad, problém výmeny mincí s ľubovoľným setom, problém batohu v všeobecnosti) žiadny prístup nie je optimálny. Na zabezpečenie optimálnosti alebo lepšej približnosti môžu byť potrebné dynamické programovanie alebo iné metódy. Pred použitím žiadneho heuristického algoritmu je potrebné overiť, či je vhodný pre danú úlohu.