SZI2017/Ćwiczenia2

Ćwiczenia 2

Reprezentowanie łamigłówek jako przestrzeni stanów

Przestrzenie stanów

Przestrzenie stanów stanowią wygodny sposób reprezentowania szerokiej klasy problemów. Przestrzeń stanów to graf skierowany (niekoniecznie skończony), w którym węzły odpowiadają możliwym “sytuacjom”, pojawiającym się w trakcie rozwiązywania problemu, zaś łuki - dozwolonym przejściom między sytuacjami. W przestrzeni stanów wyróżniamy stan początkowy oraz stany docelowe.

Na dzisiejszych ćwiczeniach nauczymy się, jak reprezentować różne problemy-łamigłówki jako przestrzenie stanów, na kolejnych zajęciach zobaczymy, jak można te łamigłówki rozwiązać.

Dla wszystkich problemów przyjmiemy jednolitą reprezentację w Pythonie, otóż zakładamy, że problem jest reprezentowany przez klasę z następującymi metodami:

  • is_valid_state(state) — sprawdza, czy state jest poprawnym stanem,

  • is_target(state) — sprawdza, czy state jest stanem docelowym,

  • transition(state) — zwraca listę wszystkich stanów osiągalnych bezpośrednio ze stanu state (ewentualnie transition_with_cost(state), która zwraca listę par stan-koszt).

Programowanie obiektowe w Pythonie nie jest trudne, zob. http://docs.python.org/tutorial/classes.html, na dzisiejsze zajęcia wystarczy wzorować się na przykładzie puzzles/CrossingRiver.py.

Przykładowe „uruchomienie” łamigłówki można znaleźć w pliku puzzles/demo.py.

Szukanie drogi (“GPS”, zadanie 201)

W tym zadaniu uwzględnimy koszt (celem będzie znalezienie najkrótszej drogi) - zamiast transition należy opracować metodę transition_with_cost, która zamiast listy stanów osiągalnych zwraca listę par stan osiągalny-koszt.

Zakładamy, że opis połączeń znajduje się w pliku tekstowym, każde połączenie opisane w osobnym wierszu za pomocą trzech pól oddzielonych tabulatorami (“”) - miasto1, miasto2, odległość między miastami (liczba całkowita).

Rozwiązując to zadanie należy się wzorować na puzzles/CrossingRiver.py, z tym, że należy zdefiniować transition_with_cost zamiast transition.

Przelewanie wina (zadanie 202)

Oto klasyczna zagadka o przelewaniu wina:

Mamy trzy beczułki wina: 6-litrową, 11-litrową i 16-litrową. Beczułka 16-litrowa jest pełna wina, zaś 6- i 11-litrowe są puste. Jak przelewać wino z beczułki do beczułki, by ostatecznie beczułka 16-litrowa zawierała połowę swojej początkowej zawartości (8 litrów - pozostałe 8 litrów ma znaleźć się w beczułce 11-litrowej)? Beczułki nie mają podziałki, w pojedynczym kroku można albo przelać całą zawartość jednej beczułki do drugiej (jeśli w tej drugiej starczy miejsca), albo dolać do beczułki do pełna z innej beczułki.

My rozpatrzymy wersję uogólnioną:

Opracować reprezentację przestrzeni stanów dla uogólnionej zagadki o przelewaniu wina: mamy N beczułek z winem o pojemnościach V1, V2,…VN litrów. W chwili początkowej beczułki zawierają odpowiednio A1, A2,…AN litrów wina. Dążymy do tego, by beczułki zawierały odpowiednio Z1, Z2,…ZN litrów wina.

Rozwiązując to zadanie należy się wzorować na pliku puzzles/CrossingRiver.py.