Back

Explore Courses Blog Tutorials Interview Questions
0 votes
2 views
in AI and Deep Learning by (50.2k points)

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 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 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.

1 Answer

0 votes
by (108k points)

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 deal is to include just enough information in a state to be able to determine whether the state is a solution to 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 opening side of the river

  • the integer c tells how many cannibals are on the opening side

  • 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 algorithms for searching through such a set of connected states.

If you are looking to learn more about Artificial Intelligence then visit this Artificial Intelligence Course which will cover topics like Euclidean distance, Pearson Correlation Coefficient, Brute Force Algorithms, traveling salesman problem, NeuroEvolution of Augmenting Topologies, Fitness Function, Resolution Algorithm,k-nearest neighbors algorithm, Markov Model, Genetic Algorithm,deep first iterative deeping and many more.

Browse Categories

...