krokiem w górę od algorytmu Dijkstry jest* (czytaj: „gwiazda”). Jeśli chodzi o znajdowanie ścieżek, algorytm Dijkstry będzie chciał wypróbować każdą ścieżkę i każdy wierzchołek, aby znaleźć najkrótszą ścieżkę między punktem początkowym a celem, podczas gdy* ma dodatkowy atrybut, heurystyczny, który powinien pozwolić mu znaleźć najkrótszą ścieżkę bez konieczności sprawdzania każdej ścieżki i wierzchołka. Każdy algorytm ma swoje przypadki użycia, ale ogólnie rzecz biorąc, zarówno Dijkstra, jak i a* mogą znaleźć najkrótszą ścieżkę, ale a* zrobi to szybciej.

przed przejściem do tego artykułu polecam znać nieco algorytm Dijkstry, ponieważ istnieje wiele punktów porównawczych. Albo jeszcze lepiej, przeczytaj mój ostatni artykuł na ten temat! https://medium.com/swlh/pathfinding-dijkstras-algorithm-65e71c346629

będę musiał ustawić kilka rzeczy dla moich przykładów, plus podać definicję co to jest heurystyka. Na początek pokażę wam rodzaj wykresu, którego chcę użyć do moich przykładów.

To jest trochę abstrakcyjne, ale chcę użyć szachownicy jako mojego wykresu i chcę umożliwić ruch między jej kwadratami. Jeśli nałożę równoważny Wykres wierzchołkami i krawędziami, powinien wyglądać mniej więcej tak.

Weźmy na przykład środkowy kwadrat/wierzchołek, E. Ma osiem sąsiednich wierzchołków, więc możemy poruszać się w górę, w dół, w lewo, w prawo i we wszystkich kombinacjach ukośnych każdego z nich. I to jest naprawdę wszystko, co starałem się ustawić tutaj: będę używać szachownicy, i pozwolę na ruch w ośmiu kierunkach. Trochę za długo, ale teraz zacznijmy patrzeć na ruch i koszt ruchu.

zaczynając od prostego, powiem, że ruch w górę, w dół, w lewo i w prawo ma koszt ruchu 1. Plansza jest zajęta, więc wyciągnę wykres i dodam ten koszt ruchu jako wagę krawędzi.

Jeśli te wagi są odległościami, a relacje i sąsiedzi są ułożone w ten sposób, to geometria może nam powiedzieć o kosztach ruchów diagonalnych. Korzystając z teorii Pitagorasa, powinniśmy uzyskać √(12 + 12) = √2, czyli mniej więcej 1.41421356237 … co nie jest zbyt dobrą liczbą do pracy. Więc ukradnę pomysł (i przytoczę moje źródła!), oraz pomnożyć i zaokrąglić koszty w dół. Dla obu rodzajów ruchu, pomnożę je przez dziesięć, a następnie obetnę ich miejsca po przecinku. To da nam ostateczne koszty 10 dla ruchów w górę, w dół, w lewo i w prawo, i 14 dla ruchów diagonalnych.

heurystyka

wydaje mi się, że trudno mi je zdefiniować, więc zacznę od pierwszego wiersza Wikipedii na ten temat:

w informatyce, sztucznej inteligencji i optymalizacji matematycznej heurystyka (z greckiego εὑρίσκω „znajduję, odkrywam”) jest techniką zaprojektowaną do szybszego rozwiązania problemu, gdy klasyczne metody są zbyt wolne lub do znalezienia przybliżonego rozwiązania, gdy klasyczne metody nie są w stanie znaleźć dokładnego rozwiązania. Osiąga się to poprzez optymalność handlu, kompletność,dokładność lub precyzję szybkości. W pewnym sensie można go uznać za Skrót.

czy to jest przydatne? Rozumiesz? Bo nie rozumiem. To znaczy, trochę to Rozumiem, i to jest dokładny opis, ale gdyby to był pierwszy raz, kiedy słyszałeś o heurystyce, nie jestem pewien, czy dostałbyś pełny obraz tego, czym są heurystyki. Może jeśli opowiem ci o heurystyce odkrywania ścieżek przez*, będziesz miał lepsze zrozumienie.

w algorytmie Dijkstry skupiono się na jednej wartości: najkrótszej odległości od indeksu początkowego. Co, kiedy o tym pomyślisz, jest trochę dziwne. Ten algorytm próbuje znaleźć nowe, krótsze ścieżki do jakiegoś miejsca docelowego, ale zawsze skupia się na tym, gdzie się zaczął. Wyobraź sobie kogoś, kto idzie po zakupy, ale idzie całą drogę do tyłu, próbując mieć oko na swój dom, dopóki nie dotrze do sklepu. W prawdziwym życiu, to prawdopodobnie nie zadziała, ale może jeśli dasz im czas, aby przejść po całym mieście, może w końcu zadziała.

