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.