PL 
EnglishDomyślny
Українська🗺️ Wyszukiwanie ścieżki A*
Zobacz, jak A* znajduje najkrótszą ścieżkę na siatce, używając f = g + h. Rysuj ściany, przesuwaj start i cel, zmieniaj heurystykę i porównaj A*, Dijkstrę i algorytm zachłanny, by zobaczyć wpływ heurystyki na liczbę rozwiniętych węzłów.
O algorytmie A*
A* (czyt. „A-star”) to algorytm przeszukiwania grafu typu best-first, który znajduje najkrótszą ścieżkę między dwoma punktami, łącząc gwarantowanie optymalny koszt dotychczasowy Dijkstry (g) z heurystycznym oszacowaniem pozostałej odległości (h), nadając każdemu węzłowi wynik priorytetu f = g + h. Opracowany przez Harta, Nilssona i Raphaela w 1968 roku, stanowi podstawę wszystkiego, od nawigacji postaci w grach wideo i planowania ruchu robotów po obliczanie tras w Google Maps. Gdy heurystyka jest dopuszczalna — czyli nigdy nie przeszacowuje prawdziwego kosztu — A* gwarantuje znalezienie optymalnej ścieżki.
Ta symulacja pozwala wybierać między A*, Dijkstrą (h = 0) a przeszukiwaniem zachłannym najpierw najlepszym (Greedy Best-First, g = 0) na siatce, gdzie można malować ściany i ważony teren (koszt ×5), przeciągać węzły startu i celu, wybierać heurystykę (Manhattan, euklidesowa lub Czebyszewa), przełączać ruchy po przekątnej i obserwować rozwijanie węzłów krok po kroku. Statystyki na żywo pokazują liczbę rozwiniętych węzłów, długość ścieżki i koszt całkowity.
Najczęściej zadawane pytania
Co oznacza f = g + h?
W A* każdy węzeł w zbiorze otwartym jest oceniany przez f(n) = g(n) + h(n), gdzie g(n) to dokładny koszt najtańszej dotychczas znalezionej ścieżki od startu do węzła n, a h(n) to heurystyczne oszacowanie kosztu od n do celu. Algorytm zawsze rozwija węzeł o najniższym f, zapewniając, że jeśli h jest dopuszczalna, przy pierwszym rozwinięciu celu jego ścieżka jest optymalna.
Czym jest heurystyka dopuszczalna?
Heurystyka h jest dopuszczalna, jeśli nigdy nie przeszacowuje prawdziwego kosztu dotarcia do celu — formalnie h(n) ≤ h*(n) dla wszystkich n. Odległość Manhattan (suma kroków poziomych i pionowych) jest dopuszczalna na siatce 4-spójnej; odległość euklidesowa jest dopuszczalna dla dowolnej siatki. Niedopuszczalna heurystyka może przyspieszyć A*, ale może zwrócić ścieżkę nieoptymalną.
Czym A* różni się od algorytmu Dijkstry?
Algorytm Dijkstry ustawia h = 0, więc rozwija węzły w kolejności ich dokładnego kosztu od startu, promieniując na zewnątrz równomiernie we wszystkich kierunkach. A* dodaje heurystykę, by naprowadzić przeszukiwanie w stronę celu, zwykle rozwijając znacznie mniej węzłów. Na otwartej siatce bez przeszkód A* z odległością Manhattan może zredukować liczbę rozwinięć węzłów o 50–90% w porównaniu z Dijkstrą.
Dlaczego przeszukiwanie zachłanne najpierw najlepsze jest szybsze, ale nie optymalne?
Przeszukiwanie zachłanne najpierw najlepsze ustawia g = 0 i używa wyłącznie h do oceny węzłów, zawsze pędząc w stronę węzła, który wygląda na najbliższy celowi. Jest to bardzo szybkie w otwartych środowiskach, ale ignoruje rzeczywisty koszt ścieżki, więc może zostać zwabione przez drogi teren lub wokół przeszkód na dłuższą trasę. W najgorszym przypadku znajduje ścieżkę, która jest dowolnie gorsza od optymalnej.
Kiedy powinienem używać odległości Manhattan, euklidesowej czy Czebyszewa?
Używaj odległości Manhattan, gdy ruch jest ograniczony do 4 kierunków (góra, dół, lewo, prawo), ponieważ dokładnie liczy minimalną liczbę kroków. Odległość euklidesowa jest odpowiednia, gdy dozwolone są ruchy po przekątnej, a koszt przekątnej równa się √2. Odległość Czebyszewa (maksimum z |Δx|, |Δy|) jest właściwym wyborem, gdy wszystkie 8 kierunków kosztuje tyle samo, co jest powszechne w wielu grach strategicznych.
Czym są komórki ważone i jak wpływają na wyszukiwanie ścieżki?
Ważone komórki reprezentują teren trudniejszy do przebycia — błoto, płytką wodę lub wyboistą drogę. W tej symulacji ważona komórka kosztuje 5 zamiast 1 za wejście, więc A* często poprowadzi trasę wokół kilku ważonych komórek zamiast przez nie. Dijkstra i A* obie poprawnie obsługują wagi; przeszukiwanie zachłanne najpierw najlepsze ignoruje koszty i może przejść wprost przez drogi teren.
Jaka jest złożoność czasowa A*?
W najgorszym przypadku A* ma złożoność czasową i pamięciową O(b^d), gdzie b to współczynnik rozgałęzienia, a d to głębokość rozwiązania optymalnego. Przy spójnej heurystyce (spełniającej nierówność trójkąta) każdy węzeł jest rozwijany co najwyżej raz, dając O(V log V) na skończonym grafie z V wierzchołkami — tę samą asymptotyczną granicę co Dijkstra z użyciem kopca binarnego.
Jak generowanie labiryntu wpływa na przeszukiwanie?
Generator labiryntu tworzy doskonały labirynt za pomocą losowego algorytmu, który wykuwa przejścia w siatce, gwarantując dokładnie jedną ścieżkę między dowolnymi dwiema komórkami. Labirynty są szczególnie wymagające dla algorytmów przeszukiwania, ponieważ wąskie korytarze eliminują heurystyczną przewagę A* — przy tylko jednej poprawnej ścieżce wszystkie algorytmy muszą zbadać mniej więcej te same węzły.
Co reprezentują kolory na siatce?
Zielony oznacza węzeł startowy, czerwony cel. Niebieskie komórki tworzą bieżący front (zbiór otwarty), ciemnoniebieski oznacza węzły odwiedzone (zamknięte), a żółty podświetla węzeł aktualnie rozwijany. Ważone komórki są brązowe. Gdy ścieżka zostanie znaleziona, jest rysowana na limonkowo od startu do celu, a dokładny koszt można odczytać w panelu statystyk.
Czy A* można używać w 3D lub na grafach innych niż siatka?
Tak — A* działa na dowolnym grafie, gdzie koszty krawędzi są nieujemne i można podać dopuszczalną heurystykę. Zastosowania w świecie rzeczywistym obejmują planowanie ruchu ramienia robota w 3D (grafy przestrzeni konfiguracyjnej), routing sieciowy (opóźnienie jako koszt) oraz analizę języka naturalnego (kraty podobne do algorytmu Viterbiego). Siatka tutaj to po prostu najbardziej intuicyjna wizualnie reprezentacja ogólnego algorytmu.
Jakie znaczenie ma licznik „rozwiniętych węzłów”?
Rozwinięte węzły liczą, ile razy algorytm zdjął węzeł z frontu i przetworzył jego sąsiadów — to podstawowa miara efektywności A*. Niższa liczba oznacza, że heurystyka dobrze naprowadza przeszukiwanie. Na siatce 30×30 (900 komórek) dobra heurystyka może często znaleźć optymalną ścieżkę, rozwijając mniej niż 100 węzłów, podczas gdy Dijkstra może rozwinąć każdą osiągalną komórkę.
O tej symulacji
Ten symulator wizualizuje algorytm przeszukiwania A* znajdujący najkrótszą ścieżkę na ważonej siatce. Każdy węzeł frontu niesie wynik f(n) = g(n) + h(n), gdzie g to dokładna przebyta odległość od startu, a h to heurystyczne oszacowanie pozostałej odległości do celu; algorytm zawsze rozwija najpierw węzeł o najniższym f. Przełączenie listy rozwijanej algorytmu na Dijkstra zeruje h, podczas gdy Greedy Best-First całkowicie pomija g, więc można obserwować ten sam labirynt rozwiązywany na trzy różne sposoby, węzeł po węźle.
🔬 Co pokazuje
Kolorowa siatka śledzi przeszukiwanie na żywo: niebieskie komórki znajdują się w otwartym froncie, ciemnoniebieskie komórki zostały w pełni rozwinięte (zamknięte), a żółty oznacza węzeł przetwarzany w danym momencie. Gdy cel zostanie osiągnięty, zwycięska trasa jest rysowana na limonkowo, a panel boczny raportuje, ile węzłów zostało rozwiniętych oraz całkowity koszt ścieżki.
🎮 Jak korzystać
Wybierz Algorytm i Heurystykę z list rozwijanych, a następnie użyj przycisków narzędzia Maluj, by dodać Ściany, teren Wagi o koszcie ×5, lub przeciągnij znaczniki Przenieś start/Przenieś cel po planszy. Zezwól na ruchy po przekątnej przełącza między ruchem w 4 i 8 kierunkach, Pokaż wartości g/h/f nakłada surowe wyniki na każdą komórkę, a Autouruchomienie, Krok, Generuj labirynt, Wyczyść ściany i Reset sterują odtwarzaniem i układem planszy.
💡 Czy wiesz, że?
A* zostało opublikowane w 1968 roku przez Petera Harta, Nilsa Nilssona i Bertrama Raphaela i mimo że ma ponad pół wieku, wciąż jest domyślnym wyborem wyszukiwania ścieżki w większości gier wideo, stosów robotyki i planerów tras, ponieważ nigdy nie bada więcej węzłów niż to konieczne, gdy otrzyma dopuszczalną heurystykę.
Najczęściej zadawane pytania
Co się dzieje, gdy przełączę odległość Manhattan na euklidesową lub Czebyszewa?
Każda heurystyka zmienia sposób, w jaki h(n) szacuje odległość do celu, co przekształca front przeszukiwania. Odległość Manhattan (kroki poziome plus pionowe) jest dokładna dla ruchu w 4 kierunkach; odległość euklidesowa (przeciwprostokątna po linii prostej) pasuje do ruchu po przekątnej; odległość Czebyszewa (większa z różnic poziomej i pionowej) pasuje do plansz, gdzie kroki po przekątnej kosztują tyle samo co ortogonalne. Wybór heurystyki, która nie doszacowuje prawdziwej odległości, utrzymuje optymalność A*, ale może rozwinąć więcej węzłów; przeszacowanie przyspiesza przeszukiwanie, ale może dać dłuższą ścieżkę.
Dlaczego malowanie kafelka Wagi zmienia trasę zamiast tylko ją spowalniać?
Kafelek Wagi kosztuje 5 za wejście zamiast 1, więc podnosi g(n) dla każdej ścieżki, która go przecina. Ponieważ A* i Dijkstra zawsze minimalizują koszt całkowity, chętnie wybiorą dłuższą trasę wokół skupiska ważonych komórek, jeśli ta trasa jest ogólnie tańsza — przeszukiwanie zachłanne najpierw najlepsze, które całkowicie ignoruje g, jest jedynym trybem, który może przejść wprost przez drogi teren.
Co dokładnie śledzi kolorowanie frontu pod maską?
Niebieskie komórki znajdują się w zbiorze otwartym — odkryte, ale jeszcze nierozwinięte — i są przechowywane w binarnym kopcu min z kluczem f, przy remisach rozstrzyganych niższą wartością h. Ciemnoniebieskie komórki są zamknięte, co oznacza, że ich sąsiedzi zostali już zbadani, a ich gScore jest ostateczny. Żółty oznacza pojedynczy węzeł zdjęty z kopca w bieżącym kroku.
Dlaczego Generuj labirynt sprawia, że przeszukiwanie zachłanne najpierw najlepsze działa dużo gorzej?
Generator labiryntu tworzy doskonały labirynt z dokładnie jedną trasą między dowolnymi dwiema komórkami, używając losowego rekurencyjnego algorytmu z nawrotami, więc nie ma skrótów, które heurystyka mogłaby wykorzystać. Przeszukiwanie zachłanne najpierw najlepsze wciąż pędzi w stronę komórki otwartej, która wygląda na najbliższą celowi po linii prostej, często wpadając w ślepe korytarze, podczas gdy A* i Dijkstra metodycznie się wycofują i próbują jedynej innej opcji.
Czy koszt ruchu po przekątnej jest obsługiwany poprawnie?
Tak — gdy zaznaczono Zezwól na ruchy po przekątnej, kroki po przekątnej kosztują √2 zamiast 1, co odpowiada ich prawdziwej długości euklidesowej, a symulator blokuje ruchy po przekątnej, które przecinałyby róg dwóch sąsiadujących ścian. Heurystyka przełącza się w tym trybie również na wzór odległości oktalnej, dzięki czemu pozostaje dopuszczalna dla ruchu w 8 kierunkach.
Obserwuj, jak A* znajduje najkrótszą ścieżkę na siatce, używając f = g + h. Maluj ściany, przeciągaj start/cel, przełączaj heurystyki i porównuj A* z Dijkstrą i przeszukiwaniem zachłannym, by zobaczyć, jak heurystyka zmienia liczbę rozwiniętych węzłów.
3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install