A* Algorytm Znajdowania Ścieżki: Dijkstry z Orientacją

Dijkstra bada wszędzie. A* ma intuicję.

Algorytm Dijkstry znajduje najkrótszą ścieżkę od węzła początkowego, rozwijając frontier w kolejności kosztów: zawsze rozszerza nieodwiedzone węzły o najmniejszym dotychczasowym koszcie. Jest to poprawne i kompletne rozwiązanie, ale jest ślepe – rozszerza węzły za Tobą, obok Ciebie i przed Tobą z równie dużą energią, ponieważ nie wie, gdzie znajduje się cel. Na otwartym siatce bada dysk.

A* (Hart, Nilsson i Raphael, 1968) zmienia dokładnie jedną rzecz. Każdy węzeł jest oceniany nie przez koszt dotarcia do niego, ale przez szacowany koszt całej ścieżki przez niego: f(n) = g(n) + h(n) g(n) = dokładny koszt najkrótszej ścieżki znalezionej do tej pory od startu do n h(n) = szacunek heurystyczny pozostałego kosztu od n do celu Rozszerz węzeł z najmniejszym f, a nie z najmniejszym g. Ta pojedyncza zmiana kieruje poszukiwania w stronę celu: na otwartym siatce dysk Dijkstry przekształca się w wąską elipsę skierowaną w kierunku celu. Ustaw h = 0 i A* degeneruje dokładnie do Dijkstry; zwiększ h, a staje się to greedy best-first search, który szybko znajduje złe ścieżki, wpadając prosto w cel.

f(n) = g(n) + h(n)

g(n) = the exact cost of the best path found so far from start to n
h(n) = a HEURISTIC estimate of the remaining cost from n to the goal

Dopuszczalne, spójne i różnica, która Cię oszukuje

A* zwraca optymalną ścieżkę, jeśli heurystyka jest dopuszczalna: nigdy nie przecenia rzeczywistej pozostałej kosztów. Dopuszczalna heurystyka jest optymistyczna – może obiecywać skrót, który nie istnieje, ale nigdy nie ostrzega przed drogą, która w rzeczywistości jest tania. Przecenienie gdziekolwiek na optymalnej ścieżce może sprawić, że A* wybierze coś gorszego.

Silniejszą właściwością jest spójność (nierówność trójkątna, zwana również monotonicznością):

h(n) ≤ koszt(n, n') + h(n') dla każdego krawędzi n → n' h(cel) = 0 Spójna heurystyka jest automatycznie dopuszczalna i daje Ci coś wartościowego: f nigdy nie maleje wzdłuż ścieżki, więc pierwszego razu, kiedy A* wyciąga węzeł z kolejki, ma już optymalny koszt g dla tego węzła. Możesz więc trwale zamknąć węzeł i nigdy go ponownie nie otworzyć. Przy jedynie-dopuszczalnej-ale-nie-spójnej heurystyce musisz być przygotowany na ponowne otwarcie zamkniętych węzłów, gdy pojawi się tańsza droga do nich później, w przeciwnym razie będziesz cicho podążał za suboptymalnymi ścieżkami. Prawie każda heurystyka w tej sekcji jest spójna, dlatego większość implementacji cicho pomija gałąź ponownego otwierania i nadal działa.

h(n) ≤ cost(n, n') + h(n')     for every edge n → n'
h(goal) = 0

Wybór heurystyki dla siatki

Heurystyka musi dokładnie odpowiadać zasadom ruchu. Jest to najczęstsza przyczyna subtelnie błędnych ścieżek i bardzo wolnych wyszukiwań:

Ruch w 4 kierunkach (N/E/S/W) h = D * (|dx| + |dy|) // Manhattan Ruch w 8 kierunkach (przeciwdiagonały kosztują D2 ≈ 1,414·D) h = D * (|dx| + |dy|) + (D2 - 2*D) * min(|dx|, |dy|) // octile Ruch pod dowolnym kątem h = D * sqrt(dx*dx + dy*dy) // Euclidean Użycie odległości Manhattan na siatce 8-kierunkowej przeszacowuje – krok po przekątnej pokrywa jednostkę dx i dy za cenę 1,414, a nie 2 – dlatego heurystyka jest niedozwolona i ścieżka może być błędna. Użycie odległości euklidesowej na siatce 4-kierunkowej jest dopuszczalne, ale słabe: zawsze niedoszacowuje, więc A* eksploruje znacznie więcej węzłów niż potrzeba. Zasada mówi, że heurystyka powinna być kosztem najtańszej ścieżki pomijającej wszystkie przeszkody, zgodnie z zasadami ruchu, które faktycznie zezwalasz na użycie.

