Labirynt i wyszukiwanie: jak komputer znajduje drogę
Wpisujesz adres w nawigacji i po chwili masz trasę. Przeciwnik w grze omija ściany i biegnie prosto do Ciebie. #Robot sprzątający objeżdża kanapę. We wszystkich tych sytuacjach komputer rozwiązuje ten sam problem: jak dojść z punktu A do B, omijając przeszkody. Do tego służą algorytmy wyszukiwania drogi.
Przygotowałem aplikację, w której uczniowie mogą narysować własny #labirynt i zobaczyć na żywo, jak cztery klasyczne algorytmy go przeszukują:
👉 Otwórz Labirynt i wyszukiwanie: labirynt.komputerowka.pl
📘 Instrukcja obsługi: komputerowka.pl/labirynt-doc
Jedna lista, cztery pomysły
Każdy z tych algorytmów robi w gruncie rzeczy to samo: trzyma listę pól „do sprawdzenia” (kolejkę) i po kolei je rozpatruje. Zapamiętuje przy tym, z którego pola do którego doszedł, żeby na końcu odtworzyć drogę. Różnią się tylko jedną decyzją: które pole z listy wziąć jako następne. Ta jedna decyzja zmienia wszystko.
| Algorytm | Bierze następne pole… | Najkrótsza droga? | Sprawdza pól |
|---|---|---|---|
| BFS (wszerz) | to, które czeka najdłużej | ✔ tak | dużo |
| DFS (w głąb) | ostatnio dodane | ✘ nie zawsze | mało |
| Dijkstra | najbliższe startu | ✔ tak | dużo |
| A* | najbliższe startu + szacunek do mety | ✔ tak | mało |
BFS: fala, która zalewa planszę
#BFS (przeszukiwanie wszerz) rozlewa się jak fala wrzucona do wody: najpierw sprawdza pola o 1 krok od startu, potem wszystkie o 2 kroki, potem o 3. Dzięki temu, gdy dotrze do mety, wiadomo na pewno, że żadna krótsza droga nie istnieje. BFS zawsze znajduje najkrótszą drogę. Płaci za to tym, że sprawdza mnóstwo pól: na otwartej planszy fala rozchodzi się we wszystkie strony, także w stronę przeciwną do mety.
DFS: uparty wędrowiec
#DFS (przeszukiwanie w głąb) wybiera zawsze pole dodane ostatnio, więc zapuszcza się w jedną stronę jak najdalej. Gdy utknie, cofa się i próbuje innej drogi. Sprawdza przez to mało pól, ale jego droga bywa kręta i długa. DFS trafi do mety, lecz niekoniecznie najkrócej. Świetnie za to nadaje się do zadań typu „czy w ogóle da się dojść?” albo do generowania labiryntów.
Dijkstra: zawsze najtańsze pole
#Algorytm #Dijkstry bierze zawsze pole najbliższe startu (najtańsze). Na planszy, gdzie każdy krok kosztuje tyle samo, działa dokładnie jak BFS i też daje najkrótszą drogę. Jego siła ujawnia się dopiero wtedy, gdy kroki mają różne koszty, na przykład droga przez błoto jest wolniejsza niż po asfalcie. Tego w aplikacji nie pokazujemy, żeby nie komplikować, ale warto o tym wspomnieć.
A*: Dijkstra z intuicją
A* (czytaj: „a z gwiazdką”) to Dijkstra, który dodatkowo zgaduje, jak daleko jeszcze do mety. Szacuje to „na oko”, licząc kroki w pionie i w poziomie, tak jakby nie było ścian (to tak zwana odległość Manhattan, czyli jak w mieście o prostopadłych ulicach). Dzięki temu A* nie rozgląda się na ślepo, tylko kieruje się prosto w stronę celu. Sprawdza przez to dużo mniej pól niż BFS i Dijkstra, a wciąż znajduje najkrótszą drogę.
Ten przybliżony szacunek nazywa się heurystyką. Ważne, żeby nigdy nie zawyżał prawdziwej odległości, bo inaczej A* mógłby przeoczyć najkrótszą trasę.
Zobacz różnicę na własne oczy
Najlepiej widać to na otwartej planszy, bez ścian, ze startem po lewej i metą po prawej:
- A* sprawdza tylko 19 pól i idzie wąskim paskiem prosto do mety.
- BFS sprawdza 237 pól, czyli prawie całą planszę, żeby znaleźć tę samą drogę długą na 18 kroków.
Obie drogi są tak samo krótkie. Różnica jest w tym, ile pracy trzeba było włożyć w ich znalezienie. Na tym polega spryt A*.
W aplikacji jest też wyścig algorytmów: ten sam labirynt z losowymi przeszkodami i cztery algorytmy naraz. Tam świetnie widać słabość #DFS. Przy drodze, którą #BFS i A* pokonują w 30 krokach, DFS potrafi wykręcić trasę na 50 kroków.
Gdzie się tego używa naprawdę
- Nawigacja samochodowa: wyznaczenie najszybszej trasy to A* na mapie dróg.
- Gry: jak przeciwnicy i postacie poruszają się po planszy.
- Roboty: odkurzacz i magazynowy robot planują ruch, omijając przeszkody.
- Sieci komputerowe: routery wyznaczają drogę pakietów (tu używa się Dijkstry).
Wypróbuj aplikację
- 🧭 Plansza na żywo: rysuj ściany, przeciągaj start i metę, wybierz algorytm i tempo. Oglądaj, jak rośnie fala sprawdzonych pól i jak na końcu zapala się droga.
- 🌀 Generator labiryntu i 🎲 losowe przeszkody jednym kliknięciem, w trzech rozmiarach planszy.
- 📊 Liczniki: sprawdzone pola, długość drogi i ile pól czeka w kolejce.
- 🏁 Wyścig algorytmów: cztery algorytmy na tym samym labiryncie, obok siebie.
- ❓ Quiz z 6 pytaniami i sekcja najczęstszych pytań.
👉 Uruchom Labirynt i wyszukiwanie: labirynt.komputerowka.pl
📘 Instrukcja z pomysłami na lekcję: komputerowka.pl/labirynt-doc
Wyzwania
- Ustaw otwartą planszę (przycisk „Puść”) i porównaj licznik „sprawdzone pola” dla A* i BFS. Ile razy więcej pól sprawdza BFS?
- Narysuj ścianę w kształcie litery U otwartej w stronę mety. Który algorytm wpadnie w pułapkę, a który ją ominie?
- W wyścigu znajdź labirynt, w którym droga DFS jest wyraźnie dłuższa od pozostałych. O ile kroków?
- Odgrodź metę ścianą ze wszystkich stron i uruchom szukanie. Co pokaże aplikacja?
- Dla ambitnych: ustaw start i metę tuż obok siebie, ale oddzielone długą ścianą. Policz, o ile dłuższa jest droga od odległości w linii prostej.
Miłego szukania drogi!
Zobacz też: wszystkie aplikacje, Wyścig sortowania, Gra w życie, Zgadnij liczbę, GPS po Gdańsku i Jak uczy się AI.
© 2026 Komputerowka.pl · Arnold Basiński
