Algorytm A*

Algorytm A*

Rodzaj	Znajdowanie najkrótszej ścieżki
Struktura danych	graf
Złożoność
Czasowa	$O(|E|)=O(b^{d})$
Pamięciowa	$O(|V|)=O(b^{d})$

Algorytm A* – algorytm heurystyczny znajdowania najkrótszej ścieżki w grafie ważonym z dowolnego wierzchołka do wierzchołka spełniającego określony warunek zwany testem celu. Algorytm jest zupełny i optymalny, w tym sensie, że znajduje ścieżkę, jeśli tylko taka istnieje, i przy tym jest to ścieżka najkrótsza. Stosowany głównie w dziedzinie sztucznej inteligencji do rozwiązywania problemów i w grach komputerowych do imitowania inteligentnego zachowania.

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*.

Działanie algorytmu

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ę $f(x)$ zdefiniowaną:

$f(x)=g(x)+h(x),$

gdzie:

• $g(x)$ – 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.$
• $h(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.

Przykład ilustrujący działanie

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.

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. Zielony – wierzchołek początkowy, niebieski – wierzchołek docelowy

Algorytm A* w pseudokodzie

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 nieodwiedzonych, sąsiadujących z odwiedzonymi.
     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

Cechy algorytmu A*

Algorytm A* jest kompletny – w każdym przypadku znajdzie optymalną drogę i zakończy działanie, jeśli taka droga istnieje. Jeśli heurystyka $h$ jest dopuszczalna (czyli nigdy nie zawyża wartości wagi na ścieżce między dowolnymi dwoma wierzchołkami) to algorytm A* jest dopuszczalny, o ile nie używamy zamkniętego zbioru. Jeśli natomiast zbiór jest zamknięty, to aby algorytm A* był dopuszczalny heurystyka $h$ musi być spójna, czyli dla wierzchołków $x$ i $y{:}$

$h(x)\leqslant d(x,y)+h(y),$

gdzie $d(x,y)$ 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 $h(x)$ 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 $h(y)$ 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*.

Przypadki graniczne

Istnieją bardziej znane algorytmy grafowe, które można sprowadzić do algorytmu A* przy charakterystycznym grafie lub charakterystyczną heurystyką:

• przeszukiwanie w głąb
• przeszukiwanie wszerz
• algorytm Dijkstry – $\forall x\ h(x)=0$

Dlaczego A* jest dopuszczalny oraz optymalny obliczeniowo?

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.

Złożoność czasowa

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:

$|h(x)-h^{*}(x)|=O(\log h^{*}(x)),$

gdzie $h^{*}$ jest optymalną heurystyką, czyli zawsze podaje dokładny, rzeczywisty koszt ścieżki z $x$ do węzła końcowego. Innymi słowy, błąd funkcji $h$ nie powinien rosnąć szybciej niż logarytm „dokładnej heurystyki” $h^{*}.$

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).

Zastosowanie

Algorytm A* w analizie składniowej PCFG

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.

Przykład działania

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

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.:

1. Możliwość wcześniejszego przygotowania oszacowań dla gramatyki jeżeli nie jest bardzo skomplikowana i przechowywanie ich – złożoność obliczeniowa takiej heurystyki jest na poziomie stałej jeśli pominiemy czas spędzony na przygotowywaniu danych.
2. Stworzenie uproszczonej gramatyki będącej przybliżeniem rozpatrywanej i szacowanie wyników na jej podstawie, co jest dużo szybsze niż analizowanie wyjściowej gramatyki.

Więcej szczegółów na temat tych dwóch heurystyk można znaleźć w punktach 3.1 i 3.2 wspomnianego artykułu.

Efekty

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.

Bibliografia

• Ivan Bratko: Prolog programming for artificial intelligence. Harlow, Anglia: Addison Wesley, 2001. ISBN 0-201-40375-7.brak strony w książce
• Rina Dechter, Judea Pearl. Generalized best-first search strategies and the optimality of A*. „Journal of the ACM”. 32 (3), s. 505–536, 1985. DOI: 10.1145/3828.3830. 

Linki zewnętrzne

• Justin Heyes-Jones A* algorithm tutorial – Tutorial o algorytmie A*
• Cuneyt Mertayak A Generic C++ A* Library – biblioteka do C++ realizująca algorytm A*
• A* Search Algorithm in JavaScript (Updated) – Brian Grinstead – strona o implementacji algorytmu A* w JavaScript (link do kodu źródłowego na licencji MIT w treści strony)