Mis on ahnus algoritm ja kuidas seda rakendatakse probleemide lahendamisel?

Hedristiline lähenemine, mis igal sammul võtab vastu kohalikult optimaalse otsuse, lootes, et see viib globaalselt optimaalse lahenduseni.

Rakendused:

1. Tegevuste valiku probleem (Activity Selection Problem):

   • Ülesanne: Valida maksimaalne arv mitte-ülekattuvaid ajavahemikke antud kogumist.
   • Hedristiline lahendus: Sorteerida ajavahemikud nende lõpuaja järgi kasvavas järjekorras. Igal sammul valida ajavahemik, mille lõpu aeg on väikseim ja mis ei kattuda juba valitud omadega.

   # Näide — Tegevuste valik
   # 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]) # Sorteeri lõpuaja järgi
   
   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. Müntide vahetamise probleem (Coin Change Problem) — kanoniliste müntide kogumite jaoks:

   • Ülesanne: Väljastada määratud summa minimaalne müntide arvuga.
   • Hedristiline lahendus: Kasutada maksimaalselt suurimaid nominaale, kuni summa on välja makstud. Toimib ainult teatud kogumite puhul (näiteks 1, 5, 10, 25).

   # Näide — Coin Change (kanonilised mündid)
   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. Kraskali algoritm minimaalsete ühenduspuude leidmiseks (Minimum Spanning Tree):

   • Ülesanne: Leida alamhulk servadest, mis ühendab kõik tipud minimaalkaalulise kogumiga.
   • Hedristiline lahendus: Sorteerida kõik servad nende kaalude järgi kasvavas järjekorras. Järk-järgult lisada servad, kui need ei moodusta tsüklit juba valitud servadega, kuni ühendatakse n-1 serva (kus n on tipude arv).

Hedristilised algoritmid on lihtsad rakendada, kuid ei pruugi alati leida globaalselt optimaalset lahendust. Mõnede ülesannete puhul (näiteks müntide vahetus, seljakoti probleem üldiselt) ei ole heuristiline lähenemine optimaalne. Optimaalsuse või parema lähedusväärtuse tagamiseks võib olla vaja kasutada dünaamilist programmeerimist või muid meetodeid. Enne heuristilise algoritmi kasutamist tuleb kontrollida, kas see sobib antud ülesande jaoks.