Jak komputer znajduje drogę?
Nawigacja, gra, robot sprzątający — wszędzie trzeba znaleźć trasę z punktu A do B omijając przeszkody. Narysuj ściany, ustaw start i metę, a potem patrz, jak cztery klasyczne algorytmy przeszukują planszę. Zobaczysz, czym się różnią i dlaczego A* jest najsprytniejszy.
Rysuj ściany myszą lub palcem. Przeciągnij 🟢 start i 🔴 metę. Na klawiaturze: wejdź Tabem w pole i naciśnij spację.
Gotowe. Kliknij „Szukaj”.
Cztery sposoby szukania
Każdy algorytm trzyma listę pól „do sprawdzenia” (kolejkę). Różnią się tym, które pole biorą z niej jako następne. Ta jedna decyzja zmienia wszystko.
BFS — wszerz
Rozlewa się jak fala równo we wszystkie strony: najpierw pola o 1 krok, potem o 2, o 3… Zawsze znajduje najkrótszą drogę, ale sprawdza mnóstwo pól.
DFS — w głąb
Idzie w jedną stronę jak najdalej, a gdy utknie, cofa się i próbuje innej. Sprawdza mało pól, ale nie gwarantuje najkrótszej drogi — często daje krętą.
Dijkstra
Bierze zawsze pole najbliższe startu (najtańsze). Na planszy, gdzie każdy krok kosztuje tyle samo, działa jak BFS i też daje najkrótszą drogę.
A* (A z gwiazdką)
Jak Dijkstra, ale dodaje szacunek odległości do mety (na oko, w linii prostej). Dzięki temu idzie prosto w stronę celu i sprawdza dużo mniej pól. Też znajduje najkrótszą drogę.
| Algorytm | Najkrótsza droga? | Zwykle sprawdza pól | Jak wybiera następne pole |
|---|---|---|---|
| BFS | ✔ tak | dużo | to, które czeka najdłużej (fala) |
| DFS | ✘ nie zawsze | mało | ostatnio dodane (idzie w głąb) |
| Dijkstra | ✔ tak | dużo | najbliższe startu |
| A* | ✔ tak | mało | najbliższe startu + szacunek do mety |
Porównaj sam: ustaw ten sam labirynt i uruchom po kolei każdy algorytm. Zapamiętaj licznik „sprawdzone pola”. A* i DFS zwykle sprawdzają najmniej, ale tylko A* (i BFS, i Dijkstra) dają najkrótszą drogę.
Wyścig algorytmów
Ten sam labirynt, cztery algorytmy naraz. Zobacz, który sprawdzi mniej pól i czy znajdzie najkrótszą drogę.
Żółta liczba to długość znalezionej drogi (mniej = lepiej), niebieska to liczba sprawdzonych pól (mniej = szybciej). Zwróć uwagę: DFS często sprawdza mało pól, ale jego droga bywa najdłuższa.
Sprawdź się
Najczęstsze pytania
Czym jest algorytm wyszukiwania drogi?
To przepis, który krok po kroku szuka trasy z jednego pola na drugie, omijając przeszkody. Komputer sprawdza kolejne pola, zapamiętuje, skąd do nich doszedł, i na końcu odtwarza najkrótszą drogę.
Czym różni się BFS od DFS?
BFS (przeszukiwanie wszerz) rozlewa się jak fala i zawsze znajduje najkrótszą drogę. DFS (przeszukiwanie w głąb) idzie w jedną stronę jak najdalej, więc sprawdza mniej pól, ale jego droga nie musi być najkrótsza.
Dlaczego A* jest szybszy niż Dijkstra?
Dijkstra rozgląda się równomiernie wokół startu. A* dodatkowo zgaduje, jak daleko jeszcze do mety (w linii prostej), i dzięki temu kieruje się prosto do celu, zamiast sprawdzać pola w przeciwną stronę. Oba znajdują najkrótszą drogę.
Co to jest heurystyka?
To szybki, przybliżony szacunek. W A* szacujemy odległość do mety, licząc kroki w pionie i poziomie, tak jakby nie było ścian (odległość Manhattan). Ten szacunek nigdy nie zawyża, dlatego A* wciąż daje najkrótszą trasę.
Gdzie się tego używa naprawdę?
W nawigacji samochodowej, w grach (jak poruszają się przeciwnicy), w robotach sprzątających, w sieciach komputerowych do wyznaczania trasy pakietów i w planowaniu ruchu magazynowych robotów.
Czy te algorytmy zawsze znajdą drogę?
Jeśli droga istnieje — tak, wszystkie cztery ją znajdą. Jeśli meta jest całkowicie odgrodzona ścianami, algorytm sprawdzi wszystkie dostępne pola i zgłosi, że drogi nie ma.