Kas yra godus algoritmas ir kaip jis taikomas problemų sprendimui?

Hedristinis požiūris, kuris kiekviename žingsnyje priima vietinį optimalų sprendimą, tikėdamasis, kad tai veda prie globaliai optimalios sprendimo.

Pritaikymas:

1. Veiklos pasirinkimo problema (Activity Selection Problem):

   • Užduotis: Pasirinkti didžiausią kiekį nesikertančių laiko intervalų iš duoto rinkinio.
   • Hedristinis sprendimas: Surūšiuoti intervalus pagal pabaigos laiką didėjimo tvarka. Kiekviename žingsnyje pasirinkti tą intervalą, kurio pabaigos laikas yra mažiausias ir kuris nesikerta su jau pasirinktais.

   # Pavyzdys — Veiklos pasirinkimas
   # 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]) # Surūšiuoti pagal pabaigos laiką
   
   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. Monetų keitimo problema (Coin Change Problem) — kanoniškių monetų rinkinių atveju:

   • Užduotis: Išduoti nurodytą sumą minimaliu monetų skaičiumi.
   • Hedristinis sprendimas: Naudoti maksimalų galimą didžiausių nominalų monetų kiekį, kol suma bus išduota. Veikia tik tam tikruose rinkiniuose (pavyzdžiui, 1, 5, 10, 25).

   # Pavyzdys — Coin Change (kanoniškių monetų)
   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. Krascal algoritmas minimaliam apjungimui (Minimum Spanning Tree):

   • Užduotis: Rasti kraštų pogrupį, kuris sujungia visus viršūnes su minimaliu bendru svoriu.
   • Hedristinis sprendimas: Surūšiuoti visas kraštas pagal svorį didėjimo tvarka. Laipsniškai pridėti kraštus, jei jie nesudaro ciklo su jau pasirinktais, kol bus sujungta n-1 kraštų (kur n — viršūnių skaičius).

Hedristiniai algoritmai yra paprasti įgyvendinti, tačiau ne visada randa globaliai optimalų sprendimą. Kai kurioms užduotims (pavyzdžiui, monetų keitimo, kuprinės problemos) hedristinis požiūris nėra optimalus. Norint garantuoti optimalumą ar geresnį artėjimą, gali prireikti dinaminio programavimo ar kitų metodų. Prieš taikant hedristinį algoritmą, būtina įsitikinti, kad jis tinkamas šiai užduočiai.