Úloha ve stavovém prostoru

V případě jednoduché úlohy „Hanoiských věží“je možné bez problému generovat celý její stavový prostor a zobrazit jej v podobě orientovaného grafu. Řešením úlohy ve stavovém prostoru tedy rozumíme nalezení takové posloupnosti operátorů, kdy nás jejich postupná aplikace přivede z počátečního stavu do některého z cílových stavů množiny V našem případě tedy cestu ze stavu (111) do stavu (222).

Obr. 3. Stavový prostor hlavolamu „Hanojské věže“, cílový stav.

Počet aplikací operátorů nazýváme počtem kroků či lépe délkou cesty.  Nalezenou posloupnost operátorů, tedy vlastní řešení pak nazýváme nalezenou cestou z počátečního do cílového stavu. Cílových stavů i nalezených cest k jejich řešení může být více a proto se zpravidla snažíme nalézt cestu z nějakého pohledu optimální. V případě uniformního ohodnocení hran jde o nejkratší cestu z počátečního stavu do stavu cílového. V případě, že je provedení jednotlivých hran z pohledu řešení ohodnoceno rozdílně, cenou rozdílnou cenou (náročností) provedení přechodu, jde o cestu s minimální cenou. Cena aplikace jednotlivých operátorů množiny   tedy nemusí být pro všechny tyto operátory vždy shodná.

Reálnou úlohu ve stavovém prostoru tedy řešíme následně:

• Zavedeme si kódování jednotlivých stavů.
• Identifikujeme operátory a omezující podmínky pro jejich aplikaci.
• Identifikujeme cílové stavy představující řešení úlohy.
• Zvolíme počáteční stav. Zpravidla je dán vlastním zadáním úlohy.
• Zvolíme strategii procházení jednotlivých stavů, tedy strategii aplikace jednotlivých operátorů – prohledávání prostoru.
• Aplikujeme zvolenou strategii, začínáme v počátečním stavu.
• V každém kroku kontrolujeme, zda právě dosažený stav (respektive cesta k němu) není hledaným řešením.

Stavový prostor může být velmi rozsáhlý či obecně nekonečný a není tedy vždy možné v konečném čase prověřit všechny možné stavy a přechody mezi nimi, jak tomu bylo v případě předchozí úlohy. Zde tedy nastupují různé strategie pro prohledávání stavového prostoru, které se snaží tento proces optimalizovat. Tyto metody si přiblížíme v následujících odstavcích.