跳转至

迭代加深搜索

定義

迭代加深是一種 每次限制搜索深度的 深度優先搜索。

解釋

迭代加深搜索的本質還是深度優先搜索，只不過在搜索的同時帶上了一個深度 \(d\)，當 \(d\) 達到設定的深度時就返回，一般用於找最優解。如果一次搜索沒有找到合法的解，就讓設定的深度加一，重新從根開始。

既然是為了找最優解，為什麼不用 BFS 呢？我們知道 BFS 的基礎是一個隊列，隊列的空間複雜度很大，當狀態比較多或者單個狀態比較大時，使用隊列的 BFS 就顯出了劣勢。事實上，迭代加深就類似於用 DFS 方式實現的 BFS，它的空間複雜度相對較小。

當搜索樹的分支比較多時，每增加一層的搜索複雜度會出現指數級爆炸式增長，這時前面重複進行的部分所帶來的複雜度幾乎可以忽略，這也就是為什麼迭代加深是可以近似看成 BFS 的。

過程

首先設定一個較小的深度作為全局變量，進行 DFS。每進入一次 DFS，將當前深度加一，當發現 \(d\) 大於設定的深度 \(\textit{limit}\) 就返回。如果在搜索的途中發現了答案就可以回溯，同時在回溯的過程中可以記錄路徑。如果沒有發現答案，就返回到函數入口，增加設定深度，繼續搜索。

實現（偽代碼） 
1
2
3
4
5
6
7
IDDFS(u,d)
    if d>limit
        return
    else
        for each edge (u,v)
            IDDFS(v,d+1)
return

注意事項

在大多數的題目中，廣度優先搜索還是比較方便的，而且容易判重。當發現廣度優先搜索在空間上不夠優秀，而且要找最優解的問題時，就應該考慮迭代加深。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用