III. Prohledávací prostor
Prohledávací prostor
Když řešíme nějaký problém, obvykle hledáme řešení, které je nejlepší ze všech možných kandidátů. Množina všech přípustných řešení (tedy množina objektů, mezi kterými se hledané řešení nachází) se nazývá prohledávací prostor (také stavový prostor). Každý bod v prohledávacím prostoru představuje jedno přípustné řešení. Každé přípustné řešení lze "označit" jeho hodnotou nebo kvalitou pro daný problém. Naším cílem je najít řešení, které odpovídá jednomu nebo více bodům v prohledávacím prostoru.
Hledání řešení tedy odpovídá hledání nějakého extrému (minima nebo maxima) v prohledávacím prostoru. Celý prohledávací prostor může být znám už v okamžiku, kdy problém řešíme, ale častěji známe jen několik bodů a další postupně generujeme během hledání.
Příklad prohledávacího prostoru
Problém je v tom, že takové hledání může být velmi složité. Často není jasné, kde začít ani kde řešení hledat. Existuje mnoho metod pro nalezení vhodného řešení (tedy ne nutně nejlepšího řešení), např. horolezecký algoritmus, tabu search, simulované žíhání a genetický algoritmus. Řešení nalezené těmito metodami se často považuje za dobré, protože bývá nemožné dokázat, které řešení je skutečně optimální.
NP-hard problémy
Příklady obtížných problémů, které nelze řešit "tradičním" způsobem, jsou NP problémy.
Existuje mnoho úloh, pro které známe rychlé (polynomiální) algoritmy. Jsou ale i takové problémy, které nelze algoritmicky řešit v polynomiálním čase. U některých problémů bylo dokonce dokázáno, že žádné řešení v polynomiálním čase neexistuje.
Existuje však i mnoho důležitých úloh, pro které je velmi těžké najít řešení, ale jakmile ho máme, lze ho snadno ověřit. Tato vlastnost vedla ke třídě NP-úplných problémů. NP znamená nondeterministický polynomiální, což znamená, že je možné řešení "uhádnout" (pomocí nějakého nondeterministického algoritmu) a pak ho ověřit, obojí v polynomiálním čase. Kdybychom měli stroj, který umí hádat, byli bychom schopni najít řešení v rozumném čase.
Pro zjednodušení se studium NP-úplných problémů obvykle omezuje na problémy, u nichž může být odpověď jen ano nebo ne. Protože ale existují i úlohy se složitějším výstupem, byla zavedena třída NP-hard problémů. Tato třída je širší než třída NP-úplných problémů.
NP problémy jsou často charakteristické tím, že na první pohled je zřejmý jednoduchý algoritmus pro nalezení řešení: prostě vyzkoušet všechna možná řešení. Takový algoritmus je však velmi pomalý (často O(2^n)) a i pro trochu větší instance problému se stává zcela nepraktickým.
Dnes nikdo neví, zda existuje nějaký rychlejší přesný algoritmus. Dokázat nebo vyvrátit to zůstává velkou výzvou pro výzkumníky. Mnoho lidí si dnes myslí, že takový algoritmus neexistuje, a proto hledají alternativní metody, např. genetické algoritmy.
Mezi NP problémy patří např. problém splnitelnosti, problém obchodního cestujícího a problém batohu. K dispozici je přehled NP problémů.