Co je to greedy algoritmus a v jakých případech se používá?

Hladový algoritmus je přístup k řešení optimalizačních úloh, který každým krokem vybírá nejlepší lokální řešení (nejvýhodnější z hlediska aktuálního okamžiku) v naději, že tato posloupnost optimálních lokálních řešení povede k globálně optimálnímu řešení. Nezohledňuje možné důsledky současného výběru na budoucí kroky.

Charakteristiky:

• Jednoduchost: Obvykle snazší implementovat než dynamické programování nebo jiné metody optimalizace.
• Rychlost: Často mají nižší výpočetní složitost.
• Záruka optimálnosti: Ne vždy zaručuje nalezení globálně optimálního řešení. Záruka platí pouze pro určité třídy úloh.

Používá se u úloh, kde je dokázáno, že lokálně optimální volba v každém kroku vede k globálně optimálnímu řešení. Příklady:

• Problém výběru aktivit (Activity Selection Problem): Výběr maximálního počtu aktivit, které se nepřekrývají časově.
• Problém s batohem (při dělení předmětů): Když lze předměty dělit. Pokud ne, jedná se o úlohu dynamického programování.
• Algoritmus Prim a Kruskal: Pro hledání minimálního kostrového stromu v grafu.
• Dijkstrův algoritmus: Pro hledání nejkratší cesty v grafu s nezápornými váhami hran.
• Huffmanovo kódování: Pro tvorbu optimálního prefixového kódu.

Příklad pseudokódu pro algoritmus výběru aktivit:

Function SelectActivities(activities):
  Sort activities by finish time
  selected_activities = empty list
  last_finish_time = 0

  For each activity in activities:
    If activity.start_time >= last_finish_time:
      Add activity to selected_activities
      last_finish_time = activity.finish_time

  Return selected_activities

Je důležité ověřit, zda je hladový algoritmus vhodný pro konkrétní úlohu, protože jinak může vést k suboptimálnímu řešení.

# Jednoduchý příklad úlohy, kde hladový algoritmus není optimální
# Úloha s mincemi: vydat co nejmenší počet mincí
# Dostupné mince: [1, 5, 10, 25] USD
# Vydat: například 30 centů

# Hladový algoritmus:
#  Vezmeme největší minci <= 30 (25) -> zbytek 5
#  Vezmeme největší minci <= 5 (5) -> zbytek 0
#  Výsledek: 2 mince (25 + 5). Zde je to optimální.

# Dostupné mince: [1, 6, 10]
# Vydat: 12 centů

# Hladový algoritmus:
#  Vezmeme největší minci <= 12 (10) -> zbytek 2
#  Vezmeme největší minci <= 2 (1) -> zbytek 1
#  Vezmeme největší minci <= 1 (1) -> zbytek 0
#  Výsledek: 3 mince (10 + 1 + 1).
#  Optimální řešení: 2 mince (6 + 6).

# Tento příklad ukazuje, že hladový algoritmus ne vždy vede k globálnímu optimu,
# pokud vlastnosti úlohy neodpovídají jeho použitelnosti (například,
# běžné nominály měn často umožňují hladový algoritmus,
# ale libovolné nominály nikoli).