algorithm => A * Pathfinding

Wprowadzenie do A *

A * (Gwiazda) to algorytm wyszukiwania służący do wyszukiwania ścieżki od jednego węzła do drugiego. Można go zatem porównać do pierwszego wyszukiwania szerokości lub algorytmu Dijkstry , pierwszego wyszukiwania głębokości lub najlepszego pierwszego wyszukiwania. Algorytm * jest szeroko stosowany w wyszukiwaniu grafów, ponieważ jest lepszy pod względem wydajności i dokładności, przy czym wstępne przetwarzanie wykresu nie jest opcją.

A * to specjalizacja Best First Search, w której funkcja oceny f jest określona w określony sposób.

f (n) = g (n) + h (n) to minimalny koszt, ponieważ początkowy węzeł do celów warunkuje przejście do węzła myślowego n .

g (n) to minimalny koszt od początkowego węzła do n .

h (n) to minimalny koszt od n do najbliższego celu do n

* Jest świadomym algorytmem wyszukiwania i zawsze gwarantuje znalezienie najmniejszej ścieżki (ścieżki o minimalnym koszcie) w jak najkrótszym czasie (jeśli używa dopuszczalnej heurystyki ). Jest więc kompletny i optymalny . Poniższa animacja pokazuje wyszukiwanie A *

Rozwiązywanie problemu 8 puzzli za pomocą algorytmu A *

Definicja problemu :

Układanka 8 to prosta gra składająca się z siatki 3 x 3 (zawierającej 9 kwadratów). Jeden z kwadratów jest pusty. Celem jest przejście do kwadratów w różnych pozycjach i wyświetlanie liczb w „stanie bramki”.

Biorąc pod uwagę początkowy stan gry z 8 łamigłówkami i stan końcowy, który należy osiągnąć, znajdź najbardziej opłacalną ścieżkę do osiągnięcia stanu końcowego ze stanu początkowego.

Stan początkowy :

_ 1 3
4 2 5
7 8 6

Stan końcowy :

1 2 3
4 5 6
7 8 _

Heurystyka do przyjęcia :

Rozważmy odległość Manhattanu między stanem obecnym a końcowym jako heurystykę tego stwierdzenia problemu.

h(n) = | x - p | + | y - q |
where x and y are cell co-ordinates in the current state
      p and q are cell co-ordinates in the final state

Funkcja kosztu całkowitego :

Tak więc funkcja kosztu całkowitego f(n) jest dana przez,

f(n) = g(n) + h(n), where g(n) is the cost required to reach the current state from given initial state

Rozwiązanie przykładowego problemu :

Najpierw znajdujemy wartość heurystyczną wymaganą do osiągnięcia stanu końcowego ze stanu początkowego. Funkcja kosztu, g (n) = 0, ponieważ jesteśmy w stanie początkowym

h(n) = 8

Powyższą wartość uzyskuje się, ponieważ 1 w stanie bieżącym jest o 1 odległość poziomą niż 1 w stanie końcowym. To samo dotyczy 2 , 5 , 6 . _ wynosi 2 odległości w poziomie i 2 odległości w pionie. Zatem całkowita wartość dla h(n) wynosi 1 + 1 + 1 + 1 + 2 + 2 = 8. Funkcja kosztu całkowitego f(n) jest równa 8 + 0 = 8.

Teraz można znaleźć możliwe stany, które można osiągnąć ze stanu początkowego i zdarza się, że możemy albo przesunąć _ w prawo, albo w dół.

Zatem stany uzyskane po przeniesieniu tych ruchów to:

1 _ 3    4 1 3
4 2 5    _ 2 5
7 8 6    7 8 6
 (1)      (2)

Ponownie funkcja kosztu całkowitego jest obliczana dla tych stanów przy użyciu metody opisanej powyżej i okazuje się, że wynosi odpowiednio 6 i 7. Wybraliśmy stan o minimalnym koszcie, którym jest stan (1). Kolejnymi możliwymi ruchami mogą być Lewo, Prawo lub Dół. Nie ruszamy się w lewo, tak jak poprzednio w tym stanie. Więc możemy poruszać się w prawo lub w dół.

