Pažravý algoritmus

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Pažravý algoritmus alebo hladný algoritmus (používajú sa aj poslovenčené varianty anglického názvu greedy algorithm) je algoritmus na riešenie optimalizačných úloh, ktorý v každom svojom kroku vyberá lokálne optimálne riešenie v nádeji, že je toto riešenie globálne optimálne.[1] Pažravé algoritmy nemusia vždy nájsť optimálne riešenie, ale existuje trieda problémov, pre ktoré ho vždy nájdu. Takéto triedy problémov sú charakterizované matematickou štruktúrou matroidu.[2] Príkladom pažravých algoritmov sú napríklad Kruskalov algoritmus alebo algoritmus na tvorbu Huffmanových kódov.

Zdroje[upraviť | upraviť zdroj]

  1. Cormen, T. H., Leiserson, Ch. E., Rivest, R. L., Stein, C.: Introduction to Algorithms. MIT Press, 2001.
  2. Oxley, J. G.: Matroid Theory. Oxford University Press, 1992.