Metody prohledávání

V následující kapitole si přiblížíme stručně základní metody prohledávání stavového prostoru, které se vyskytují v řadě modifikací. Obecně můžeme metody pro prohledávání stavového prostoru rozdělit následně:

• neinformované,
• informované,
• lokální.

Neinformované metody aplikují jednotlivé operátory slepě, procházejí stavovým prostorem bez jakékoli aprioriní informace o výhodnosti aplikace toho kterého operátoru. Pro daný stav jsou tedy zpravidla všechny přechody (všechny aplikace operátorů) stejně pravděpodobné. Metody nijak nehodnotí, zda je aktuální stav či cesta k němu výhodná a nesnaží se odhadovat, zda je cíli bližší či vzdálenější. Nicméně jsou jednoduché a nevyžadují výpočet žádné složité ohodnocovací funkce.

Oproti tomu informované metody se snaží na základě nějaké jednodušší či složitější funkce odhadnout, zda bude daný přechod z konkrétního stavu z hlediska řešení problému výhodnější než jiný. Pokud pomineme psychologii, postupují tyto algoritmy podobně jako šachista, který se na základě zhodnocení aktuální situace snaží rozhodnout, který následující tah zvolí. Není schopen v té chvíli vyhodnotit všechny možné kombinace (prohledat všechny stavy) na více tahů dopředu, ke svému rozhodnutí tedy používá heuristiku a zvolí tah, který se mu v tu chvíli zdá jako nejvýhodnější. Hráč s lepší heuristikou pak zpravidla vítězí.

Zvláštní třídu představují metody lokální, které mají hlavní výhodu ve své relativně malé paměťové náročnosti a snadné implementaci. V zásadě se jedná o informované metody, které ale vyhodnocují v každém stavu jen výhodnost nejbližších následníků daného stavu a rezignují na zapamatování si stavů předchozích. Chovají se tedy lokálně, nevrací se v orientovaném grafu zpět, postupují stále jen kupředu až do chvíle, kdy jsou všichni následníci méně vhodní, než aktuální uzel. Největším problémem těchto metod tak představuje skutečnost, že mohou uváznout v lokálním minimu.