A* to zestaw kroków (algorytm), które komputery mogą wykorzystać do określenia, jak szybko dostać się gdzieś pomiędzy dwoma miejscami. Jeśli masz listę lokalizacji i wiesz, jak trudno jest dostać się z jednej prosto do drugiej, użycie A* może szybko wskazać najszybszą drogę. Jest to algorytm podobny do algorytmu Dijkstry, ale zgaduje tak, że nie spędza tak dużo czasu próbując powolnych dróg. Jest to dobra seria kroków, jeśli chcesz tylko ścieżkę między dwoma miejscami. Jeśli zamierzasz poprosić o wiele ścieżek z tej samej mapy, to istnieją szybsze sposoby, które znajdują wszystkie odpowiedzi naraz, takie jak algorytm Floyda-Warshalla. A* nie zadziała, jeśli chcesz odwiedzić kilka miejsc podczas jednej podróży (Travelling salesman problem).

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.