Niniejszy artykuł jest częścią cyklu teoria grafów. |
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
Algorytm A* – algorytm przeszukiwania grafu, odnajdujący najkrótszą ścieżkę pomiędzy dwoma danymi wierzchołkami grafu (lub dokładniej: między wierzchołkiem początkowym a dowolnym z wierzchołków docelowych). Wykorzystuje heurystykę. Przy przeszukiwaniu grafu najpierw sprawdza najbardziej obiecujące, jeszcze nieodkryte wierzchołki.
Algorytm został opisany pierwotnie w 1968 roku przez Petera Harta, Nilsa Nilssona oraz Bertrama Raphaela. W ich pracy naukowej został nazwany algorytmem A. Ponieważ jego użycie daje optymalne zachowanie dla danej heurystyki, nazwano go A*.
Spis treści |
Algorytm A* od wierzchołka początkowego tworzy ścieżkę, za każdym razem wybierając wierzchołek x z dostępnych w danym kroku niezbadanych wierzchołków tak, by minimalizować funkcję 
zdefiniowaną:
gdzie:
– droga pomiędzy wierzchołkiem początkowym a x. Dokładniej: suma wag krawędzi, które należą już do ścieżki plus waga krawędzi łączącej aktualny węzeł z x.
– przewidywana przez heurystykę droga od x do wierzchołka docelowego.W każdym kroku algorytm dołącza do ścieżki wierzchołek o najniższym współczynniku f. Kończy w momencie natrafienia na wierzchołek będący wierzchołkiem docelowym.
Oto przykład działania algorytmu A* dla grafu, którego wierzchołkami są miasta, wagami krawędzi odległości drogowe, a heurystyka h(x) jest odległością w linii prostej. Przykład pokazuje prostą sytuację, w której A* wykona nawrót ze względu na niesłuszne przewidywania heurystyki.
open set i closed set nie mają nic wspólnego ze zbiorami otwartymi i domkniętymi w znaczeniu topologicznym.
function A*(start,goal) closedset := the empty set % Zbiór wierzchołków przejrzanych. openset := set containing the initial node % Zbiór wierzchołków nie odwiedzonych. g_score[start] := 0 % Długość optymalnej trasy. while openset is not empty x := the node in openset having the lowest f_score[] value if x = goal return reconstruct_path(came_from,goal) remove x from openset add x to closedset foreach y in neighbor_nodes(x) if y in closedset continue tentative_g_score := g_score[x] + dist_between(x,y) tentative_is_better := false if y not in openset add y to openset h_score[y] := heuristic_estimate_of_distance_to_goal_from(y) tentative_is_better := true elseif tentative_g_score < g_score[y] tentative_is_better := true if tentative_is_better = true came_from[y] := x g_score[y] := tentative_g_score f_score[y] := g_score[y] + h_score[y] % Przewidywany dystans od startu do celu przez y. return failure function reconstruct_path(came_from,current_node) if came_from[current_node] is set p = reconstruct_path(came_from,came_from[current_node]) return (p + current_node) else return the empty path
Algorytm A* jest kompletny – w każdym przypadku znajdzie optymalną drogę i zakończy działanie, jeśli taka droga istnieje. Heurystyka h jest dopuszczalna, jeśli nigdy nie zawyża wartości wagi na ścieżce między dowolnymi dwoma wierzchołkami, czyli: dla wierzchołków x i y:
gdzie 
oznacza faktyczną odległość między wierzchołkami x i y.
Spełnienie tego warunku gwarantuje poprawność decyzji podejmowanych przez algorytm w oparciu o heurystykę, ponieważ nie zajdzie sytuacja, w której dla pewnego x będzie większe niż faktyczna długość ścieżki z x do wierzchołka docelowego. Niespełnienie warunku oznacza, że algorytm mógłby wskazać nieoptymalną ścieżkę, jeśli dla pewnego węzła y w optymalnej ścieżce 
byłoby zawyżone.
Algorytm A* jest optymalny dla danej heurystyki, co znaczy, że nie istnieje inny algorytm, który z pomocą tej samej heurystyki odwiedziłby mniej wierzchołków niż A*.
Istnieją bardziej znane algorytmy grafowe, które można sprowadzić do algorytmu A* przy charakterystycznym grafie lub charakterystyczną heurystyką:
Zakładając, że używana w algorytmie heurystyka jest dopuszczalna, możemy stwierdzić, iż A* jest dopuszczalny (ang. admissible). Oznacza to, że zawsze poda nam prawidłowe rozwiązanie, jeżeli takowe istnieje. Co więcej, algorytm ten podczas działania przeszukuje mniej węzłów niż jakikolwiek inny dopuszczalny algorytm przeszukiwania z taką samą heurystyką. Dzieje się tak, ponieważ A* tworzy "optymistyczne" oszacowanie kosztu ścieżki przez każdy węzeł, który bierze pod uwagę – optymistyczny w tym sensie, że prawdziwy koszt ścieżki przez dany węzeł do węzła końcowego będzie co najmniej tak duży jak oszacowanie.
Kiedy A* kończy przeszukiwanie, ma (z definicji) znalezioną ścieżkę, której koszt jest mniejszy niż szacowany koszt jakiejkolwiek innej ścieżki (innej, czyli przechodzącej co najmniej przez jeden węzeł niewchodzący w skład znalezionej ścieżki). Ponieważ oszacowania są optymistyczne, algorytm A* może bezpiecznie zignorować te inne ścieżki. Innymi słowy, A* nigdy nie "przeoczy" ścieżki o niższym koszcie i dlatego jest dopuszczalny.
Przypuśćmy teraz, że jakiś inny algorytm B kończy swoje przeszukiwanie ze ścieżką, której koszt jest nie mniejszy niż szacowany koszt ścieżki przez jakiś węzeł X niewchodzący w skład znalezionej ścieżki. Algorytm B, bazując na informacjach wynikających z posiadanej heurystyki, nie może wykluczyć możliwości, że ścieżka przez węzeł X może mieć niższy koszt niż znaleziona ścieżka. Z tego wynika, że jeśli B bierze pod uwagę mniejszą liczbę węzłów niż A*, to B nie jest dopuszczalny. W związku z tym można stwierdzić, że A* bierze pod uwagę najmniejszą liczbę węzłów ze wszystkich dopuszczalnych algorytmów przeszukiwań, oczywiście pod warunkiem, że algorytmy te nie używają heurystyk dających bardziej dokładne oszacowania.
Obliczeniowa złożoność czasowa algorytmu A* zależy od zastosowanej heurystyki. W najgorszym przypadku liczba przeszukanych węzłów rośnie wykładniczo w stosunku do długości rozwiązania (najkrótszej ścieżki), natomiast rośnie już tylko wielomianowo, jeśli funkcja heurystyki h spełnia następujący warunek:
gdzie 
jest optymalną heurystyką, czyli zawsze podaje dokładny, rzeczywisty koszt ścieżki z 
do węzła końcowego. Innymi słowy, błąd funkcji h nie powinien rosnąć szybciej niż logarytm "dokładnej heurystyki" .
Bardziej problematyczne niż koszt czasowy jest zużycie pamięci przez A*. W najgorszym przypadku algorytm musi zapamiętać liczbę węzłów, która rośnie wykładniczo w stosunku do długości rozwiązania. Kilka wariantów algorytmu A* zostało stworzonych, by rozwiązać ten problem. Niektóre z nich to: IDA* (ang. iterative deepening A*), MA* (ang. memory-bounded A*), SMA* (ang. simplified memory-bounded A*) oraz RBFS (ang. recursive best-first search).
Algorytm A* znajduje zastosowanie w analizie składniowej bezkontekstowych gramatyk probabilistycznych (PCFG) w celu przyspieszenia analizy przy zachowaniu poprawności wyniku – w przeciwieństwie do niektórych metod PCFG, algorytm A* zwróci zawsze drzewo Viterbiego, czyli o maksymalnym możliwym prawdopodobieństwie, w przeciwieństwie do metod "best-first" (w języku polskim pojawiający się czasem pod ogólniejszą nazwą "algorytm zachłanny") i "finite-beam", które tego nie gwarantują.
Algorytm A* w tym zastosowaniu zaproponowali Dan Klein i Christopher Manning[1].
Dla następującej gramatyki:
| poprzednik | reguła | prawdopodobieństwo |
|---|---|---|
| S | S → NPN VP | 1 |
| VP | VP → V NPA | 0,75 |
| VP → V NPA NPG | 0,25 | |
| V | V → schował | 1 |
| PP | PP → do NPG | 1 |
| NPN | NPN → NN | 0,6 |
| NPN → NN PP | 0,4 | |
| NPG | NPG → NG | 0,7 |
| NPG → NG PP | 0,3 | |
| NPA | NPA → NA | 0,6 |
| NPA → NA PP | 0,4 | |
| NN | NN → szewc | 0,4 |
| NN → pasta | 0,3 | |
| NN → buty | 0,3 | |
| NG | NG → szewca | 0,3 |
| NG → pasty | 0,4 | |
| NG → butów | 0,3 | |
| NA | NA → szewca | 0,25 |
| NA → pastę | 0,3 | |
| NA → buty | 0,45 |
i zdania "Szewc schował pastę do butów", użytego jako przykład w artykule probabilistyczna gramatyka bezkontekstowa, w procesie rozbioru zdania trafiamy na jedną niejednoznaczność, więc możliwe scenariusze od tego momentu są następujące:
NN=Szewc, V=schował, NA=pastę, PP=do butów
Algorytm A* posługuje się heurystyką przy wyborze ścieżki. W przypadku analizy składniowej heurystyka będzie służyła do przybliżania prawdopodobnego wyniku analizy "reszty"
Poniższa ilustracja pokazuje dwie alternatywy dla analizy składniowej użytego przykładu. Dotychczasowa ścieżka jest już fragmentem poprawnie zanalizowanym (w sensie Viterbiego, kolor zielony). Wartość g(x) dla aktualnie rozważanego węzła x (kolor żółty) obliczamy zatem z prawdopodobieństw w dotychczasowym fragmencie oraz prawdopodobieństwa aktualnego węzła x, mnożąc wartość przez -1, tak aby algorytm wybierający najniższe wartości odnalazł najwyższe prawdopodobieństwo.
| S (1) | |||||||||||||||||||||||||||||||||||||||
| NPN (0,6) | VP (0,75) | ||||||||||||||||||||||||||||||||||||||
| NN (0,4) | V (1) | NPA (0,4) | |||||||||||||||||||||||||||||||||||||
| NA (0,3) | PP (1) | ||||||||||||||||||||||||||||||||||||||
| NPG (0,7) | |||||||||||||||||||||||||||||||||||||||
| NG (0,3) | |||||||||||||||||||||||||||||||||||||||
| szewc | schował | pastę | do | butów | |||||||||||||||||||||||||||||||||||
| S (1) | |||||||||||||||||||||||||||||||||||||||
| NPN (0,6) | VP (0,25) | ||||||||||||||||||||||||||||||||||||||
| NN (0,4) | V (1) | NPA (0,6) | PP (1) | ||||||||||||||||||||||||||||||||||||
| NA (0,3) | NPG (0,7) | ||||||||||||||||||||||||||||||||||||||
| NG (0,3) | |||||||||||||||||||||||||||||||||||||||
| szewc | schował | pastę | do | butów | |||||||||||||||||||||||||||||||||||
Heurystyka używana przez algorytm A* oparta jest o (zwykle nie wszystkie) pozostałe węzły (kolor czerwony) – musi pozwalać na oszacowanie prawdopodobieństwa wyniku pozostałej części procesu analizy składniowej, przy ustalonym już, uprzednio przeanalizowanym fragmencie. Manning i Klein w rozdziale 3 swojego artykułu pośród proponowanych heurystyk wymieniają m.in.:
Więcej szczegółów na temat tych dwóch heurystyk można znaleźć w punktach 3.1 i 3.2 wspomnianego artykułu[1].
Panowie Manning i Klein deklarują, że zastosowanie algorytmu A* z opracowanymi przez nich heurystykami dało w rezultacie redukcję liczby odwiedzanych podczas analizowania węzłów nawet do mniej niż 3% dotychczas odwiedzanych przez metody klasyczne ("exhaustive parsing"). Dla innych zaproponowanych heurystyk wartość ta wynosiła również po kilka procent.
