Prohledávání stavového prostoru je skupinou metod řešení úloh, spadající do oblasti umělé inteligence. Jeho princip spočívá ve vhodném procházení stavů řešené domény za účelem nalezení požadovaného stavu.
Sp
= (S, Φ) je dvojce tvořená
1. množinou stavů S = {s}
2. množinou operátorů (přechodů mezi stavy) Φ = {φ}
sk
= φki(si)
(sk
se nazývá následník, si
se nazývá předchůdce)
Metody prohledávání lze dělit do tří základních skupin:
1. slepé - úplné prohledávání nevyužívající žádné dodatečné informace – zde postupně aplikujeme všechny použitelné operátory
2. heuristické - úplné nebo částečné prohledávání využívající hodnocení zvolené cesty – zde operátory vybíráme na základě nějakého kritéria
3. náhodné – zde volíme operátory náhodně.
Systematické (nenáhodné) strategie (resp.algoritmy) jsou založeny na expanzi (rozvinutí) daného stavu (uzlu). Rozvinutím uzlu se myslí aplikace všech použitelných operátorů; získáme tak všechny následníky daného uzlu. Algoritmy obvykle využívají dva seznamy: seznam rozvinutých uzlů ROZVIN a seznam nerozvinutých uzlů NEROZVIN.
Při prohledávání do šířky jsou následníci vybíráni pro expanzi ze seznamu typu fronta. Postupně procházíme strom řešení po vrstvách a prohledáme všechny uzly, které mají menší hloubku, než je hloubka koncového stavu. Každý uzel přitom navštívíme nejvýše jednou. Při tomto způsobu prohledávání máme jistotu, že vždy nalezneme optimální řešení (koncový stav s nejmenší hloubkou).
Při prohledávání do hloubky jsou následníci vybíráni pro expanzi ze seznamu typu zásobník. Na rozdíl od prohledávání do šířky můžeme některými uzly procházet vícekrát, neboť se často musíme navracet (tzv. backtracking). Při tomto způsobu prohledávání nemusíme nalézt optimální řešení (koncový stav s nejmenší hloubkou) a dokonce žádné řešení (pokud má stavový prostor nekonečnou větev, do které „zabloudíme“). Pro úlohy s konečným stavovým prostorem a s jedním koncovým stavem ale nalezneme stejné řešení jako při prohledávání do šířky.
Heuristické prohledávání je založeno na kritériu (heuristice), které umožňuje posoudit vhodnost použití jednotlivých operátorů aplikovatelných na daný stav. Vhodnost operátoru můžeme intuitivně chápat jako to, do jaké míry nás použití operátoru přiblíží ke koncovému stavu (řešení úlohy).
Heuristická funkce je funkce, která každému stavu s přiřadí číslo, vyjadřující jeho kvalitu z hlediska řešení úlohy.
Vhodnost operátoru (a tedy kvalita příslušného následníka) může být v dané úloze definována různě. Různé podoby kritéria samozřejmě ovlivní volbu operátorů a tím i dobu (počet kroků) potřebných k nalezení řešení.
Heuristické prohledávání do hloubky, kde heuristikou je odhad vzdálenosti ke koncovému stavu. Následníky rozvinutého uzlu nejprve uspořádáme dle heuristiky a pak zařadíme do zásobníku.
Lokální varianta tohoto algoritmu je založena na tom, že pro daný stav volíme dle heuristiky nejlepšího následníka a pracujeme pouze s ním. Seznam NEROZVIN je tedy jednoprvkový. Tato varianta tedy hledá „pouze“ lepší uzel, než je ten současný. To může způsobit řadu problémů:
• uváznutí v lokálním extrému (žádný následník není lepší než rozvíjený uzel, který ale nepředstavuje řešení problému),
• problém plošiny (rozvíjený uzel i jeho následníci jsou stejně kvalitní – není tedy jasné kterým směrem postupovat).