迭代深化深度优先搜索 - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for 迭代深化深度优先搜索.

迭代深化深度优先搜索

维基百科,自由的百科全书

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

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

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

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


例子

Graph.traversal.example.svg

走这张图

深度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
{{bottomLinkPreText}} {{bottomLinkText}}
迭代深化深度优先搜索
Listen to this article