Neinformované prohledávání

Jak již bylo řečeno, společným rysem neinformovaných metod je, že při pořadí procházení jednotlivých stavů nepoužívají žádnou ohodnocovací heuristickou funkci, která by odhadovala výhodnost následníků daného stavu a vybírala toho nejnadějnějšího z nich. Algoritmy postupně prohledávají vyhledávací strom jen v závislosti na jeho topologii, označujeme je také jako slepé metody prohledávání stavového prostoru.

Obr. 5. Prohledávací strom - příklad.

Jednotlivé algoritmy se liší pořadím, ve kterém jsou stavy generovány a tedy i procházeny. Generování cesty můžeme vyjádřit pomocí dohodnutého pravidla zápisu generování cesty, kdy začínáme z počátečního uzlu 1 zapsaného jako a postupně generujeme uzly další, které jsou výsledkem provedení operátoru   na zvolený stav, například aplikací všech přípustných operátorů přechodu na první stav dostáváme zápis Poté je operátor přechodu aplikován na další stav z vygenerované množiny, například Získáme tak vygenerovanou posloupnost stavů včetně cesty, které do nich vedly. Je třeba si uvědomit, že mezi pojmy uzel a stavje jistý rozdíl. Zatímco pojmem stav rozumíme skutečně jen stav úlohy jako takový, uzly vyhledávacího stromu zahrnují mimo stavu samotného i další informace. Jedná se zpravidla o informaci o cestě k uzlu (odkaz na rodiče), aplikované operátory přechodu, hloubku uzlu ve vyhledávacím stromě. V případě informovaného prohledávání pak i ohodnocení uzlu heuristickou funkcí.

Obvyklé bývá u neinformovaných metod zavedení dvou množin stavů, množiny OPEN, která obsahuje dosud neprověřené, nově generované stavy a množiny CLOSE, která naopak obsahuje stavy již prověřené, expandované.  Stavy obsažené v množině CLOSE již nejsou při expanzi uzlu znova zařazovány do množiny OPEN a jsou tedy prověřeny jen 1x.

V následující části se seznámíme s některými neinformovanými metodami prohledávání stavového prostoru a uvedeme jejich obvyklé české i anglického pojmenování.