A* (A-star) — heurystyczny algorytm znajdowania najkrótszej ścieżki

Co to jest A* — krótki opis

A* to algorytm wyszukiwania najkrótszej (najtańszej) ścieżki w grafie, który łączy podejście przeszukiwania najlepiej-rosnącego (best-first search) z informacją heurystyczną. Dla każdego węzła oblicza się wartość:

• g(n) — koszt najtańszej znalezionej dotąd ścieżki od węzła startowego do węzła n,
• h(n) — heurystyczne oszacowanie kosztu najtańszej ścieżki z węzła n do celu,
• f(n) = g(n) + h(n) — szacowany całkowity koszt przejścia przez n do celu.

Algorytm wybiera do rozwinięcia węzeł o najmniejszym f(n), co sprawia, że kieruje się jednocześnie znanym kosztem i przewidywanym kosztem do celu.

Własności heurystyki

• Admissible (dopuszczalna) — heurystyka nie przeszacowuje rzeczywistego kosztu do celu: dla wszystkich n h(n) ≤ rzeczywisty koszt do celu. Gwarantuje to optymalność A* (znajdzie najtańszą ścieżkę).
• Consistent/Monotoniczna (spójna) — dla każdej krawędzi (n→m) zachodzi h(n) ≤ koszt(n,m) + h(m). Spójność upraszcza implementację (nie trzeba ponownie rozważać węzłów w otwartym zbiorze) i również zapewnia optymalność.

Przykłady heurystyk dla siatek 2D: Manhattan (odległość L1) nadaje się gdy ruch jest tylko w czterech kierunkach, Euclidean (odległość w linii prostej) gdy ruch jest dowolny kierunkowo. Jeżeli ustawimy h(n)=0, A* zachowuje się jak algorytm Dijkstry.

Właściwości algorytmu

• Kompletność — A* jest kompletny, jeśli graf ma skończoną liczbę węzłów lub heurystyka nie prowadzi do nieskończonego eksplorowania stanów.
• Optymalność — jeśli heurystyka jest dopuszczalna (i często spójna), A* znajdzie optymalną ścieżkę.
• Złożoność czasowa i pamięciowa — w najgorszym przypadku (słaba lub zerowa heurystyka) złożoność może rosnąć wykładniczo w rozmiarze przestrzeni stanu. A* zwykle wymaga dużej pamięci, ponieważ przechowuje otwarty i zamknięty zbiór węzłów.

Jak zaimplementować A* — podstawowe kroki

• Utwórz zbiór otwarty (open set) i dodaj węzeł startowy z g(start)=0 i f=start+h(start).
• Utwórz zbiór zamknięty (closed set) na węzły już odwiedzone.
• Póki open set nie jest pusty:
  • Wyjmij węzeł n o najmniejszym f(n).
  • Jeśli n jest celem — zakończ i odtwórz ścieżkę korzystając z wskaźników do rodzica.
  • Dla każdego sąsiada m węzła n policz proponowany koszt g_temp = g(n) + koszt(n,m). Jeśli m nie jest w open lub g_temp < g(m), zaktualizuj g(m), ustaw rodzica m na n i ustaw f(m) = g(m) + h(m). Jeśli m nie jest w open — dodaj go.
  • Przenieś n do closed set.

W praktycznej implementacji open set przechowuje się w kolejce priorytetowej (min-heap) indeksowanej po f(n), a closed set jako hash/zestaw do szybkiego sprawdzania odwiedzin. Przydatne jest też przechowywanie mapy rodziców dla odtwarzania zakończonej ścieżki.

Praktyczne uwagi i optymalizacje

• Wybór heurystyki — im dokładniejsza, ale dopuszczalna heurystyka, tym mniej węzłów zostanie zbadanych. Zbyt optymistyczne (niska) h zwiększy koszt wyszukiwania; zbyt pesymistyczna (przeszacowana) może utracić optymalność.
• Tie-breaking — przy równych f można preferować większe g (bliżej startu) lub mniejsze h; wpływa to na kształt ścieżki i szybkość znalezienia rozwiązania.
• Memory-bounded A* — wersje takie jak IDA* (iterative deepening A*) używają mniej pamięci kosztem dodatkowych przejść, co jest przydatne przy ograniczeniach pamięciowych.
• Weighted A* — mnożnik przy heurystyce (f = g + w*h, w>1) przyspiesza wyszukiwanie kosztem utraty gwarancji optymalności; stosowane, gdy potrzebne jest szybkie rozwiązanie przy akceptowalnej jakości.
• Bidirectional A* — jednoczesne przeszukiwanie od startu i od celu może znacząco skrócić przestrzeń przeszukiwania, ale wymaga odpowiedniego dopasowania heurystyk.

Zastosowania

• Planowanie ścieżek w grach komputerowych i symulacjach (ruch jednostek po siatce).
• Nawigacja robotów i pojazdów autonomicznych (planowanie trasy z uwzględnieniem przeszkód i kosztów).
• Rozwiązywanie problemów kombinatorycznych modelowanych jako grafy (np. puzzle przesuwne), o ile cel jest pojedynczy.
• Systemy trasowe i logistyka, kiedy poszukujemy pojedynczej optymalnej trasy między dwoma punktami.

Ograniczenia

• A* nie jest efektywny, gdy trzeba równocześnie znaleźć optymalne trasy dla wielu par punktów — wtedy lepsze mogą być algorytmy wielopunktowe jak Floyd-Warshall lub precomputing struktur (np. contraction hierarchies dla map drogowych).
• Przy problemach typu Travelling Salesman Problem (wielu celów wymagających odwiedzin) A* w prostej postaci nie jest odpowiedni — wymagane są modyfikacje lub inne algorytmy heurystyczne/metryczne.
• Złożoność pamięciowa może być krytyczna — A* przechowuje dużą część grafu w pamięci, co dla wielkich przestrzeni stanów bywa niepraktyczne.

Podsumowując, A* to uniwersalny i mocny algorytm do znajdowania najkrótszych ścieżek pomiędzy dwoma punktami, o ile dobierzemy odpowiednią heurystykę i uwzględnimy ograniczenia pamięciowe. W praktyce jest to jedna z najczęściej stosowanych metod w grach, robotyce i systemach nawigacyjnych.