Mi az a greedy algoritmus, és hogyan alkalmazzák problémák megoldására?

A greedy algoritmus egy heurisztikus megközelítés, amely minden lépésben helyben optimális döntést hoz, abban a reményben, hogy ez globálisan optimális megoldáshoz vezet.

Alkalmazások:

1. Tevékenységválasztási probléma:

   • Probléma: Válassza ki a megadott halmazból a lehető legtöbb nem átfedő időintervallumot.
   • Greedy megoldás: Rendezze az intervallumokat növekvő végidő szerint. Minden lépésben válassza ki a legkisebb végidővel rendelkező intervallumot, amely nem átfedő a már kiválasztottakkal.

   # Példa tevékenységválasztásra
   # 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]) # Rendezés végidő szerint
   
   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. Pénzváltási probléma (Coin Change Problem) kanonikus érme készletekhez:

   • Probléma: Adja ki a megadott összeget a lehető legkevesebb érme felhasználásával.
   • Greedy megoldás: Használja a lehető legtöbb a legnagyobb névértékű érméből, amíg az összeg ki nem fizetett. Csak bizonyos érme készleteknél működik (pl. 1, 5, 10, 25).

   # Példa érmeváltásra (kanonikus érme készletekhez)
   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 algoritmus a minimális feszítőfa megtalálásához:

   • Probléma: Egy összefüggő, súlyozott, irányítatlan gráf olyan részhalmazát találja meg, amely összeköti az összes csúcsot minimális összsúly mellett.
   • Greedy megoldás: Rendezze az összes élt súly szerint növekvő sorrendbe. Adja hozzá az éleket sorrendben, ha nem alkotnak ciklust a már kiválasztott élekkel, amíg n-1 él nem lesz hozzáadva (ahol n a csúcsok száma).

A greedy algoritmusok könnyen megvalósíthatók, de nem mindig találják meg a globálisan optimális megoldást általános problémákra. Néhány problémánál (pl. pénzváltás arbitrary készletekkel, általános hátizsák probléma) a greedy megközelítés nem optimális. Az optimalitás vagy jobb közelítés garantálásához dinamikus programozás vagy más módszerek lehetnek szükségesek. Mielőtt alkalmazná a greedy algoritmust, győződjön meg arról, hogy az alkalmas az adott problémára.