2

我正在使用 DFS 制作迷宫求解器，我想为它实现搜索树，但我对人工智能有点陌生，我想在这个问题上得到一点帮助。

我先举一个迷宫的例子：

char maze[5][9] = 
    "#########",
    "#  #    #",
    "# ##  # #",
    "#     # #",
    "#########",

所以我的 DFS 搜索树应该是这样的：

    "#########",
    "#12#15 10 11 #",
    "#3##14 9 #12 #",
    "#456 7 8 #13 #",
    "#########",

父级的第一个子级 -> 右单元格（如果为空）

父级的第二个子级 -> 底部单元格（如果为空）

父级的第三个子级 -> 左单元格（如果它为空）

父级的第 4 个子级 -> 顶部单元格（如果为空）

我的求解器将接收我的迷宫数组作为参数。我的问题是：

第一个问题：这实际上是我的演员访问节点的方式吗？

第二个问题：在代码中我需要将 15 声明为 10 的孩子吗？（在其他情况下，例如 9 和 14）

第三个问题：当我的求解器收到数组时，我是否需要对数组进行预处理并从数组中构造树，还是我的演员会在他去的时候构造它？

4

1 回答 1

2

我还假设“如果解决方案树已经在树中，则不要在解决方案树中包含节点”的规则？因为那肯定有帮助。

通常情况下，树是隐式的，你只构建你实际访问的树的部分，当你回滚时经常把东西拆掉。

您的求解器会跟踪树中的当前步骤。您可能还想跟踪您在迷宫中探索过的细胞。如果迷宫只有#和字符，则用于*表示您已访问此求解器中的单元格。

你从某个位置开始。如果那个位置是有效的，你用 a 标记它，*这样你就不会回到它，并将那个位置（比如，(1,1)）添加到你的路径的“堆栈”中。

现在，您遵循上面编写的规则。检查您当前位置下的单元格。是空的吗？（不是 a#或 a *）如果是这样，递归，询问是否找到了出路。

如果它找到了出路，则采用它找到的路径，将当前节点添加到前面，然后将该路径作为出路返回。

如果没有，请在下一个相邻单元格中搜索（按上述顺序）。

最后，用调用它的函数包装上述递归例程，然后*从映射中删除标记。

你走过的树是隐式编码的。构建树迫使您访问每个节点，并且您只想构建您必须构建的部分。

这可以通过多种方式进行优化。您可以通过处理地图的“幽灵”副本来避免写入地图。您可以通过将堆栈传递给递归版本来避免预先设置，如果它们失败，它们会小心地删除任何额外的节点，如果它们成功则将它们保持打开状态。或者您可以使用一个真正的堆栈，并使用一个包装函数（在所有工作完成后）反转路径，并以更传统的顺序对路径进行编码。

于 2013-11-08T20:34:06.193 回答