迭代深化深度优先搜索

图与树 搜索算法
α–β A* B* 回溯 集束 贝尔曼-福特 最佳优先 双向 Borůvka 分支限界 BFS 大英博物馆 D* DFS 深度限制 迪杰斯特拉 Edmonds 弗洛伊德 边缘搜索 爬山 IDA* 迭代加深 Johnson 跳点 克鲁斯克尔 词典BFS LPA* 普里姆 SMA* 最短路径快速
分类
图算法 搜索算法 算法列表
相关主题
动态规划 图的遍历 树的遍历

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

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

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

例子

走这张图

深度0

A，没了

深度1

ABCE，没了

深度2

A, B, D, F,

这时该往回走

C, G, E,完了， F（F撞了）

深度3

A, B, D, F, E,

这时该往回走

C, G,完了， E, F, B（这三个撞了）

算法

以下虛擬码展示了由递归地使用限制深度的 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