Geek Answers Handbook

Cannibals and missionaries using IDDFS and GreedyBFS

Three cannibals and three missionaries must cross the river. Their boat can only contain two people. If the cannibals outnumber the missionaries on both sides of the river, the missionaries are in trouble (I will not describe the results). Every missionary and cannibal can row a boat. How do all six cross the river?

I can’t find an algorithm to solve this problem using IDDFS (depth-of-depth search) and GreedyBFS (greedy best search). The idea of ​​how to solve this will make me happy.

Edited by:

I found an algorithm for IDDFS in the 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 understand what the extension (node) in DLS () should 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 be grateful for any help.

+5
2

? , - , , , 3 , ( 2 ). c m (2 c 2 ), 2 (3 c), c (2 c 3 ), c c .

, DFS? , 2 ^ 6 ( {1,2,3,4,5,6}), , , . - (, ), , - , node 0 {}, node 63 {1,2,3,4,5,6}, , BFS, DFS.

+4

, , . - ( , ). , , , , , . : m , , c , , boolean b , . (m, c, b), , , . , , .

+4
source

More articles:


All Articles