Dodatkowym problemem są powiązania. Na siatce bez przeszkód ogromna liczba ścieżek ma identyczny f, a A* błąka się przez wszystkie, eksplorując gruszkę zamiast linii. Standardowe rozwiązanie polega na rozbijaniu powiązań w kierunku prostej – delikatnie zwiększ h o czynnik około (1 + 1/oczekiwana_długość_ścieżki) lub dodaj mały człon wektorowy krzyżowy przeciwko wektorowi początkowo-celowemu. Ścieżka pozostaje optymalna w praktyce i region eksploracji drastycznie się kurczy.

4-way movement (N/E/S/W)
    h = D * (|dx| + |dy|)                       // Manhattan

8-way movement (diagonals cost D2 ≈ 1.414·D)
    h = D * (|dx| + |dy|) + (D2 - 2*D) * min(|dx|, |dy|)   // octile

any-angle movement
    h = D * sqrt(dx*dx + dy*dy)                 // Euclidean

Implementacja i gdzie faktycznie przechodzi czas

otwartość = kolejka priorytetowa (zbiór kopcowy), oznaczona wartością f start = 0; push(start, h(start)) while (otwartość nie jest pusta): aktualny = pop_min(otwartość) // O(log n) jeśli aktualny to cel: zwróć rekonstrukcję(cameFrom, aktualny) zamknięty.dodaj(aktualny) dla każdego sąsiada nb aktualnego: jeśli nb jest w zamkniętym: kontynuuj tymczasowa = g[aktualny] + koszt(aktualny, nb) jeśli (tymczasowa < g[nb]): // lepsza ścieżka do nb cameFrom[nb] = aktualny g[nb] = tymczasowa push_or_decrease_key(otwartość, nb, tymczasowa + h(nb)) Otwarty zbiór musi być kolejką priorytetową. Przeszukiwanie liniowe w poszukiwaniu minimum zamienia się w O(n) i jest przyczyną, dla której wiele ręcznie pisanych implementacji A* powoli działa. Zbiór kopcowy zapewnia O(log n) operacji popu i pusha oraz wystarcza do dowolnej siatki, którą można narysować. Dwa dodatkowe praktyczne punkty: przechowuj g i rodzica w płaskich tablicach o indeksach y*w + x zamiast w mapie skokowej oznaczonych obiektami, a jeśli kopiec nie posiada operacji zmniejszającej klucz, po prostu ponownie dodaj węzeł z lepszym f i usuń przestarzałe wpisy podczas ich wypychania (sprawdź, czy poparty f pasuje do aktualnego g + h). Wymaga to trochę pamięci i jest szybsze niż utrzymywanie indeksu.

open = priority queue (binary heap), keyed by f
g[start] = 0; push(start, h(start))

while (open not empty):
  current = pop_min(open)                 // O(log n)
  if current is goal: return reconstruct(cameFrom, current)
  closed.add(current)
  for each neighbour nb of current:
    if nb in closed: continue
    tentative = g[current] + cost(current, nb)
    if (tentative < g[nb]):               // a better route to nb
      cameFrom[nb] = current
      g[nb] = tentative
      push_or_decrease_key(open, nb, tentative + h(nb))

Warto znać różne warianty

Ważona A* f = g + w·h, gdzie w > 1. Jest to rozwiązanie niewłaściwe, ale gwarantuje ścieżkę w czynniku w od optymalnej i drastycznie przyspiesza poszukiwania. Wartość w ≈ 1,2–2 jest powszechna.

Punkt skoku (Jump Point) Na siatkach o stałej cenie (uniform-cost grids), pomija całe korytarze symetrycznych węzłów bez ich rozbudowywania. Zapewnia to ten sam optymalny szlak, często o rzędu wielkości mniej rozszerzeń.

Theta* Pozwala na ścieżki pod dowolnym kątem, pozwalając węzłowi na posiadanie dowolnego przodka z widokiem bezszwowego połączenia (line-of-sight), eliminując brzydkie schody w kształcie litery „L” produkowane przez A* dla siatki.

D* Lite Naprawia poprzednie poszukiwania, gdy mapa ulega zmianie, zamiast planować od zera – jest to standardowy wybór dla robota odkrywającego przeszkody w miarę poruszania się.

HPA* Hierarchiczny: planowanie na gruboziarnistej grafie klastrów, a następnie precyzja wewnątrz każdego klastra. Skalowalność do ogromnych map.

Weighted A*    f = g + w·h, with w > 1. Inadmissible, but the
               path is guaranteed within a factor w of optimal and
               the search is dramatically faster. w ≈ 1.2–2 is common.

Jump Point     On uniform-cost grids, skips over whole corridors of
Search (JPS)   symmetric nodes without expanding them. Same optimal
               path, often an order of magnitude fewer expansions.

Theta*         Allows any-angle paths by letting a node's parent be
               any ancestor with line-of-sight, removing the ugly
               45° staircase that grid A* produces.

D* Lite        Repairs the previous search when the map changes
               instead of replanning from scratch — the standard
               choice for a robot discovering obstacles as it moves.

HPA*           Hierarchical: plan on a coarse graph of clusters,
               refine inside each cluster. Scales to huge maps.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz A* Pathfinding i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.