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

Question

三个食人者和三个传教士必须渡河。他们的船只能坐两个人。如果食人者的数量超过传教士的数量，那么在河的两边，传教士就会遇到麻烦(我不会描述结果)。每个传教士和每个食人者都可以划船。六个人怎么都过河？

我找不到使用 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) 应该在我的问题中完成什么。 这是我的节点类:

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

}

如有任何帮助，我将不胜感激。

Answer 1

没有算法如何解决？你的模型很小，不需要任何编程就可以解决，首先两个食人者去另一边，然后其中一个乘船返回并带走另一个食人者到另一边，现在另一边有 3 个食人者，其中一个背对，两个传教士去另一边(现在 2 c 和 2 m 在另一边)。在这个时候，一个 c 和一个 m 返回(2 c 和 2 m 排在第一位)，然后 2 m 到另一边(另一边 3m一个 c)，另一侧唯一的 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等方法太多了。