[科普中國]-深度受限搜索

深度受限搜索是一種搜索方法，首先擴展根節(jié)點，然后擴展根節(jié)點的所有后繼，接著再擴展它們的后繼，從而一層一層的對節(jié)點進(jìn)行擴展。

相關(guān)概述人工智能中的搜索策略大體分為兩種：無信息搜索和有信息搜索。無信息搜索是指我們不知道接下來要搜索的狀態(tài)哪一個更加接近目標(biāo)的搜索策略，因此也常被成為盲目搜索；而有信息搜索則是用啟發(fā)函數(shù)f（n）來衡量哪一個狀態(tài)更加接近目標(biāo)狀態(tài)，并優(yōu)先對該狀態(tài)進(jìn)行搜索，因此與無信息搜索相比往往能夠更加高效得解決問題。

深度優(yōu)先搜索DFS擴展根節(jié)點的一個后繼，然后擴展它的一個后繼，直到到達(dá)搜索樹的最深層，那里的節(jié)點沒有后繼，于是DFS回溯到上一層，擴展另外一個未被擴展的節(jié)點。在有限狀態(tài)空間中，DFS是完備的，因為它可以把所有空間遍歷一遍；而在無限空間中，DFS則有可能會進(jìn)入深度無限的分支，因此是不完備的。DFS的時間復(fù)雜度為為O(b)，而空間復(fù)雜度僅為O（d），因為我們只需要保存當(dāng)前分支的狀態(tài)，因此空間復(fù)雜度遠(yuǎn)遠(yuǎn)好于BFS。然而DFS并不能保證找到最優(yōu)解。

深度受限搜索設(shè)定一個最大深度dmax，當(dāng)搜索深度大于dmax的時候立即回溯，從而避免了在無窮狀態(tài)空間中陷入深度無限的分支。1

迭代加深的深度有限搜索迭代加深的深度有限搜索也設(shè)定一個最大深度dmax，開始我們把dmax設(shè)為1，然后進(jìn)行深度受限搜索，如果么有找到答案，則讓dmax加一，并再次進(jìn)行深度有限搜索，以此類推直到找到目標(biāo)。這樣既可以避免陷入深度無限的分支，同時還可以找到深度最淺的目標(biāo)解，從而在每一步代價一致的時候找到最優(yōu)解，再加上其優(yōu)越的空間復(fù)雜度，因此常常作為首選的無信息搜索策略。2

本詞條內(nèi)容貢獻(xiàn)者為:

李斌 - 副教授 - 西南大學(xué)