Kas ir alkatīgs algoritms un kādos gadījumos tas tiek izmantots?

Žadinis algoritms — 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:

• Paprastums: Paprastai įgyvendinamas lengviau nekā dinamis programēšana vai kitos optimizācijas metodes.
• Īss laiks: Bieži vien ir zemāka skaitļošanas sarežģītība.
• Optimuma garantija: Ne vienmēr garantē, ka atradīsiet globāli optimālu risinājumu. Garantija attiecas tikai uz noteiktām uzdevumu klasēm.

Izmanto uzdevumos, kur ir pierādīts, ka katra soļa vietējais optimālais izvēle noved pie globāli optimāla risinājuma. Piemēri:

• Aktivitāšu izvēles uzdevums (Activity Selection Problem): Maksimālais aktivitāšu skaits, kas nesaskaras laikā.
• ** Mugursoma (ja var dalīt priekšmetus):** Kad priekšmetus var dalīt. Ja nē, tas ir dinamisks programmēšanas uzdevums.
• Prim un Kruskal algoritmi: Minimizējošo koku meklēšanai grafikā.
• Dijkstra algoritms: Ceļa meklēšanai grafikā ar pozitīviem svariem.
• Huffmana kodēšana: Optimizētas prefiksa koda izveidei.

Piemērs pseido-koda aktivitāšu izvēles algoritmam:

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

Svarīgi pārbaudīt, vai žadinis algoritms ir piemērots konkrētai uzdevumam, jo pretējā gadījumā tas var novest pie suboptimāla risinājuma.

# Vienkāršs piemērs uzdevumam, kur žadinis algoritms nav optimāls
# Monētu izsniegšanas uzdevums: izsniegt minimālo monētu skaitu
# Pieejamās monētas: [1, 5, 10, 25] USD
# Izsniegt: piemēram, 30 centus

# Žadinis algoritms:
# ņemam lielāko monētu <= 30 (25) -> atlikums 5
# ņemam lielāko monētu <= 5 (5) -> atlikums 0
# Rezultāts: 2 monētas (25 + 5). Šeit tas ir optimāli.

# Pieejamās monētas: [1, 6, 10]
# Izsniegt: 12 centus

# Žadinis algoritms:
# ņemam lielāko monētu <= 12 (10) -> atlikums 2
# ņemam lielāko monētu <= 2 (1) -> atlikums 1
# ņemam lielāko monētu <= 1 (1) -> atlikums 0
# Rezultāts: 3 monētas (10 + 1 + 1)
# Optimizētais risinājums: 2 monētas (6 + 6)

# Šis piemērs rāda, ka žadinis algoritms ne vienmēr noved pie globāla optimāla risinājuma,
# ja uzdevuma īpašības neatbilst tā piemērojamībai (piemēram,
# standarta nomināli valūtā bieži ļauj žadīgo algoritmu,
# bet brīvi nomināli — nē).