6

三个食人者和三个传教士必须过河。他们的船只能载两个人。如果食人族的人数超过传教士，在河的两边，传教士就有麻烦了（我不会描述结果）。每个传教士和每个食人者都可以划船。六个人怎么能过河？

我找不到使用 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;
    }

}

我将不胜感激任何帮助。

4

2 回答 2

4

没有算法怎么解决？您的模型很小，无需任何编程即可解决，前两个食人者去另一边，然后其中一个用船返回并将另一个食人者带到另一边，现在另一边有 3 个食人者其中一个返回和两个传教士去另一边（现在 2 c 和 2 m 在另一边）。在这一次，一个c带一个m回来（2 c和2 m排在第一位），然后2 m再到另一边（3 m在另一侧有一个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。

于 2012-03-24T11:47:46.710 回答
4

为了使用您提到的算法，您需要弄清楚问题的状态空间是什么。状态是对问题中某个情况的完整描述（无论是起始情况、最终情况还是中间情况）。诀窍是在一个状态中包含足够的信息，以便能够确定该状态是否是问题的解决方案，如果不是，下一步该做什么。在您的情况下，表示状态的一种可能方法是使用三个变量：整数m表示河的起点有多少传教士，整数c表示起点有多少食人族，布尔值b告诉船在哪一边。给定值(m, c, b)，您可以确定您可以采取哪些可能的操作，以及这会将您带到哪些其他状态。您提到的算法实际上是用于搜索这样一组连接状态的算法。

于 2012-03-24T11:50:57.477 回答