Stavovy-prostor.md

# 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í](Neinformovane-prohledavani), [hrách](Hry-a-herni-strom) i [plánování](Inteligentni-agenti) 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í](Lokalni-prohledavani), 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: | Zápis | Název | Co hledáš | Příklad ||---|---|---|---|| `(X, ?, R)` | deduktivní | kam se dostanu | simulace, výpočet, hra || `(?, Y, R)` | abduktivní | odkud jsem přišel | diagnostika, vyšetřování || `(X, Y, ?)` | induktivní | jak se to dělá | strojové učení | **Induktivní úloha je celé strojové učení.** Máš vstupy, máš požadované výstupy a hledáš pravidla. Přesně to dělá [perceptron](Neuron-a-perceptron), [rozhodovací strom](Priznakove-metody) i [neuronová síť](MLP-a-backpropagation). 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](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ů: | Symbol | Význam ||---|---|| `b` | faktor větvení, tedy průměrný počet následníků uzlu || `d` | hloubka nejmělčího cíle || `m` | maximální hloubka větve (může být nekonečná) || `ℓ` | limit hloubky, pokud ho metoda používá || `C*` | cena optimálního řešení | 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í](Hry-a-herni-strom).** ## 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: | Operátor | Podmínka | Cena ||---|---|---|| `p1` | sousední pole je prázdné | 1 || `p2` | prázdné pole ob jednu figuru | 1 || `p3` | prázdné pole ob dvě figury | 2 | 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](Neinformovane-prohledavani#ucs-když-hrany-nestojí-stejně).** 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](Dekompozice-a-AND-OR-grafy) 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 | Příznak | Kde je problém ||---|---|| Algoritmus se nikdy nezastaví | stav není dost konkrétní, vznikají cykly - chybí seznam navštívených || Řešení je nesmyslně dlouhé | příliš jemné operátory, nebo chybí cena || Řešení neexistuje, ale mělo by | některý operátor v `RULES` chybí, nebo má moc přísnou podmínku || Paměť dojde dřív než čas | špatně zvolená metoda, viz [prostorová složitost](Neinformovane-prohledavani) || Cíl se nepozná | cílový test testuje stav místo vlastnosti stavu | ## 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.