====== - 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.


===== Wprowadzenie =====

Do przeczytania i przygotowania:
  * [[http://artint.info/html/ArtInt_46.html|3 States and Searching]]
  * [[http://aima.cs.berkeley.edu/|3 Solving Problems by Searching]]

===== Narzędzia =====

Podstawowym narzędziem do realizacji ćwiczeń jest program [[http://www.aispace.org/search/|Graph Searching]] z [[http://www.aispace.org|AIspace]].

Uzupełniająco i poszerzająco, można po zajęciach przejść do laboratorium  [[http://ai.ia.agh.edu.pl/wiki/pl:prolog:prolog_lab:prolog_lab_graphsearch|Planowanie tras przejazdu w Prologu]].

===== Ćwiczenia =====
==== Proste grafy ====

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]]

  - Załaduj przykładowe zadanie //Simple Tree Graph//.
  - Zaznajom się z możliwościami wyświetlania parametrów grafu.
  - Zapisz go pod nową nazwą.
  - 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)
  - Zmodyfikuj graf i powtórz szukanie rozwiązań.
  - Przeanalizuj inne dostarczone przykłady, znajdź taki, na którym można pokazać lepsze działanie algorytmu heurystycznego.

==== Analiza przykładu: podróż do Bukaresztu ====
Przykład pochodzi z [[http://aima.cs.berkeley.edu/|3 Solving Problems by Searching]].

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

{{:pl:prolog:prolog_lab:aima-romania-distances.png|Mapa drogowa Rumunii}}

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

{{:pl:prolog:prolog_lab:aima-romania-sld.png|Odległości w linii prostej}}

==== Modelowanie przykładu ====

  * 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.

==== Szukanie trasy ====

  * Znajdź trasę (zakładka //Solve//).
  * Wypróbuj różne algorytmy szukania w tym [[http://www.aispace.org/search/help/tutorial4.shtml|nieherustyczne i heurystyczne]].
  * Porównaj i zapisz wyniki (znaleziona ścieżka i jej koszt, oraz ilość analizowanych węzłów). 

==== Heurystyczne szukanie trasy ====

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

==== Własna mapa ====

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