# 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.