Kas yra godus algoritmas ir kokiais atvejais jis taikomas?

Žadinis algoritmas — tai požiūris į optimizavimo užduočių sprendimą, kuris kiekvienu žingsniu pasirenka geriausią vietinį sprendimą (pelningiausią pagal dabartinį momentą variantą) tikėdamasis, kad ši optimalių vietinių sprendimų seka veda prie globaliai optimalaus sprendimo. Jis neatsižvelgia į galimus dabartinio pasirinkimo padarinius būsimuose žingsniuose.

Savybės:

• Paprastumas: Paprastai įgyvendinamas lengviau nei dinaminis programavimas ar kitos optimizavimo metodikos.
• Greitis: Dažnai turi mažesnę skaičiavimo sudėtingumą.
• Optimumo garantija: Ne visada garantuoja, kad rasite globaliai optimalų sprendimą. Garantija taikoma tik tam tikroms užduočių klasėms.

Naudojamas užduotyse, kur įrodyta, kad kiekvieno žingsnio vietinis optimalus pasirinkimas veda prie globaliai optimalios sprendimo. Pavyzdžiai:

• Veiklos pasirinkimo užduotis (Activity Selection Problem): Maksimalus veiklų skaičius, kurios nesikerta laike.
• ** Kuprinė (kai galima dalyti daiktus):** Kai daiktus galima dalyti. Jei ne, tai dinaminio programavimo užduotis.
• Prim ir Kruskal algoritmai: Minimalių apibrėžtinių medžių paieškai grafe.
• Dijkstro algoritmas: Kelio paieškai grafe su ne neigiamais svoriais.
• Huffmano kodavimas: Optimalios prefiksinės kodavimo schemos kūrimui.

Pavyzdinis pseudokodo pavyzdys veiklos pasirinkimo algoritmui:

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

Svarbu patikrinti, ar žadinis algoritmas tinkamas konkrečiai užduočiai, nes priešingu atveju jis gali duoti suboptimalius sprendimus.

# Paprastas pavyzdys užduoties, kur žadinis algoritmas nėra optimalus
# Monetų išdavimo užduotis: išduoti mažiausią monetų skaičių
# Prieinamos monetos: [1, 5, 10, 25] USD
# Išduoti: pavyzdžiui, 30 centų

# Žadinis algoritmas:
# Imame didžiausią monetą <= 30 (25) -> likutis 5
# Imame didžiausią monetą <= 5 (5) -> likutis 0
# Rezultatas: 2 monetos (25 + 5). Čia tai optimalu.

# Prieinamos monetos: [1, 6, 10]
# Išduoti: 12 centų

# Žadinis algoritmas:
# Imame didžiausią monetą <= 12 (10) -> likutis 2
# Imame didžiausią monetą <= 2 (1) -> likutis 1
# Imame didžiausią monetą <= 1 (1) -> likutis 0
# Rezultatas: 3 monetos (10 + 1 + 1).
# Optimumas: 2 monetos (6 + 6).

# Šis pavyzdys rodo, kad žadinis algoritmas ne visada pasiekia globalų optimalų,
# jei užduoties savybės neatitinka jo taikymo galimybių (pavyzdžiui,
# standartiniai nominalai dažnai leidžia žadiniam algoritmui,
# bet atsitiktiniai nominalai — ne).