Metoda A*

Popis

Algoritmus využívá opět principu hladového prohledávání, ale do vyhodnocení heuristické funkce již zahrnuje i cenu cesty do aktuálního n-tého uzlu, tedy Funkce je cena cesty do uzlu odhad ceny cesty z -tého uzlu do uzlu cílového, představujícího řešení úlohy. Funkce tedy představuje odhad nejlevnější cesty do cíle, která vede přes

Algoritmus A* vyžaduje použití přípustné heuristiky kde je skutečná cena cesty do cíle. V případě, že tomu tak není, je algoritmus označován pouze jako algoritmus A. Heuristická funkce tedy provádí optimistický odhad ceny cest do cíle, žádná reálná cesta nemůže mít nižší cenu (být kratší), než použitá heuristika. V našem příkladě rumunských měst je toto splněno, neboť vzdušná vzdálenost mezi dvěma městy musí být vždy kratší nebo limitně stejná, jako délka silnice, která je spojuje.
Principiálně funguje algoritmus A* naprosto stejně jako GS, pouze s tím rozdílem, že provádí prioritní seřazení stavů podle hodnoty funkce

Zkusme se podívat, jak by se algoritmus A* choval při nalezení cesty z Aradu do Bucharesti.

Obr. 10. Postupné generování cesty – A* algoritmus

Až do uzlu Sibiu algoritmus postupuje stejnou cestou, jako GS. Zde vyhodnotí funkci pro všechny následníky. Přesto, že Fagaras je oproti Rimnicu vzdušnou čarou blíže k cíli (178 km oproti 193 km), metoda A* zvolí jako další expandovaný uzel Rimnicu. Po započtení ceny cesty z Aradu do Fagarase (239 km) resp. Rimnicu (220 km) totiž dochází algoritmus k tomu, že cesta přes Rimnicu (413 km) je celkově výhodnější oproti cestě přes Fagaras (417 km). Hodnota funkce je stále jen odhadem délky cesty, neboť mimo exaktně vyčíslené ceny  (délky) již absolvované cesty obsahuje i odhad délky cesty následující založený jen na vzdušné vzdálenosti mezi městy. Nicméně přípustnost heuristiky zaručuje nalezení optimální cesty.

Vlastnosti algoritmu

Jelikož algoritmu expanduje uzly postupně podle vzrůstající hodnoty odhadu ceny cesty do cíle musí nakonec pro konečný počet uzlů s ohodnocením do cíle dorazit. Algoritmus A* je tedy za předpokladu splnění podmínky konečného počtu uzlů s hodnotou  úplný.Podmínka konečného počtu takových uzlů by nemusela být splněna, pokud by byl faktor větvení b nekonečný, nebo v případě, že by se v grafu vyskytovala nekonečná větev, byť s konečnou cenou. To může nastat v případě, že je pro uzly na této větvi nulová.

Podmínkou úplnosti A* je tedy použití přípustné heuristiky (každý přechod tedy něco stojí) a konečný faktor větvení v grafu.

Pro ohodnocení uzlů funkcí kde je skutečná cena cesty do cíle,  expanduje A* všechny uzly s některé s prověří na přítomnost cíle a nezabývá se žádnými uzly s

Přípustná heuristika zaručuje, že algoritmus A* je optimální.

Předpokládejme, že se nacházíme v určitém uzlu, ze kterého vycházejí dvě hrany. Jedna hrana směřuje přímo do uzlu se suboptimálním cílem druhá hrana směřuje do obecného uzlu v jehož podstromu se nachází optimální cíl se skutečnou cenou cesty

1. Uzel je cílový, proto platí, že
2. Z přípustnosti heuristiky plyne, že
3. Víme, že algoritmus A* se rozhoduje podlerostoucí hodnoty funkce Pokud by byl algoritmem zvolen uzel muselo by tedy platit, že
4. Z bodů b) a c) plyne, že Dosazením z bodu a) pak dostáváme, že

Bod d) je ale ve zřejmém rozporu s tím, že cesta cena cesty do suboptimálního cíle je menší, než skutečná cena cesty do cíle

Nemůže se tedy stát, že by byl z libovolného uzlu zvolen algoritmem A* suboptimální cíl   s hodnotou funkce protože odhad ceny pro uzel n na cestě k optimálnímu cíli   s cenou cesty je s ohledem na přípustnost (tedy vždy optimistický odhad) heuristiky vždy nižší.

Časová složitost algoritmu A* je exponenciální, v nejhorším případě (pokud je kostanta ) odpovídá složitostí algoritmu prohledávání do šířky, ale je vždy lepší než BFS, nemusí expandovat uzly s

(15)

ale heuristika dokáže reálně dobu prohledávání často podstatně redukovat.

Prostorová složitost je v základní variantě podobně jako časová také exponenciální a je rovna 

(16)

Je ale možné použít modifikace pro její redukci, jako například použití algoritmu IDS podle maximální ceny kdy pro každou další iteraci IDS volíme jako počáteční uzel s nejnižší hodnotou funkce která je ale současně vyšší než aktuální Tato metoda je označována jako IDA*. Další možností je pak ořezávat neslibné stavy a cesty do těchto stavů. Ušetříme tak kapacitu paměti za cenu suboptimálnosti takového řešení.

Výhody a nevýhody

Jedná se o úspěšný algoritmus, kdy samozřejmě v závislosti na kvalitě heuristiky obvykle významně redukuje časovou složitost prohledávání. Navíc je úplný a optimální, neprodlužuje již dlouhé cesty.

Podobně jako v případě GS je zapotřebí ošetřit možnost zacyklení algoritmu pomocí množiny CLOSE. Relativně velkou paměťovou složitost lze redukovat za cenu suboptimálnosti algoritmu.