A*
A* (A star) 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.[1] Používá stejné principy jako Dijkstrův algoritmus, ale přidává navíc heuristický prvek.
Historie
[editovat | editovat zdroj]V roce 1964 Nils Nilsson přišel s heuristickým vylepšením Dijkstrova algoritmu. Tento algoritmus nazval A1. 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
[editovat | editovat zdroj]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. 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 , která ohodnocuje jednotlivé uzly pro určení pořadí, v kterém se mají procházet. Tato funkce se skládá ze dvou funkcí: , kde funkce je funkce představující vzdálenost mezi počátečním a daným uzlem, představuje heuristickou funkci. 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 navíc splňuje podmínku pro každou hranu grafu ( je délka této hrany), potom 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. ještě nenavštívených uzlů. Čím menší je hodnota pro daný uzel , 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 a 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 , než libovolný jiný uzel z fronty, nebo dokud není tato fronta prázdná. Hodnota 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
[editovat | editovat zdroj]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ů. 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
[editovat | editovat zdroj]![Algoritmus v akci](http://upload.wikimedia.org/wikipedia/commons/5/5d/AstarExample.gif)
Ukázka algoritmu A* v akci. Uzly představují města spojená hranami, 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
[editovat | editovat zdroj]Č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í. 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 splňuje následující podmínku:
kde je optimální heuristika, tj. přesná vzdálenost z do koncového uzlu. Jinými slovy podmínka říká, že chyba heuristiky neporoste rychleji, než logaritmus optimální heuristiky.[2][3]
Související články
[editovat | editovat zdroj]Reference
[editovat | editovat zdroj]- ↑ A Formal Basis for the Heuristic Determination of Minimum Cost Paths, Nilsson, N. J.; Raphael, B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. Transactions on Systems Science and Cybernetics SSC4. 1968, s. 100–107.
- ↑ PEARL, Judea. Heuristics: Intelligent Search Strategies for Computer Problem Solving. [s.l.]: Addison-Wesley, 1984. Dostupné online. ISBN 0-201-05594-5. (anglicky)
- ↑ RUSSELL, S. J.; NORVIG, P. Artificial Intelligence: A Modern Approach. Upper Saddle River, N.J.: Prentice Hall, 2003. Dostupné online. ISBN 0-13-790395-2. S. 97–104. (anglicky)
Externí odkazy
[editovat | editovat zdroj]Obrázky, zvuky či videa k tématu A* na Wikimedia Commons
Galerie A* na Wikimedia Commons
Slovníkové heslo A* ve Wikislovníku