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. 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. 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. 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. 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. 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. 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ě.

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ů.
    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ši 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
        foreach 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

Ukázka algoritmu A* v akci. 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í. 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.

Související články

• Dijkstrův algoritmus