Algorytm A*

Algorytm Dijkstry znajduje najkrótszą drogę do celu, ale szuka we wszystkich kierunkach naraz, także w stronę przeciwną do celu. Algorytm A* dodaje jedną informację, oszacowanie, jak daleko jest jeszcze do celu, i nagle przeszukiwanie zmierza prosto do niego.

Graf, w którym wierzchołki z ostateczną odległością tworzą wąski pas od startu w stronę celu, z przerywaną linią prostą wskazującą cel i kolejką narysowaną pod spodem
Graf, w którym wierzchołki z ostateczną odległością tworzą wąski pas od startu w stronę celu, z przerywaną linią prostą wskazującą cel i kolejką narysowaną pod spodem

Idea

Gdy szukasz trasy na mapie, nie sprawdzasz dróg prowadzących od celu tak samo starannie jak dróg prowadzących do niego. Algorytm A* robi to samo. Każdy wierzchołek dostaje wynik: dotychczasową odległość od startu, g, plus oszacowanie pozostałej odległości, h. Przeszukiwanie zawsze idzie dalej od wierzchołka o najniższym wyniku, więc wierzchołki leżące w stronę celu idą pierwsze.

Krok po kroku

Daj startowi odległość 0 i wstaw go do kolejki z wynikiem h(start). Powtarzaj: weź wierzchołek o najniższym wyniku i oznacz jego odległość jako ostateczną. Jeśli to cel, zakończ: cofając się po zapamiętanych wierzchołkach, otrzymasz ścieżkę. W przeciwnym razie dla każdego sąsiada, który nie ma ostatecznej odległości, oblicz jego odległość przez ten wierzchołek. Jeśli jest mniejsza od dotychczasowej, obniż ją, zapamiętaj ten wierzchołek jako drogę do niego i daj sąsiadowi wynik równy nowej odległości plus jego oszacowanie. Gdy dwa wyniki są równe, wzięcie najpierw wierzchołka z mniejszym oszacowaniem zwykle szybciej prowadzi do celu.

Przykład

Weźmy start A i cel D. A–B ma długość 2 i B–D 2, a A–C ma 1 i C–D 5. Oszacowania w linii prostej do D wynoszą 3 z A, 2 z B i 3 z C. A zaczyna z wynikiem 0 + 3 = 3. Wzięcie A daje B wynik 2 + 2 = 4, a C wynik 1 + 3 = 4. Przy remisie A* bierze B, wierzchołek z mniejszym oszacowaniem, a B daje D wynik 4 + 0 = 4. D ma teraz najniższy wynik z najmniejszym oszacowaniem, więc zostaje wzięty: najkrótsza ścieżka to A → B → D, o długości 4, a C, który prowadzi w złą stronę, nigdy nie dostaje ostatecznej odległości. Algorytm Dijkstry najpierw ustaliłby ostateczną odległość C, bo to wierzchołek najbliższy A.

Dobre oszacowanie

Oszacowanie nigdy nie może być dłuższe od prawdziwej odległości do celu; takie oszacowanie nazywa się dopuszczalnym i z nim A* zawsze znajduje najkrótszą ścieżkę. Linia prosta jest dopuszczalna, bo żadna trasa nie jest krótsza od linii prostej. Jeśli w dodatku oszacowanie nigdy nie spada o więcej niż długość krawędzi między jednym wierzchołkiem a następnym, jest spójne i żadnego wierzchołka z ostateczną odległością nie trzeba już nigdy sprawdzać ponownie. Im bliżej prawdy jest oszacowanie, tym mniej wierzchołków potrzebuje A*. Oszacowanie 0 jest dopuszczalne, ale bezużyteczne: A* staje się wtedy algorytmem Dijkstry. Za duże oszacowanie przyspiesza A*, ale może przeoczyć najkrótszą ścieżkę.

Historia i zastosowania

Peter Hart, Nils Nilsson i Bertram Raphael ze Stanford Research Institute opublikowali A* w 1968 roku, pracując nad robotem Shakey, jednym z pierwszych robotów mobilnych. Ich wcześniejsze wersje nazywały się A1 i A2; gwiazdka oznaczała wersję, której optymalność udowodnili. Dziś A* prowadzi postacie wokół przeszkód w grach wideo, planuje trasy i ruchy robotów oraz rozwiązuje łamigłówki takie jak układanka 15, gdzie oszacowanie sumuje, jak daleko każdy klocek jest od swojego miejsca.

Shakey, mobilny robot Stanford Research Institute, sfotografowany w Computer History Museum. Peter Hart, Nils Nilsson i Bertram Raphael opublikowali A* w 1968, pracując nad nim.
Shakey, mobilny robot Stanford Research Institute, sfotografowany w Computer History Museum. Peter Hart, Nils Nilsson i Bertram Raphael opublikowali A* w 1968, pracując nad nim.

Wypróbuj

Otwórz aplikację i naciśnij Krok. Liczby na krawędziach to ich długości, które tu odpowiadają temu, jak długie są narysowane, a przerywana linia pokazuje oszacowanie w linii prostej do celu. Kolejka pod grafem wymienia wierzchołki według wyniku, od najniższego. Gdy cel ma ostateczną odległość, wiersz stanu porównuje, dla ilu wierzchołków A* ustalił ostateczną odległość, z tym, ilu potrzebowałby algorytm Dijkstry. Wybierz cel w dalekim rogu dużego grafu, aby zobaczyć największą różnicę.

Często zadawane pytania

Co oznacza gwiazdka w A*?

Hart, Nilsson i Raphael najpierw opisali algorytmy, które nazwali A1 i A2. A* („A gwiazdka”) to wersja, o której udowodnili, że znajduje najkrótszą ścieżkę, rozwijając najmniej wierzchołków spośród porównywalnych algorytmów z tym samym oszacowaniem, gdy oszacowanie jest spójne.

Jaka jest złożoność czasowa A*?

W najgorszym przypadku, z bezużytecznym oszacowaniem, A* wykonuje tę samą pracę co algorytm Dijkstry: O((V + E) log V) z kopcem binarnym. Z dobrym oszacowaniem ustala ostateczną odległość tylko dla części wierzchołków, dlatego w praktyce jest szybki.

Co jest dobrą heurystyką dla A*?

Powinna być szybka do obliczenia, nigdy nie przeszacowywać prawdziwej odległości i być jak najbliżej niej. Na siatce, po której można się ruszać tylko w górę, w dół, w lewo i w prawo, częstym wyborem jest odległość Manhattan; na mapie odległość w linii prostej.

Co, jeśli heurystyka przeszacowuje?

Wtedy A* może zwrócić ścieżkę, która nie jest najkrótsza, bo może skończyć, zanim sprawdzi lepszą trasę. Niektóre programy robią to celowo (ważony A*), aby oddać trochę jakości ścieżki za dużo większą szybkość.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj algorytm A*