# Dekompozice úlohy a AND/OR grafy

Hanojské věže s dvaceti kotouči mají řešení o `2^20 − 1`, tedy zhruba milionu tahů. Zkus je najít [prohledáváním](Neinformovane-prohledavani) a strávíš u toho zbytek života.

Zkus je vyřešit rozkladem a máš to na tři řádky, které se vejdou do jedné rekurzivní funkce.

Rozdíl není v algoritmu, ale ve formulaci. V obyčejném stavovém prostoru hledáš **jednu cestu**. Tady hledáš **strom**, jehož všechny větve musí být vyřešené naráz. To je jiný typ grafu a má vlastní jméno.

Předpokládá to [stavový prostor](Stavovy-prostor), zejména část o rozkladu úlohy na podúlohy. Tahle stránka formalizuje, co tam bylo naznačené na Merge Sortu.

## To pravidlo

Běžný graf má jen OR uzly: **stačí, aby jeden následník vedl k řešení**. AND/OR graf přidá druhý typ uzlu, u kterého **musí být vyřešeni všichni následníci naráz**.

Z toho plyne všechno ostatní, včetně toho, že řešením už není cesta, ale podgraf.

## Hanojské věže

Tři tyče `A`, `B`, `C`. Na tyči `A` je `n` kotoučů seřazených podle velikosti. Úkolem je přeskládat je z `A` pomocí `C` na tyč `B`, nikdy nesmí ležet větší na menším. Zapisuje se to `n(A, B, C)`.

Rozklad na tři fáze:

1. Přeskládat `n − 1` kotoučů z `A` pomocí `B` na `C`, tedy `(n−1)(A, C, B)`.
2. Přeložit jeden kotouč z `A` na `B`, tedy `1(A, B, C)`.
3. Přeskládat `n − 1` kotoučů z `C` pomocí `A` na `B`, tedy `(n−1)(C, B, A)`.

Schéma pro `n = 3`:

```mermaid
flowchart TD
    R["3(A,B,C)"] --- X1["2(A,C,B)"]
    R --- X2["1(A,B,C)"]
    R --- X3["2(C,B,A)"]
    X1 --- Y1["1(A,B,C)"]
    X1 --- Y2["1(A,C,B)"]
    X1 --- Y3["1(B,C,A)"]
    X3 --- Y4["1(C,A,B)"]
    X3 --- Y5["1(C,B,A)"]
    X3 --- Y6["1(A,B,C)"]
```

**Všechny hrany v tomhle schématu jsou AND hrany.** Nemůžeš si vybrat jednu ze tří fází - potřebuješ všechny tři, ve správném pořadí. Kdyby to byly OR hrany, „vyřešil" bys věže tím, že přeložíš jeden kotouč a prohlásíš hotovo.

Zároveň je tady vidět, proč se rozklad vyplatí. Strom má hloubku `n` a v každé úrovni se úloha zdvojnásobí, takže popíše `2^n − 1` tahů. **Ale popíše je zápisem o velikosti `O(n)`**, protože se ta struktura opakuje. Prohledávání by muselo těch milion tahů projít jeden po druhém.

## AND/OR graf: definice

**AND/OR graf** je graf se dvěma typy vnitřních uzlů:

- **AND uzel** - jako součást řešení vyžaduje průchod **všemi** svými poduzly.
- **OR uzel** - chová se jako běžný uzel klasického grafu, stačí jeden podstrom.

**Strom řešení** `T` problému `P` s AND/OR grafem `G` se definuje takhle:

- Problém `P` je kořen stromu `T`.
- Je-li `P` **OR uzel** v `G`, pak **právě jeden** z jeho následníků se svým stromem řešení je v `T`.
- Je-li `P` **AND uzel** v `G`, pak **všichni** jeho následníci se svými stromy řešení jsou v `T`.
- Každý list stromu řešení `T` je cílovým uzlem v `G`.

Ta poslední podmínka je ta, kterou lidi nejčastěji přeskočí. **Nedořešená větev znamená, že celý strom není řešením** - ne že je řešení částečné. U AND uzlu neexistuje „skoro hotovo".

