Ta aplikacja internetowa umożliwia wyświetlenie graficznej reprezentacji szeregu różnych algorytmów przeszukiwania grafu, podczas rozwiązywania wybranych przez Ciebie 8 problemów logicznych.
Rozpoczynanie
Po lewej stronie tej aplikacji zobaczysz Panel sterowania. Korzystając z Panelu sterowania, możesz skonfigurować następujące aspekty aplikacji:
- Stan początkowy i stan celu
- Który algorytm wyszukiwania użyć
- Którą funkcję heurystyczną użyć, jeśli używasz algorytmu wyszukiwania z informacją
- I czy używać trybu jednoetapowego czy burst mode
Każda z tych opcji zostanie opisana bardziej szczegółowo poniżej.
Stany początkowe i docelowe
Aby ustawić stan początkowy lub docelowy, możesz kliknąć przycisk „Edytuj stan” lub graficzną reprezentację stanu.
Powinieneś zobaczyć okienko jak poniżej:
Aby zmienić kafelek, po prostu kliknij na kafelek, który chcesz zamienić, a następnie wprowadź nową wartość na klawiaturze. Spowoduje to zamianę kafelka z tym, który poprzednio posiadał tę wartość.
Algorytm wyszukiwania
N-Puzzle obsługuje pięć różnych algorytmów wyszukiwania opartych na grafie. Pierwsze trzy z nich to algorytmy wyszukiwania bez informacji (Uninformed Search Algorithms):
- Breadth-first Search
- Depth-first Search
- Iterative Deepening Search
Dwa pozostałe to algorytmy wyszukiwania z informacją (Informed Search Algorithms):
- A* Search
- Greedy Search
Jeśli wybierzesz Informed Search Algorithm, to będziesz musiał również wybrać Heuristic Function.
Funkcja Heurystyczna
N-Puzzle obsługują trzy różne Funkcje Heurystyczne:
- Odległość Euklidesowa
- Odległość Manhattanowa (Odległość Miasto-Blok)
- Kamienie Poza Miejscem
Tryb Jednoetapowy lub Burst
N-Puzzle mogą być używane w dwóch trybach. Domyślnie jest to tryb Single-Step, który pozwala na „przewijanie” wyszukiwania, jeden krok po drugim. Jest to przydatne, aby lepiej zrozumieć, jak działa algorytm wyszukiwania.
Drugim trybem jest tryb Burst. Po uruchomieniu, tryb Burst Mode kontynuuje wyszukiwanie aż do znalezienia stanu docelowego. Wyszukiwanie w trybie Burst Mode może być wstrzymane, ale nie może być 'przewinięte’.
Drzewo wyszukiwania
Oprezentacja stanu
Podczas gdy wyszukiwanie jest aktywne, będziesz w stanie zobaczyć wizualną reprezentację drzewa wyszukiwania. Każdy węzeł w tym drzewie wyszukiwania reprezentuje układ płytek (lub stan) i jest narysowany jako pole, które jest podzielone na 4 sekcje.
Następujący diagram pokazuje węzeł pobrany z wyszukiwania Greedy:
Największa sekcja to stan układanki. Poniżej widać dwie mniejsze sekcje.
Poniżej stanu układanki znajdują się dwie sekcje. Sekcja po lewej stronie to głębokość węzła. Sekcja po prawej stronie to wynik heurystyczny. Wynik heurystyczny jest używany tylko z algorytmami wyszukiwania świadomego, więc jeśli używasz algorytmów Breadth-first, Depth-first lub Iterative Deepening Search, wynik heurystyczny zostanie pominięty.
Ostatnia sekcja zapisuje kolejność, w jakiej węzły zostały rozwinięte. Na przykład, węzeł główny będzie zawsze '#1′, a następny węzeł, który zostanie rozwinięty będzie oznaczony jako '#2′.
Kolory węzłów
Aby uczynić drzewo wyszukiwania bardziej 'czytelnym’, obramowanie każdego węzła jest oznaczone kolorem w oparciu o jego bieżący stan.
Następujący diagram przedstawia algorytm A* (z heurystyką odległości euklidesowej) zastosowany do problemu, który można rozwiązać w zaledwie dwóch ruchach:
Kolory można interpretować następująco:
| Kolor | Znaczenie |
|---|---|
| Niebieski | Jeśli węzeł znajduje się na Liście Otwartej to będzie podświetlony na niebiesko. |
| Czerwony | Po każdej iteracji algorytmu wyszukiwania węzeł, który zostanie rozwinięty jako następny, zostanie podświetlony na czerwono. Dotyczy to nawet sytuacji, gdy węzeł docelowy został znaleziony. |
| Szary | Jeśli stan został już zbadany, zostanie wyszarzony. Na przykład, w kroku 2) powyższego diagramu, stan początkowy został pokolorowany na szaro, aby wskazać, że został zbadany. W kroku 3) węzeł reprezentujący stan początkowy jest ponownie odkrywany, ale nie będzie on rozwijany, ponieważ stan początkowy został rozwinięty przez węzeł główny. |
| Zielony | Po znalezieniu stanu docelowego zostanie on podświetlony na zielono. |
| Złoty | Po znalezieniu węzła reprezentującego stan docelowy, wszystkie węzły na ścieżce powrotnej do węzła głównego zostaną podświetlone na złoto. |
| Purpurowy | Przy użyciu Iteracyjnego Wyszukiwania Pogłębiającego, niezbadane węzły, które przekraczają maksymalną głębokość, nie zostaną dodane do listy otwartych. Węzły te będą oznaczone kolorem fioletowym. |
Listy otwarte i zamknięte
Podczas działania algorytmów wyszukiwania utrzymywane są dwie listy. Pierwsza z nich to Lista Otwarta – służy ona do śledzenia węzłów, które zostały odkryte, ale nie zostały jeszcze zbadane.
Druga to Lista Zamknięta – służy ona do śledzenia węzłów, które zostały zbadane lub węzłów, które nie zostaną zbadane, ponieważ reprezentują stany, które zostały już zbadane przez inne węzły.
Gdy wyszukiwanie jest aktywne, liczba węzłów na Listach otwartych i zamkniętych będzie widoczna w lewym górnym rogu:
Kredyty
.