c++ - 为 DFS 求解器从数组构造树

Question

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

我先举一个迷宫的例子:

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

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

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

父级的第一个子级 -> 右侧单元格(如果为空)

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

父级的第三个子级 -> 左单元格(如果为空)

父级的第四个子级 -> 顶部单元格(如果为空)

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

第一个问题:这实际上是我的 actor 访问节点的方式吗？

第二个问题:在代码中我需要将 15 声明为 10 的子级吗？ (也有其他情况，例如 9 与 14)

第三个问题:当我的解算器收到数组时，我是否需要对数组进行预处理并从数组构造树，还是我的 Actor 会边构造它边做？

Answer 1

我还假设“如果节点已经在树中，则不将其包含在解决方案树中”的规则？因为这确实有帮助。

通常，树是隐式的，您只构建实际访问的树的部分，通常会在回滚时将其拆除。

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

您从某个位置开始。如果该位置有效，则用 * 标记它，这样您就不会再返回该位置，然后将该位置(例如 (1,1))添加到你的路径的“堆栈”。

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

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

如果没有，则在下一个相邻单元格中搜索(按上述顺序)。

最后，用一个调用它的函数包装上面的递归例程，然后从 map 中删除 * 标记。

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

这可以通过多种方式进行优化。您可以通过处理 map 的“幽灵”拷贝来避免写入 map 。您可以通过将堆栈传递给递归版本来避免前置，递归版本会在失败时小心地删除任何额外的节点，并在成功时保留它们。或者，您可以使用真实的堆栈，并使用包装函数向后对路径进行编码，该函数(在完成所有工作之后)反转路径，使其处于更常规的顺序。