Úvod

Tato kapitola se zabývá množinou algoritmů umělé inteligence, které shrnujeme pod společné pojmenování algoritmy pro prohledávání stavového prostoru. Nejprve je třeba objasnit, která třída úloh je za pomoci těchto algoritmů obvykle řešena. Jedná se zpravidla o řešení problémů, kde na základě dostupných informací nejsme schopni dané řešení nalézt přímým výpočtem, nebo je realizace výpočtu pro nalezení řešení neúměrně obtížná. Ovšem musíme být schopni popsat okamžitý stav řešení úlohy.

Příkladem může být nalezení nejkratší cesty mezi dvěma městy, výhra v šachové partii, nebo vyřešení hlavolamů „Hanojské věže“ či „Loydova patnáctka“.  Neexistence snadného řešení realizovaného přímým výpočtem ještě neznamená, že nejsme schopni definovat řídící strategii, která dané řešení nalezne.  Například v případě hlavolamu „Loydova patnáctka“ se snažíme z počátečního nastavení 15 kamenů v mřížce 4x4 seřadit tyto očíslované kameny podle velikosti a dosáhnout tak řešení hlavolamu.  Naše strategie může být i taková, že se budeme pokoušet náhodně realizovat metodou pokus omyl tahy, které jsou v danou chvíli přípustné. Postupně tak z počáteční konfigurace dovolenými tahy generujeme konfigurace další a vždy hodnotíme, zda je daná konfigurace řešením (kameny jsou seřazeny) či nikoli. Zvolili jsme tedy řídící strategii, která vždy náhodně zvolí jeden z možných tahů a přesune kámen. Takový postup je sice možný, ale není příliš efektivní. Algoritmy pro prohledávání stavového prostoru se snaží tyto prohledávací strategie optimalizovat.