Cannibals and missionaries using IDDFS and GreedyBFS

Question

Three cannibals and three missionaries must cross a river. Their boat can only hold two people. If the cannibals outnumber the missionaries, on either side of the river, the missionaries are in trouble (I won't describe the results). Each missionary and each cannibal can row the boat. How can all six get across the river?

I can't find an algorithm for solving this problem using IDDFS (Iterative deepening depth-first search) and GreedyBFS (greedy best-first search). An idea on how to solve this would make me happy as well.

Edited:

I found an algorithm for IDDFS on wiki:

IDDFS(root, goal)
{
  depth = 0
  repeat
  {
    result = DLS(root, goal, depth)
    if (result is a solution)
      return result
    depth = depth + 1
  }
}


DLS(node, goal, depth) 
{
  if (depth == 0 and node == goal)
    return node
  else if (depth > 0)
    for each child in expand(node)
      DLS(child, goal, depth-1)
  else
    return no-solution
}

But I can't figure out what expand(node) in DLS() is supposed to accomplish in my problem. This is my Node class:

public class Node{
    //x-no of missionaries
    //y-no of cannibals
    //z-position of boat
    int x,y;
    boolean z;
    Node(int x,int y,boolean z){
        this.x=x;
        this.y=y;
        this.z=z;
    }
    public int getM(){
        return this.x;
    }
    public int getC(){
        return this.y;
    }
    public boolean getB(){
        return this.z;
    }
    public void setM(int x){
        this.x=x;
    }
    public void setC(int y){
        this.y=y;
    }
    public void setB(boolean z){
        this.z=z;
    }

}

I would appreciate any help.

Are you struggling with seeing how the state space can be explored with a search, or with what the criterion for the best path should be? — Aasmund Eldhuset, Mar 24 '12 at 11:29
*"How can all six get across the river?"* Well, if you mean 'alive or semi-digested', the problem is easy! ;) — Andrew Thompson, Mar 24 '12 at 11:32
It's usually not the search method but your representation of the problem. What are all the possible actions and states in this problem? Also note that people can get on board at either side of the river, not just the side at which they started. — Simeon Visser, Mar 24 '12 at 11:33
I'm trying to implement a search algorithm using IDS and GBFS.But I can't figure out how they(IDS and GBFS) work. — user1217380, Mar 24 '12 at 11:42
@user unknown: since only two people can use the boat at the same time, neither party can form a majority on the boat. — Philip, Mar 27 '12 at 07:54

Saeed Amiri · Accepted Answer · 2012-03-24T12:03:30.873

How to solve it without algorithm? your model is small and it can be solve without any programming, first two cannibals going to the other side, then one of them backs with boat and takes another cannibal to other side, now there are 3 cannibals on the other side one of them backs and two missionary going to the other side (now 2 c and two m are in other side). in this time one c with one m comes back (2 c and 2 m in first place), and again 2 m going to the other side (3m in other side with one c), again the only c in the other side comes back and carries two c on the other side (2 c and 3 m in the other side), again one c comes back and moves latest c to the other side.

How to simulate it with algorithms like DFS? Create a digraph, there are 2^6 positions (all possible subsets of {1,2,3,4,5,6}), they are related to each other if you can go from one position to another by using available moves. some nodes are dead nodes (nodes which causes more cannibal in one side), you will remove this nodes from your graph, then your task is to check is there a way to go from node 0 {}, to node 63 {1,2,3,4,5,6}, which can be solve in too many ways like BFS, DFS.

score 4 · Answer 2 · answered Mar 24 '12 at 11:50

In order to use the algorithms you mention, you need to figure out what the state space of the problem is. A state is a complete description of a situation in the problem (be it the starting situation, the final situation, or an intermediate situation). The trick is to include just enough information in a state to be able to determine whether the state is a solution of the problem, and, if not, what to do next. In your case, one possible way of representing the state is to use three variables: the integer m tells how many missionaries are on the starting side of the river, the integer c tells how many cannibals are on the starting side, and the boolean b tells which side the boat is on. Given values for (m, c, b), you can determine which possible actions you can take, and which other states this will bring you to. The algorithms you mention are really algorithms for searching through such a set of connected states.

Cannibals and missionaries using IDDFS and GreedyBFS

2 Answers2