深度受限搜尋

深度受限搜尋是一種搜尋方法，首先擴展根節點，然後擴展根節點的所有後繼，接著再擴展它們的後繼，從而一層一層的對節點進行擴展。

基本介紹

• 中文名：深度受限搜尋
• 套用領域：深度學習，電機工程

相關概述

人工智慧中的搜尋策略大體分為兩種：無信息搜尋和有信息搜尋。無信息搜尋是指我們不知道接下來要搜尋的狀態哪一個更加接近目標的搜尋策略，因此也常被成為盲目搜尋；而有信息搜尋則是用啟發函式f（n）來衡量哪一個狀態更加接近目標狀態，並優先對該狀態進行搜尋，因此與無信息搜尋相比往往能夠更加高效得解決問題。

深度優先搜尋

DFS擴展根節點的一個後繼，然後擴展它的一個後繼，直到到達搜尋樹的最深層，那裡的節點沒有後繼，於是DFS回溯到上一層，擴展另外一個未被擴展的節點。在有限狀態空間中，DFS是完備的，因為它可以把所有空間遍歷一遍；而在無限空間中，DFS則有可能會進入深度無限的分支，因此是不完備的。DFS的時間複雜度為為O(b)，而空間複雜度僅為O（d），因為我們只需要保存當前分支的狀態，因此空間複雜度遠遠好於BFS。然而DFS並不能保證找到最優解。

深度受限搜尋設定一個最大深度d_max，當搜尋深度大於d_max的時候立即回溯，從而避免了在無窮狀態空間中陷入深度無限的分支。

疊代加深的深度有限搜尋

疊代加深的深度有限搜尋也設定一個最大深度d_max，開始我們把d_max設為1，然後進行深度受限搜尋，如果么有找到答案，則讓d_max加一，並再次進行深度有限搜尋，以此類推直到找到目標。這樣既可以避免陷入深度無限的分支，同時還可以找到深度最淺的目標解，從而在每一步代價一致的時候找到最優解，再加上其優越的空間複雜度，因此常常作為首選的無信息搜尋策略。