wychodząc z tej głupiej analogii, a * różni się od Dijkstry, ponieważ sugeruje odwrócenie się i pójście do przodu. A*, podobnie jak Dijkstra, również śledzi, jak daleko jest od domu, ale jego unikalną cechą jest to, że śledzi również, jak daleko jest od miejsca przeznaczenia. Wykonując kolejny krok, Dijkstra sprawdzi, która ścieżka jest obecnie najkrótsza, ale A* idzie o krok dalej i zastanowi się, czy ten krok zbliża go do celu. Mówiąc prościej, A* ma przybliżone oszacowanie pozostałej odległości do celu, a kiedy to oszacowanie zbliża się do zera, wie, że porusza się we właściwym kierunku. To jest heurystyka, której będziemy używać w naszych przykładach.

przejście przez algorytm

To będzie raczej prosty przykład, ale powinien pokazać podstawowy przepływ i powtórzenie algorytmu. Postaram się podać linki w moich odniesieniach do innych, bardziej skomplikowanych przykładów, ale to powinien być dobry podkład dla tych. Użyję ustawienia podobnego do tego, jak pokazałem Dijkstrę.

jeszcze jedna różnica między Dijkstrą a* jest taka, że Dijkstra natychmiast zaczyna zapętlać, ale* musi zrobić małą konfigurację dla początkowego wierzchołka. Zróbmy to teraz i zobaczmy, jak będzie działać stół.

najpierw dodamy a do otwartego zestawu. Po drugie, obliczymy odległość A od początku. Oczywiście, odległość od A do A wynosi zero, więc zostanie dodana do tabeli, i będę mieć, że jest to liczba w lewym górnym rogu kwadratu A. Po trzecie, określimy odległość heurystyczną. Możemy to zrobić na wiele sposobów, ważne jest tylko to, że mierzymy tę odległość w ten sam sposób dla każdego kwadratu. Będę używał odległości „w linii prostej” dla wszystkich odległości heurystycznych, co oznacza, że mogę ponownie użyć twierdzenia Pitagorasa. W tym przypadku będziemy obliczać √(202 + 302) i okaże się, że A jest odległością 36.0555127546… od L (zaokrąglę miejsca po przecinku do najbliższej dziesiątej, aby zaoszczędzić miejsce). Dodam to do stołu i umieszczę w prawym górnym rogu kwadratu A. Wreszcie suma. Dodam najkrótszą odległość od początku do odległości heurystycznej, dodam ją do tabeli i umieszczę na środku kwadratu A.

to nasz punkt wyjścia i możemy teraz spojrzeć na sąsiadów A i dodać ich wartości do tabeli.

najpierw dodamy B, E i F do otwartego zestawu. Następnie możemy znaleźć ich najkrótsze odległości od początku, a ponieważ wszystko jest o krok od początku, będzie to po prostu 10 dla B I E, i 14 dla ruchu przekątnej do F. Dla odległości heurystycznej użyjemy twierdzenia Pitagorasa od każdego kwadratu do końca wierzchołka. Na koniec otrzymamy ich sumy i dodamy „a”do każdej z poprzednich kolumn wierzchołków.

w tym momencie zrobiliśmy wszystko, co było nam potrzebne z A, więc zostanie on przeniesiony do zamkniętego zbioru i będziemy potrzebować nowego aktualnego wierzchołka. Aby określić, który wierzchołek powinien zostać zbadany następnie, przyjrzymy się zbiorowi otwartemu i znajdziemy wierzchołek, który ma najniższą sumę. Teraz to jest F z sumą 36,1. Więc zrobimy z niego bieżący wierzchołek i zaczniemy opracowywać wartości dla jego sąsiadów.

f ma ośmiu sąsiadów, ale tylko pięciu zostanie tutaj zmienionych. Po pierwsze, A jest teraz w zamkniętym zestawie, więc nie można go teraz zmienić. Dla pozostałych siedmiu dodamy je do otwartego zestawu (chyba że są już jego częścią), a następnie od początku popracujmy nad ich odległościami. To będzie działać podobnie jak algorytm Dijikstry, i będziemy dodawać Odległość F Od początku do odległości każdego z sąsiadów od F. na naszej tabeli Odległość F Od początku wynosi 14, więc wypełnimy 14+10=24 lub 14+14=28 dla nich. Jednak B i E mają już krótsze odległości do startu, więc ich rekordy tabeli nie są aktualizowane. Zostaje pięć wierzchołków, które zostaną zaktualizowane, z C, I I K dostającymi 28, A G I J dostającymi 24 dla ich odległości od startu. Następnie użyj twierdzenia Pitagorasa dla heurystycznych odległości każdego z tych wierzchołków, następnie Oblicz ich sumy, a na koniec dodaj ” F ” do poprzedniej kolumny wierzchołków dla wierzchołków, które zostały zaktualizowane.

