Podręcznik

4. Algorytm A-star

Algorytm A* to zaawansowana metoda znajdowania najkrótszej ścieżki pomiędzy dwoma punktami w grafie, szczególnie popularna w grach komputerowych, systemach nawigacyjnych i robotyce. Jest to algorytm informowany (heurystyczny), łączący zalety algorytmu Dijkstry i przeszukiwania best-first.

Podstawą działania algorytmu A* jest funkcja oceny f(v) = g(v) + h(v), gdzie g(v) to koszt przebycia ścieżki od punktu początkowego do węzła v, a h(v) to heurystyczna ocena kosztu dotarcia z v do punktu końcowego. Heurystyka h(v) musi być oszacowaniem nie większym niż rzeczywisty koszt, by zapewnić poprawność działania algorytmu. 

W najprostszych implementacjach najczęściej używa się następujących funkcji heurystycznych:

• standardowa odległość euklidesowa  (dla uproszczenia obliczeń zakłada się zwykle, że jeśli bok kwadratu=10, to jego przekątna ma długość równą 14) – taka funkcja zapewnia niedoszacowanie wartości odległości od celu (nie ma drogi krótszej, niż odcinek łączący dwa punkty) i tym samym znalezienie optymalnego rozwiązania.
• typu Manhattan (odległość dwóch węzłów to suma ich odległości w pionie i w poziomie – „poruszamy się po ulicach”) - nie ma ona własności niedoszacowania, ale kosztem pewności wyniku przyspiesza znacznie obliczenia.

Etapy działania algorytmu A*:

1. Inicjalizacja - tworzymy dwie główne struktury danych:
   • kolejkę otwartą (ang. open set) – zawiera węzły do odwiedzenia, uporządkowane według wartości f(v).
   • kolejkę zamkniętą (ang. closed set) – zawiera węzły już odwiedzone
   Wstawiamy wierzchołek początkowy do kolejki otwartej. Ustawiamy g(start) = 0 i f(start) = h(start).
2. Przeglądanie kolejnych wierzchołków - Dopóki kolejka otwarta nie jest pusta:
   • wybieramy wierzchołek v z najniższą wartością f(v) (czyli najbardziej obiecujący)
   • jeśli v to cel – zakończ algorytm i odtwórz ścieżkę
   • w przeciwnym razie: przenieś v do kolejki zamkniętej
3. Aktualizacja sąsiadów - dla każdego sąsiada n węzła v:
   • jeśli n jest w zamkniętej liście – pomiń
   • oblicz koszt dotarcia do n przez v: tentative_g = g( v ) + koszt(v, n)
   • jeśli n nie jest w kolejce otwartej lub tentative_g < g( n ):
     • zaktualizuj g( n ) i oblicz f( n ) = g( n ) + h( n )
     • ustaw v jako rodzica n (potrzebne do odtworzenia ścieżki)
     • jeśli n nie jest w kolejce otwartej – dodaj go
4. Zakończenie algorytmu - jeżeli kolejka otwarta stanie się pusta, a cel nie został znaleziony to nie istnieje ścieżka między punktami.