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
upraviť- ↑ 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š. |