Mi az a greedy algoritmus és milyen esetekben alkalmazzák?

A greedy algoritmus egy megközelítés az optimalizációs problémák megoldására, amely minden lépésben a legjobb helyi megoldást választja (a jelenlegi pillanat szempontjából legelőnyösebb lehetőséget), abban a reményben, hogy ez a helyi optimális megoldások sorozata globálisan optimális megoldáshoz vezet. Nem veszi figyelembe a jelenlegi választás esetleges következményeit a jövőbeli lépésekre.

Jellemzők:

• Egyszerűség: Általában könnyebb megvalósítani, mint a dinamikus programozás vagy más optimalizációs módszerek.
• Gyorsaság: Gyakran alacsonyabb számítási összetettséggel rendelkezik.
• Optimális garancia: Nem garantálja mindig a globálisan optimális megoldás megtalálását. Csak bizonyos problémacsoportokra vonatkozik garancia.

Olyan problémákban alkalmazzák, ahol bebizonyosodott, hogy minden lépésben a helyben optimális választás vezet a globálisan optimális megoldáshoz. Példák:

• Aktivítás kiválasztási probléma: A lehető legtöbb, időben nem átfedő aktivitás kiválasztása.
• Hátizsák probléma (tételek frakcionálásával): Amikor a tételek oszthatók. Ellenkező esetben dinamikus programozási problémáról van szó.
• Prim és Kruskal algoritmusai: A minimális feszítőfa keresése gráfban.
• Dijkstra algoritmusa: A legrövidebb út megtalálása nem-negatív élsúlyokkal rendelkező gráfban.
• Huffman-kódolás: Az optimális prefixkód felépítése.

Példa pseudokód az aktivitás kiválasztási algoritmushoz:

Függvény VálasszaAktivitásokat(aktivitások):
  Rendezze az aktivitásokat a befejezési idő szerint
  kiválasztott_aktivitások = üres lista
  utolsó_befejezési_idő = 0

  Minden aktivitás esetén:
    Ha az aktivitás.kezdési_idő >= utolsó_befejezési_idő:
      Adja hozzá az aktivitást a kiválasztott_aktivitásokhoz
      utolsó_befejezési_idő = aktivitás.befejezési_idő

  Visszaadja a kiválasztott_aktivitásokat

Fontos ellenőrizni, hogy a greedy algoritmus alkalmazható-e egy adott problémára, mert különben aluloptimalizált megoldást adhat.