From WikiZMSI

Spis treści 1 Przeszukiwanie przestrzeni stanów 1.1 Problemy do rozwiązania 1.1.1 Analiza problemów i przygotowanie reprezentacji 1.2 Do przeanalizowania w domu 1.3 Zagadnienia na wejściówkę

Przeszukiwanie przestrzeni stanów

Celem laboratorium jest nabycie doświadczenia w formułowaniu problemów dla zadań przeszukiwania przestrzeni stanów.

Co należy wiedzieć zanim...:

• Przeszukiwanie, to eksploracja różnych możliwych stanów rozwiązywanego problemu w poszukiwaniu zadanego rozwiązania i wybieranie spośród stanów kolejnego (strategie bez informacji) lub takiego, który daje szansę dotarcia do rozwiązania efektywniej (strategie z informacją).
• Nie trzeba znać wszystkich stanów!!! Wystarczy określić:
  • ogólną reprezentację stanu,
  • punkt startu (stan początkowy),
  • rozwiązanie (stan końcowy) oraz
  • możliwe operatory, akcje które wytworzą z jednego stanu kolejne.

Przeszukiwanie jest stosowane w różnych zadaniach: automatyczne rozwiązywanie problemów logicznych: gry, wnioskowanie (systemy ekspertowe), znajdowanie drogi w grafie (mapa, węzły sieci komputerowej), poruszanie się po nieznanym terenie (labirynt), montaż itp., itd.

Problemy do rozwiązania

Zagadnienia do analizy:

• Misjonarze i kanibale: aby zrozumieć grę należy spróbować swoich sił w grze.
• Mamy do dyspozycji dwa wiadra. Jedno ma pojemność 4l a drugie pojemność 3l. Do dyspozycji jest też nieskończony zasób wodny do napełniania wiader. Rozpoczynamy grę z pustymi wiadrami. Należy zakończyć grę, gdy w wiadrze o pojemności 4l zostaną tylko 2l, a wiadro 3l będzie puste. (Wolfram demonstration)

Analiza problemów i przygotowanie reprezentacji

• Rozważyć jakie dane muszą być pamiętane, by opisać wszystkie ważne elementy rozpatrywanego zagadnienia.
• Każda istotna dana, będzie zmienną w formalnej reprezentacji stanu (struktura danych przechowująca informacje o problemie)
• Podać reprezentację stanu i wyznaczyć dziedziny zmiennych.
• Podać stan początkowy w wybranej reprezentacji.
• Podać stan końcowy w wybranej reprezentacji.
• Rozważyć jakie operacje można wykonywać w zadaniu. Jakie są akcje dozwolone, a jakie stany są zabronione.
• Podać operatory zgodne z wybraną reprezentacją stanu. Podać dokładną listę warunków ograniczających.

Do przeanalizowania w domu

• Problem 4 hetmanów (uproszczony problem 8-hetmanów) Zagraj.
• Problem 8-puzzle. Prosta przesuwanka składająca się z 8 elementów.
• Sudoku
• Labirynt
• Krzyżówki

Zagadnienia na wejściówkę

Umiejętność analitycznego spojrzenia na różne problemy (głównie do analizy w domu) celem określenia struktury danych i funkcji (operatorów) prowadzących do formalnej reprezentacji danych.