Jak działa wyszukiwanie ścieżek A *?


67

Chciałbym zrozumieć na podstawowym poziomie, w jaki sposób działa wyszukiwanie ścieżek A *. Pomocne będą wszelkie implementacje kodu lub psuedo-code, a także wizualizacje.


Oto mały artykuł z animowanym GIF-em, który pokazuje w ruchu algorytm Dijkstry.
Ólafur Waage

Strony A * Amita były dla mnie dobrym wprowadzeniem. Na YouTubie można znaleźć wiele dobrych wizualizacji szukających algorytmu AStar .
jdeseno

Byłem zdezorientowany wieloma wyjaśnieniami A *, zanim znalazłem ten świetny samouczek: policyalmanac.org/games/aStarTutorial.htm Najczęściej o tym mówiłem, pisząc implementację A * w ActionScript: newarteest.com/flash /astar.html
jhocking

4
-1 Wikipedia ma artykuł na A * z wyjaśnieniem, kod źródłowy, wizualizacji i ... . Niektóre odpowiedzi tutaj zawierają linki zewnętrzne z tej strony wiki.
user712092

4
Ponadto, ponieważ jest to dość złożony temat, który jest bardzo interesujący dla twórców gier, myślę, że potrzebujemy informacji tutaj. Pamiętam, jak Joel powiedział kiedyś, że chce, aby StackOverflow był największym hitem, gdy ludzie google pytają o programowanie.
jhocking

Odpowiedzi:


63

Zrzeczenie się

Istnieje mnóstwo przykładów kodu i objaśnień A *, które można znaleźć w Internecie. To pytanie otrzymało również wiele świetnych odpowiedzi z wieloma przydatnymi linkami. W mojej odpowiedzi postaram się podać ilustrowany przykład algorytmu, który może być łatwiejszy do zrozumienia niż kod lub opisy.


Algorytm Dijkstry

Aby zrozumieć A *, sugeruję najpierw przyjrzeć się algorytmowi Dijkstry . Pozwól, że poprowadzę cię przez kroki, które algorytm Dijkstry wykona dla wyszukiwania.

Nasz węzeł początkowy jest Ai chcemy znaleźć najkrótszą ścieżkę do F. Każda krawędź wykresu ma związany z tym koszt ruchu (oznaczony jako czarne cyfry obok krawędzi). Naszym celem jest ocena minimalnego kosztu podróży dla każdego wierzchołka (lub węzła) wykresu, dopóki nie osiągniemy naszego węzła celu.

Zilustrowane przez Dijkstry, część 1

To jest nasz punkt wyjścia. Mamy do sprawdzenia węzły listy, obecnie jest to:

{ A(0) }

Ama koszt 0, wszystkie inne węzły są ustawione na nieskończoność (w typowej implementacji byłoby to coś podobnego int.MAX_VALUElub podobnego).

Zilustrowane przez Dijkstry, część 2

Bierzemy węzeł o najniższym koszcie z naszej listy węzłów (ponieważ nasza lista zawiera tylko A, to jest nasz kandydat) i odwiedzamy wszystkich jego sąsiadów. Ustalamy koszt każdego sąsiada:

Cost_of_Edge + Cost_of_previous_Node

i śledzić poprzedni węzeł (pokazany jako mała różowa litera poniżej węzła). Amoże być teraz oznaczony jako rozwiązany (czerwony), abyśmy go więcej nie odwiedzali. Nasza lista kandydatów wygląda teraz następująco:

{ B(2), D(3), C(4) }

Ilustrowany przez Dijkstry, część 3

Ponownie bierzemy węzeł o najniższym koszcie z naszej listy ( B) i oceniamy jego sąsiadów. Ścieżka do Djest droższa niż obecny koszt D, dlatego można ją odrzucić. Ezostaną dodane do naszej listy kandydatów, która teraz wygląda następująco:

{ D(3), C(4), E(4) }

Ilustracja Dijkstry, część 4

Następny węzeł do sprawdzenia jest teraz D. Połączenie z Cmożna odrzucić, ponieważ ścieżka nie jest krótsza niż istniejący koszt. Znaleźliśmy krótszą ścieżkę E, więc koszt Ei poprzedni węzeł zostaną zaktualizowane. Nasza lista wygląda teraz tak:

{ E(3), C(4) }

Ilustracja Dijkstry, część 5

Tak jak poprzednio, badamy węzeł o najniższym koszcie z naszej listy, który jest teraz E. Ema tylko jednego nierozwiązanego sąsiada, który jest również węzłem docelowym. Koszt dotarcia do węzła docelowego jest ustawiony na, 10a jego poprzedni węzeł na E. Nasza lista kandydatów wygląda teraz następująco:

