Stavový prostor, čili jak se úloha vůbec zadá stroji

Nejčastější chyba v praxi není špatný algoritmus. Je to špatně formulovaná úloha. Napíšeš, že „hledáme nejkratší cestu", a pak zjistíš, že nevíš, co je stav, co je operátor a kdy má algoritmus skončit. Prohledávací metody z toho pak vyjdou jako magie, protože není jasné, čím vlastně procházejí.

Přitom celý aparát je jednoduchý a jednou naučený platí pro všechno, co v prohledávání, hrách i plánování přijde.

Tahle stránka zavádí formální zápis úlohy, ukazuje, co je operátor, a definuje čtyři veličiny, kterými se pak měří každá prohledávací metoda. Nepočítá se tu nic konkrétního - to dělají navazující stránky. Matematika je tu jen značení, ne důkazy.

To pravidlo

Úloha je dvojice množin stavů a sada operátorů, které mezi stavy přecházejí. Řešením je posloupnost operátorů, která tě dostane z výchozího stavu do cílového.

To je celé. Zbytek stránky je jen zápis téhle věty a pár důsledků, které z ní plynou.

Formální zápis

Mějme dvě množiny stavů:

X = {x1, x2, ..., xK}      množina výchozích stavů
Y = {y1, y2, ..., yM}      množina cílových stavů

Řešením úlohy rozumíme posloupnost operací, jíž převedeme úlohu z některého výchozího stavu xi do některého cílového stavu yj. Obecně jde tedy o zobrazení X → Y.

Graficky je to posloupnost stavů propojených operátory:

xi ≡ s0  --rp-->  sp  --rq-->  sq  --rs-->  ss  --rt-->  st ≡ yj

Stavy sp, sq, ss jsou vnitřní (mezi)stavy a nikoho nezajímají samy o sobě. rp až rt jsou elementární operátory z množiny RULES = {r1, r2, ..., rL}.

Když posloupnost operátorů slepíš dohromady, dostaneš kompoziční operátor:

xi --RKij--> yj,      kde RKij = rp rq rs rt

Tohle je nejdůležitější věc na stránce: řešením není cílový stav, ale cesta k němu. U některých úloh cesta nikoho nezajímá a stačí konfigurace - těm se pak věnuje lokální prohledávání, které je celé postavené na téhle výjimce.

Tři druhy úloh podle toho, co neznáš

Úlohou nazveme trojici (X, Y, R), kde dvě složky známe a třetí určujeme. Podle toho, která chybí, dostaneš tři úplně různé druhy úloh:

Induktivní úloha je celé strojové učení. Máš vstupy, máš požadované výstupy a hledáš pravidla. Přesně to dělá perceptron, rozhodovací strom i neuronová síť. Když si to jednou takhle zařadíš, přestane strojové učení vypadat jako oddělený svět.

Abduktivní úloha má háček. Poskytuje exaktní řešení pouze tehdy, je-li RKij bijekcí. Když k jednomu následku vede víc příčin, nemáš z čeho vybrat - a to je důvod, proč se diagnostika dělá pravděpodobnostně, viz Bayesova klasifikace.

Čtyři čísla, kterými se měří každá metoda

Každou prohledávací metodu posuzuješ podle čtyř věcí a v téhle podobě to potkáš u každého algoritmu v téhle wiki:

Úplnost. Najde metoda řešení, pokud existuje? Metoda, která umí zabloudit do nekonečné větve, úplná není.

Optimálnost. Najde metoda nejlepší řešení? Metoda může být úplná a přitom vracet zbytečně drahou cestu.

Časová složitost. Kolik uzlů metoda vygeneruje.

Prostorová složitost. Kolik uzlů si musí naráz pamatovat. Tohle je v praxi ta veličina, která rozhoduje - čas se dá odčekat, paměť ne.

Složitosti se vyjadřují pomocí pěti parametrů:

U šachů je b ≈ 35 a m ≈ 100, takže strom má zhruba 35^100 ≈ 10^154 uzlů. Pro srovnání: ve viditelném vesmíru je odhadem 10^80 atomů. Proto se šachy neřeší prohledáním celého stromu a proto vůbec existuje alfa-beta prořezávání.

Elementární versus kompoziční operátor a proč na tom záleží

Volba operátorů rozhoduje o velikosti stavového prostoru víc než cokoliv jiného. Když si zvolíš příliš jemné operátory, dostaneš obrovský strom. Když příliš hrubé, přijdeš o řešení.

Ukázkový případ je hra 4 kameny, kde máš sloupec pěti polí s kameny B, B, C, C a jedním prázdným místem. Operátory jsou tři:

Kdybys p2 a p3 vynechal, úloha má pořád řešení, jen výrazně delší. Kdybys naopak přidal operátor „přehoď libovolné dva kameny", vyřešíš ji na jeden tah - a přijdeš o smysl úlohy, protože takový operátor v původním zadání není povolený.

Nerovnoměrné ceny operátorů (tady 1 a 2) jsou přesně to, kvůli čemu existuje prohledávání podle ceny. Kdyby všechny operátory stály stejně, stačilo by BFS.

Rozklad úlohy na podúlohy

Druhá cesta, jak se vyrovnat s velkým stavovým prostorem, není lepší prohledávání, ale jiná formulace. Složitý problém se rozdělí na menší části, každá se vyřeší zvlášť a řešení se složí.

Motivace je čtvero: přehlednost, možnost paralelizace, snadné testování a snížení složitosti.

Kanonický příklad je Merge Sort:

1. Rozděl - pole rozdělíme na dvě poloviny.
2. Rekurze - každou polovinu opět dělíme, dokud nemáme pole o jednom prvku.
3. Panuj - postupně slučujeme seřazené části dohromady.

Pro vstup [38, 27, 43, 3, 9, 82, 10] vyjde po slučování [3, 9, 10, 27, 38, 43, 82].

Formální aparát pro rozklad je AND/OR graf a má vlastní stránku, protože se od běžného stavového prostoru liší v jedné podstatné věci: některé uzly vyžadují vyřešení všech svých následníků, ne jednoho.

Co se na tom nejčastěji rozbije

Shrnutí v jedné větě

Úloha je trojice (X, Y, R), řešením je posloupnost operátorů, a všechno, co se pak o metodách říká, je jen odpověď na čtyři otázky: najde to, najde to nejlepší, za jak dlouho a v kolika bajtech.