[科普中國(guó)]-深度受限搜索

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

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

深度優(yōu)先搜索DFS擴(kuò)展根節(jié)點(diǎn)的一個(gè)后繼，然后擴(kuò)展它的一個(gè)后繼，直到到達(dá)搜索樹的最深層，那里的節(jié)點(diǎn)沒有后繼，于是DFS回溯到上一層，擴(kuò)展另外一個(gè)未被擴(kuò)展的節(jié)點(diǎn)。在有限狀態(tài)空間中，DFS是完備的，因?yàn)樗梢园阉锌臻g遍歷一遍；而在無(wú)限空間中，DFS則有可能會(huì)進(jìn)入深度無(wú)限的分支，因此是不完備的。DFS的時(shí)間復(fù)雜度為為O(b)，而空間復(fù)雜度僅為O（d），因?yàn)槲覀冎恍枰４娈?dāng)前分支的狀態(tài)，因此空間復(fù)雜度遠(yuǎn)遠(yuǎn)好于BFS。然而DFS并不能保證找到最優(yōu)解。

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

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

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

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