Dijkstrův algoritmus a Best-First-Search#
Dijkstrův algoritmus pracuje tak, že navštěvuje vrcholy grafu počínaje výchozím bodem objektu. Poté opakovaně zkoumá nejbližší dosud nezkoumaný vrchol a přidává jeho vrcholy do množiny zkoumaných vrcholů. Rozšiřuje se směrem ven z výchozího bodu, dokud nedosáhne cíle. Dijkstrův algoritmus zaručeně najde nejkratší cestu z výchozího bodu do cíle, pokud žádná z hran nemá zápornou cenu. (Píšu „nejkratší cesta“, protože často existuje více rovnocenně krátkých cest.) Na následujícím obrázku je růžový čtverec výchozí bod, modrý čtverec je cíl a čajové plochy ukazují, jaké oblasti Dijkstrův algoritmus skenoval. Nejsvětlejší čajové oblasti jsou ty, které jsou nejdále od výchozího bodu, a tvoří tak „hranici“ průzkumu:
Algoritmus Greedy Best-First-Search pracuje podobným způsobem s tím rozdílem, že má k dispozici určitý odhad (nazývaný heuristika), jak daleko od cíle se kterýkoli vrchol nachází. Místo aby vybral vrchol, který je nejblíže výchozímu bodu, vybere vrchol, který je nejblíže cíli. Greedy Best-First-Search nezaručuje nalezení nejkratší cesty. Probíhá však mnohem rychleji než Dijkstrův algoritmus, protože používá heuristickou funkci, která vede cestu k cíli velmi rychle. Pokud se například cíl nachází jižně od výchozí pozice, Greedy Best-First-Search bude mít tendenci zaměřit se na cesty, které vedou na jih. V následujícím diagramu žlutá barva představuje uzly s vysokou heuristickou hodnotou (vysoké náklady na cestu k cíli) a černá uzly s nízkou heuristickou hodnotou (nízké náklady na cestu k cíli). Ukazuje, že Greedy Best-First-Search dokáže najít cesty velmi rychle ve srovnání s Dijkstrovým algoritmem:
Obě tyto ukázky však ilustrují nejjednodušší případ – když na mapě nejsou žádné překážky a nejkratší cesta je skutečně přímá. Uvažujme konkávní překážku popsanou v předchozí části. Dijkstrův algoritmus se nadře více, ale zaručeně najde nejkratší cestu:
Greedy Best-First-Search naproti tomu odvede méně práce, ale jeho cesta zjevně není tak dobrá:
Problém je v tom, že Greedy Best-First-Search je „chamtivý“ a snaží se postupovat k cíli, i když to není správná cesta. Protože bere v úvahu pouze náklady na cestu k cíli a ignoruje náklady na dosavadní cestu, pokračuje dál, i když se cesta, po které jde, stala opravdu dlouhou.
Nebylo by hezké zkombinovat to nejlepší z obou? A* byl vyvinut v roce 1968, aby kombinoval heuristické přístupy jako Greedy Best-First-Search a formální přístupy jako Dijsktrův algoritmus. Je trochu neobvyklý v tom, že heuristické přístupy obvykle poskytují přibližný způsob řešení problémů, aniž by zaručovaly, že dostanete nejlepší odpověď. A* je však postaven nad heuristikou, a přestože vám samotná heuristika nedává záruku, A* vám může zaručit nejkratší cestu.