Cesko.wiki A*
Author
Albert FloresA* je počítačový algoritmus používaný pro vyhledávání optimálních cest v kladně ohodnocených grafech. Byl vytvořen v roce 1968 Peterem Hartem, Nilsem Nilssonem a Bertramem Raphaelem. Používá stejné principy jako Dijkstrův algoritmus, ale přidává navíc heuristický prvek.
Historie
V roce 1964 Nils Nilsson přišel s heuristickým vylepšením Dijkstrova algoritmu. Tento algoritmus nazval A1. +more V roce 1967 Peter E. Hart vylepšil tento algoritmus, ale nedokázal ukázat, že je opravdu optimální. Tento algoritmus nazval A2. Poté v roce 1968 Bertram Raphael dokázal, že A2 je optimální pro konzistentní heuristiku. Jeho důkaz obsahoval část, kde ukázal, že jeho nový algoritmus A2 je nejlepším algoritmem pro dané podmínky. Pojmenoval ho tedy unixovou shellovou syntaxí A*, čili jako A a všechny možné další verze.
Popis algoritmu
A* používá hladový princip pro nalezení optimální cesty z daného počátečního uzlu do požadovaného koncového uzlu. Optimální cestou se rozumí nejkratší, nejrychlejší, nejlevnější atd. +more cesta v závislosti na reprezentaci hodnot vah hran v grafu. Pro účely tohoto článku je hledána nejkratší cesta.
K tomu používá funkci obvykle označenou f(x), která ohodnocuje jednotlivé uzly pro určení pořadí, v kterém se mají procházet. Tato funkce se skládá ze dvou funkcí: f(x) = g(x) + h(x), kde funkce g(x) je funkce představující vzdálenost mezi počátečním a daným uzlem, h(x) představuje heuristickou funkci. +more Tato funkce odhaduje správnost postupu při vyhledávání optimální cesty za pomoci vzdálenosti z aktuálního uzlu do uzlu konečného. Zároveň musí být přípustná, tzn. nesmí nadhodnocovat vzdálenost k cíli. Například v navigaci může být použita jako heuristika vzdálenost vzdušnou čarou, jelikož je to fyzicky nejkratší možná cesta.
Pokud heuristika h navíc splňuje podmínku h(x) \le d(x,y) + h(y) pro každou hranu x, y grafu (d je délka této hrany), potom h je monotónní (někdy též označována jako konzistentní). V tomto případě algoritmus navštíví každý uzel maximálně jednou.
Samotný algoritmus pak probíhá následovně. Je vytvořena a udržována prioritní fronta otevřených, tj. +more ještě nenavštívených uzlů. Čím menší je hodnota f(x) pro daný uzel x, tím vyšší má prioritu. V každém kroku algoritmu je uzel s nejvyšší prioritou odebrán z prioritní fronty a jsou spočítány hodnoty f a h pro jeho sousední uzly. Tyto uzly jsou pak přidány do prioritní fronty anebo jsou sníženy jejich hodnoty, pokud ve frontě už jsou a nové hodnoty jsou nižší. Algoritmus pokračuje, dokud nemá konečný uzel menší hodnotu f, než libovolný jiný uzel z fronty, nebo dokud není tato fronta prázdná. Hodnota f koncového uzlu je poté délkou nejkratší cesty grafem. Pokud je potřeba znát i konkrétní cestu, je nutné udržovat si i seznam uzlů na této cestě. Pro udržování stačí pamatovat si v každém uzlu jeho (libovolného) předchůdce na nejkratší cestě.
Pseudokód
Následující pseudokód popisuje algoritmus A*: function A*(start, cíl) closedset := prázdná množina // Množina již uzavřených uzlů. openset := množina obsahující pouze počáteční uzel // Množina otevřených uzlů. +more g_skore[start] := 0 // Délka aktuální optimální cesty. h_skore[start] := heuristický_odhad_vzdálenosti(start, cíl) f_skore[start] := h_skore[start] // Předpokládaná délka cesty mezi startem a cílem jdoucí přes y. while openset is not empty x := otevřený uzel s nejmenší hodnotou f_skore[] if x = cíl return rekonstruuj_cestu(přišel_z[cíl]) vyjmi x z openset přidej x do closedset for each y in sousední_uzly(x) if y in closedset continue stávající_g_skore := g_skore[x] + d(x, y).
if y not in openset add y to openset stávající_je_lepší := true elseif stávající_g_skore < g_skore[y] stávající_je_lepší := true else stávající_je_lepší := false if stávající_je_lepší = true přišel_z[y] := x g_skore[y] := stávající_g_skore h_skore[y] := heuristický_odhad_vzdálenosti(y, cíl) f_skore[y] := g_skore[y] + h_skore[y] return failure
function rekonstruuj_cestu(aktuální_uzel) if přišel_z[aktuální_uzel] is set p = rekonstruuj_cestu(přišel_z[aktuální_uzel]) return (p + aktuální_uzel) else return aktuální_uzel
Příklad
alt=Algoritmus v akci Ukázka algoritmu A* v akci. +more Uzly představují města spojená hranami, h(x) je vzdálenost vzdušnou čarou. Zeleně je označený počáteční uzel, modře koncový uzel a oranžově jsou označené uzavřené uzly.
Složitost
Časová složitost algoritmu závisí na použité heuristice. V nejhorším případě je počet prozkoumaných uzlů exponenciální vzhledem k délce řešení. +more V optimálním případě je složitost polynomiální. Optimálním případem se rozumí stav, kdy je prohledávaný prostor stromem, existuje pouze jeden optimální stav a heuristická funkce h splňuje následující podmínku: :|h(x) - h^*(x)| = \mathcal{O}(\log h^*(x)) kde h^* je optimální heuristika, tj. přesná vzdálenost z x do koncového uzlu. Jinými slovy podmínka říká, že chyba heuristiky h neporoste rychleji, než logaritmus optimální heuristiky.