Čo je to greedy algoritmus a v akých prípadoch sa používa?

Hladný algoritmus je prístup k riešeniu optimalizačných úloh, ktorý každým krokom vyberá najlepšie lokálne riešenie (najvýhodnejší z hľadiska aktuálneho okamihu) v nádeji, že táto sekvencia optimálnych lokálnych riešení povedie k globálne optimálnemu riešeniu. Nezohľadňuje možné dôsledky súčasného výberu na budúce kroky.

Charakteristiky:

• Jednoduchosť: Obvykle jednoduchšie implementovať ako dynamické programovanie alebo iné metódy optimalizácie.
• Rýchlosť: Často majú nižšiu výpočtovú zložitosť.
• Záruka optimálnosti: Ne vždy zaručuje nájdenie globálne optimálneho riešenia. Záruka platí len pre určité triedy úloh.

Používa sa pri úlohách, kde je dokázané, že lokálne optimálny výber na každom kroku vedie k globálne optimálnemu riešeniu. Príklady:

• Úloha o výbere aktivít (Activity Selection Problem): Výber maximálneho počtu aktivít, ktoré sa neprekrývajú v čase.
• Úloha o batohu (pri delení predmetov): Keď je možné predmety deliť. Ak nie, ide o úlohu dynamického programovania.
• Algoritmus Príma a Kruskal: Pre hľadanie minimálneho rozvetveného stromu v grafe.
• Dijkstrův algoritmus: Pre hľadanie najkratšej cesty v grafe s nezápornými váhami hrán.
• Kódovanie Huffmana: Pre tvorbu optimálneho prefixového kódu.

Príklad pseudokódu pre algoritmus výberu aktivít:

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é overiť, či je hladný algoritmus vhodný pre konkrétnu úlohu, pretože inak môže viesť k suboptimálnemu riešeniu.

# Jednoduchý príklad úlohy, kde hladný algoritmus nie je optimálny
# Úloha o vydaní mincí: vydanie čo najmenšieho počtu mincí
# Dostupné mince: [1, 5, 10, 25] USD
# Vydanie: napríklad, 30 centov

# Hladný algoritmus:
# Vezmeme najväčšiu mincu <= 30 (25) -> zvyšok 5
# Vezmeme najväčšiu mincu <= 5 (5) -> zvyšok 0
# Výsledok: 2 mince (25 + 5). Toto je optimálne.

# Dostupné mince: [1, 6, 10]
# Vydanie: 12 centov

# Hladný algoritmus:
# Vezmeme najväčšiu mincu <= 12 (10) -> zvyšok 2
# Vezmeme najväčšiu mincu <= 2 (1) -> zvyšok 1
# Vezmeme najväčšiu mincu <= 1 (1) -> zvyšok 0
# Výsledok: 3 mince (10 + 1 + 1).
# Optimálne riešenie: 2 mince (6 + 6).

# Tento príklad ukazuje, že hladný algoritmus nie vždy vedie k globálnemu optima,
# ak vlastnosti úlohy neodpovedajú jeho použiteľnosti (napríklad,
# štandardné nominály mien často umožňujú hladný algoritmus,
# ale ľubovoľné nominály - nie).