## Příklad: cesta mezi městy

Hledáme cestu z `a` do `z`, přičemž se musí projet přes jeden ze dvou hraničních přechodů, `k` nebo `l`.

- **OR uzel:** `a → z` se dá vyřešit **buď** přes `k`, **nebo** přes `l`. Stačí jedna možnost.
- **AND uzly:** cesta přes `k` znamená vyřešit `a → k` **a zároveň** `k → z`. Obojí, ne jedno.

Celkové řešení je tedy **podgraf AND/OR grafu, který nevynechává žádného následníka AND-uzlu**.

Všimni si, jak přirozeně to odpovídá tomu, jak o problému mluvíš nahlas: „musím se dostat na hranici a pak z hranice do cíle, a hranici si můžu vybrat." Slova „a zároveň" a „nebo" v běžné řeči jsou přesně ty dva typy uzlů.

## Merge Sort jako AND/OR strom

Rozděl a panuj je AND/OR graf, ve kterém **nejsou žádné OR uzly**. Není z čeho vybírat, jen se pořád dělí:

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 `[3, 9, 10, 27, 38, 43, 82]`.

**Seřazení levé poloviny a seřazení pravé poloviny je AND.** Bez jedné z nich sloučení nedává smysl. Přesně proto se dá Merge Sort triviálně paralelizovat - AND větve jsou na sobě nezávislé a můžou běžet naráz. To u OR uzlů neplatí, tam se paralelismem plýtvá.

## Proč se to vyplatí

**Přehlednost.** Každá podúloha se dá pochopit sama o sobě.

**Paralelizace.** AND větve jsou nezávislé, takže se dají počítat současně.

**Snadné testování.** Podúlohu otestuješ zvlášť a nemusíš spouštět celek.

**Snížení složitosti.** Tohle je ten hlavní důvod. Rozklad mění exponenciální úlohu na sadu malých, které se dají popsat opakující se strukturou.

## Kde dekompozice přestává platit

**Podúlohy nesmí být propletené.** Rozklad předpokládá, že řešení jedné části neznemožní řešení druhé. Když na sobě podúlohy závisí sdílenými zdroji, dostaneš buď špatné řešení, nebo nekonečné přeplánovávání. V plánování se tomu říká interakce podcílů a je to důvod, proč plánovač neumí naivně řešit „nakup mléko a zároveň buď doma".

**Rozklad musíš dodat ty.** Algoritmus rozklad nevymyslí. Hanojské věže se rozkládají na tři fáze, protože to někdo vymyslel, ne protože by to bylo v zadání. **Tady je celý rozdíl mezi dekompozicí a prohledáváním: prohledávání funguje bez nápadu, dekompozice ne.**

**Nezávislé podúlohy se dají řešit dvakrát.** Když se stejná podúloha objeví ve víc větvích, spočítáš ji vícekrát. Řeší se to memoizací, čímž se ze stromu stane graf a z rekurze dynamické programování.

## Co si odnést

**AND uzel = všichni následníci, OR uzel = jeden následník.** Celá teorie stojí na tomhle rozdílu.

**Řešením je podgraf, ne cesta.** U AND uzlu neexistuje částečné řešení.

**Každý list stromu řešení musí být cílový uzel.** Nedořešená větev ruší celý strom.

**Rozklad je nápad, ne algoritmus.** Prohledávání funguje bez tebe, dekompozice ne.

**AND větve se dají paralelizovat.** Proto je Merge Sort dobrý příklad a proto se rozděl-a-panuj drží.

## Kam dál

- **[Stavový prostor](Stavovy-prostor)** - odkud rozklad úlohy vychází
- **[Neinformované prohledávání](Neinformovane-prohledavani)** - alternativa, kterou dekompozice obchází
- **[Hry a herní strom](Hry-a-herni-strom)** - herní strom je AND/OR graf, kde OR uzly patří tobě a AND uzly soupeři
- **[Inteligentní agenti](Inteligentni-agenti)** - plánování jako hledání posloupnosti akcí