Algorytm wyszukiwania A* - A* search algorithm

Klasa	Algorytm wyszukiwania
Struktura danych	Wykres
Wydajność w najgorszym przypadku	${\ Displaystyle O (| E |) = O (b ^ {d})}$
Najgorsza złożoność przestrzeni	${\ Displaystyle O (| V |) = O (b ^ {d})}$

A* (wymawiane „A-star”) to algorytm przechodzenia przez graf i wyszukiwania ścieżki , który jest często używany w wielu dziedzinach informatyki ze względu na swoją kompletność, optymalność i optymalną wydajność. Jedną z głównych praktycznych wad jest jego złożoność przestrzenna, ponieważ przechowuje wszystkie wygenerowane węzły w pamięci. Tak więc w praktycznych systemach wyznaczania tras podróży jest on generalnie lepszy od algorytmów, które mogą wstępnie przetwarzać graf w celu uzyskania lepszej wydajności, a także podejść ograniczonych pamięcią; jednak A* jest nadal najlepszym rozwiązaniem w wielu przypadkach. ${\ Displaystyle O (b ^ {d})}$

Peter Hart , Nils Nilsson i Bertram Raphael ze Stanford Research Institute (obecnie SRI International ) po raz pierwszy opublikowali algorytm w 1968 roku. Można go postrzegać jako rozszerzenie algorytmu Dijkstry . A* osiąga lepszą wydajność, używając heurystyki do kierowania wyszukiwaniem.

Historia

A* został wymyślony przez naukowców pracujących nad planowaniem ścieżki robota Shakey.

A* powstał w ramach projektu Shakey , którego celem było zbudowanie robota mobilnego zdolnego do planowania własnych działań. Nils Nilsson pierwotnie zaproponował użycie algorytmu Graph Traverser do planowania ścieżki Shakeya. Graph Traverser kieruje się funkcją heurystyczną h ( n ) , szacowaną odległością od węzła n do węzła docelowego: całkowicie ignoruje g ( n ) , odległość od węzła początkowego do węzła n . Bertram Raphael zasugerował użycie sumy g ( n ) + h ( n ) . Peter Hart wynalazł koncepcje, które teraz nazywamy dopuszczalnością i spójnością funkcji heurystycznych. A* został pierwotnie zaprojektowany do znajdowania ścieżek o najniższym koszcie, gdy koszt ścieżki jest sumą jej kosztów, ale wykazano, że A* może być użyty do znalezienia optymalnych ścieżek dla dowolnego problemu spełniającego warunki algebry kosztów.

Oryginalna praca A* z 1968 r. zawierała twierdzenie, że żaden algorytm podobny do A* nie może rozwinąć mniejszej liczby węzłów niż A*, jeśli funkcja heurystyczna jest spójna, a reguła rozstrzygania remisów A* jest odpowiednio dobrana. Kilka lat później opublikowano „korektę”, w której stwierdzono, że spójność nie jest wymagana, ale okazało się to fałszywe w ostatecznym badaniu Dechtera i Pearla dotyczącym optymalności A* (obecnie określanym jako efektywność optymalna), który podał przykład A* z heurystyką, która była dopuszczalna, ale niespójna, rozszerzając arbitralnie więcej węzłów niż alternatywny algorytm podobny do A*.

Opis

A* jest świadomym algorytmem wyszukiwania lub wyszukiwaniem najlepszym-pierwszym , co oznacza, że ​​jest sformułowany w kategoriach grafów ważonych : zaczynając od określonego węzła początkowego grafu, ma on na celu znalezienie ścieżki do danego węzła celu o najmniejszym koszt (najmniejsza przebyta odległość, najkrótszy czas itp.). Robi to, utrzymując drzewo ścieżek rozpoczynających się w węźle początkowym i rozszerzając te ścieżki o jedną krawędź na raz, aż do spełnienia kryterium zakończenia.

W każdej iteracji swojej głównej pętli A* musi określić, która z jego ścieżek ma się rozciągać. Czyni to w oparciu o koszt ścieżki i oszacowanie kosztu wymaganego do wydłużenia ścieżki aż do celu. W szczególności A* wybiera ścieżkę, która minimalizuje

${\ Displaystyle f (n) = g (n) + h (n)}$

