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:

Narzędzia

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.

Ć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

  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.

Analiza przykładu: podróż do Bukaresztu

Przykład pochodzi z 3 Solving Problems by Searching.

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

Mapa drogowa Rumunii

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

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 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ę.
pl/prolog/prolog_lab/classicsearch.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0