三名食人族和三名传教士需要渡过一条河。他们的船只能承载两人。如果在河的任何一边，食人族的数量超过了传教士，传教士就会有麻烦（我就不描述结果了）。每个传教士和每个食人族都可以划船。如何让这六个人都安全渡河呢？

我找不到使用IDDFS（迭代加深深度优先搜索）和GreedyBFS（贪婪最佳优先搜索）来解决这个问题的算法。如果能得到解决这个问题的思路，我会很高兴。

编辑：

我在维基上找到了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-传教士数量    //y-食人族数量    //z-船的位置    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;    }}

任何帮助我都会非常感激。

回答：

如何在不使用算法的情况下解决这个问题？ 你的模型很小，可以不通过编程来解决。首先，两个食人族渡到对岸，然后其中一个返回并带另一个食人族到对岸，现在对岸有三个食人族，其中一个返回，然后两个传教士渡到对岸（现在对岸有两个食人族和两个传教士）。此时，一个食人族和一个传教士返回（在起始地点有两个食人族和两个传教士），然后两个传教士再次渡到对岸（对岸有三个传教士和一个食人族），然后对岸唯一的食人族返回并带两个食人族到对岸（对岸有两个食人族和三个传教士），然后一个食人族返回并带最后一个食人族到对岸。

如何使用像DFS这样的算法来模拟这个问题？ 创建一个有向图，有2^6个位置（{1,2,3,4,5,6}的所有可能子集），如果可以通过可用的移动从一个位置到达另一个位置，则它们之间有关联。有些节点是死节点（导致一侧食人族数量更多的节点），你需要从图中移除这些节点，然后你的任务是检查是否有从节点0 {}到节点63 {1,2,3,4,5,6}的路径，这可以通过许多方法解决，如BFS、DFS。