我想知道当我们使用开放迷宫或封闭迷宫进行DFS、BFS和A*搜索算法时,结果会发生什么变化?输出是否有较大差异,例如扩展节点数量的增加、成本等?
最佳答案
朴素的 DFS 在某些开放式迷宫中可能会进入无限循环,而在封闭式迷宫中它总是会结束。我不认为 BFS 或 A* 会落入这个陷阱。 (我所说的“朴素 DFS”是指在遍历节点时不会将节点标记为“已访问”的 DFS。) 编辑:丹尼尔的评论迫使我在白天而不是在 sleep 前的困倦时刻重新思考这个答案。我承认 A* 将节点标记为已访问,作为其基本功能的一部分。然而,我仍然认为 BFS 甚至可以在不标记节点的情况下解决开放迷宫。虽然效率不高,但如果迷宫有解,BFS 就会找到它。根据定义,它会在进入下一个深度之前尝试某个深度的所有可能路径。因此,如果存在长度为 10 的解,BFS 会在尝试任何深度为 11 的解之前找到它。
关于algorithm - 使用 DFS、BFS、A* 解决迷宫,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3315241/