Ostateczne
W kolejce
Sprawdzone krawędzie

  • Bieżący
  • W kolejce
  • Ostateczne
  • Ścieżka
  • Oszacowanie w linii prostej
Kliknięcie wierzchołka ustawia

Więcej o algorytmie A*

Algorytm A*

Algorytm A* znajduje najkrótszą ścieżkę od startu do celu, tak jak algorytm Dijkstry, ale wie mniej więcej, gdzie jest cel. Każdy wierzchołek dostaje oszacowanie pozostałej odległości, czyli linię prostą do celu, a przeszukiwanie zawsze idzie dalej od wierzchołka o najmniejszej sumie dotychczasowej odległości i tego oszacowania. Kliknij wierzchołek, aby od niego zacząć, wybierz cel i idź krok po kroku, aby zobaczyć, jak przeszukiwanie zmierza do celu i zostawia nietknięte całe rogi grafu. Naciśnij Odtwórz, aby obejrzeć przeszukiwanie, albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Kliknij wierzchołek, aby uczynić go startem; przełącz kliknięcie na Cel i kliknij inny wierzchołek, aby uczynić go celem. Liczba na każdej krawędzi to jej długość, liczba na każdym wierzchołku to jego dotychczasowa odległość, a przerywana linia to oszacowanie pozostałej odległości w linii prostej. Rząd pod grafem to kolejka, od najniższego wyniku, z wynikiem każdego wierzchołka: dotychczasowa odległość plus oszacowanie. Nowy graf tworzy inny graf; wybierz, ile ma mieć wierzchołków i krawędzi. Gdy plansza jest zaznaczona, strzałki przesuwają o krok, spacja odtwarza i wstrzymuje, a Home i End przeskakują na początek i na koniec.

Jak to działa

  1. Kliknij wierzchołek, aby uczynić go startem. Przełącz kliknięcie na Cel i kliknij inny wierzchołek, aby uczynić go celem.
  2. Naciśnij Odtwórz albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce przeszukiwania.
  3. Obserwuj wyniki w kolejce i przerywane oszacowanie w linii prostej. Na koniec porównaj, ilu wierzchołków potrzebował A*, a ilu algorytm Dijkstry.

Jak działa algorytm A*

Daj startowi odległość 0 i wstaw go do kolejki. Każdy wierzchołek w kolejce ma wynik: dotychczasową odległość plus oszacowanie pozostałej odległości. Powtarzaj: weź wierzchołek o najniższym wyniku i oznacz jego odległość jako ostateczną. Jeśli to cel, zakończ. W przeciwnym razie dla każdego sąsiada, który nie ma ostatecznej odległości, dodaj długość krawędzi do odległości wierzchołka; jeśli to mniej niż dotychczasowa odległość sąsiada, obniż ją, zapamiętaj wierzchołek jako drogę do niego i wstaw sąsiada do kolejki z nowym wynikiem.

Dlaczego oszacowanie nie może być za duże

A* znajduje najkrótszą ścieżkę, dopóki oszacowanie nigdy nie mówi, że cel jest dalej, niż jest naprawdę: takie oszacowanie jest dopuszczalne. Linia prosta jest dopuszczalna, bo żadna droga między dwoma miejscami nie jest krótsza od linii prostej. Za duże oszacowanie może sprawić, że A* pominie najlepszą trasę; oszacowanie 0 wszędzie zmienia A* w algorytm Dijkstry, który jest bezpieczny, ale szuka we wszystkich kierunkach. Im lepsze oszacowanie, tym mniej wierzchołków potrzebuje A*. W aplikacji każda krawędź jest tak długa, jak ją narysowano, z zaokrągleniem w górę, więc linia prosta jest bezpiecznym oszacowaniem.

Często zadawane pytania

Czym jest algorytm A*?

To algorytm wyszukiwania ścieżki, który znajduje najkrótszą ścieżkę od startu do celu. Działa jak algorytm Dijkstry, ale porządkuje kolejkę według dotychczasowej odległości plus oszacowania pozostałej odległości, więc zmierza do celu, zamiast rozchodzić się we wszystkich kierunkach.

Czym jest heurystyka dopuszczalna?

To oszacowanie odległości do celu, które nigdy nie jest większe od prawdziwej najkrótszej odległości. Z dopuszczalnym oszacowaniem A* zawsze znajduje najkrótszą ścieżkę. Klasycznym przykładem jest odległość w linii prostej na mapie.

Czy A* jest szybszy od algorytmu Dijkstry?

Zwykle tak, gdy potrzebujesz drogi do jednego celu i masz dobre oszacowanie: A* ustala ostateczną odległość dla mniejszej liczby wierzchołków, bo te leżące z dala od celu dostają wysokie wyniki. Przy oszacowaniu 0 robi dokładnie to samo co algorytm Dijkstry. Algorytm Dijkstry jest lepszy, gdy potrzebujesz odległości do wszystkich wierzchołków.

Gdzie używa się A*?

W grach wideo do prowadzenia postaci wokół przeszkód, w planerach tras, w planowaniu ruchu robotów i w programach rozwiązujących łamigłówki, takie jak układanka 15, gdzie oszacowanie liczy, jak daleko klocki są od swoich miejsc.

Czy mój graf jest gdzieś wysyłany?

Nie. Graf powstaje i jest przeszukiwany w przeglądarce, a ostatnie ustawienia zostają w jej pamięci lokalnej.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Przejdź do edytora