V této kapitole se budeme zabývat úlohami, jejichž postup řešení lze reprezentovat stavovým prostorem. Stavový prostor matematicky popíšeme jako orientovaný graf, jehož vrcholy jsou všechny možné stavy světa (v němž probíhá řešení úlohy). 

• Svět se nachází v počátečním stavu a úkolem je změnit jej do jednoho z cílových stavů. 
• Toho můžeme dosáhnout pomocí série akcí, měnících stav světa, které reprezentujeme hranami grafu. Pro každou akci provedenou v určitém stavu musíme vědět, jak změní svět - tedy do jakého stavu jej převede.
• Budeme předpokládat, že každá akce (hrana grafu) má nezápornou cenu, a že se tato cena v čase nemění.
• V některých úlohách nejsou cílové stavy předem známy, ale je dána jen podmínka, kterou musí splňovat; pak musíme vždy po dosažení nového stavu tuto podmínku otestovat.
• Zpravidla chceme, abychom cílového stavu dosáhli co nejsnáze. K tomu potřebujeme znát cenu každé cesty na grafu.
  
• Pro jednoduchost budeme zatím předpokládat, že tato cena je rovna součtu cen všech vykonaných akcí, tedy hran, z nichž se cesta skládá. 

Prohledávání stavového prostoru začíná z počátečního stavu, postupně procházíme další stavy (uzly grafu). Jednotlivé algoritmy se liší hlavně výběrem dalších uzlů v závislosti na informacích, kterými disponují. Uvědomme si, že prohledávací algoritmus "nevidí" graf jako celek, ale u každého uzlu "vidí" jen jeho sousedy, a cenu přechodu do každého z nich. Jelikož stavový prostor bývá obrovský, někdy i nekonečný, je zásadní najít (nejlevnější) cestu do cílového stavu co nejrychleji. Ukážeme si základní sadu algoritmů od nejjednodušších ke složitějším.

Jednou prozkoumané uzly si zpravidla potřebujeme zapamatovat, a také si o nich udržovat užitečné informace (například jakou cenu jsme vynaložili na dosažení uzlu). Nejčastěji to probíhá formou stromového prohledávání, využívající užitečnou datovou strukturu - prohledávací strom. Pozor, tento strom není totožný s grafem prohledávaného stavového prostoru. Společné mají jen to, že ve stromě se nacházejí informace o dosud prohledaných uzlech a hranách původního grafu. Uzel prohledávacího stromu typicky obsahuje:

• aktuální stav problému
  
• odkaz na rodičovský uzel ve stromě
  
• akci, která vedla od rodiče do aktuálního stavu
  
• cenu cesty do aktuálního stavu
  
• hloubku (vzdálenost od kořene stromu)
  

Na začátku obsahuje prohledávací strom jen kořen - uzel s počátečním stavem, v němž jsou odkaz na rodiče a poslední akce nevyplněny, cena a hloubka je nula. Jak algoritmus pokračuje, ve stromě přibývají další uzly. Množinu všech dosud neprozkoumaných  uzlů stromu nazveme OPEN (v knize Russel & Norvig [5] se tato množina nazývá frontier). Na začátku tato množina obsahuje kořen stromu. Dále bude potřebovat množinu už prozkoumaných uzlů CLOSED (autoři [5] ji nazývají explored). Krok algoritmu stromového prohledávání vypadá takto:

• pokud je množina OPEN prázdná, algoritmus končí neúspěchem
• vyber jeden uzel z množiny OPEN, odstraň jej z OPEN a přidej do CLOSED
• pokud je to cílový uzel, algoritmus končí úspěchem
• expanduj vybraný uzel:  
  
• urči jeho sousedy ve stavovém prostoru, kteří nejsou v OPEN ani CLOSED
• přidej je do množiny OPEN
  

Jednotlivé stromové prohledávací algoritmy se tedy liší hlavně výběrem uzlu z čela, který je expandován. Algoritmy můžeme rozdělit do dvou skupin:

• Neinformované (slepé) prohledávání: kromě samotného grafu stavového prostoru nemá žádnou dodatečnou informaci, která by dovolila odhadnout, který uzel z množiny OPEN je nejslibnější (mohla by přes něj vést nejkratší cesta k cíli).
  
• Informované (heuristické) prohledávání: dokáže odhadnout, které uzly je výhodné expandovat, například pomocí odhadu ceny zbývající do cíle přes zvolený uzel.
  

Neinformované metody

Neinformované metody se používají, pro svou neefektivitu, jen v případech malých stavových prostorů, anebo v úlohách, kde nemáme naprosto žádnou informaci o vnitřním uspořádání stavového prostoru a vztazích mezi stavy. 

Prohledávání do šířky

Z množiny OPEN je vždy vybrán nejstarší přidaný uzel, tato množina tedy může fungovat jako fronta FIFO. Výsledkem je, že strom je prohledáván po jednotlivých úrovních počínaje kořenem. Situaci ilustruje obr. 1

Obr. 1. Prohledávání do šířky - pořadí procházení uzlů F, B, G, A, D, I, C, E, H. By Rory O'Kane - edited public domain file http://commons.wikimedia.org/wiki/File:Sorted_binary_tree_inorder.svg.

Prohledávání se stejnoměrnou cenou

Pokud mají všechny akce ve stavovém prostoru stejnou cenu, najde prohledávání do šířky vždy optimální (nejlevnější) cestu do cílového stavu. Pokud to tak ale není, lze algoritmus vylepšit tak, že vždy expanduje stav z množiny OPEN, do kterého vede z kořene cesta s nejnižší cenou. Množina OPEN pak může fungovat jako prioritní fronta. Algoritmus vyžaduje ještě drobné úpravy, pro podrobnosti odkazujeme na [5], kap. 3.4.2. Někteří autoři řadí tento algoritmus do skupiny informovaných algoritmů, přestože vlastně žádná heuristická informace není použita.

Z množiny OPEN je vždy vybrán naposledy přidaný uzel, tato množina tedy může fungovat jako fronta LIFO (= zásobník). Výsledkem je, že ve stromě vždy prohledáváme jednu větev do hloubky, a teprve až narazíme na list, vracíme se rekurzívně zpátky a prohledáváme další větve. Situaci ilustruje obr. 2.

Obr. 2. Prohledávání do hloubky - pořadí procházení uzlů F, B, A, D, C, E, G, I, H. By Sorted_binary_tree.svg: Milesderivative work: Pluke (talk) - Sorted_binary_tree.svg, Public Domain, https://commons.wikimedia.org/w/index.php?curid=10616003

Prohledávání do hloubky s omezením na hloubku

Pokud je stavový prostor nekonečně veliký, nemusí prohledávání do hloubky nikdy najít cílový stav, i kdyby se nacházel poblíž počátečního. Proto se do algoritmu někdy zařazuje omezení na hloubku uzlu - jakmile je dosažena určitá vzdálenost d od kořene, uzel se už dále neexpanduje a algoritmus se vrací ve stromě zpět. Je to vlastně jako bychom omezili prohledávání stavového prostoru jen na uzly, které mají od kořene hloubku nejvýše d. S uzly s hloubkou d algoritmus zachází, jakoby neměly žádné sousedy. Pokud se cílový stav nachází dále, algoritmus selže. Proto se tento algoritmus dále vylepšuje iterativním zvětšováním hloubky - pokud není cíl nalezen, zvětšíme přípustnou hloubku a celý algoritmus se opakuje.

Informované metody

Kdykoli je to možné, dáváme přednost informovaným metodám, které urychlují prohledávání stavového prostoru na základě dodatečných informací o tom, jak vybírat perspektivní stavy pro expandování - tj. přes které nejspíše povede nejkratší cesta z počátečního do koncového stavu. Takové informace závisí na konkrétní úloze, a často jsou jen přibližné nebo odhadované. Například u hry Lišák [4] můžeme vzít jako nejperspektivnější stav, který má co nejméně kamenů ve špatné pozici. U problému hledání nejkratší cesty [5], pokud jsou k dispozici zeměpisné souřadnice jednotlivých měst, můžeme brát jako nejlepší stav s minimální vzdáleností vzdušnou čarou od cíle. 

Uspořádané prohledávání (best-first search):

Metoda je založena na použití hodnotící funkce f(n), která určuje "perspektivnost" stavu n v množině OPEN pro jeho expandování. Metoda vybírá stav s nejmenší hodnotou f(n); pokud je takových stavů více, je vybrán libovolný z nich.

Hodnotící funkce má zpravidla tvar f(n) = g(n) + h(n), kde

g(n) je cena optimální cesty z počátečního stavu do stavu n,

h(n) je odhadovaná cena cesty ze stavu n do některého z cílových stavů.

Pokud budeme ignorovat složku g(n) (položíme g(n) = 0), dostaneme algoritmus tzv. hladového uspořádaného prohledávání (greedy best-first search) , který nezaručuje nalezení optimální cesty, viz [5] kap. 3.5.1. Pokud naopak položíme h(n) = 0, dostaneme algoritmus prohledávání se stejnoměrnou cenou popsaný výše. Pokud bychom položili g(n) = h(n) = 0, výsledkem je náhodné prohledávání stavového prostoru.

Algoritmus A*

Ve většině případů neznáme cenu optimální cesty ze stavu n do cíle, takže hodnota h(n) je jen heuristickým odhadem. Pro efektivitu prohledávání je důležité, aby tento odhad měl určité vlastnosti. Základní je tato: funkce h(n) se nazývá přípustná heuristická funkce, pokud platí 0 ≤ h(n) ≤ h*(n), kde h*(n) je optimální (nejmenší) cena cesty ze stavu n do cíle. Přípustná heuristika je tedy optimistická - odhad ceny do cíle nesmí převýšit skutečnou cenu. Všimněte si, že oba odhady ceny zmíněné v úvodu do informovaných metod tuto podmínku splňují. Platí totiž následující tvrzení:

Algoritmus uspořádaného prohledávání s funkcí f(n) = g(n) + h(n), kde h(n) je  přípustná heuristická funkce, najde vždy optimální (nejlevnější) cestu do cílového stavu, pokud existuje.

Pozn. výše uvedené značení h(n) a h*(n) je použito v monografii Russel & Norvig, v prezentacích a na těchto stránkách e-learningu. Bohužel česká monografie Mařík a kol. používá značení přesně opačné, tedy heuristický odhad ceny je značen h*(n) a skutečná optimální cena jako h(n).

Pokud funkce h(n) splňuje navíc silnější podmínku tzv. monotonicity (viz [4] str. 49), pak je možné algoritmus uspořádaného prohledávání zjednodušit a urychlit. Totéž platí pro algoritmus uspořádaného prohledávání v [5] na str. 84, který je optimální i pro přípustné heuristiky. 

Heuristické prohledávání s omezenou pamětí

Hlavní nevýhodou algoritmu A* je jeho vysoká spotřeba paměti, protože si udržuje informace o všech dosud ohodnocených uzlech. To je často je příčinou nenalezení řešení, když algoritmus vyčerpá veškerou dostupnou paměť. Existuje řada variant prohledávání s heuristickou funkcí h(n) , které se snaží spotřebu paměti omezit. Stručně zmíníme dva z nich.

Algoritmus IDA* (iterative deepening A*) vychází z iterativního prohledávání do hloubky popsaného výše. Jediný rozdíl je v tom, že namísto omezení na hloubku uzlu v prohledávacím stromu používá omezení na hodnotu funkce f(n) prohledávaného uzlu. 

Algoritmus SMA* (simplified memory-bounded A*, [5] kap. 3.5.3) se snaží, zjednodušeně řečeno, omezit spotřebu paměti tím, že pokud se zaplní dostupná paměť a nelze už expandovat další uzly, tak odstraní informace o uzlu s nejhorší hodnotou f(n). Navíc ještě uchovává v rodiči tohoto zapomenutého uzlu informace o jeho ceně, která může být později použita.

Systémy GPS, STRIPS a PLANNER 

Softwarové systémy umělé inteligence GPS (General Problem Solver, 1959), STRIPS (Stanford Research Institute Problem Solver, 1971) a PLANNER (vyvinut na MIT, 1971) představovaly první implementace prohledávání stavového prostoru a plánování akcí v něm. Přestože nedosáhly komerčního významu, umožnily pochopit řadu obtíží automatického řešení problémů ve stavovém prostoru, které byly později využity v komerčních řešeních. Pro podrobnosti odkazujeme na  [4] díl (1) kap. 2.3.