Dijkstra i A*: Wyjaśnienie algorytmów najkrótszej ścieżki

Grafy, wagi i relaksacja

Graf G = (V, E) składa się z wierzchołków i krawędzi; w grafie ważonym każda krawędź (u, v) ma nieujemną wagę w(u,v), reprezentującą odległość, czas lub inny rodzaj nakładki. Algorytmy najkrótszych ścieżek szukają minimalnej kosztowej ścieżki z źródła do jednego lub wszystkich innych wierzchołków, a prawie wszystkie z nich dzielą się wspólną operacją – relaksacją: jeśli nowo odkryta ścieżka do v jest tańsza niż najlepsza znana dotychczas, to ją aktualizuje.

Relaxation:
  if d[v] > d[u] + w(u,v):
      d[v] = d[u] + w(u,v)
      parent[v] = u

d[v] = current best known distance from source to v
Initially: d[s] = 0, d[v] = ∞ for all other v

Algorytm Dijkstry

Dijkstra (1959) przetwarza wierzchołki według ich przybliżonej najkrótszej odległości, używając kolejki priorytetowej: powtarzająco wyjmują wierzchołek o najmniejszej znanej odległości i rozluźnia każdą krawędź prowadzącą stamtąd. Ponieważ wagi krawędzi są nieujemne, raz wyjęty wierzchołek ma dowolnie zdefiniowaną odległość — żaden nieprzetworzony wierzchołek nie mógłby nigdy zaproponować drogi do niego tańszej. Ta gwarancja przerwuje się, gdy pozwolimy na ujemne wagi krawędzi, co jest powodem dla czego algorytm Dijkstra wymaga Bellmana-Forda (O(VE), obsługuje ujemne wagi, wykrywa ujemne cykle) jako alternatywy. Wydajność zależy heavily od kolejki priorytetowej: nieuporządkowana tablica daje O(V²), odpowiednia dla gęstych grafów; drzewo binarne daje O((V+E) log V), praktyczny wybór dla rzadkich grafów typowych dla sieci drogowych, gdzie algorytm Dijkstra z drzewem binarnym na mapie miasta zawierającej milion węzłów działa w przybliżonym czasie 50-100ms.

Szukanie A* i heurystyki

A* (Hart, Nilsson, Raphael, 1968) ulepsza Dijkstrę dla poszukiwań z jednym celem poprzez dodanie heurystyki h(v), szacunku kosztu pozostającego od v do celu:

f(v) = g(v) + h(v) g(v) = dokładny koszt od źródła do v (taki sam jak w Dijkstrze d[v]) h(v) = heurystyczny szacunek kosztu od v do celu Podstawowe heurystyki: Odległość euklidesowa: h(v) = √((x_v−x_t)² + (y_v−y_t)²) Odległość manhattanowska: h(v) = |x_v−x_t| + |y_v−y_t| (grafovy siatkowe) Dijkstra rozpyla się w koncentrycznych kręgach od źródła; A*, sortując swoją kolejkę priorytetową według f zamiast g, rozpyla elipsę skierowaną ku celowi — w grafach typu sieci drogowych zwykle rozważa 5 do 100 razy mniej wierzchołków. Gwarancja, że A* nadal znajduje prawdziwie optymalny ścieżkę zależy od admissibilności: h(v) nigdy nie może przewyższać rzeczywistego pozostającego kosztu. Odległość euklidesowa i manhattanowska są obie admissible (i zgodne, spełniając nierówność trójkąta, która unika ponownego otwierania wierzchołków); heurystyka zawsze zwracająca zero jest trivialnie admissible i zmniejsza A* do prostego Dijkstry. Warianty ważone, takie jak f = g + w·h z w > 1, są nieadmissible, ale szybsze, zapewniając tylko ścieżkę w zakresie (1+ε) od optymalnej — typowe compromisy w AI do czasu rzeczywistego.

f(v) = g(v) + h(v)
  g(v) = exact cost from source to v   (same as Dijkstra's d[v])
  h(v) = heuristic estimate of cost from v to the goal

Common heuristics:
  Euclidean distance:  h(v) = √((x_v−x_t)² + (y_v−y_t)²)
  Manhattan distance:  h(v) = |x_v−x_t| + |y_v−y_t|   (grid graphs)

Warianty i zastosowanie w praktyce

Systemy produkcyjne dodają nadal więcej sztuczek: wyszukiwanie dwukierunkowe działa od źródła i docelowego punktu jednocześnie, spotykając się na połowie; Punkt Saltania przycinanie dużych ilości węzłów intermedyarnych na siatkach o stałej kosztowości dla przyspieszenia 10-100 razy; Hierarchie kontraktowe przerabiają wcześniej skróty drobne przedmiotem oferty, co pozwala na zapytanie o trasę długości 1000 km w sieci drogowej kontynentowej w miliardzie sekundy. Google Maps, Apple Maps i Waze używają wariantów tych technik z danymi ruchu w czasie rzeczywistym. Motorzy gier wykonują tysiące zapytań A* na sekundę nad siatkami nawigacyjnymi do znalezienia ścieżek NPC, routery internetowe wykonują bezpośrednio algorytm Dijkstry na bazach danych stanu połączeń dla routingu OSPF, a roboty używają D* Lite do efektywnego ponawiania planów podczas zmiany ich mapy świata — ta sama podstawowa idea odkryta w 1956 roku nadal routuje samoloty, pakiety i piksele dzisiaj.

Często zadawane pytania

Wypróbuj na żywo

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