#1 Download computer science & engineering books free           #2 Display your sponsored posts here. Reach 10,000+ students. Contact: info[at]cpentalk.com for quote           #3 Take the Ultimate Trivia Quiz. See where you rank globally.
+1 vote
in Artificial Intelligence by
The missionaries and cannibals problem is usually stated as follows. 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. This problem is famous in AI because it was the subject of the first paper that approached problem formulation from an analytical viewpoint (Amarel, 1968).

a. Formulate the problem precisely, making only those distinctions necessary to ensure a valid solution. Draw a diagram of the complete state space.

b. Implement and solve the problem optimally using an appropriate search algorithm. Is it a good idea to check for repeated states?

c. Why do you think people have a hard time solving this puzzle, given that the state space is so simple?

1 Answer

+1 vote
by
selected by (user.guest)
 
Best answer

The given data are

1. There are three missionaries and three cannibals on the left bank of a river.

2. They wish to cross over to the right bank using a boat that can only carry two at a time.

3. The number of cannibals on either bank must never exceed the number of missionaries on the same bank, otherwise the missionaries will become the cannibals' dinner.

4. Plan a sequence of crossings that will take everyone safely across.

For solving this, we use a 3-tuple (m, c, b) to represent the state of one side of the river, since the other side can be easily inferred. Here, m stands for the number of missionaries, c, the number of cannibals, and b, whether the boat is at this side of the river. Initially, we have the state (3, 3, 1) and the goal state should be (0, 0, 0).

State space diagram

image

Here, Actions are taken as

m --- one missionary crosses the river

c --- one cannibal crosses the river

mm ---- two missionaries cross the river

cc --- two cannibals cross the river

mc --- one missionary and one cannibal cross the river

b)

Yes, it is the good idea for the repeated states to solve the problem optimally using an appropriate search algorithm. Here, all the links in the state space are bidirectional, indicating the graph is full of cycles. However, all the cycles correspond to the case where we undo an action immediately after it is performed.

c)

Even though the state space is simple, people have a hard time solving this puzzle because most of the moves are either illegal or revert to the previous state. Also there is a feeling of a large branching factor and no clear way to proceed.

Related questions

Welcome to CPEN Talk
Solution-oriented students of computer engineering on one platform to get you that

ONE SOLUTION

Chuck Norris can write multi-threaded applications with a single thread.
...