Pažravý algoritmus

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

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

Tento článok týkajúci sa informatiky je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš.

[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.

[1]

[2]