{ C(4), F(10) }

Zilustrowane przez Dijkstry, część 6

Następnie badamy C. Możemy zaktualizować koszt i poprzedni węzeł dla F. Ponieważ nasza lista ma teraz Fwęzeł o najniższych kosztach, gotowe. Nasza ścieżka może być zbudowana przez prześledzenie poprzednich najkrótszych węzłów.


Algorytm *

Zastanawiasz się więc, dlaczego wyjaśniłem ci Dijkstrę zamiast algorytmu A * ? Cóż, jedyną różnicą jest sposób ważenia (lub sortowania) kandydatów. Z Dijkstra to:

Cost_of_Edge + Cost_of_previous_Node

Z A * to:

Cost_of_Edge + Cost_of_previous_Node + Estimated_Cost_to_reach_Target_from(Node)

Gdzie Estimated_Cost_to_reach_Target_fromjest powszechnie nazywany funkcją heurystyczną . Jest to funkcja, która spróbuje oszacować koszt dotarcia do węzła docelowego. Dobra funkcja heurystyczna umożliwi osiągnięcie mniejszej liczby węzłów w celu znalezienia celu. Podczas gdy algorytm Dijkstry rozszerzyłby się na wszystkie strony, A * będzie (dzięki heurystyce) szukać w kierunku celu.

Strona Amita o heurystyce ma dobry przegląd popularnych heurystyk.


2
Warto zauważyć, że heurystyka nie zawsze przyspieszy wyszukiwanie, aby znaleźć najlepszą trasę. Na przykład, jeśli Twoja heurystyka jest w odległości od celu, ale realna trasa znajduje się wokół krawędzi mapy - w tym przypadku wyszukiwanie przeszuka całą mapę, zanim znajdzie właściwą trasę. Z pewnością więc musisz myśleć, jest coś, czego nie rozumiem? To nie działa! - należy zrozumieć, że celem heurystyki jest ograniczenie wyszukiwania w WIĘKSZOŚCI przypadków, a Twoim zadaniem jest znalezienie takiego, który jest „najlepszym” ze wszystkich dostępnych rozwiązań dla twoich konkretnych potrzeb.
SirYakalot,

2
@AsherEinhorn To będzie lepsze (lub w najgorszym przypadku równe) niż niedoinformowane wyszukiwanie, takie jak Djikstry.
bummzack,

tak tak, masz absolutną rację. Może byłem niejasny, że przykład, o którym wspominałem w powyższym komentarzu, to teoretyczny senario „najgorszego przypadku” dla A * z tą heurystyczną ALE, ale Dijkstra zrobiłaby to KAŻDY czas. Przez większość czasu A * będzie lepszy nawet przy bardzo prostej heurystyce. Chodzi mi o to, że heurystyka na początku może być myląca, ponieważ „odległość do celu” nie zawsze ma sens w każdym scenariuszu - chodzi o to, że ma ona większość.
SirYakalot


W tej odpowiedzi można by wspomnieć o tym, co sprawia, że ​​heurystyka jest dopuszczalna, w sensie zagwarantowania, że ​​A * znajdzie najkrótszą drogę. (W skrócie: Aby być dopuszczalnym, heurysta nigdy nie może przeceniać faktycznej odległości do celu. Niedopuszczalna heurystyka może czasami być przydatna, ale może spowodować, że A * zwróci ścieżki nieoptymalne.)
Ilmari Karonen

26

Znalezienie ścieżki * jest najlepszym rodzajem wyszukiwania, które wykorzystuje dodatkową heurystykę.

Pierwszą rzeczą, którą musisz zrobić, to podzielić obszar wyszukiwania. Dla tego wyjaśnienia mapa jest kwadratową siatką kafelków, ponieważ większość gier 2D wykorzystuje siatkę kafelków i dlatego jest łatwa do wizualizacji. Pamiętaj jednak, że obszar wyszukiwania można podzielić w dowolny sposób: być może siatkę heksadecymalną, a nawet dowolne kształty, takie jak Ryzyko. Różne pozycje mapy są nazywane „węzłami”, a ten algorytm będzie działał za każdym razem, gdy masz do przejścia kilka węzłów i zdefiniowane połączenia między węzłami.

