0

I got an interesting problem yesterday (Yes, for homework, but it seems like this is on topic) The problem goes like this: Three missionaries and three cannibals wish to cross a river. There is a boat which can carry three people and either a missionary or a cannibal can operate the boat. It is never permissible for cannibals to outnumber missionaires, neither in the boat nor on either shore. What is the smallest number of trips necessary to make the crossing. Bonus: How many trips are necessary if the boat holds only two people?

This seems to be a popular question in the field of AI, and from what I read the only way to do it is using the sate "331" As the number of cannibals, missionaries, and boats on the wrong side respectively, and then generating all the actions that could be taken and ruling out the non valid ones, then subtracting each of the valid ones from the state, creating a "tree" of sorts and continuing until the state is "000". The only way this seems feasible to me is using a computer program (Unless you have a LOT of time on your hands), but this expects you to it on paper.

My question is, how would I complete this problem without using a computer, completely on paper?

EDIT: This seems to have caused some confusion, I want to calculate the smallest number of trips possible without actually solving the problem of how they would do it.

Community
  • 1
Nico A
  • 4,934
  • 4
  • 23
  • 49
  • https://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem#Solving – Victor Aug 07 '15 at 02:18
  • I've looked at that, and this involves taking the sate, generating each of the possible actions, taking the valid ones and generating all of the possible actions for those, and so on. I wouldn't consider that scratch paper work... that would probably lead to close to 100 or more actions to generate. – Nico A Aug 07 '15 at 02:21
  • 1
    You are overthinking the problem. A single page of paper is more than sufficient. – hardmath Aug 07 '15 at 02:34
  • 1
    Three cannibals cross the river. One comes back and and gets off the boat while the three missionaries cross. One of the other cannibals goes back and picks up the last cannibal. I don't believe it can be done in two trips. – John Douma Aug 07 '15 at 02:39

2 Answers2

2

Any state is completely determined by the number of each type of person on one particular side, and where the boat is, which is at most $4 \times 4 \times 2$ states.

Maybe you do not realize that you obviously do not have to consider the same state twice? Start with the starting state. At each step list all possible states that can be reached from the states in the list in the previous step. If your list includes the ending state you can backtrack through the lists to find your solution. Doing this already ensures that the list in each step has at most 32 states. For larger problems this may not be good enough, in which case you can exclude the states you have already seen from each list, so that each state is listed only once ever.

In general, most recursive algorithms can be exponentially sped up with the simple technique of memoization. In the above we are remembering states we have seen and avoiding them because an optimal solution will not have a cycle.

user21820
  • 57,693
  • 9
  • 98
  • 256
  • Sorry, my brain is just not working this morning, where did you get those 2 fours from? – Nico A Aug 07 '15 at 12:20
  • @TreFox: How many of each type of person can be on a particular side of the river? – user21820 Aug 07 '15 at 12:29
  • @TreFox: Using your own encoding that you never explained, you should already know how many possible states there are. – user21820 Aug 07 '15 at 12:31
  • Oh, I get what you are saying now. See my latest edit, I don't want to actually solve how they would do it, I want to calculate the least number of steps possible. Is this possible, or do you have to solve one to solve the other? – Nico A Aug 07 '15 at 13:13
  • @TreFox: Well if you understood my answer it had answered your question. You want the least steps to reach the ending state. That is exactly the number of steps you take to list the ending state! – user21820 Aug 07 '15 at 14:12
  • Oh! I get it! Sorry for the confusion, and thanks for the solution! – Nico A Aug 07 '15 at 14:21
0

One solution

Bank A$\qquad\qquad$Boat$\qquad\qquad$BankB
MMMC$\qquad\qquad$CC$\;\qquad\Rightarrow$
MMMC$\quad\Leftarrow\qquad$C$\qquad\quad\qquad$C
MMM$\;\;$$\qquad\qquad$CC$\;\qquad\Rightarrow\quad\;\,$C
MMM$\;\;\quad\Leftarrow\qquad$C$\qquad\quad\qquad$CC
MC$\;\;\;\;\;\;\qquad\qquad$MM$\qquad\Rightarrow\;\;\;\,$CC
MC$\qquad\;\;\Leftarrow\qquad$MC$\qquad\qquad\;$MC
CC$\qquad\;\;\;\;\;\;\;\qquad$MM$\qquad\Rightarrow\;\;\;\,$MC
CC$\qquad\;\;\;\Leftarrow\qquad$C$\qquad \qquad\;\;\;\;$MMM

The rest is obvious.
Regarding your question as to how you would go about it using just pen and paper, I started with the state BankA{MC}, Boat{MC}, BankB{MC}, there wasn't too much fiddling around from there to get the answer, not much paperwork at all.

Peter
  • 366