多目标迷宫中DFS找到非最近目标时搜索节点数能否少于BFS

首先给出明确结论：这种情况完全可能存在。

原理说明 #

我们可以结合两种搜索算法的特性分析：

• BFS是按层遍历的广搜算法，一定会优先找到距离起点最近的目标，但代价是必须遍历完当前层的所有节点，才会进入下一层搜索
• DFS是深度优先的搜索算法，会沿着一条路径走到头再回溯，只要路径上碰到目标就会立刻返回，不需要遍历同层的其他无关节点

实际场景举例 #

我们可以举一个非常直观的例子验证：
假设你的迷宫是树状结构，起点为根节点：

1. 根节点共有1000个直接子节点，其中第1000个子节点的下一级就是最近的目标A，A到起点的距离是2，是所有目标里最近的
2. 根节点的第1个子节点往下延伸3层就有另一个目标B，B到起点的距离是4，比A更远

如果DFS的遍历优先级是优先访问序号更小的子节点：

• DFS的遍历路径是根→子1→孙1→曾孙1→B，总共只搜索了5个节点就找到了目标B，直接返回结果，此时找到的B并不是最近的目标
• BFS需要先遍历完第一层的全部1000个子节点，直到遍历到第1000个子节点时，才会在下一层找到最近的目标A，整个过程至少要搜索1001个节点，远多于DFS的搜索量

Pacman场景适配 #

这种情况在Pacman游戏里非常常见：如果最近的豆子藏在排序靠后的邻接分支里，而稍远的豆子刚好在DFS优先遍历的路径上，就会出现DFS更快找到非最近目标、总搜索量远小于BFS的情况。

内容的提问来源于stack exchange，提问作者Tugsuu