W każdym razie, zaczynając od danego kafelka początkowego:

  • 8 płytek wokół płytki początkowej jest „punktowanych” na podstawie a) kosztu przejścia z aktualnej płytki do następnej płytki (zazwyczaj 1 dla ruchów poziomych lub pionowych, sqrt (2) dla ruchu po przekątnej).

  • Każdej płytce przypisuje się dodatkowy wynik „heurystyczny” - przybliżoną względną wartość przejścia do każdej płytki. Stosuje się różne heurystyki, najprostszą jest odległość w linii prostej między środkami danej płytki i płytki końcowej.

  • Bieżąca płytka jest następnie „zamykana”, a agent przesuwa się do sąsiadującej otwartej płytki, ma najniższy wynik ruchu i najniższy wynik heurystyczny.

  • Ten proces powtarza się, dopóki nie zostanie osiągnięty węzeł celu lub nie ma już otwartych węzłów (co oznacza, że ​​agent jest zablokowany).

Aby zapoznać się ze schematami ilustrującymi te kroki, zapoznaj się z tym poradnikiem dla dobrego początkującego .

Istnieje kilka ulepszeń, które można wprowadzić, głównie w poprawie heurystyki:

  • Biorąc pod uwagę różnice terenu, nierówności, stromość itp.

  • Czasami przydaje się również „przesuwanie” po siatce, aby zablokować obszary mapy, które nie są wydajnymi ścieżkami: na przykład kształt litery U skierowany w stronę agenta. Bez testu wymiatania agent najpierw wszedłby w U, odwrócił się, a następnie opuścił i okrążył krawędź U. „Prawdziwy” inteligentny agent zauważyłby pułapkę w kształcie litery U i po prostu jej uniknął. Zamiatanie może pomóc w symulacji tego.


1
Wyjaśnienie za pomocą wykresu, węzłów, krawędzi byłoby bardziej jasne niż tylko kafelki. Nie pomaga zrozumieć, że bez względu na strukturę przestrzeni w grze, możesz zastosować ten sam algorytm, o ile masz powiązane informacje o pozycji w tej przestrzeni.
Klaim

Twierdziłbym, że w rzeczywistości byłoby to mniej jasne, ponieważ trudniej jest to wyobrazić. Ale tak, w tym wyjaśnieniu należy wspomnieć, że siatka kafelkowa nie jest wymagana; w rzeczywistości
zedytuję

14

Nie jest najlepszy, ale to implementacja A * w C ++ kilka lat temu.

Prawdopodobnie lepiej, że wskażę ci zasoby niż próbę wyjaśnienia całego algorytmu. Ponadto, czytając artykuł na wiki, zagraj w wersję demonstracyjną i sprawdź, czy możesz sobie wyobrazić, jak to działa. Zostaw komentarz, jeśli masz konkretne pytanie.

  1. A * na Wikipedii
  2. Demonstracja * Java

4
Twój przykład w Pythonie jest w C ++.
Buns of Aluminium

@finish - Dobrze widzieć, jak ktoś to łapie! Codzienne czynności koncentrują się obecnie wokół Pythona. Dzięki!
David McGraw

3
Twój przykład w C ++ może równie dobrze być C.
spowolniony

4
Przykładem może być również asembler dla całej posiadanej struktury. To nie jest nawet A *, jak to jest akceptowana odpowiedź?

4
Przepraszam, że nie jest to zgodne z normami, była to jedna z moich pierwszych prób kodowania, kiedy zaczynałem. Dodaj coś do komentarza / edytuj post, aby udostępnić własne rozwiązanie.
David McGraw,

6

Pomocny może być artykuł ActiveTut na temat wyszukiwania ścieżek . Omówiono zarówno algorytm A *, jak i algorytm Dijkstry oraz różnice między nimi. Jest skierowany do programistów Flash, ale powinien zapewnić dobry wgląd w teorię, nawet jeśli nie używasz Flasha.


4

Jedną z rzeczy, które należy wizualizować podczas pracy z A * i algorytmem Dijkstry, jest to, że A * jest kierowane; stara się znaleźć najkrótszą ścieżkę do określonego punktu, „zgadując”, w którą stronę patrzeć. Algorytm Dijkstry znajduje najkrótszą ścieżkę do / każdego / punktu.


1
To nie jest tak naprawdę dokładny opis różnicy między A * i Dijkstra. To prawda, że ​​Dijkstra rozwiązuje jedno źródło dla wszystkich punktów, ale gdy jest używany w grach, zwykle zostaje odcięty, gdy tylko znajdziesz ścieżkę do celu. Prawdziwa różnica między nimi polega na tym, że A * jest informowany przez heurystę i może znaleźć ten cel z mniejszą liczbą gałęzi.

