使用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()中的扩展(节点)应该在我的问题中完成.这是我的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等多种方式解决。