A* algoritmus: definice, princip a použití při hledání nejkratší cesty
A* algoritmus: princip, heuristika a praktické použití při hledání nejkratší cesty — rychlé, efektivní trasování pro mapy, hry a robotiku.
A* je algoritmus pro hledání nejkratší cesty v grafu. Je to heuristicky řízená varianta prohledávání, která kombinuje skutečně dosaženou vzdálenost od počátečního bodu (g(n)) s odhadem zbývající vzdálenosti k cíli (h(n)) a na základě součtu f(n) = g(n) + h(n) vybírá, které uzly prozkoumat jako první. Díky tomu obvykle najde cílovou cestu rychleji než prostý Dijkstraův algoritmus (Dijkstrovu algoritmu) při zachování optimálnosti za vhodných podmínek heuristiky.
Princip fungování
Algoritmus udržuje množinu otevřených uzlů (frontu), které ještě čekají na rozbalení, a množinu uzavřených uzlů, které už byly zpracovány. Postup je obecně následující:
- Vloží se počáteční uzel do otevřené množiny s g(start)=0 a f(start)=h(start).
- Opakovaně se vybere uzel z otevřené množiny s nejmenší hodnotou f, tento uzel se rozbalí (přesun do uzavřené množiny) a zkontrolují se jeho sousedé.
- Pro každého souseda se spočítá nová hodnota g (cena do souseda přes aktuální uzel). Pokud je cesta lepší než předchozí nalezená, aktualizují se hodnoty g, f a ukazatel pro rekonstrukci cesty.
- Algoritmus končí, když je cílový uzel rozbalen (nalezen nejkratší známý způsob), nebo když otevřená množina je prázdná (cesta neexistuje).
Heuristika: admissibilita a konzistence
Klíčová část A* je heuristika h(n), která odhaduje náklady z uzlu n do cíle. Důležité vlastnosti:
- Admissibilní heuristika nikdy nepřecení skutečné náklady do cíle (tj. h(n) ≤ skutečné náklady). Pokud je heuristika admissibilní, A* vrátí optimální (nejkratší) cestu.
- Konzistentní (monotónní) heuristika splňuje podmínku h(n) ≤ cost(n, m) + h(m) pro všechny hrany (n,m). Konzistence zaručuje, že po rozbalení uzlu už se jeho hodnota g nemusí zlepšit — není potřeba uzly znovu otevírat, což zjednodušuje implementaci.
Příklady heuristik pro mřížku: Manhattanova vzdálenost (ideální pro pohyb po osách), Euclidovská vzdálenost (volný pohyb v rovině), Chebyshevova (když jsou povoleny diagonální kroky se stejnou cenou).
Pseudokód a implementační poznámky
initialize openSet with start g[start] = 0 f[start] = h(start) while openSet not empty: current = node in openSet with lowest f if current == goal: return reconstruct_path(cameFrom, current) remove current from openSet add current to closedSet for each neighbor of current: tentative_g = g[current] + cost(current, neighbor) if neighbor in closedSet and tentative_g >= g[neighbor]: continue if tentative_g < g[neighbor] or neighbor not in openSet: cameFrom[neighbor] = current g[neighbor] = tentative_g f[neighbor] = g[neighbor] + h(neighbor) if neighbor not in openSet: add neighbor to openSet
Praktické tipy:
- Pro otevřenou množinu použijte prioritní frontu (min-heap) indexovanou podle f, případně s podporou aktualizace priorit.
- Uchovávejte mapu cameFrom pro rekonstrukci cesty po nalezení cíle.
- Pro konzistentní heuristiku není nutné znovu otevírat uzly v množině closed; pro ne-konzistentní heuristiku je vhodné povolit „reopen“ se správnou logikou.
- V praxi může mít smysl uvažovat tie-breaking pravidla (např. preferovat vyšší g při shodném f), což vede k hladším nebo kratším cestám v herních aplikacích.
Komplexita
- Časová složitost: v nejhorším případě exponenciální vůči hloubce řešení; v praxi závisí na kvalitě heuristiky — lepší heuristika (bližší skutečné hodnotě) výrazně snižuje prohledávaný prostor.
- Paměťová náročnost: A* ukládá otevřené i uzavřené množiny, takže vyžaduje paměť měřítka počtu prozkoumaných uzlů (může být výrazně náročná u velkých grafů).
Varianty a optimalizace
- Weighted A*: používá f = g + w·h s faktorem w>1 — rychlejší, ale může ztratit optimálnost; pro w≥1 získáte kompromis mezi rychlostí a kvalitou řešení.
- Bidirectional A*: spouští dvě prohledávání od startu a cíle a hledá průsečík — může ušetřit čas, ale vyžaduje soulad heuristik a obvykle složitější implementaci.
- Memory-bounded A* (IDA*, SMA*): varianty, které omezují paměť použitou A*, vhodné pro omezené prostředí.
- Hierarchické nebo navazující mapy: sníží problém rozkladem na několik úrovní (používá se v GIS nebo hrách).
Použití
- Hry (pathfinding postav) — díky rychlosti a možnosti použít doménové heuristiky.
- Robotika a plánování trajektorií — hledání kolizně volných tras v mapách.
- GIS a navigace — nalezení nejkratší nebo nejrychlejší trasy v silniční síti.
- Simulace a umělá inteligence — obecné prohledávání stavového prostoru, pokud je vhodná heuristika.
Omezení
- A* hledá jednu nejkratší cestu mezi dvěma body — pokud chcete najít všechny páry nejkratších cest najednou, existují efektivnější algoritmy (např. Floyd-Warshall).
- Neřeší komplikovanější optimalizační úlohy typu „návštěva více míst v jedné cestě“ (např. problém obchodního cestujícího), které vyžadují jiné metody.
- Paměťová náročnost může být limitující pro velmi velké nebo vysokodimenzionální stavové prostory.
Krátký příklad (mřížka)
Máte mřížku 2D, pohyb povolen po 4 směrech, cena kroku = 1. Pokud používáte Manhattanovu heuristiku (součet rozdílů souřadnic), je heuristika admissibilní a konzistentní. A* prohledá méně uzlů než Dijkstra (který nevyužívá heuristiku) a najde nejkratší počet kroků od startu k cíli.
Stručně řečeno: A* je efektivní a univerzální algoritmus pro hledání jedné nejkratší cesty, pokud lze definovat rozumnou heuristiku. U velkých problémů nebo pro specializované požadavky však zvažte varianty a optimalizace, nebo jiné algoritmy vhodnější pro daný úkol.
Kroky
A* nejprve potřebuje seznam všech míst, kam se můžete dostat, a pak potřebuje seznam, jak daleko je cesta mezi jednotlivými místy. Pak vám řekne, jak se nejrychleji dostanete z místa A do místa Z.
Pro příklad řekneme, že A je spojeno s místy B a C a B a C jsou spojeny s D a E. D a E jsou spojeny se Z. Existují 4 možné způsoby, jak se dostat z A do Z. Můžete jít A-B-D-Z, A-C-D-Z, A-B-E-Z nebo A-C-E-Z. Počítač používající A* se nejprve podívá, jak obtížné je dostat se z A do B a z A do C. To jsou "náklady" pro tato místa. Náklady místa znamenají, jak obtížné je dostat se z místa A do tohoto místa. Po zapsání obou nákladů se počítač podívá, jak obtížné je dostat se z místa B do místa D, a přičte to k nákladům na místo B. To zapíše jako náklady na D. Pak se počítač podívá, jak obtížné je dostat se z místa C do místa D, a přičte to k nákladům místa C. To jsou jiné náklady pro D, a pokud jsou menší než ty, které už má, nahradí ty staré. Počítač chce znát pouze nejlepší cestu, takže cestu s vyššími náklady ignoruje. Zapamatuje si pouze jednu z cest A-B-D a A-C-D, podle toho, která je rychlejší.
Počítač pokračuje a najde nejrychlejší cestu do E. Nakonec se vydá z D do Z a najde náklady a z E do Z a najde náklady. Získá konečnou cenu pro Z, a to je nejmenší cena, kterou může získat. Nyní počítač ví, která cesta je nejrychlejší, a zná odpověď. Počítač může provést podobnou sérii kroků, ale s mnoha a mnoha dalšími místy. Pokaždé se podívá na místo, které je nejblíže k místu A, a sečte náklady na sousedy tohoto místa.
Lidově se výše uvedené sérii kroků říká Dijkstrův algoritmus. Dijkstrův algoritmus může být pomalý, protože se podívá na mnoho míst, která mohou jít špatným směrem ze Z. Pokud byste se počítače zeptali, jak se dostat z jednoho města do blízkého, Dijkstrův algoritmus by mohl skončit hledáním v jiném státě.
A* tento problém řeší. A* umožňuje počítači odhadnout, jak daleko to bude z každého místa na konec. Počítač může tento odhad použít k tomu, aby přibližně určil, jak daleko bude trvat cesta z určitého místa do místa Z. Místo toho, aby se podíval jen na místo, které je nejblíže k místu A, podívá se na to, které bude mít pravděpodobně nejnižší celkový součet. Tuto celkovou hodnotu zjistí tak, že k očekávané zbývající vzdálenosti přičte náklady. Tímto způsobem se může podívat pouze tím směrem, kde to bude pravděpodobně lepší. Nevadí, když odhad není dokonalý, ale i pouhý špatný odhad může program urychlit. Pokud se snažíte najít cestu mezi dvěma místy v reálném světě, je dobrým odhadem právě vzdálenost mezi nimi po přímce. Skutečná cesta přes silnice bude delší, ale díky tomu ji program odhadne a nepůjde špatným směrem.
V matematické nebo informatické literatuře je tento odhad často funkcí místa a nazývá se heuristika. Každé místo je vrchol a každá cesta mezi dvěma místy je hrana. Jedná se o slova z teorie grafů.
Vyhledávání