迭代深化深度优先搜索

迭代深化深度优先搜索 （iterative deepening depth-first search (IDS or IDDFS))）是对状态空间的搜索策略。它重复地运行一个有深度限制的深度优先搜索，每次运行结束后，它增加深度并迭代，直到找到目标状态。

IDDFS 与广度优先搜索有同样的时间复杂度，而空间复杂度远优。

IDDFS 第一次访问节点的累积顺序是广度优先的。

例子

对于这张图，若使用标准的深度优先搜索（DFS），则算法会在B、F、E、A之间无限循环，而永远不会检查C和G。

因此，我们可以限制搜索的深度，当达到限制深度时，即使还有未检查的子节点，也会强制搜索其他待检查的节点。

具体作法如下:

首先，限制搜索深度为0，此时只会检查A。

接着，深度增加至1，此时会依序检查A、B、C、E。

接着，深度增加至2，此时会依序检查A、B、D、F、C、G、E、F。由于深度限制的关系，算法得以检查所有的节点。

值得注意的是，在上述的示例中，F被检查了两次。这是因为DFS会优先检查一条分支上的所有节点，且检查节点的同时会将其从堆栈（stack）中移除，因此DFS往往不会避开已检查的节点，但也因此拥有优于广度优先搜索的空间复杂度。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 and 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