Informované prohledávání a algoritmus A*

Máš mapu rumunských měst a chceš z Aradu do Bukurešti. Vzdušnou čarou umíš odhadnout, jak daleko je každé město od cíle. Zdálo by se, že stačí vždycky jít do toho, které vypadá nejblíž.

Nestačí. Tenhle postup vrátí cestu za 450, zatímco optimum je 418. Chyba není v tom, že by byl odhad špatný. Chyba je v tom, že se zapomnělo na cenu už ušlé cesty.

Tahle stránka je o jedné jediné rovnici, která tuhle chybu opravuje, a o podmínce, za které pak funguje dokazatelně. Předpokládá to stavový prostor a neinformované metody - zejména UCS, protože A* je jeho přímé rozšíření. Důkaz optimálnosti je tu celý, ale vejde se na pět řádků.

Heuristická funkce

Informované prohledávání má navíc jedinou věc: odhad vzdálenosti stavu od cíle. Tomu odhadu se říká heuristická funkce a značí se h(n).

Platí pro ni dvě věci: h(n) > 0 pro stavy mimo cíl a h(Goal) = 0. Ta druhá podmínka je důležitější, než vypadá - kdyby v cíli odhad nulový nebyl, algoritmus by se do cíle nikdy nedostal, protože by ho pořád považoval za nedokončený.

U rumunských měst je heuristikou přímá vzdálenost do Bukurešti. Ta se dá z mapy odečíst pravítkem, aniž bys znal silnice. To je typický tvar heuristiky: uvolníš nějaké omezení úlohy a spočítáš, co by stálo řešení bez něj. Silnice zatáčejí, vzdušná čára ne, a proto je odhad vždycky optimistický.

Hladové hledání a proč selže

Greedy Best-First Search je nejjednodušší možné využití heuristiky:

f(n) = h(n)

Expanduj vždycky uzel, který vypadá nejblíž k cíli. Nic víc.

Na úloze Arad → Bukurešť vrátí řešení o ceně 450 proti optimu 418. Rozdíl není velký, ale je systematický a dá se udělat libovolně velkým.

Důvod selhání je jedním slovem: g. Hladová metoda se dívá jen dopředu a naprosto ignoruje, kolik už stálo dostat se sem. Klidně tě zavede sto kilometrů oklikou, protože poslední město z ní vypadalo o dva kilometry blíž.

Chová se přesně jako DFS, jen s lepším pořadím větví. Do slepé uličky zaleze stejně ochotně, jen elegantněji.

A*: jedna rovnice, která to spraví

Hodnotící funkce A* sečte obě informace:

f(n) = g(n) + h(n)

kde g(n) je skutečná cena cesty z počátku do n a h(n) je odhad ceny z n do cíle. Součet f(n) je tedy odhad ceny nejlevnější cesty, která vede přes uzel n.

To je celé. Vážně. Zbytek téhle stránky je jen rozvedení téhle jedné rovnice a jedné podmínky, kterou musí h splnit.

Všimni si dvou krajních případů, ze kterých je vidět, kde A* stojí:

A je tedy UCS, které navíc kouká dopředu.* Kdo si to jednou takhle zařadí, nemá s ním problém.

Přípustnost, čili jediná podmínka

A* nefunguje s libovolnou heuristikou. Vyžaduje přípustnou (admissible) heuristiku:

0 ≤ h(n) ≤ h*(n)

kde h*(n) je skutečná cena cesty z n do cíle. Slovy: odhad nikdy nesmí být větší než skutečnost. Heuristika smí být optimistická, nesmí být pesimistická.

Tohle je nejdůležitější věta na celé stránce a zároveň místo, kde to lidi nejčastěji položí. Nepřípustná heuristika neznamená, že A* přestane fungovat. Znamená, že přestane být optimální a nikdo si toho nevšimne, protože nějakou cestu vrátí a ta bude vypadat rozumně.

Přímá vzdálenost je přípustná, protože po silnici to nikdy nemůže být kratší než vzdušnou čarou. Součet manhattanských vzdáleností dlaždic v patnáctce je přípustný, protože každá dlaždice potřebuje alespoň tolik tahů. Počet špatně umístěných dlaždic je přípustný taky, jen slabší - a slabší heuristika znamená víc expandovaných uzlů.

Důkaz optimálnosti

Vejde se na pět řádků a stojí za to si ho projít, protože z něj je vidět, kde se přípustnost používá.

Předpokládej pro spor, že A* vygeneruje suboptimální cíl G2. Nechť n je neexpandovaný uzel ležící na nejkratší cestě k optimálnímu cíli G1. Pak:

f(G2) = g(G2) > g(G1) ≥ f(n)

Rozeber si to po částech:

