Hladový algoritmus v NP úplných problémech

Abstract

V optimalizačních problémech je hodně úloh, které jsou NP-úplné. To znamená, že nelze nalézt algoritmus jiné než exponenciální složitosti, který problém řeší. Příkladem může být například úloha plnění batohu, problém barvení grafu, či problém obchodního cestujícího. Hladový algoritmus je heuristika, která spočívá v lokálně optimální volbě v každé fázi. V mnoho situacích tato strategie nepřináší optimální řešení. Může ale přinést řešení, které se v rozumném čase blíží optimálnímu. Cílem práce je aplikování hladového algoritmu na různé NP úplné problémy, jeho modifikace a studium jeho chování.