关于广度优先完整性与深度优先不完整性的问题
geo*_*rge 13 breadth-first-search depth-first-search
根据Norimaig在AIMA(人工智能:一种现代方法)中,深度优先算法并不完整(并不总是产生解决方案),因为有些情况下子树下降将是无限的.
另一方面,如果分支因子不是无限的,则称广度优先方法是完整的.但是,在DFS中子树无限的情况下,是不是有点像"东西"？
如果树的深度是有限的,那么DFS不能说是完整的吗？那么BFS是如何完成的而DFS不是完整的,因为BFS的完整性依赖于分支因子是有限的!
没有无限的分支因子,树可以是无限的.例如,考虑Rubik's Cube的状态树.给定立方体的配置,有一定数量的移动(18,我相信,因为移动包括选择9个"平面"中的一个并在两个可能的方向之一中旋转它).然而,树是无限深的,因为完全可能例如仅交替地来回旋转同一平面(从未取得任何进展).为了防止DFS这样做,通常会缓存所有访问状态(有效地修剪状态树) - 正如您可能知道的那样.但是,如果状态空间太大(或实际上是无限的),这将无济于事.
我没有广泛研究过AI,但是我认为说DFS不完整的理由是(完全性毕竟只是一个定义的术语)是无限深的树比无限的树更频繁地出现分支因子(因为具有无限的分支因子意味着你有无数的选择,我认为这种选择并不常见 - 游戏和模拟通常是离散的).即使对于有限树,BFS通常也会表现得更好,因为DFS很可能从错误的路径开始,在到达目标之前探索树的大部分.不过,正如你指出,在一个有限的树,DFS 将最终找到解决办法,如果它的存在.
DFS不能卡在循环中(如果我们有一个打开和关闭状态列表).算法不完整,因为它在无限空间中找不到解,即使解的深度d远低于无穷大.
想象一个奇怪定义的状态空间,其中每个节点具有与Fibonacci序列中的跟随数相同的后继数.因此,它是递归定义的,因此是无限的.我们正在寻找节点2(图中标记为绿色).如果DFS以树的右分支开始,则将需要无数个步骤来验证我们的节点不在那里.因此它不完整(它不会在合理的时间内完成).BFS会在第3次迭代中找到解决方案.
Rubik的立方体状态空间是有限的,它是巨大的,但是有限的(人类陷入循环但DFS不会重复相同的移动两次).DFS会发现如何解决它的效率非常低,有时这种解决方案是不可行的.通常我们认为最大深度是无限的,但我们的资源(存储器)总是有限的.