本页使用了标题或全文手工转换

迭代深化深度优先搜索

维基百科,自由的百科全书
跳到导航 跳到搜索

在计算机科学中,迭代深化搜索(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 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