The problem was that these cannibals would kill and eat missionaries as soon as there were more cannibals than missionaries at some place. Thus our missionaries had to devise a plan that guaranteed that there were never any missionaries in the minority at either side of the river. The cannibals, however, could be trusted to cooperate otherwise.
![]()
Answer:
Designed and implemented a search algorithm to solve the 'Missionary and Cannibals Problem'
This is the 12 step process for completing this brain corker. I will call the starting place side A and the destination side B.
Problem Statement:
Three missionaries and three cannibals are on one side of the river, along with a boat that can hold at most two people. Find a way to get everyone from one side of the river to the other side of the river, without leaving any group of missionaries (on either side of the river or in the boat) outnumbered by the cannibals in that place.
Solution:
Consider the missionaries, cannibals and the boat are initially on the left bank of the river, and they have to go to the right bank.
State:
S= (M,C) that denotes the number of missionaries and cannibals on the left bank of the river. Thus, Start state: (3,3) and Goal state: (0,0)
![]()
Invalid States:
When the number of missionaries and cannibals on either banks of the river is greater than 3 or less than 0. Also, the number of missionaries is less than the number of cannibals on any bank of the river.
Actions:
There will be five possible actions that can occur during the various states in the problem:
One missionary moving from one bank to another: (1,0)
One cannibal moving from one bank to another: (0,1)
One missionary and one cannibal moving from one bank to another: (1,1)
Two missionaries moving from one bank to another: (2,0)
Two cannibals moving from one bank to another: (0,2)
Since there has to be at least one missionary or cannibal on the boat for it to move, (0,0) cannot be an action.
Also, whenever missionaries and/or cannibals move from left bank to right, the value of the action is subtracted, and when they move from the right bank to left, the value is added.
The state space diagram for the problem is shown below:
The highlighted blocks track the correct path from the initial state to the final state.
![]() Comments are closed.
|
AuthorWrite something about yourself. No need to be fancy, just an overview. Archives
December 2022
Categories |