LAB: Klasyczne algorytmy szukania rozwiązań

Celem ćwiczenia jest zapoznanie się z klasycznymi algorytmami szukania rozwiązań. Są to algorytmy przeszukiwania grafów, gdyż przestrzeń poszukiwań jest modelowana w postaci grafu.

Do przeczytania i przygotowania:

• 3 States and Searching
• 3 Solving Problems by Searching

Podstawowym narzędziem do realizacji ćwiczeń jest program Graph Searching z AIspace.

Uzupełniająco i poszerzająco, można po zajęciach przejść do laboratorium Planowanie tras przejazdu w Prologu.

Pracuj w parze z Koleżanką/Kolegą. (Uruchom narzędzie pisząc w konsoli tekstowej ais-search.) W Windows uruchom http://www.aispace.org/search/version4.5.2/search.exe

1. Załaduj przykładowe zadanie Simple Tree Graph.
2. Zaznajom się z możliwościami wyświetlania parametrów grafu.
3. Zapisz go pod nową nazwą.
4. Wypróbuj różne algorytmy szukania: porównaj wynik działania 3 wybranych algorytmów, zapisz wyniki (znaleziona ścieżka i jej koszt, oraz ilość analizowanych węzłów)
5. Zmodyfikuj graf i powtórz szukanie rozwiązań.
6. Przeanalizuj inne dostarczone przykłady, znajdź taki, na którym można pokazać lepsze działanie algorytmu heurystycznego.

Przykład pochodzi z 3 Solving Problems by Searching.

Jesteś w mieście Arad, masz dojechać do Bukaresztu, pytanie jaka jest najkrótsza droga?

Znasz też odległości w linii prostej z danego miasta do Bukaresztu (SLD).

• Przyjrzyj się powyższej mapie Rumunii.
• Zbuduj odpowiadający jej graf (zakładka Create).
• Wystarczy, że nazwiesz wierzchołki pierwszymi literami nazw miast.
• Zacznij tworzyć krawędzie od Arad w kierunku Bukaresztu.
• Na razie NIE interesują cię odległości w linii prostej.

• Znajdź trasę (zakładka Solve).
• Wypróbuj różne algorytmy szukania w tym nieherustyczne i heurystyczne.
• Porównaj i zapisz wyniki (znaleziona ścieżka i jej koszt, oraz ilość analizowanych węzłów).

• Dodaj informacje o odległości SLD, jako heurystyki węzłów.
• Ponownie użyj algorytmów różnego rodzaju i porównaj wyniki.

• Zamodeluj własną mapę i znajdź na niej trasę.