Algorytm A*
![]() | |
Rodzaj | Znajdowanie najkrótszej ścieżki |
---|---|
Struktura danych | graf |
Złożoność | |
Czasowa |
|
Pamięciowa |
|
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 z dostępnych w danym kroku niezbadanych wierzchołków tak, by minimalizować funkcję zdefiniowaną:
gdzie:
- – droga pomiędzy wierzchołkiem początkowym a Dokładniej: suma wag krawędzi, które należą już do ścieżki plus waga krawędzi łączącej aktualny węzeł z
- – przewidywana przez heurystykę droga od do wierzchołka docelowego.
W każdym kroku algorytm dołącza do ścieżki wierzchołek o najniższym współczynniku 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 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](http://upload.wikimedia.org/wikipedia/commons/5/5d/AstarExample.gif)
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 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 musi być spójna, czyli dla wierzchołków i
gdzie oznacza faktyczną odległość między wierzchołkami i
Spełnienie tego warunku gwarantuje poprawność decyzji podejmowanych przez algorytm w oparciu o heurystykę, ponieważ nie zajdzie sytuacja, w której dla pewnego będzie większe niż faktyczna długość ścieżki z do wierzchołka docelowego. Niespełnienie warunku oznacza, że algorytm mógłby wskazać nieoptymalną ścieżkę, jeśli dla pewnego węzła 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*.
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 –
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 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 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).
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[1].
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.:
- 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.
- 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[1].
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.
Przypisy
Bibliografia
- Ivan Bratko: Prolog programming for artificial intelligence. Harlow, Anglia: Addison Wesley, 2001. ISBN 0-201-40375-7.
- 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)
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów | |
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |