# 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](Stavovy-prostor) a [neinformované metody](Neinformovane-prohledavani) - 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.

| Vlastnost | Hodnota |
|---|---|
| Úplnost | **ne** (nekonečné prostory, cykly) |
| Optimálnost | **ne** |
| Čas | `O(b^m)` |
| Paměť | `O(b^m)` |

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

| Když | `f(n)` | Chová se jako |
|---|---|---|
| `h(n) = 0` všude | `g(n)` | [UCS](Neinformovane-prohledavani#ucs-když-hrany-nestojí-stejně) |
| `g(n)` se ignoruje | `h(n)` | hladové hledání |
| obojí | `g + h` | **A*** |

**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*

| Vlastnost | Hodnota |
|---|---|
| Úplnost | **ano**, pokud je počet uzlů s `f < C*` konečný |
| Optimálnost | **ano** (při přípustné heuristice) |
| Čas | `O((b*)^d)` |
| Paměť | `O((b*)^d)` |

`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](Neinformovane-prohledavani#bfs-nejkratší-cesta-za-cenu-kterou-nezaplatíš).

Řeší to dvě varianty:

**IDA\* (Iterative Deepening A\*)** - stejný trik jako [IDS](Neinformovane-prohledavani#ids-metoda-která-opakuje-práci-a-vyplatí-se-to), 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:

| Operátor | Podmínka | Cena |
|---|---|---|
| `p1` | sousední pole je prázdné → přesun | 1 |
| `p2` | prázdné pole ob jednu figuru → přeskok | 1 |
| `p3` | prázdné pole ob dvě figury → přeskok | 2 |

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

| Příznak | Kde je problém |
|---|---|
| Vrací platnou, ale ne nejlevnější cestu | nepřípustná heuristika (přestřeluje) |
| Expanduje skoro celý prostor | příliš slabá heuristika, `h` je blízko nule |
| Nikdy se nezastaví v cíli | `h(Goal) ≠ 0` |
| Dojde paměť | vlastnost A*, přepiš na IDA* nebo RBFS |
| Chová se jako UCS | `h` je konstantní nebo nulová |
| Chová se jako hladové hledání | zapomenuté `g` v součtu `f = g + h` |
| Cyklí mezi dvěma stavy | chybí evidence navštívených a znovuotevírání uzlů |

## 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í](Neinformovane-prohledavani)** - kostra, na které A* stojí
- **[Lokální prohledávání](Lokalni-prohledavani)** - když je stavový prostor tak velký, že se cesta hledat nedá
- **[Hry a herní strom](Hry-a-herni-strom)** - stejná myšlenka odhadu, ale s protihráčem
- **[Genetické algoritmy](Geneticke-algoritmy)** - prohledávání, které se cestou vůbec nezabývá