gdzie n to następny węzeł na ścieżce, g ( n ) to koszt ścieżki od węzła początkowego do n , a h ( n ) to funkcja heurystyczna, która szacuje koszt najtańszej ścieżki od n do celu. A* kończy się, gdy ścieżka, którą wybierze do przedłużenia, jest ścieżką od początku do celu lub jeśli nie ma ścieżek kwalifikujących się do przedłużenia. Funkcja heurystyczna jest specyficzna dla problemu. Jeśli funkcja heurystyczna jest dopuszczalna , co oznacza, że ​​nigdy nie przeszacowuje rzeczywistego kosztu dotarcia do celu, A* gwarantuje zwrócenie ścieżki o najniższym koszcie od początku do celu.

Typowe implementacje A* wykorzystują kolejkę priorytetową do wykonania powtórnego wyboru węzłów o minimalnym (szacowanym) koszcie do rozbudowy. Ta kolejka priorytetowa nazywana jest zestawem otwartym lub marginesem . Na każdym kroku algorytmu węzeł z najniższą wartością f ( x ) jest usuwany z kolejki, wartości f i g jego sąsiadów są odpowiednio aktualizowane i sąsiedzi ci są dodawani do kolejki. Algorytm jest kontynuowany do momentu, gdy usunięty węzeł (a zatem węzeł z najniższą wartością f spośród wszystkich węzłów brzegowych) stanie się węzłem docelowym. Wartość f tego celu jest wówczas również kosztem najkrótszej ścieżki, ponieważ h przy celu wynosi zero w dopuszczalnej heurystyce.

Opisany dotychczas algorytm podaje nam tylko długość najkrótszej ścieżki. Aby znaleźć rzeczywistą sekwencję kroków, algorytm można łatwo zmienić, tak aby każdy węzeł na ścieżce śledził swojego poprzednika. Po uruchomieniu tego algorytmu węzeł końcowy będzie wskazywał na swojego poprzednika i tak dalej, dopóki poprzednik jakiegoś węzła nie będzie węzłem początkowym.

Na przykład podczas wyszukiwania najkrótszej trasy na mapie h ( x ) może reprezentować odległość w linii prostej do celu, ponieważ jest to fizycznie najmniejsza możliwa odległość między dowolnymi dwoma punktami. W przypadku mapy siatkowej z gry wideo użycie odległości Manhattan lub odległości oktylu staje się lepsze w zależności od dostępnego zestawu ruchów (4-kierunkowych lub 8-kierunkowych).

Algorytm odnajdywania ścieżki* poruszający się po losowo generowanym labiryncie

Odtwórz multimedia

Ilustracja wyszukiwania A* w celu znalezienia ścieżki między dwoma punktami na wykresie.

Jeśli heurystyka h spełnia dodatkowy warunek h ( x ) ≤ d ( x , y ) + h ( y ) dla każdej krawędzi ( x , y ) grafu (gdzie d oznacza długość tej krawędzi), wówczas wywoływane jest h monotonne lub spójne . Dzięki spójnej heurystyce, A* gwarantuje znalezienie optymalnej ścieżki bez przetwarzania żadnego węzła więcej niż raz, a A* jest równoważne z uruchomieniem algorytmu Dijkstry z obniżonym kosztem d' ( x , y ) = d ( x , y ) + h ( y ) - h ( x ) .

Pseudo kod

Poniższy pseudokod opisuje algorytm:

function reconstruct_path(cameFrom, current)
    total_path := {current}
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.prepend(current)
    return total_path

// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
    // The set of discovered nodes that may need to be (re-)expanded.
    // Initially, only the start node is known.
    // This is usually implemented as a min-heap or priority queue rather than a hash-set.
    openSet := {start}

    // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start
    // to n currently known.
    cameFrom := an empty map

    // For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
    gScore := map with default value of Infinity
    gScore[start] := 0

    // For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
    // how short a path from start to finish can be if it goes through n.
    fScore := map with default value of Infinity
    fScore[start] := h(start)

    while openSet is not empty
        // This operation can occur in O(1) time if openSet is a min-heap or a priority queue
        current := the node in openSet having the lowest fScore[] value
        if current = goal
            return reconstruct_path(cameFrom, current)

        openSet.Remove(current)
        for each neighbor of current
            // d(current,neighbor) is the weight of the edge from current to neighbor
            // tentative_gScore is the distance from start to the neighbor through current
            tentative_gScore := gScore[current] + d(current, neighbor)
            if tentative_gScore < gScore[neighbor]
                // This path to neighbor is better than any previous one. Record it!
                cameFrom[neighbor] := current
                gScore[neighbor] := tentative_gScore
                fScore[neighbor] := gScore[neighbor] + h(neighbor)
                if neighbor not in openSet
                    openSet.add(neighbor)

    // Open set is empty but goal was never reached
    return failure

