Z Wikipedii

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Breadth-first search Depth-first search Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego

edytuj ten szablon

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 nie odkryte wierzchołki.

Algorytm opisany pierwotnie w 1968 roku przez Petera Harta, Nilsa Nilssona oraz Bertram Raphael. W ich pracy naukowej został nazwany algorytmem A. Ponieważ jego użycie daje optymalne zachowanie dla danej heurystyki, nazwano go A*.

[edytuj] Działanie algorytmu

Algorytm A* począwszy 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ą:

gdzie:

• g(x) - droga pomiędzy wierzchołkiem początkowym a x. Dokładniej: suma wag krawędzi jakie już należą 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 (lub jednym z wierzchołków docelowych)

[edytuj] 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. 
 
 
 zielony - wierzchołek początkowy, niebieski - wierzchołek docelowy

[edytuj] 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 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

[edytuj] Cechy algorytmu A*

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 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. Nie speł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*.

[edytuj] Przypadki graniczne

Istnieją bardziej znane algorytmy grafowe, które można osiągnąć używając A* charakterystycznym grafie i/lub z charakterystyczną heurystyką:

• Przeszukiwanie w głąb
• Przeszukiwanie wszerz
• Algorytm Dijkstry -

[edytuj] Dlaczego A* jest dopuszczalny oraz optymalny obliczeniowo?

Zakładając iż używana w algorytmie heurystyka jest dopuszczalna, możemy stwierdzić iż A* jest dopuszczalny (ang. admissible). Oznacza to, iż zawsze poda nam prawidłowe rozwiązanie, jeżeli takowe istnieje. Co więcej algorytm ten podczas działania przeszukuje mniej węzłow niż jakikolwiek inny dopuszczalny algorytm przeszukiwania z taką samą heurystyką. Dzieje się tak, gdyż A* tworzy “optymistyczne” oszacowanie kosztu ścieżki przez każdy węzeł, który bierze pod uwagę - optymistyczny w sensie, iż 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). Ale z faktu, iż te 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 nie wchodzący w skład znalezionej ścieżki. Algorytm B nie może wykluczyć, bazując na informacjach wynikających z posiadanej heurystyki, możliwości, że ścieżka przez węzeł X może mieć niższy koszt niż znaleziona ścieżka. Z tego wynika, iż jeżeli B bierze pod uwagę mniejszą ilość 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.

[edytuj] Złożoność

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

[edytuj] Bibliografia

• Ivan Bratko: PROLOG Programming for Artificial Inteligence. Addison-Wesley, 2001. ISBN 0201-40375-7. 
• Rina Dechter, Judea Pearl: Generalized best-first search strategies and the optimality of A*, vol. 32 i. 3. Journal of the ACM, 1985, ss. 505–536. DOI:10.1145/3828.3830. 

[edytuj] Linki zewnętrzne

• Tarik Attar Implementation and visualisation of the A* algorithm - Implementacja w PHP i wizualizacja z pomocą Google Maps API
• Justin Heyes-Jones A* algorithm tutorial - Tutorial o algorytmie A*
• Cuneyt Mertayak A Generic C++ A* Library - biblioteka do C++ realizująca algorytm A*