Umělá inteligence
Obsah Soubory
Prohledávání

Dekompozice a AND/OR grafy

Aktualizováno 5 min čtení 966 slov

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 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, 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:

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

Odkazuje sem