Algorytm A*

0

Cześć,

Szukam pomocy w kwestii interpretacji algorytmu A*. Czytałem dość sporo materiałów o nim, ale nadal pewne rzeczy są dla mnie tam niejasne. Głównym problemem, z którym się zderzyłem to heurystyka. Mam pewien projekt, w którym chciałem wykorzystać i zaprezentować działanie tego algorytmu, ale brakuje mi wiedzy odnośnie właśnie heurystyki, a konkretnie wariantu Manhattan Distance. We wszelkich materiałach, które miałem okazję zobaczyć, heurystyka podawana była jako gotowe wartości i nie było za bardzo wiadomo, skąd się one wzięły. Wzór na obliczenie heurystyki znam, ale jakoś nijak ma się to do tego, co było prezentowane. Czy ktoś z Was posiada jakieś dobre materiały, które wyjaśniają od podstaw działanie tego algorytmu z uwzględnieniem heurystyki? Albo mógłby jakoś przybliżyć ten temat w bardziej zrozumiały sposób?

0

Z tego co pamiętam, jako heurystykę w A* wykorzystywało się "rzeczywistą odległość" (czyli mierzoną w przestrzeni, a nie po krawędziach grafu) między wybranym punktem a docelowym. Czyli każdy węzeł grafu powinien mieć jakiś wektor opisujący jego współrzędne - w najprostszym przypadku 2D niech będzie to para

Pi = (xi, yi)

Jeżeli w danym momencie analizujesz dwa węzły A, B, z których chciałbyś dotrzeć do punktu C, to aby dokonać wyboru musisz znać dystans po krawędziach od początkowego punktu (powiedzmy D) do obu punktów A, B, oraz ich odległość w przestrzeni mierzoną według pewnej normy - to może być odległość kartezjańska, manhattan, jaką tylko wybierzesz.

1

Jakieś 2 lata temu implementowałem ten algorytm na podstawie http://csis.pace.edu/~benjamin/teaching/cs627/webfiles/Astar.pdf
Jak dla mnie świetny materiał. Zwłaszcza, że przykładowe ilustracje są zrobione bardziej pod praktyczne wykorzystanie niż teorię ;)
Zaimplementowany Algorytm działał poprawnie w moim prototypie gry w Unity.

Ten artykuł przyjmuje przybliżoną heurystykę, ignorujemy przeszkody i poruszamy się tylko w prawo lub w lewo. W kierunku węzła docelowego, sumując koszty ruchu po drodze.

0
Lucas83 napisał(a):

Cześć,

Głównym problemem, z którym się zderzyłem to heurystyka. Mam pewien projekt, w którym chciałem wykorzystać i zaprezentować działanie tego algorytmu, ale brakuje mi wiedzy odnośnie właśnie heurystyki, a konkretnie wariantu Manhattan Distance. We wszelkich materiałach, które miałem okazję zobaczyć, heurystyka podawana była jako gotowe wartości i nie było za bardzo wiadomo, skąd się one wzięły.

Algorytm ocenia koszt ścieżki jako:
znaną obecną długość przebytej ścieżki
plus
nieznaną, szacunkową (oszacowaną przy pomocy heurystyki, np. Manhattan D.) odległość do celu.

Manhattan Distance w dwuwymiarowym gridzie węzłów (bez połączeń ukośnych) to po prostu odległość w osi X plus odległość w osi Y.
Jest to dopuszczalne oszacowanie, bo nie przeszacowuje kosztu odległości do celu (nie może na pewno istnieć krótsza ścieżka do celu).

0

OK, dziękuję za dotychczasowe wskazówki, chyba zrozumiałem jak działa heurystyka. Natomiast pojawiło mi się nowe pytanie. Czy jeśli dopuszczam w algorytmie poruszanie się po dwuwymiarowej macierzy tylko w kierunku góra, dół, lewo oraz prawo, to czy muszę wyznaczać wszystkich ośmiu sąsiadów obecnie procesowanego fragmentu? Czy wystarczy, że wygeneruję pozycje dla czterech sąsiadów (górny, dolny, lewy oraz prawy)?

1 użytkowników online, w tym zalogowanych: 0, gości: 1