Skip to main content

MISSIONARY CANNIBAL PROBLEM SOLUTION IN AI | BLOG |

DATE :- 09/02/2020

Both problems we have seen in the previous module were comparatively simple as there was the little
prerequisite for applying rules. To emphasize that important part, let us take two more problems which rely heavily on the prerequisites for applying a rule.

A missionary cannibal problem

Let us take our next example to reiterate our understanding of state space, the start state, the end
state, the rules and using those rules to solve the problem, especially the preconditions under which a
rule is to be applied.

 The problem is called a missionary and cannibal problem. Three missionaries and three cannibals found themselves on one side of a river. All of them have to move to the other side. The only boat available for communication can carry maximum two of them at a time. Minimum one of the travelers must come back to get the boat on the side where others are waiting. Another condition is, at no point in time, the missionaries should be less than the number of cannibals on any side of the river (otherwise they will eat those missionaries).

One of the many ways to represent the state space is as follows.

L (M1,C1) && R (M2, C2) && (BL || BR) where

(M1 >= C1 || M1 = 0),

(M2 >= C2 || M2 = 0),

M1 + M2 = 3, M1, M2  (0, 3)

C1 + C2 = 3, C1, C2  (0, 3)

L indicates left and R indicates right sides.
M1 is missionaries on the left side while C1 indicates the cannibals on the left side,
M2 and C2 indicate the same for the right side,
A total number of missionaries and cannibals must remain the same as 3 for any valid state so the
summation of M1 and M2 and C1 and C2 must be 3 for a valid state.
BL indicates boat on the left side while BR indicates a boat on the right side. We can have a boat on one side but not on both sides of the river.
The state space thus indicates that M1 missionaries and C1 cannibals are on left side of the river while M2 missionaries and C2 cannibals are on the right side of the river and boat is either on the left or the right side of the river.

One solution


L(3,3) && R (0,0) && BL -> L(3,1) && R (0,2) && BR

L(3,1) && R (0,2) && BR-> L(3,2) && R (0,1) && BL

L(3,2) && R (0,1) && BL -> L(3,0) && R (0,3) && BR

L(3,0) && R (0,3) && BR -> L(3,1) && R (0,2) && BL

L(3,1) && R (0,2) && BL -> L(1,1) && R (2,2) && BR

L(1,1) && R (2,2) && BR -> L(2,2) && R (1,1) && BL

L(2,2) && R (1,1) && BL -> L(0,2) && R (3,1) && BR

L(0,2) && R (3,1) && BR -> L(0,3) && R (3,0) && BL

L(0,3) && R (3,0) && BL -> L(0,1) && R (3,2) && BR

L(0,1) && R (3,2) && BR -> L(0,2) && R (3,1) && BL

L(0,2) && R (3,1) && BL -> L(0,0) && R (3,3) && BR 
Labels:

Comments

Post a Comment

Popular posts from this blog

Idle Solar Defence Policy

  Privacy Policy This privacy policy applies to the Idle Solar Defence app (hereby referred to as "Application") for mobile devices that was created by krg (hereby referred to as "Service Provider") as a Free service. This service is intended for use "AS IS". Information Collection and Use The Application collects information when you download and use it. This information may include information such as Your device's Internet Protocol address (e.g. IP address) The pages of the Application that you visit, the time and date of your visit, the time spent on those pages The time spent on the Application The operating system you use on your mobile device The Application does not gather precise information about the location of your mobile device. The Service Provider may use the information you provided to contact you from time to time to provide you with important information, required notices and marketing promotions. For a better experience, while using ...
Post a Comment
Read more

Chicken Cartel Privacy Policy

  Privacy Policy This privacy policy applies to the Chicken Cartel app (hereby referred to as "Application") for mobile devices that was created by (hereby referred to as "Service Provider") as a Free service. This service is intended for use "AS IS". Information Collection and Use The Application collects information when you download and use it. This information may include information such as Your device's Internet Protocol address (e.g. IP address) The pages of the Application that you visit, the time and date of your visit, the time spent on those pages The time spent on the Application The operating system you use on your mobile device The Application does not gather precise information about the location of your mobile device. The Service Provider may use the information you provided to contact you from time to time to provide you with important information, required notices and marketing promotions. For a better experience, while using the Appl...
Post a Comment
Read more

Surf Evolution Privacy Policy

  Privacy Policy This privacy policy applies to the Surf Evolution app (hereby referred to as "Application") for mobile devices that was created by Lazy Galaxy (hereby referred to as "Service Provider") as a Free service. This service is intended for use "AS IS". Information Collection and Use The Application collects information when you download and use it. This information may include information such as Your device's Internet Protocol address (e.g. IP address) The pages of the Application that you visit, the time and date of your visit, the time spent on those pages The time spent on the Application The operating system you use on your mobile device The Application does not gather precise information about the location of your mobile device. The Service Provider may use the information you provided to contact you from time to time to provide you with important information, required notices and marketing promotions. For a better experience, while us...
Post a Comment
Read more