Prohledávání stavového prostoru

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.

Úvod

Jedním ze základních úkolů umělé inteligence jsou metody pro strojové řešení úloh. Přes vysoký výpočetní výkon, kterým dnešní počítače oplývají, je pro naprostou většinu problémů zcela nemyslitelné, aby stroj hledal řešení postupným testováním všech možností. Vznikla potřeba hledání nějak efektivně řídit. Pokud si řešenou doménu rozdělíme do různých stavů a definujeme, že jeden z těchto stavů je počáteční, některé stavy jsou cílové a mezi různými stavy je možné aplikováním určitých akcí (operátorů) přecházet, vznikne nám tak stavový prostor. Když si jej představíme jako orientovaný graf, jehož uzly jsou stavy a přechody udávají akci, jejímž vykonáním se dostaneme z jednoho stavu do druhého, spočívá pak nalezení řešení v nalezení cesty v grafu mezi počátečním a cílovým uzlem (viz Grafové algoritmy).

Otázkou však je, jakým způsobem tuto cestu hledat. Stavový prostor totiž může být pro řadu úloh příliš rozsáhlý, v některých případech dokonce nekonečný. Cílové stavy budou tedy od počátečního vzdáleny natolik, že počítač ani nemusí být schopen k žádnému z nich jednoduchými metodami v rozumném čase a s omezenou operační pamětí cestu najít. Navíc uvažme, že cílové stavy často nejsou známy – k dispozici je třeba jen představa o tom, jak by měly takové stavy vypadat.

Z těchto důvodů vznikly v uplynulých desítkách let různé metody (algoritmy) prohledávání stavového prostoru s různými výhodami a nevýhodami. Nelze říci, že některá z metod je jednoznačně lepší než jiná. Záleží vždy na povaze řešené úlohy, požadavcích na řešení a dostupných prostředcích.

Metody

Způsob hodnocení metod

Existují v podstatě tři základní vlastnosti, podle kterých lze metody hodnotit:

• Časová složitost – minimální/maximální/průměrný čas potřebný k vyřešení úlohy danou metodou. Čas jakožto absolutní veličina je závislý na výpočetním výkonu, proto se v praxi reprezentuje např. jako počet prozkoumaných stavů, což je objektivnější.

• Prostorová složitost - minimální/maximální/průměrné množství operační paměti potřebné k řešení úlohy. V zájmu nezávislosti na platformě se místo údaje o počtu megabytů používá např. počet stavů současně uchovaných v paměti.

• Kvalita získaných výsledků - zahrnuje výpověď o tom, zda je daná metoda úplná (nalezne řešení vždy, když existuje), optimální (nalezené řešení je nejlepší ze všech) apod.

Metody prohledávání stavového prostoru se obvykle dělí na neinformované a informované.

Neinformované metody

Neinformované metody prohledávání nemají k dispozici žádné vhodné znalosti o stavovém prostoru, které by jim umožnily urychlit cestu k cíli. Jsou tak odsouzeny k systematickému procházení všech uzlů, dokud nenaleznou řešení. Jednotlivé algoritmy se od sebe liší jen způsobem, jakým toto systematické procházení provádějí.

• prohledávání do šířky (Breadth-first search)
• prohledávání do hloubky (Depth-first search)
• prohledávání do hloubky s omezením (Depth-limited search)
• iterativní prohledávání do hloubky (Iterative deepening search)
• obousměrné prohledávání (Bidirectional search)

Informované metody

Informované metody prohledávání mají navíc znalosti o stavovém prostoru, které jim umožňují odhadnout, jak daleko se nachází řešení od aktuálního stavu. Tento odhad reprezentuje tzv. heuristická funkce $h(n)$. Čím nižší hodnoty $h(n)$ nabývá, tím spíše povede cesta k řešení skrze stav $n$. Heuristickou funkci dodává na základě znalostí člověk a informované metody jsou na ní kriticky závislé. Čím lepší heuristika je k dispozici, tím rychleji a s menším zatížením paměti dojde k nalezení řešení.

• uspořádané prohledávání (Best-first search) – Prohledávání do šířky upřednostňující „slibné“ stavy
  • hladové prohledávání (Greedy search)
  • Uniform-cost search – Prohledávání s uniformní cenou (řadí se k neinformovaným metodám)
  • algoritmus A*
  • paprskové prohledávání (Beam search)
• Local search – Lokální metody prohledávání
  • gradientní prohledávání – Horolezecký algoritmus
  • simulované žíhání (Simulated annealing)

Související články

• Kategorie: Grafové algoritmy

Literatura

RUSSEL, S.; NORVIG, P. Artificial Intelligence: A Modern Approach. 2. vyd. New Jersey, USA: Prentice Hall, 2003. Dostupné online. ISBN 0-13-790395-2. S. 59-136. 

MAŘÍK, V., a kol. Umělá inteligence (1). Praha: Academia, 1993. ISBN 80-200-0496-3. S. 33–57.