Uwaga: W tym pseudokodzie, jeśli do węzła dotrze jedna ścieżka, zostanie usunięty z openSet, a następnie zostanie osiągnięty tańszą ścieżką, zostanie on ponownie dodany do openSet. Jest to niezbędne, aby zagwarantować, że zwracana ścieżka jest optymalna, jeśli funkcja heurystyczna jest dopuszczalna, ale niespójna . Jeśli heurystyka jest spójna, po usunięciu węzła z openSet ścieżka do niego jest optymalna, więc test 'tentative_gScore < gScore[sąsiad]' zawsze zakończy się niepowodzeniem, jeśli węzeł zostanie ponownie osiągnięty.

Ilustracja wyszukiwania A* w celu znalezienia ścieżki od węzła początkowego do węzła docelowego w problemie planowania ruchu robota . Puste kółka reprezentują węzły w zbiorze otwartym , czyli te, które pozostają do zbadania, a wypełnione są w zbiorze zamkniętym. Kolor na każdym zamkniętym węźle wskazuje odległość od celu: im bardziej zielony, tym bliżej. Najpierw widać, że A* porusza się w linii prostej w kierunku celu, a następnie uderzając w przeszkodę, bada alternatywne trasy przez węzły z otwartego zbioru.

Zobacz także: algorytm Dijkstry

Przykład

Przykład działania algorytmu A*, w którym węzłami są miasta połączone drogami, a h(x) to odległość w linii prostej do punktu docelowego:

Klucz: zielony: start; niebieski: bramka; pomarańczowy: odwiedzony

Algorytm A* ma również zastosowania w świecie rzeczywistym. W tym przykładzie krawędzie to tory kolejowe, a h(x) to odległość po wielkim okręgu (najkrótsza możliwa odległość na kuli) do celu. Algorytm szuka ścieżki między Waszyngtonem, DC a Los Angeles.

Szczegóły dotyczące wdrożenia

Istnieje szereg prostych optymalizacji lub szczegółów implementacji, które mogą znacząco wpłynąć na wydajność implementacji A*. Pierwszym szczegółem, na który należy zwrócić uwagę, jest to, że sposób, w jaki kolejka priorytetowa obsługuje powiązania, może mieć znaczący wpływ na wydajność w niektórych sytuacjach. Jeśli powiązania zostaną zerwane, więc kolejka zachowuje się w sposób LIFO , A* będzie zachowywać się jak wyszukiwanie w głąb wśród ścieżek o równych kosztach (unikając eksploracji więcej niż jednego równie optymalnego rozwiązania).

Gdy na końcu wyszukiwania wymagana jest ścieżka, często w każdym węźle znajduje się odniesienie do rodzica tego węzła. Pod koniec wyszukiwania te odniesienia mogą być wykorzystane do odzyskania optymalnej ścieżki. Jeśli te odniesienia są zachowywane, może być ważne, aby ten sam węzeł nie pojawiał się w kolejce priorytetów więcej niż raz (każdy wpis odpowiada innej ścieżce do węzła i każdy z innym kosztem). Standardowym podejściem jest tutaj sprawdzenie, czy węzeł, który ma zostać dodany, znajduje się już w kolejce priorytetowej. Jeśli tak, to wskaźniki priorytetu i rodzica są zmieniane tak, aby odpowiadały ścieżce o niższym koszcie. Standardowa kolejka priorytetów oparta na stercie binarnej nie obsługuje bezpośrednio operacji wyszukiwania jednego z jej elementów, ale można ją rozszerzyć o tablicę mieszającą, która mapuje elementy na ich pozycję w stercie, umożliwiając wykonanie tej operacji zmniejszania priorytetu w czas logarytmiczny. Alternatywnie, sterta Fibonacciego może wykonywać te same operacje o priorytecie zmniejszania w stałym zamortyzowanym czasie .

Przypadki specjalne

Algorytm Dijkstry , jako kolejny przykład algorytmu wyszukiwania o jednolitym koszcie, może być postrzegany jako szczególny przypadek A* gdzie dla wszystkich x . Ogólne wyszukiwanie w głąb może być zaimplementowane za pomocą A*, biorąc pod uwagę, że istnieje globalny licznik C zainicjowany z bardzo dużą wartością. Za każdym razem, gdy przetwarzamy węzeł, przypisujemy C do wszystkich jego nowo odkrytych sąsiadów. Po każdym pojedynczym zadaniu zmniejszamy licznik C o jeden. Zatem im wcześniej dany węzeł zostanie odkryty, tym wyższa będzie jego wartość. Zarówno algorytm Dijkstry, jak i wyszukiwanie w głąb mogą być zaimplementowane wydajniej bez uwzględniania wartości w każdym węźle. ${\ Displaystyle h (x) = 0}$${\ Displaystyle h (x)}$${\ Displaystyle h (x)}$

