迭代深化深度优先搜索

本條目存在以下問題，請協助改善本條目或在討論頁針對議題發表看法。 此條目需要擴充。 (2016年12月23日) 请協助改善这篇條目，更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。 此條目没有列出任何参考或来源。 (2016年5月10日) 維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。 此條目需要編修，以確保文法、用詞、语气、格式、標點等使用恰当。 (2016年5月10日) 請按照校對指引，幫助编辑這個條目。（幫助、討論）

迭代深化深度优先搜索 （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