Dekompozice-a-AND-OR-grafy.md

# 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`: ```mermaidflowchart 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í