Nieruchomości

Zakończenie i kompletność

Na grafach skończonych z nieujemnymi wagami krawędzi A* ma gwarantowane zakończenie i jest kompletne , tj. zawsze znajdzie rozwiązanie (ścieżkę od początku do celu), jeśli takie istnieje. Na nieskończonych grafach ze skończonym współczynnikiem rozgałęzienia i kosztami krawędzi, które są ograniczone od zera ( dla niektórych stałych ), A* ma gwarancję zakończenia tylko wtedy, gdy istnieje rozwiązanie. ${\textstyle d(x,y)>\varepsilon >0}$${\displaystyle \varepsilon}$

Dopuszczalność

Mówi się, że algorytm wyszukiwania jest dopuszczalny, jeśli gwarantuje zwrócenie optymalnego rozwiązania. Jeżeli funkcja heurystyczna używana przez A* jest dopuszczalna , to A* jest dopuszczalne. Intuicyjny „dowód” tego jest następujący:

Kiedy A* kończy wyszukiwanie, znalazł ścieżkę od początku do celu, której rzeczywisty koszt jest niższy niż szacowany koszt dowolnej ścieżki od początku do celu przez dowolny otwarty węzeł (wartość węzła ). Gdy heurystyka jest dopuszczalna, te szacunki są optymistyczne (niezupełnie — patrz następny akapit), więc A* może bezpiecznie zignorować te węzły, ponieważ nie mogą one prowadzić do rozwiązania tańszego niż to, które już posiada. Innymi słowy, A* nigdy nie przeoczy możliwości stworzenia ścieżki o niższych kosztach od początku do celu, więc będzie kontynuować poszukiwania, dopóki nie będzie takich możliwości. ${\displaystyle f}$

Rzeczywisty dowód jest nieco bardziej skomplikowany, ponieważ wartości otwartych węzłów nie gwarantują optymizmu, nawet jeśli heurystyka jest dopuszczalna. Dzieje się tak, ponieważ wartości otwartych węzłów nie są gwarantowane jako optymalne, więc suma nie jest gwarantowana, aby była optymistyczna. ${\displaystyle f}$${\displaystyle g}$${\displaystyle g+h}$

Optymalna wydajność

Algorytm A jest optymalnie wydajny w odniesieniu do zbioru alternatywnych algorytmów Alts na zbiorze problemów P jeśli dla każdego problemu P w P i każdego algorytmu A′ w Alts zbiór węzłów rozwinięty przez A w rozwiązywaniu P jest podzbiorem (prawdopodobnie równe) zbioru węzłów rozszerzonego o A′ w rozwiązaniu P. Ostateczne badanie optymalnej sprawności A* jest dziełem Riny Dechter i Judei Pearl. Rozważali różne definicje Alt i P w połączeniu z heurystyką A*, która jest po prostu dopuszczalna lub zarówno spójna, jak i dopuszczalna. Najciekawszym pozytywnym wynikiem, jaki wykazali, jest to, że A*, ze spójną heurystyką, jest optymalnie wydajny w odniesieniu do wszystkich dopuszczalnych algorytmów wyszukiwania podobnych do A* we wszystkich ″niepatologicznych″ problemach wyszukiwania. Z grubsza mówiąc, ich pojęcie niepatologicznego problemu jest tym, co teraz rozumiemy przez „aż do rozstrzygnięcia”. Wynik ten nie obowiązuje, jeśli heurystyka A* jest dopuszczalna, ale niespójna. W tym przypadku Dechter i Pearl wykazali, że istnieją dopuszczalne algorytmy typu A*, które mogą rozszerzyć dowolnie mniej węzłów niż A* w niektórych niepatologicznych problemach.

Optymalna wydajność dotyczy zbioru rozwiniętych węzłów, a nie liczby rozwinięć węzłów (liczby iteracji głównej pętli A*). Gdy używana heurystyka jest dopuszczalna, ale niespójna, węzeł może być wielokrotnie rozszerzany o A*, w najgorszym przypadku wykładniczą liczbę razy. W takich okolicznościach algorytm Dijkstry mógłby znacznie przewyższyć A*.

