Devise your representation for the Missionaries and Cannibals problem and implement it either with pen and paper or in the programming language of your choice. Use it to solve the problem.

How efficient is your representation compared with that used in Section 3.9.1 of this book? Does it come up with the same answer?

Which approach is easier for an observer to quickly grasp? Which would you say is the better representation overall, and why?

Transcribed Image Text:

3.9.1 Example 1: Missionaries and Cannibals The Missionaries and Cannibals problem is a well-known problem that is often used to illustrate AI techniques. The problem is as follows: Three missionaries and three cannibals are on one side of a river, with a canoe. They all want to get to the other side of the river. The canoe can only hold one or two people at a time. At no time should there be more cannibals than mis- sionaries on either side of the river, as this would probably result in the mis- sionaries being eaten. To solve this problem, we need to use a suitable representation. First of all, we can consider a state in the solving of the problem to consist of a certain number of cannibals and a certain number of missionaries on each side of the river, with the boat on one side or the other. We could rep- resent this, for example, as 3,3,1 0,0,0 The left-hand set of numbers represents the number of cannibals, mission- aries, and canoes on one side of the river, and the right-hand side repre- sents what is on the other side. Because the number that is on one side is entirely dependent on the num- ber that is on the other side, we can in fact just show how many of each are on the finishing side, meaning that the starting state is represented as 0,0,0 and the goal state is 3,3,1