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.Cormen, T. H., Leiserson, Ch. E., Rivest, R. L., Stein, C.: Introduction to Algorithms. MIT Press, 2001. 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.Oxley, J. G.: Matroid Theory. Oxford University Press, 1992. Príkladom pažravých algoritmov sú napríklad Kruskalov algoritmus alebo algoritmus na tvorbu Huffmanových kódov.

 Zdroje 

Kategória:Algoritmy