Ograniczony relaks

Wyszukiwanie* wykorzystujące heurystykę, która jest równa 5,0(=ε) razy spójna heurystyka i uzyskuje ścieżkę suboptymalną.

Chociaż kryterium dopuszczalności gwarantuje optymalną ścieżkę rozwiązania, oznacza to również, że A* musi zbadać wszystkie równie cenne ścieżki, aby znaleźć optymalną ścieżkę. Aby obliczyć przybliżone najkrótsze ścieżki, można przyspieszyć wyszukiwanie kosztem optymalności poprzez rozluźnienie kryterium dopuszczalności. Często chcemy ograniczyć tę relaksację, aby zagwarantować, że ścieżka rozwiązania nie będzie gorsza niż (1 + ε ) razy optymalna ścieżka rozwiązania. Ta nowa gwarancja jest określana jako dopuszczalna ε .

Istnieje kilka algorytmów ε -dopuszczalnych:

• Ważone A*/Wagi statyczne. Jeśli h ( n ) jest dopuszczalny heurystyczny funkcja ważonych wersji A * używa h _wagowo ( n ) = ε H ( n ) , ε > 1 jako funkcję heurystycznego i wykonywać A * jak zwykle (co ostatecznie dzieje się szybciej niż przy użyciu h _a, ponieważ rozwijana jest mniejsza liczba węzłów). Ścieżka znaleziona w ten sposób przez algorytm wyszukiwania może mieć koszt co najwyżej ε razy wyższy niż ścieżka o najniższym koszcie na wykresie.
• Ważenie dynamiczne korzysta z funkcji kosztu , gdzie i gdzie jest głębokością wyszukiwania, a N jest przewidywaną długością ścieżki rozwiązania.${\ Displaystyle f (n) = g (n) + (1 + \ varepsilon w (n)) h (n)}$${\ Displaystyle w (n) = {\ zacząć {przypadki} 1-{\ Frac {d (n)} {N}} i d (n) \ równoważnik N \ \ 0 i {\ tekst {w przeciwnym razie}} \ koniec {przypadki }}}$${\ Displaystyle d (n)}$
• Próbkowane dynamiczne ważenie wykorzystuje próbkowanie węzłów w celu lepszego oszacowania i odciążenia błędu heurystycznego.
• ${\ Displaystyle A_ {\ varepsilon} ^ {*}}$. używa dwóch funkcji heurystycznych. Pierwsza to lista FOCAL, która służy do wyboru węzłów kandydujących, a druga h _F służy do wyboru najbardziej obiecującego węzła z listy FOCAL.
• A _ε wybiera węzły za pomocą funkcji , gdzie A i B są stałymi. Jeśli nie można wybrać żadnych węzłów, algorytm cofa się za pomocą funkcji , gdzie C i D są stałymi.${\ Displaystyle Af (n) + Bh_ {F} (n)}$${\ Displaystyle Cf (n) + Dh_ {F} (n)}$
• AlphaA* próbuje promować eksploatację w głąb, preferując ostatnio rozbudowane węzły. AlphA* używa funkcji kosztu , gdzie , gdzie λ i Λ są stałymi z , π ( n ) jest rodzicem n , a ñ jest ostatnio rozwiniętym węzłem.${\ Displaystyle f_ {\ alfa} (n) = (1 + w_ {\ alfa} (n)) f (n)}$${\ Displaystyle w_ {\ alfa} (n) = {\ zacząć {przypadki} \ lambda & g (\ pi (n)) \ leq g ({\ tylda {n}}) \ \ \ lambda i {\ tekst {w przeciwnym razie }}\end{przypadki}}}$${\ Displaystyle \ lambda \ leq \ Lambda}$

Złożoność

Złożoność razem z A * zależy od heurystyki. W najgorszym przypadku nieograniczonej przestrzeni poszukiwań liczba rozwiniętych węzłów jest wykładnicza na głębokości rozwiązania (najkrótsza ścieżka) d : O ( b ^d ) , gdzie b jest współczynnikiem rozgałęzienia (średnia liczba następców na stan ). Zakłada się, że stan docelowy w ogóle istnieje i jest osiągalny od stanu początkowego; jeśli tak nie jest, a przestrzeń stanów jest nieskończona, algorytm nie zostanie zakończony.

