什么是迭代深化深度优先搜索介绍

在计算机科学中，迭代深化搜索（iterative deepening search）或者更确切地说迭代深化深度优先搜索 (iterative deepening depth-first search (IDS or IDDFS)) 是一个状态空间（状态图）搜索策略。在这个搜索策略中，一个具有深度限制的深度优先搜索算法会不断重复地运行，并且同时放宽对于搜索深度的限制，直到找到目标状态。IDDFS 与广度优先算法是等价的，但对内存的使用会少很多；在每一步迭代中，它会按深度优先算法中的顺序，遍历搜索树中的节点，但第一次访问节点的累积顺序实际上是广度优先的。

迭代深化深度优先搜索算法

以下虚拟码展示了由递归地使用限制深度的 DFS (深度优先搜索) 算法来实现的 IDDFS 算法 (叫作 DLS)。

procedure IDDFS(root)    for depth from 0 to ∞        found ← DLS(root, depth)        if found ≠ null            return found procedure DLS(node, depth)    if depth = 0 or node is a goal        return node    else if depth > 0        foreach child of node            found ← DLS(child, depth−1)            if found ≠ null                return found    return null

迭代深化深度优先搜索特点

IDDFS结合了深度优先搜索的空间效率和广度优先搜索的完整性（当分支因子是有限的时）。当路径成本是节点深度的非递减函数时，它是最佳的。

由于迭代加深访问状态多次，它可能看起来很浪费，但事实证明并不是那么昂贵，因为在树中大多数节点都在底层，所以如果上层访问多个并不重要倍。

IDDFS在游戏树搜索中的主要优点是早期搜索倾向于改进常用的启发式方法，例如killer heuristic和alpha-beta pruning，以便在最终深度搜索时更准确地估计各个节点的得分可以发生，并且搜索完成得更快，因为它以更好的顺序完成。例如，如果首先搜索最佳动作，则alpha-beta pruning效率最高。

第二个优点是算法的响应性。因为早期迭代使用

的小值，所以它们执行得非常快。这允许算法几乎立即提供结果的早期指示，随后在

增加时进行细化。当在交互式设置中使用时，例如在国际象棋游戏程序中，该工具允许程序随时使用在其已完成的搜索中找到的当前最佳移动来播放。这可以表达为搜索的每个深度都会逐渐产生更好的解决方案近似值，尽管每个步骤完成的工作都是递归的。对于传统的深度优先搜索，这是不可能的，这不会产生中间结果。

迭代深化深度优先搜索具体介绍

迭代深化深度优先搜索时间复杂度

在一个良好平衡的树中IDDFS的时间复杂度与广度优先搜索相同，即

，其中

是分支因子，

是目标的深度。

证明

在迭代加深搜索中，深度

的节点展开一次，深度

的节点展开两次，依此类推到搜索树的根部， 被展开

次。因此，迭代深化搜索中的扩展总数是

其中

是深度展开次数

是深度{ displaystyle d-1} d-1的扩展数，依此类推。 保理

给出

让。

然后我们有

这与无限序列相比少

合并后

然后我们可以得到

自

或

是一个独立于

（深度）的常数， 如果

（即，如果分支因子大于1），深度优先迭代加深搜索的运行时间为。

迭代深化深度优先搜索例子

对于

且

，数字为

总之，从深度

一直到深度

的迭代加深搜索仅扩展

多个节点而不是单个广度 - 当

时，第一次或深度限制搜索到深度。

分支因子越高，重复扩展状态的开销越低，但即使分支因子为2，迭代加深搜索也只需要完整广度优先搜索的两倍。 这意味着迭代加深的时间复杂度仍为。

迭代深化深度优先搜索空间复杂度

IDDFS的空间复杂度是

，其中是目标

的深度。

迭代深化深度优先搜索证明

由于IDDFS在任何时候都参与深度优先搜索，因此它只需要存储一堆节点，这些节点代表它正在扩展的树的分支。 由于它找到了最佳长度的解，因此该堆栈的最大深度为

，因此最大空间量为。

通常，当存在大的搜索空间且解决方案的深度未知时，迭代深化是首选的搜索方法。

迭代深化深度优先搜索实例分析

如图一所示：

从A开始的深度优先搜索，假设在右边缘之前选择所示图形中的左边缘，并假设搜索记住先前访问过的节点并且保证不会重复（因为这是一个小图），访问节点的顺序将按照以下形式：A，B，D，F，E，C，G。在此搜索中遍历的边形成Trémaux树，这是一种在图论中具有重要应用的结构。

在不记住先前访问过的节点的情况下执行相同的搜索导致以A，B，D，F，E，A，B，D，F，E等顺序访问节点，永远得到在A，B，D，F中 ，E循环，永远不会达到C或G。

迭代加深会阻止此循环，并将在以下深度上到达以下节点，假设它从上到下依次进行：

0: A

1: A, B, C, E

（注意迭代加深已经得到了C，而传统的深度优先搜索没有。）

2: A, B, D, F, C, G, E, F

（注意，仍然得到C，但它后来出现。另请注意，它通过不同的路径看到E，并循环回F两次。）

3: A, B, D, F, E, C, G, E, F, B

对于此图，随着更多深度的添加，两个周期“ABFE”和“AEFB”将在算法放弃并尝试另一个分支之前变得更长。

迭代深化深度优先搜索相关算法

与迭代深化相似的是一种称为迭代延长搜索的搜索策略，它可以增加路径成本限制而不是深度限制。 它按照增加路径成本的顺序扩展节点; 因此，它遇到的第一个目标是路径成本最低的目标。 但迭代延长会产生大量开销，使得它不如迭代加深那么有用。

迭代加深A *是最佳优先搜索，其基于类似于在A *算法中计算的“f”值执行迭代加深。