niedziela, 30 października 2016

Zagadka o misjonarzach i kanibalach w PyGame

W ramach zabawy z nowo rozpoczętym na studiach przedmiotem nazwanym Sztuczna Inteligencja i Systemy Doradcze postanowiłem zaimplementować przeszukiwanie przestrzeni stanów problemu misjonarzy i kanibali.

Problem brzmi następująco: na brzegu rzeki stoi trzech misjonarzy, trzech kanibali łódka mieszcząca co najwyżej dwie osoby. Wszystkie sześć osób chce przedostać się na drugą stronę rzeki za pomocą łódki, każdy potrafi wiosłować.

Jedyną trudnością jest to, że pozostawienie na którymś brzegu rzeki większej liczby kanibali niż misjonarzy kończy się zjedzeniem misjonarzy.

Jeśli przy którymś brzegu stoi łódka, to liczba kanibali (misjonarzy), przy tym brzegu jest sumą kanibali (misjonarzy) w łodzi i stojących na tym brzegu.

Poniżej zamieszczam kod, który prezentuje rozwiązanie dla dowolnej liczby kanibali, misjonarzy i dowolnej pojemności łódki. Wyjście programu dla opisanego wyżej przypadku wygląda następująco.
M M M K K K  |
M M M K      | K K
M M M K K    | K
M M M        | K K K
M M M K      | K K
M K          | M M K K
M M K K      | M K
K K          | M M M K
K K K        | M M M
K            | M M M K K
M K          | M M K K
             | M M M K K K

https://gist.github.com/samorajp/a182fb22eb59fe89b620#file-misjonarze-py

Dodatkowo napisałem aplikację przy pomocy biblioteki PyGame, która przestawia rozwiązanie interaktywnie.
Kod programu wrzucony na githuba znajduje się poniżej:
https://gist.github.com/samorajp/66bbc1760b854e8ff3f1#file-pygame_vis-py
Do działania powinno wystarczyć posiadanie zainstalowanej biblioteki PyGame oraz umieszczenie w jednym katalogu pliku misjonarze.py i pygame_vis.py.




Brak komentarzy :

Prześlij komentarz