PSI/LS/z2
From WikiZMSI
[edytuj]
Algorytmy przeszukiwania
Celem laboratorium zapoznanie się z działaniem różnymi algorytmami przeszukiwania przestrzeni stanów.
Co należy wiedzieć zanim...:
- Przeszukiwanie ma znaleźć ścieżkę wiodącą od stanu początkowego do końcowego (rozwiązania).
- Aby tego dokonać tworzy się drzewo/graf przeszukiwania rozpoczynający się w punkcie startu i kończący się w rozwiązaniu.
- Drzewo/Graf składa się z węzłów i krawędzi.
- Węzły, to stany, a krawędzie to wykonane operatory.
- Rozwinięcie węzła to proces wykonania wszystkich operatorów na danym węźle. Przez to powstają węzły potomne.
- Strategie (algorytmy) przeszukiwania różnią się tym, że w różnej kolejności rozwijają węzły w drzewie/grafie.
[edytuj]
Narzędzie do wykorzystania na zajęciach
Na zajęciach wykorzystany zostanie aplet AIspace Graph Searching prezentujący działanie różnych algorytmów przeszukiwania rozwiązując różne przykładowe grafy.
[edytuj]
Zagadnienia na wejściówkę
- Jak działają strategie Breadth First Search, Depth First Search, A*.
- Wady i zalety strategi.
- Co to jest funkcja heurystyczna.
- Jaki wpływ na działanie strategii A* mają różne heurystyki.
- Z menu Algorithm wybierz kolejno Depth First Search, Breadth First Search oraz A* z heurystykami NUMBER OF TAILS OUT i CITY BLOCK.
- Wykonaj zestawienie opisujące:
- długość ścieżki do rozwiązania (wartość g)
- liczba przeszukanych węzłów (wartość po #)
- liczba węzłów w liście OPEN
- liczba węzłów w liście CLOSED
- wartość początkowa heurystyki
- Zapisz wnioski z analizy danych w tabeli.