java - 食人族和传教士使用IDDFS和GreedyBFS

三名食人者和三名传教士必须过河。他们的船只能容纳两个人。如果食人者的人数超过了在河两岸的传教士，那么传教士将陷入困境(我不会描述结果)。每个宣教士和每个食人者都可以划船。六个人怎么过河？

我找不到使用IDDFS(迭代加深深度优先搜索)和GreedyBFS(贪婪最佳优先搜索)来解决此问题的算法。如何解决这个问题的想法也会让我高兴。

编辑:

我在Wiki上找到了IDDFS的算法:

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
}

但是我不知道在我的问题中DLS()中的expand(node)应该完成什么。
这是我的Node类:

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;
    }

}

我将不胜感激任何帮助。

最佳答案

没有算法怎么解决？ 您的模型很小，无需进行任何编程即可求解，首先有两个食人族前往另一侧，然后其中一个背着船向另一侧吞下另一个食人族，现在另一侧有3个食人族后背和两名传教士前往另一侧(现在2 c和2 m在另一侧)。在这个时候，一个带有一个c的m回来了(第一个位置2 c和2 m)，然后又回到了另一边2 m(另一边带有一个c的另一个3m)，另一边的唯一c又回来了并在另一侧携带两个c(在另一侧携带2 c和3 m)，再次一个c返回，并将最新的c移到另一侧。

如何使用DFS之类的算法对其进行仿真？ 创建一个有向图，有2 ^ 6个位置({1,2,3,4,5,6}的所有可能子集)，如果您可以使用可用的移动方法从一个位置转到另一个位置，则它们相互关联。一些节点是死节点(在一侧会导致更多食人的节点)，您将从图形中删除该节点，然后您的任务是检查是否存在从节点0 {}到节点63 {1,2的方法。 ，3,4,5,6}，这可以通过多种方式解决，例如BFS，DFS。