Znów znajdujemy stany uzyskane z (1).

1 3 _    1 2 3
4 2 5    4 _ 5
7 8 6    7 8 6
 (3)      (4)

(3) prowadzi do funkcji kosztu równej 6, a (4) prowadzi do 4. Rozważymy również (2) uzyskane, przed którymi funkcja kosztu jest równa 7. Wybór z nich minimum prowadzi do (4). Kolejnymi możliwymi ruchami mogą być Lewo, Prawo lub Dół. Otrzymujemy stany:

1 2 3    1 2 3    1 2 3
_ 4 5    4 5 _    4 8 5
7 8 6    7 8 6    7 _ 6
 (5)      (6)      (7)

Otrzymujemy koszty równe 5, 2 i 4 odpowiednio dla (5), (6) i (7). Mamy też poprzednie stany (3) i (2) odpowiednio z 6 i 7. Wybraliśmy stan minimalnego kosztu, który wynosi (6). Kolejne możliwe ruchy to Up, a Down i wyraźnie Down prowadzą nas do stanu końcowego prowadzącego do wartości funkcji heurystycznej równej 0.

* Ścieżka przez labirynt bez przeszkód

Powiedzmy, że mamy następującą siatkę 4 na 4:

Załóżmy, że to labirynt . Jednak nie ma ścian / przeszkód. Mamy tylko punkt początkowy (zielony kwadrat) i punkt końcowy (czerwony kwadrat). Załóżmy również, że aby przejść z zielonego na czerwony, nie możemy poruszać się po przekątnej. Rozpoczynając od zielonego kwadratu, zobaczmy, do których kwadratów możemy się przenieść, i zaznaczmy je na niebiesko:

Aby wybrać, do którego kwadratu chcesz przejść, musimy wziąć pod uwagę 2 heurystyki:

Wartość „g” - To jest odległość tego węzła od zielonego kwadratu.
Wartość „h” - to odległość od tego węzła od czerwonego kwadratu.
Wartość „f” - jest to suma wartości „g” i wartości „h”. To ostatnia liczba, która mówi nam, do którego węzła się przenieść.

W celu obliczenia tych heurystyk użyjemy następującego wzoru: distance = abs(from.x - to.x) + abs(from.y - to.y)

Jest to znane jako formuła „Manhattan Distance” .

Obliczmy wartość „g” dla niebieskiego kwadratu bezpośrednio na lewo od zielonego kwadratu: abs(3 - 2) + abs(2 - 2) = 1

Świetny! Mamy wartość: 1. Teraz spróbujmy obliczyć wartość „h”: abs(2 - 0) + abs(2 - 0) = 4

Doskonały. Teraz uzyskamy wartość „f”: 1 + 4 = 5

Zatem końcowa wartość dla tego węzła to „5”.

Zróbmy to samo dla wszystkich pozostałych niebieskich kwadratów. Duża liczba na środku każdego kwadratu to wartość „f”, podczas gdy liczba w lewym górnym rogu to wartość „g”, a liczba w prawym górnym rogu to wartość „h”:

Obliczyliśmy wartości g, h i f dla wszystkich niebieskich węzłów. Teraz, co wybieramy?

Którykolwiek ma najniższą wartość f.

Jednak w tym przypadku mamy 2 węzły o tej samej wartości f, 5. Jak wybieramy między nimi?

Po prostu wybierz jeden losowo lub ustaw priorytet. Zwykle wolę mieć taki priorytet: „W prawo> W górę> W dół> W lewo”

Jeden z węzłów o wartości f 5 prowadzi nas w kierunku „w dół”, a drugi w lewo. Ponieważ Down ma wyższy priorytet niż Left, wybieramy kwadrat, który zabiera nas „Down”.

Zaznaczam teraz węzły, dla których obliczyliśmy heurystykę, ale do których nie przestawiłem, jako pomarańczowy, a węzeł, który wybraliśmy jako cyjan: