Co je to greedy algoritmus a jak se používá při řešení problémů?

Hladový algoritmus je heuristický přístup, který v každém kroku přijímá lokálně optimální řešení v naději, že to povede k globálně optimálnímu řešení.

Použití:

1. Problém výběru aktivit (Activity Selection Problem):

   • Úkol: Vybrat maximální počet nepřekrývajících se časových intervalů z dané sady.
   • Hladové řešení: Seřadit intervaly podle vzestupného času ukončení. V každém kroku vybrat interval s nejmenším časem ukončení, který se nepřekrývá s již vybranými.

   # Příklad výběru aktivit
   # 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]) # Seřadit podle času ukončení
   
   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ýměny mincí (Coin Change Problem) pro kanonické sady mincí:

   • Úkol: Vyplatit zadanou částku minimálním počtem mincí.
   • Hladové řešení: Použít maximální možný počet největších nominálních hodnot mincí, dokud nebude částka vyplacena. Funguje pouze pro určité sady mincí (například 1, 5, 10, 25).

   # Příklad výměny mincí (pro 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. Kruskalův algoritmus pro nalezení minimální kostrové stromu (Minimum Spanning Tree):

   • Úkol: Najít podmnožinu hran, která spojuje všechny vrcholy s minimální celkovou váhou hran.
   • Hladové řešení: Seřadit všechny hrany podle váhy vzestupně. Postupně přidávat hrany, pokud nevytvářejí cyklus s již vybranými hranami, dokud nebude spojeno n-1 hran (kde n je počet vrcholů).

Hladové algoritmy jsou jednoduché na implementaci, ale ne vždy najdou globálně optimální řešení pro libovolné úlohy. Pro některé úlohy (například problém výměny mincí s libovolnou sadou mincí, problém batohu obecně) není hladový přístup optimální. Pro zajištění optimálnosti nebo lepší aproximace může být nutné použít dynamické programování nebo jiné metody. Před použitím hladového algoritmu je třeba ověřit, že je vhodný pro danou úlohu.