• f(G2) = g(G2), protože v cílovém uzlu je h = 0.
• g(G2) > g(G1), protože G2 je z předpokladu suboptimální.
• g(G1) ≥ f(n), protože h je přípustná - odhad z n nemůže přestřelit skutečný zbytek cesty k G1.

Z toho plyne f(G2) > f(n). A* ale vybírá uzel s nejmenším f, takže by expandoval n dřív než G2. To je spor s předpokladem, že n zůstal neexpandovaný.

Ta nerovnost g(G1) ≥ f(n) je jediné místo, kde se přípustnost použije. Odtud plyne, proč se bez ní důkaz rozpadne.

Vlastnosti A*

b* je efektivní faktor větvení - kolik následníků by musel mít strom, aby při dané hloubce vygeneroval tolik uzlů, kolik jich A* skutečně vygenerovalo. Čím lepší heuristika, tím blíž je b* jedničce. Při b* = 1 jde algoritmus rovnou k cíli bez jediného odbočení.

Paměť je pořád exponenciální a je to hlavní praktický problém A.* Drží si v paměti všechny vygenerované uzly a u velkých úloh na tom padne dřív, než mu dojde čas - přesně jako BFS.

Řeší to dvě varianty:

IDA* (Iterative Deepening A*) - stejný trik jako IDS, jen se místo hloubky iteruje limit na f. Paměť klesne na lineární.

RBFS (Recursive Best-First Search) - rekurzivní varianta s lineární pamětí, která si u opuštěných větví pamatuje nejlepší f a v případě potřeby se k nim vrátí.

Spočítaný příklad: hra 4 kameny

Modelová úloha, na které je vidět, jak se f = g + h počítá. Počáteční stav je sloupec pěti polí s kameny B, B, C, C a prázdným polem dole. Cílem jsou kameny C nahoře a B dole.

Operátory a jejich ceny:

Funkce se definují takhle:

• h(i) = minimální počet špatně umístěných kamenů do cíle
• g(i) = cena pohybu figur po cestě do i podle použitých operátorů
• f(i) = g(i) + h(i)

Zkontroluj si na tom přípustnost. Každý špatně umístěný kámen potřebuje alespoň jeden tah, aby se dostal na místo, a každý tah stojí alespoň jedna. Odhad h tedy nikdy nepřestřelí skutečnou cenu a A* je optimální.

Kdybys počítal h jako součet vzdáleností kamenů od jejich cílových pozic, dostaneš silnější a pořád přípustnou heuristiku - jeden tah může kámen posunout o dvě pozice (p3) za cenu 2, takže součet vzdáleností je pořád dolní odhad ceny. Silnější heuristika = menší b* = menší strom.

Kdybys naopak h vynásobil dvěma „pro jistotu, ať to jde rychleji", přípustnost porušíš. Algoritmus doběhne rychleji a vrátí nesprávnou odpověď.

Jak se dělá dobrá heuristika

Uvolni omezení úlohy. Přesná cena řešení zjednodušené úlohy je vždycky přípustná heuristika té původní. Manhattanská vzdálenost v patnáctce je cena úlohy, ve které dlaždice smějí procházet skrz sebe.

Silnější heuristika je lepší, dokud se dá spočítat rychle. Když h1(n) ≥ h2(n) pro všechna n a obě jsou přípustné, h1 dominuje a A* s ní expanduje méně uzlů. Ale odhad, jehož výpočet trvá déle než expandování těch ušetřených uzlů, je špatný obchod.

Z několika heuristik ber maximum. h(n) = max(h1(n), h2(n)) je pořád přípustná a dominuje oběma.

Kontroluj přípustnost, ne intuici. Napiš si jeden konkrétní stav, spočítej skutečnou cenu do cíle ručně a porovnej s h. Když je h větší, máš chybu - i kdyby algoritmus na testech dával správné odpovědi.

Co se na tom nejčastěji rozbije

Co si odnést

f(n) = g(n) + h(n). Cena, kterou už jsi zaplatil, plus odhad zbytku. To je celý A*.

Hladové hledání zahazuje g a tím i optimalitu. Rozdíl 450 versus 418 na rumunských městech.

Přípustnost znamená h ≤ h*. Optimistický odhad ano, pesimistický nikdy.

Nepřípustná heuristika tichým způsobem zabije optimalitu. Program běží dál a vrací horší řešení.

A je pořád exponenciální v paměti.* Na velké úlohy patří IDA*.

A s h = 0 je UCS.* Není to jiná rodina algoritmů, je to tatáž s dodatkem.

Kam dál

• Neinformované prohledávání - kostra, na které A* stojí
• Lokální prohledávání - když je stavový prostor tak velký, že se cesta hledat nedá
• Hry a herní strom - stejná myšlenka odhadu, ale s protihráčem
• Genetické algoritmy - prohledávání, které se cestou vůbec nezabývá