Hladový algoritmus v NP úplných problémech - Pokorný, Ondřej (Univerzita Pardubice, 2025)
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í.
Greedy algorithm in NP complete problems
Keywords: graf; časová složitost; NP-úplný problém; hladový algoritmus; barvení grafu; chromatické číslo; problém batohu; problém obchodního cestujícího; graph; time complexity; NP-complete problem; greedy algorithm; graph coloring; chromatic number; knapsack problem; travelling salesman problem