Algorytm A*
Dijkstra z wyczuciem kierunku. Do kosztu każdego miejsca dodaje szacunek kosztu, który jeszcze zostaje, więc najpierw próbuje miejsc, które wyglądają na najbliższe celu.
- czas O((V + E) log V)
- pamięć O(V)
- używa kolejki priorytetowej
Co to znaczy?
- Koszt: tyle kosztuje ruch. W labiryncie wejście na zwykłe pole kosztuje 1, w błoto 3, a do wody 9; w grafie to liczba na krawędzi.
- Kolejka priorytetowa: kolejka, w której pierwszy idzie najtańszy, a nie ten, kto przyszedł pierwszy.
- Szacunek (h): przewidywany koszt, który jeszcze zostaje. A* pozostaje dokładny tylko wtedy, gdy szacunek nigdy nie jest za wysoki.
- Relaksacja krawędzi: sprawdzenie, czy przejście przez bieżące miejsce daje sąsiadowi niższy koszt, i przyjęcie go, jeśli tak.
- w kolejce
- bieżący
- gotowy
- najtańsza droga
- ziemia · 1
- błoto · 3
- woda · 9
- ściana
Nowy: Start w A1 z kosztem 0 i szacunkiem 26 do celu. To jedyny element w kolejce.
Spacja: odtwórz lub wstrzymaj. Strzałki lewo/prawo: krok. Home i End: przeskocz.
Spróbuj: Wybierz otwarte pole i przełączaj między Dijkstrą a A*: oba znajdują drogę o tym samym koszcie, ale A* zdejmuje z kolejki dużo mniej pól.
Jak to działa
A* działa jak Dijkstra, ale układa kolejkę według f = dotychczasowy koszt + h, gdzie h szacuje koszt, który jeszcze zostaje. W labiryncie h to liczba ruchów do M z pominięciem ścian i błota, w grafie odległość w linii prostej podzielona przez 10. Dopóki h nigdy nie zawyża, droga, jaką A* ma w chwili wzięcia celu, jest najtańsza, dokładnie jak u Dijkstry. Im lepszy szacunek, tym mniej miejsc trzeba obejrzeć.
Kiedy warto go użyć
A* sprawdza się, gdy szukasz jednego celu i umiesz oszacować, jak daleko jest: znajdowanie drogi w grach, roboty, planowanie tras na mapie. Przy h = 0 to dokładnie Dijkstra. Szacunek, który potrafi zawyżać, przyspiesza A*, ale może kosztować utratę najtańszej drogi.