WsdSI/LBioJK/z1

From WikiZMSI

Spis treści

[edytuj]

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.

[edytuj]

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)
[edytuj]

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.
[edytuj]

Do przeanalizowania w domu

[edytuj]

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.

Źródło: "http://wikizmsi.zut.edu.pl/wiki/WsdSI/LBioJK/z1"