algorithm - 使用 DFS、BFS、A* 解决迷宫

Question

我想知道当我们对 DFS、BFS 和 A* 搜索算法使用开放迷宫或封闭迷宫时结果的变化？输出是否有很大差异，例如扩展节点数量的增加、成本等？

Answer 1

幼稚的 DFS 可以在某些开放迷宫中进入无限循环，而在封闭迷宫中它总是会结束。我认为 BFS 或 A* 不会落入那个陷阱。（“天真的 DFS”是指在遍历节点时不会将节点标记为“已访问”的节点。）编辑：丹尼尔的评论迫使我在白天重新思考这个答案，而不是在我去之前的困倦时刻床。我承认 A* 将节点标记为已访问，作为其基本功能的一部分。但是，我仍然认为 BFS 甚至可以在不标记节点的情况下解决开放的迷宫。它不会有效率，但如果有解决迷宫的方法，BFS 会找到它。根据定义，它是在移动到下一个深度之前在某个深度尝试所有可能的路径。因此，如果存在长度为 10 的解，BFS 会在尝试任何深度为 11 的解之前找到它。

Answer 2

是的。由于不同的策略以完全不同的顺序穿越迷宫，因此存在很大差异

Answer 3

与幼稚的 dfs 和 bfs 相比，A* 可能非常有效。但是你需要找到一个好的函数来评估从你当前位置到目标的成本。