Prohledávání stavového prostoru je základem mnoha technik umělé inteligence, využívá se například pro řešení logických úloh, výběr optimálního tahu, hledání nejkratší cesty nebo plánování akcí robota.

Stavový prostor úlohy se skládá ze stavů (možné konfigurace úlohy) a akcí (přechody mezi stavy). Jeden ze stavů je počáteční a alespoň jeden stav je cílový. Přechody mohou mít přidruženou cenu.

Plán je libovolná posloupnost akcí. Řešení úlohy je takový plán, který nás dostane z počátečního stavu do cílového. Optimální řešení je řešení, které má nejnižší cenu. (Cena plánu je nejčastěji součet cen jednotlivých přechodů.)

Zkoušení všech možností

Nejjednodušším algoritmem, který najde řešení vždy (pokud existuje) je generuj a testuj. Tento algoritmus generuje všechny možné plány a testuje, zda jde o řešení úlohy. Jde tedy o využití hrubé síly, techniky návrhu algoritmů založené na zkoušení všech možností. Zásadní nevýhodou hrubé síly je její časová náročnost. Počet plánů roste exponenciálně vzhledem k délce plánu.

Stromové prohledávání

Mnohé plány však nemusí být vůbec proveditelné, nebo se opakovaně vracejí do stejného stavu. Je proto výhodnější testovat plány průběžně po každé akci – jakmile se dostaneme do slepé uličky nebo dříve prozkoumaného stavu, nemusíme žádné další plány začínající touto posloupností akcí prozkoumávat.

Stromové prohledávání je obecný název pro takový způsob prohledávání, kdy postupně konstruujeme a vyhodnocujeme plány po každé akci. Postup prohledávání plánů lze popsat prohledávacím stromem, ve kterém vrcholy reprezentují plány (a současně stav, do kterého se vykonáním plánu dostaneme) a orientované hrany reprezentují akce, které rozšiřují předchozí plán o jeden krok. Prohledávací strom zachycuje stavový prostor tak, jak ho postupně objevuje prohledávací algoritmus. Existuje několik variant stromového prohledávání, které se liší v tom, který plán rozšiřují (tj. který z objevených stavů prozkoumávají jako další):

Prohledávání do hloubky (DFS, angl. Depth First Search) vybírá poslední objevený stav. DFS má dobrou paměťovou složitost, protože si pamatuje pouze plány na aktuální větvi prohledávacího stromu.

V této ukázce předpokládáme, že DFS zkouší akce po směru hodinových ručiček (doprava–dolů–doleva–nahoru). Čísla u stavů popisují pořadí objevení. Cíl byl nalezen v 7. kroce a nalezený plán má 4 kroky (doprava–dolů–dolů–doleva).

Prohledávání do šířky (BFS, angl. Breadth First Search) prohledává stavy po vrstvách podle počtu akcí od počátečního stavu. To sice zvyšuje paměťovou složitost (je potřeba si pamatovat více stavů), ale vede k nalezení nejkratšího řešení.

Čísla u stavů v ukázce BFS zachycují vzdálenosti od počátečního stavu, což odpovídá pořadí procházení „po vrstvách“. BFS našlo optimální řešení (dolů–dolů) po prozkoumání 6 stavů.

Prohledávání podle ceny (UCS, angl. Uniform Cost Search) je variací BFS, které umožňuje nalézt nejlevnější řešení, i když mají akce různou cenu. K rozšíření vybíráme plán s nejnižší cenou.

Pro ukázku UCS jsme přidali do plánku dvě hnědé bažiny s třikrát vyšší cenou přechodů. Čísla ve čtverečcích zde zachycují cenu plánu. V tomto případě je nejlevnější řešení (s cenou 4) doprava–dolů–dolů–doleva a UCS ho nalezne. (BFS by vrátilo řešení dolů–dolů s cenou 6.)

Informované prohledávání

Prohledávání lze urychlit pomocí heuristik poskytujících odhad vzdálenosti do cíle. Taková informace je závislá na konkrétní úloze. Prohledávání využívající heuristiky označujeme jako informované prohledávání. (Algoritmy v předchozích sekcích označujeme naopak jako „neinformované“.)

Hladové prohledávání se řídí pouze hodnotou heuristiky a vybírá vždy akci, která nás dostane nejblíže cíli. Pokud hrozí slepé uličky, je potřeba hladový přístup zkombinovat se stromovým prohledáváním (jde tedy o tzv. hladové stromové prohledávání) – jako další stav vybíráme ten s nejnižším odhadem ceny podle heuristiky. Hladové prohledávání je velmi rychlé, negarantuje však nalezení optimálního řešení.

V této ukázce stromového hladového prohledávání odpovídají čísla u stavů heuristickému odhadu ceny do cíle. Heuristikou je vzdálenost od cíle spočítaná jako součet odchylek sloupce a řádku. Algoritmus našel cestu do cíle během dvou kroků, nikoliv však cestu nejlevnější.

A* prohledávání („A star“) kombinuje prohledávání podle ceny (UCS) s heuristikou. Jde o stromové prohledávání, kdy jako další stav vybíráme takový, který má nejnižší součet dosavadní ceny a heuristického odhadu zbývající ceny do cíle. Pokud je heuristika optimistická (poskytuje dolní odhad skutečné ceny), pak A* nelezne optimální řešení a nalezne ho tím rychleji, čím těsnější odhady skutečné ceny heuristika poskytuje.

Součet u stavů popisuje prioritu pro A*: [dosavadní cena] + [odhad zbývající ceny]. A* našlo optimální řešení a prozkoumalo přitom méně stavů než UCS (6 místo 8).