Problem Statement
"Three missionaries and three cannibals are on one side of a river, along with a boat that can hold one or two people. Find a way to get everyone to the other side without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place."
Problem Formulation
Part a) Formulate the problem precisely, making only those distinctions necessary to ensure a valid solution. Draw a diagram of the complete state space. Here is my formulation of the problem with the 5 components outlined in chapter 3 of the text.
States: A state will feature the number of cannibals on left and right, number of missionaries on left and right, and whether or not the boat has crossed the river.
Initial State: 3 cannibals and 3 missionaries on left bank, the boat has not crossed the river.
Actions: SHIP(# Cannibals, #Missionaries): sends people from side the boat is currently on, to the other side.
Transition Model: SHIP: This will move the boat to whatever side of the river it isn't on. SHIP action only works if there are enough people on the side travelling, and of the given type, that are being shipped. Also the shipping may not cause missionaries to die on the other side (avoid invalid state).
NOTE A ship can't be sent across the river when empty. This is the big catch.
Goal Test: 3 cannibals and 3 missionaries are on the right bank of river. Path Cost: The number of actions needed to do this correctly.
Each action has a positive constant cost. It took me about 3 formulation attempts before I reached this conclusion. The key point is abstraction: ensuring we only describe the relevant information.
Designing for Morris_AIMA Software
I've followed my framework structure used in past for problems such as this. The design wasn't too difficult, I created a new project layout and various classes to handle nodes/states.One issue I'm finding more noticeable is unit testing. It's really essential now. Typing out code alone won't give you a precise solution, and the bugs aren't trivial as with problems such as simple searches. I'll begin with unit testing for the next problem I implement.
You can find the project code for yourself here. I created a StateNode that contains the path cost, parent, action, and state for generating a graph.
The search I used was Breadth First Search, which is optimal for this problem considering all step costs are equal.
Program demo
The program runs the main act() loop and performs breadth first search. After 11 cycles the solution is generated. The series of actions to reach the goal state are as follows.distance to goal: 11 (INITIAL STATE)
state: {LEFT=(3 cannibals, 3 missionaries RIGHT=(0 cannibals, 0 missionaries) river=left side}
ACTION: Ship(1 cannibal, 1 missionary) from left to right of river
distance to goal: 10
state: {LEFT=(2 cannibals, 2 missionaries RIGHT=(1 cannibals, 1 missionaries) river=right side}
ACTION: Ship(0 cannibals, 1 missionary) from right to left of river
distance to goal: 9
state: {LEFT=(2 cannibals, 3 missionaries RIGHT=(1 cannibals, 0 missionaries) river=left side}
ACTION: Ship(2 cannibals, 0 missionary) from left to right of river
distance to goal: 8
state: {LEFT=(0 cannibals, 3 missionaries RIGHT=(3 cannibals, 0 missionaries) river=right side}
ACTION: Ship(1 cannibals, 0 missionary) from right to left of river
distance to goal: 7
state: {LEFT=(1 cannibals, 3 missionaries RIGHT=(2 cannibals, 0 missionaries) river=left side}
ACTION: Ship(0 cannibals, 2 missionary) from left to right of river
distance to goal: 6
state: {LEFT=(1 cannibals, 1 missionaries RIGHT=(2 cannibals, 2 missionaries) river=right side}
ACTION: Ship(1 cannibals, 1 missionary) from right to left of river
distance to goal: 5
state: {LEFT=(2 cannibals, 2 missionaries RIGHT=(1 cannibals, 1 missionaries) river=left side}
ACTION: Ship(0 cannibals, 2 missionary) from left to right of river
distance to goal: 4
state: {LEFT=(2 cannibals, 0 missionaries RIGHT=(1 cannibals, 3 missionaries) river=right side}
ACTION: Ship(1 cannibals, 0 missionary) from right to left of river
distance to goal: 3
state: {LEFT=(3 cannibals, 0 missionaries RIGHT=(0 cannibals, 3 missionaries) river=left side}
ACTION: Ship(2 cannibals, 0 missionary) from left to right of river
distance to goal: 2
state: {LEFT=(1 cannibals, 0 missionaries RIGHT=(2 cannibals, 3 missionaries) river=right side}
ACTION: Ship(1 cannibals, 0 missionary) from right to left of river
distance to goal: 1
state: {LEFT=(2 cannibals, 0 missionaries RIGHT=(1 cannibals, 3 missionaries) river=left side}
ACTION: Ship(2 cannibals, 0 missionary) from left to right of river
GOAL STATE:
state: {LEFT=(0 cannibals, 0 missionaries RIGHT=(3 cannibals, 3 missionaries) river=right side}
Part b) Is it a good idea to check for repeated states?
Yes, as there are many of them in this problem. Every action can be repeated.
Part c) Why do you think people have a hard time solving this puzzle, given that the state space is so simple?
Since there are so many cycles in the state space graph, it's very simple to end up in either a repeated state, or a dead end. There are very few clean cut paths to the end-point and we as humans don't look all the way to the solution immediately. We don't use any clean cut algorithm, so it's hard for us to know if we're repeating behaviour or not.
thanks
ReplyDeleteThanks mate
ReplyDelete