From WikiZMSI

Spis treści 1 Algorytmy przeszukiwania 1.1 Narzędzie do wykorzystania na zajęciach 1.2 Interfejs apletu 2 Zadanie domowe 2.1 Program 2.2 Sprawozdanie z wykonanych zadań 2.2.1 Wielkość problemu 2.2.2 Porównanie różnych strategii 2.2.3 Zaobserwowanie struktury drzewa 2.2.4 Wady i zalety strategii 3 Zagadnienia na wejściówkę

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.

Narzędzie do wykorzystania na zajęciach

Na zajęciach wykorzystany zostanie aplet AI-Search Algorithm Animation software prezentujący działanie różnych algorytmów przeszukiwania rozwiązując ośmioelementowe puzzle. Aplet uruchamia się w okienku i posiada własne menu.

Interfejs apletu

• Przyciski w okienku służą do wykonania zadania (rozwiązania puzzli) wybraną wcześniej z menu strategią.
  • Start - rozpoczyna od węzła startowego.
  • Next - rozwija kolejny węzeł wybrany przez daną strategię.
  • Back - cofa wykonane rozwinięcie
  • Reset - czyści ustawienia i wykonane obliczenia.
  • Suwak SLOW-FAST zmienia prędkość generowania potomków.
  • Po prawej stronie znajduje się informacja o liczbie węzłów w liście potomków, którzy czekają do rozwinięcia (OPEN LIST) jak i liście węzłów już sprawdzonych (CLOSED LIST).
  • Na końcu paska podany jest stan początkowy i końcowy (rozwiązanie).

• Okno z grafem
  • Każdy węzeł, to stan w ośmioelementowych puzzlach. Pozycja w drzewie jest prezentowana na rysunku.
  • Dwa pola pod tabliczką puzzli, to odpowiednio wartość g() --- dotychczasowy koszt ścieżki i h() ocena heurystyczna kosztu dotarcia do rozwiązania. Dla strategii przeszukiwania bez informacji pole g jest głębokością, a pole h ma wartość 0.
  • Kolory węzłów reprezentują:
    • niebieski --- lista węzłów przeszukanych (CLOSED)
    • żółty --- lista węzłów do rozwinięcia (OPEN)
    • zielony --- węzeł z listy OPEN wybrany do rozwinięcia.

• Menu Mode
  • Single step with/without algorithm --- analiza wykonania algorytmu krok po korku. Podgląd kodu algorytmu następuje przez wybranie opcji Display algorithm w menu Settings
  • User Prediction Mode --- pozwala użytkownikowi na odgadywanie kolejności rozwijanych węzłów na podstawie znajomości stosowanej strategii. Wskazuje się węzeł do rozwinięcia przez jego kliknięcie. Jeżeli wskazanie jest poprawne węzeł zostanie rozwinięty, w przeciwnym przypadku nie dzieje się nic.
  • Burst Mode --- pozwala na obserwację kształtu grafu i ocenę wielkości struktur danych (list OPEN i CLOSED) niezbędnych do znalezienia rozwiązania. W tym trybie połączenia między węzłami nie są widoczne (dla trybu Any Problem). Po znalezieniu rozwiązania ścieżka oznaczona jest zielonymi węzłami. Możliwa jest obserwacja kolejnych przeszukiwanych węzłów w trybie Fixed Problem, gdzie pokazany jest tylko fragment drzewa, gdyż rozwiązanie znajduje się na głębokości 7.

• Menu Problem
  • Pozwala na definiowanie własnego stanu początkowego (Set 8-puzzle start board).
  • Pozwala na definiowanie własnego stanu końcowego (Set 8-puzzle goal board).

Zadanie domowe

Do wyboru zadanie:

• program
• sprawozdanie.

Program

Implementacja algorytmu BFS do poszukiwania rozwiązania zadanego SUDOKU. Można użyć heurystyki: przeszukiwać najpierw gałęzie z najmniejszą liczbą wariantów. Język programowania dowolny. Zaliczenie programu przez jego omówienie i wysłanie kodu.

Sprawozdanie z wykonanych zadań

Wynik w postaci pliku o nazwie imie_nazwisko.pdf wyślij na adres prowadzącego. Wiadomość zatytułuj: Sprawozdanie WdSIBio nr 1. Poniżej opis, co powinno zawierać sprawozdanie:

Wielkość problemu

Ile istnieje permutacji (różnych stanów) układanki?

Porównanie różnych strategii

1. Uruchom aplet.
2. Z menu Mode wybierz Single Step with/without Algorithm
3. W menu Problem ustaw jako pozycję startową i końcową dowolną wybraną przez siebie i wykonaj punkty 4 i 5. Uwaga: proszę zapewnić znalezienie rozwiązania przed zawieszeniem się aplikacji :-).
4. Z menu Algorithm wybierz kolejno Depth First Search, Breadth First Search oraz A* z heurystykami NUMBER OF TAILS OUT i CITY BLOCK.
5. Wykonaj zestawienie opisujące:
   1. długość ścieżki do rozwiązania (wartość g)
   2. liczba przeszukanych węzłów (wartość po #)
   3. liczba węzłów w liście OPEN
   4. liczba węzłów w liście CLOSED
   5. wartość początkowa heurystyki
6. Zapisz wnioski z analizy danych w tabeli.

Zaobserwowanie struktury drzewa

1. Z menu Mode wybierz Burst Mode (Any 8-Puzzle Problem)
2. Z menu Algorithm wybierz kolejno Depth First Search, Breadth First Search oraz A* z heurystykami NUMBER OF TAILS OUT i CITY BLOCKi.
3. Zaobserwuj wielkość drzewa i kierunek jego przyrostu dla każdej strategii.
4. Zanotuj wnioski, jeżeli to możliwe, to narysuj schematycznie jak przebiega przeszukiwanie.

Wady i zalety strategii

Korzystając z dowolnych materiałów zestaw wady i zalety każdej ze strategii. Podaj źródła na końcu opracowania.

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 Greedy i A* mają różne heurystyki.