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

Rinku privacy policy

Privacy Policy krg built the Rinku app as a Free app. This SERVICE is provided by krg at no cost and is intended for use as is. This page is used to inform visitors regarding my policies with the collection, use, and disclosure of Personal Information if anyone decided to use my Service. If you choose to use my Service, then you agree to the collection and use of information in relation to this policy. The Personal Information that I collect is used for providing and improving the Service. I will not use or share your information with anyone except as described in this Privacy Policy. The terms used in this Privacy Policy have the same meanings as in our Terms and Conditions, which are accessible at Rinku unless otherwise defined in this Privacy Policy. Information Collection and Use For a better experience, while using our Service, I may require you to provide us with certain personally identifiable information. The information that I request will be retained on your device and is not...
Post a Comment
Read more

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

Build A Family Privacy

  Privacy policy This Service is provided by KRG at no cost and is intended for use as is. This page is used to inform visitors regarding our policies with the collection, use, and disclosure of Personal Information if anyone decided to use our Service. If you choose to use our Service, then you agree to the collection and use of information in relation to this policy. The Personal Information that we collect is used for providing and improving the Service. We will never sell your information, and will not use or share your information with anyone except as described in this Privacy Policy. The terms used in this Privacy Policy have the same meanings as in our Terms and Conditions. Information Collection and Use For a better experience, while using our Service, we may require you to provide us with certain personally identifiable information, including but not limited to IDFA. The information that we request will be retained by us and used as described in this privacy policy. The a...
Post a Comment
Read more