Hledání cesty A*

O(E log V)

A* najde nejkratší cestu jako BFS, ale vynakládá úsilí chytře. Každá kandidátská buňka má skóre f = g + h, kde g je skutečná vzdálenost od startu a h je heuristický odhad zbývající vzdálenosti — tady manhattanská vzdálenost k cíli. Vždy rozvine otevřenou buňku s nejmenším f, takže tlačí k cíli místo slepého rozšiřování. Dokud heuristika nikdy nepřeceňuje (manhattanská vzdálenost na jednotkové mřížce je přípustná), A* zaručeně najde optimální cestu — stejně dlouhou jako BFS — a obvykle navštíví jen zlomek buněk.

Klikni na buňku pro přepnutí zdi
Mřížka
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Ohodnoť start jako f = g + h a vlož ho do otevřené množiny.
  2. Rozviň otevřenou buňku s nejnižším f.
  3. Pro každého volného souseda, je-li tahle cesta levnější, aktualizuj jeho g a přepočítej skóre.
  4. Když je rozvinut cíl, sleduj ukazatele na rodiče zpět — cesta je optimální.

Pseudokód

1aStar(grid, start, goal):            # O(E log V)2  g[start] ← 0;  open ← {start}3  while open not empty:4    cell ← node in open with least f  # f = g + h5    if cell = goal: stop6    for nbr in free neighbours(cell):7      if g[cell] + 1 < g[nbr]:8        g[nbr] ← g[cell] + 1; prev[nbr] ← cell9        f[nbr] ← g[nbr] + manhattan(nbr, goal)10        add nbr to open11  walk prev from goal back to start