F jest kompletne i zostanie przeniesione do zamkniętego zbioru, a nowy bieżący wierzchołek zostanie wybrany na podstawie tego, który wierzchołek w otwartym zbiorze ma najniższą sumę. Jest bardzo blisko, ale K jest o jedną dziesiątą mniejsze (i tak, jest to spowodowane różnicą zaokrąglenia, ale w tym przypadku okazuje się, że jest to dobry tie breaker). K będzie nowym wierzchołkiem do zbadania, więc zacznijmy od jego sąsiadów.

k ma sześciu sąsiadów, z których trzech jest już w otwartym zbiorze, więc dwa ostatnie h i l zostaną dodane do otwartego zbioru. Teraz obliczymy ich odległości od początku. Odległość K od startu wynosi 28, więc będziemy pracować z 28 + 10=38 Dla G, J i L, i 28 + 14=42 Dla H. jednak G I J mają już mniejsze odległości do rozpoczęcia, więc nie będą aktualizowane. Znajdziemy heurystyczne odległości dla każdego, obliczymy ich sumy i dodamy „K” do każdego poprzedniego wierzchołka, który został zaktualizowany.

k jest kompletne i przeniesione do zbioru zamkniętego, a następny wierzchołek w otwartym z najmniejszą sumą to L, nasz cel!

teraz, gdy L jest bieżącym wierzchołkiem, algorytm się kończy i możemy użyć naszej tabeli, aby prześledzić ścieżkę z powrotem do początku:

• poprzedni wierzchołek L to K
• poprzedni wierzchołek K to F
• f’ poprzedni wierzchołek to a, wierzchołek początkowy.

oznacza to, że najkrótsza ścieżka to> F> K> L.

analizując wyniki

w porównaniu z algorytmem Dijkstry, a* pozostawił po sobie niezły bałagan. Spójrzmy na kilka nieparzystych punktów. Zaczynając, spójrz na wierzchołek C i jego odległość do startu: 28. Wydaje się to dziwne, ponieważ A I C są tylko dwoma poziomymi ruchami od siebie, więc Najkrótsza odległość powinna wynosić 20. W tej chwili C wydaje się myśleć, że jego najkrótsza droga do A to dwa ukośne ruchy przez F.

gdy algorytm Dijkstry się skończy, powinien dostarczyć bardzo kompletną tabelę odległości od punktu początkowego. Odwrotnie, tabela A*ma błędne wartości i całkowicie brakuje wierzchołka D. ale dostał tę samą odpowiedź, co Dijkstra, i zrobił to znacznie szybciej. Dijkstra chciał sprawdzić wszystkie 12 wierzchołków przed zadeklarowaniem, że znalazł najkrótszą ścieżkę; a* musiał tylko spojrzeć na 4, zanim znalazł właściwą ścieżkę. Ta zmiana prędkości wynika z heurystyki, której używaliśmy: tak często, jak tylko mogliśmy, chcieliśmy zamykać dystans z naszym celem. Jeśli wrócimy do definicji Wikipedii Dla heurystyki, a* zamienił kompletność na szybkość.

spróbujmy innego małego przykładu, ale z przeszkodą w drodze do celu.

punktem wyjścia jest lewy górny wierzchołek, a* próbuje znaleźć najkrótszą ścieżkę do prawego dolnego wierzchołka. Czarne kwadraty reprezentują lukę na wykresie i nie mogą być przesuwane. Jeśli* podąża za swoją heurystyką „zawsze zbliżaj się do celu”, te czarne kwadraty doprowadzą go do ślepego zaułka.

w tym momencie, a* będzie szukać najmniejszych Sum, które będą kwadratami tuż poniżej i na prawo od początkowego wierzchołka. A* będzie badać obie ścieżki, ale ścieżka w dół będzie biegać w innym ślepym zaułku, a ścieżka w prawo znajdzie drogę wokół czarnych kwadratów. Może to rozegrać się nieco inaczej niż to, ale załóżmy, że w ten sposób A* poradził sobie z tym scenariuszem. Nawet gdy został wciągnięty w ślepe zaułki, był w stanie wrócić i znaleźć inną ścieżkę, i nie musiał patrzeć na każdy wierzchołek (prawy górny wierzchołek został ponownie pominięty). Oznacza to, że gdy gwiazda* pracuje w najgorszym momencie, jest tak szybka, jak normalna wydajność Dijkstry. Każdy algorytm ma doskonale poprawne przypadki użycia, ale jeśli chodzi o znajdowanie ścieżek i znajdowanie najkrótszych ścieżek, lepszym wyborem jest*.