Funkcja heurystyczna ma istotny wpływ na praktycznym wykonywaniu A *, gdyż dobry heurystyczny pozwala A * przycinać dala wielu b ^d węzłów że niedoinformowani wyszukiwania rozwinie. Jego jakość można wyrazić w postaci efektywnego współczynnika rozgałęzienia b * , który można wyznaczyć empirycznie dla przypadku problemu, mierząc liczbę węzłów generowanych przez rozwinięcie, N i głębokość rozwiązania, a następnie rozwiązując

${\ Displaystyle N + 1 = 1 + b ^ {*} + (b ^ {*}) ^ {2} + \ kropki + (b ^ {*}) ^ {d}.}$

Dobre heurystyki to te z niskim efektywnym współczynnikiem rozgałęzienia (optymalnym jest b * = 1 ).

Złożoność czasowa jest wielomianowa, gdy przestrzeń poszukiwań jest drzewem, istnieje jeden stan docelowy, a funkcja heurystyczna h spełnia następujący warunek:

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

gdzie h ^* jest optymalną heurystyką, dokładnym kosztem przejścia od x do celu. Innymi słowy, błąd h nie będzie rósł szybciej niż logarytm „idealnej heurystyki” h ^*, która zwraca prawdziwą odległość od x do celu.

Przestrzeń złożoność A * jest mniej więcej taka sama, jak w przypadku wszystkich innych algorytmów przeszukiwania grafów, ponieważ zachowuje wszystkie wygenerowane węzły w pamięci. W praktyce okazuje się to być największą wadą wyszukiwania A*, prowadzącą do rozwoju wyszukiwania heurystycznego ograniczonego do pamięci, takiego jak pogłębianie iteracyjne A* , A* ograniczone pamięcią i SMA* .

Aplikacje

A* jest często używany do rozwiązywania typowego problemu ze znajdowaniem ścieżki w aplikacjach, takich jak gry wideo, ale pierwotnie został zaprojektowany jako ogólny algorytm przechodzenia przez graf. Znajduje zastosowanie w różnych problemach, w tym w problemie parsowania przy użyciu gramatyk stochastycznych w NLP . Inne przypadki obejmują wyszukiwanie informacyjne z nauką online.

Relacje z innymi algorytmami

Tym, co odróżnia A* od zachłannego algorytmu wyszukiwania „najlepszy-pierwszy”, jest to, że bierze on pod uwagę koszt/odległość już przebytą, g ( n ) .

Niektóre popularne warianty algorytmu Dijkstry można postrzegać jako szczególny przypadek A*, gdzie heurystyka dla wszystkich węzłów; z kolei zarówno Dijkstra, jak i A* są szczególnymi przypadkami programowania dynamicznego . Samo A* jest szczególnym przypadkiem uogólnienia branch i bound . ${\ Displaystyle h (n) = 0}$

Warianty

• Zawsze A*
• Blok A*
• D*
• Pole D*
• Grzywka
• Oszczędność marginesów A* (FSA*)
• Uogólnione Adaptacyjne A* (GAA*)
• Przyrostowe wyszukiwanie heurystyczne
• Obniżone A*
• Pogłębianie iteracyjne A* (IDA*)
• Wyszukiwanie punktu skoku
• Planowanie przez całe życie A* (LPA*)
• Nowe dwukierunkowe A* (NBA*)
• Uproszczona pamięć ograniczona A* (SMA*)
• Teta*

A* można również dostosować do dwukierunkowego algorytmu wyszukiwania . Należy zwrócić szczególną uwagę na kryterium zatrzymania.

Zobacz też

• Wyszukiwanie wszerz
• Wyszukiwanie w głąb
• Planowanie ścieżek pod dowolnym kątem , szukaj ścieżek, które nie ograniczają się do poruszania się wzdłuż krawędzi wykresu, ale mogą przyjmować dowolny kąt

Uwagi

Bibliografia

Dalsza lektura

• Nilsson, NJ (1980). Zasady sztucznej inteligencji . Palo Alto, Kalifornia: Tioga Publishing Company. Numer ISBN 978-0-935382-01-3.

Zewnętrzne linki

• Jasne, wizualne wyjaśnienie A*, z poradami i przemyśleniami na temat znajdowania ścieżki
• Wariacja na temat A* zwana hierarchicznym odnajdywaniem ścieżki A* (HPA*)
• Briana Grinsteada. "A* Algorytm wyszukiwania w JavaScript (zaktualizowany)" . Zarchiwizowane od oryginału w dniu 15 lutego 2020 . Pobrano 8 lutego 2021 .