Aby dodać do wyjaśnienia Joe: A * znajdzie również ścieżkę do wszystkich punktów, jeśli pozwolisz, ale w grach zwykle chcemy zatrzymać się wcześniej. A * działa jak algorytm Dijsktry, z tym że heurystyka pomaga zmienić kolejność węzłów, aby najpierw zbadać najbardziej obiecujące ścieżki. W ten sposób zwykle możesz zatrzymać się nawet wcześniej niż z algorytmem Dijkstry. Na przykład, jeśli chcesz znaleźć ścieżkę od środka mapy do strony wschodniej, algorytm Dijkstry będzie badał równo we wszystkich kierunkach i zatrzyma się, gdy znajdzie stronę wschodnią. * Spędzi więcej czasu na drodze na wschód niż na zachód i dotrze tam wcześniej.
amitp

3

Tak więc jako pierwsze stwierdzenie, A * jest algorytmem eksploracji grafów. Zwykle w grach jako wykres używamy kafelków lub innej geometrii świata, ale możesz użyć A * do innych celów. Dwa algorytmy ur dla przejścia przez wykres to wyszukiwanie w pierwszej kolejności w głębokości i wyszukiwanie w pierwszej kolejności. W DFS zawsze w pełni eksplorujesz swoją obecną gałąź, zanim spojrzysz na rodzeństwo bieżącego węzła, aw BFS zawsze patrzysz najpierw na rodzeństwo, a potem na dzieci. A * próbuje znaleźć środek między nimi, w którym eksplorujesz gałąź (czyli bardziej jak DFS), gdy zbliżasz się do pożądanego celu, ale czasami zatrzymaj się i spróbuj rodzeństwa, jeśli może mieć lepsze wyniki w swojej gałęzi. Rzeczywista matematyka polega na tym, że przechowujesz listę możliwych węzłów do zbadania, gdzie każdy ma „dobroć” wynik wskazujący, jak blisko (w pewnym sensie abstrakcyjnym) jest cel, przy czym niższe wyniki są lepsze (0 oznacza, że ​​cel został znaleziony). Wybierz, którego użyć następnie, znajdując minimum wyniku plus liczbę węzłów z dala od katalogu głównego (co jest zwykle bieżącą konfiguracją lub bieżącą pozycją w wyszukiwaniu ścieżek). Za każdym razem, gdy eksplorujesz węzeł, dodajesz wszystkie jego dzieci do tej listy, a następnie wybierasz nowy najlepszy.


3

Na poziomie abstrakcyjnym A * działa w następujący sposób:

  • Traktujesz świat jako dyskretną liczbę połączonych węzłów, np. siatka lub wykres.
  • Aby znaleźć ścieżkę przez ten świat, musisz znaleźć listę sąsiednich „węzłów” w tej przestrzeni, prowadzącą od początku do celu.
  • Naiwne podejście byłoby następujące: oblicz każdą możliwą permutację węzłów, które zaczynają się od węzła początkowego i kończą na węźle końcowym, i wybierz najtańszą. To oczywiście zabrałoby wieczność na wszystkich, z wyjątkiem najmniejszych przestrzeni.
  • Dlatego alternatywne podejścia próbują wykorzystać pewną wiedzę o świecie, aby odgadnąć, które permutacje są warte rozważenia w pierwszej kolejności i wiedzieć, czy dane rozwiązanie można pokonać. To oszacowanie nazywa się heurystycznym.
  • A * wymaga heurystyki, która jest dopuszczalna . Oznacza to, że nigdy nie przecenia.
    • Dobrą heurystyką dla problemów z wyszukiwaniem ścieżek jest odległość euklidesowa, ponieważ wiemy, że najkrótsza trasa między 2 punktami to linia prosta. To nigdy nie przecenia odległości w rzeczywistych symulacjach.
  • * Rozpoczyna się od węzła początkowego i próbuje kolejnych permutacji tego węzła plus każdego sąsiada, i sąsiadów jego sąsiada itp., Używając heurystyki, aby zdecydować, która permutacja ma spróbować później.
  • Na każdym kroku A * patrzy na najbardziej obiecującą ścieżkę do tej pory i wybiera następny sąsiedni węzeł, który wydaje się być „najlepszy”, w oparciu o przebytą do tej pory odległość i szacunki heurystyczne dotyczące tego, jak daleko pozostanie do pokonania węzeł.
  • Ponieważ heurystyka nigdy nie przecenia, a odległość do tej pory znana jest z dokładności, zawsze wybierze najbardziej optymistyczny następny krok.
    • Jeśli ten kolejny krok osiągnie cel, wiesz, że znalazł najkrótszą trasę od ostatniej pozycji, ponieważ było to najbardziej optymistyczne przypuszczenie, które z pozostałych poprawnych pozostały.
    • Jeśli nie osiągnął celu, pozostawiono go do zbadania później. Algorytm wybiera teraz następną najbardziej obiecującą możliwość, więc powyższa logika nadal obowiązuje.
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.