人工智能深度優(yōu)先算法課程設(shè)計(jì)報(bào)告

1、人工智能課程報(bào)告B.深度優(yōu)先算法 題級(jí)：XXXXXXXXXXX號(hào)：XXXXXXXXXXX名：XXXXXXXXXXX【摘要】結(jié)合生活中解決搜索問題所常用的思考方法與解題方法，從深度優(yōu)先探 討了提高程序效率的適用技巧?！娟P(guān)鍵詞】1搜索順序；2搜索對(duì)象;3搜索優(yōu)化；一、深度優(yōu)先搜索的優(yōu)化技巧我們?cè)谧鍪虑榈臅r(shí)候，經(jīng)常遇到這類問題給出約束條件，求一種滿足 約束條件的方案，這類問題我們叫它約束滿足問題。對(duì)于約束滿足問題，我 們通?？梢詮乃阉鞯捻樞蚝退阉鞯膶?duì)象入手,進(jìn)而提高程序的效率。二、搜索的順序及對(duì)象：在解決約束滿足問題的時(shí)候，問題給出的約束條件越強(qiáng)，對(duì)于搜索就越有利。 之所以深度優(yōu)先搜索的效率在很大程

2、度上優(yōu)于窮舉,就是因?yàn)樗谒阉鬟^程中很 好的利用了題目中的約束條件進(jìn)行優(yōu)化，達(dá)到提高程序效率的目的。顯然，在同樣的一棵搜索樹中，越在接近根接點(diǎn)的位置利用約束條件優(yōu)化效 果就越好。如何在搜索中最大化的利用題目的約束條件為我們提供剪枝的依據(jù), 是提高深度優(yōu)先搜索效率的一個(gè)很重要的地方。而不同的搜索順序和搜索對(duì)象就 直接影響到我們對(duì)于題目約束條件的運(yùn)用。三、搜索特點(diǎn)由于深度搜索過程中有保留已擴(kuò)展節(jié)點(diǎn)，則不致于重復(fù)構(gòu)造不必要的子樹系 統(tǒng)。深度優(yōu)先搜索并不是以最快的方式搜索到解,因?yàn)槿裟繕?biāo)節(jié)點(diǎn)在第i層的某處, 必須等到該節(jié)點(diǎn)左邊所有子樹系統(tǒng)搜索完畢之后，才會(huì)訪問到該節(jié)點(diǎn)，因此，搜 索效率還取決于目標(biāo)節(jié)點(diǎn)

3、在解答樹中的位置。由于要存儲(chǔ)所有已被擴(kuò)展節(jié)點(diǎn),所以需要的內(nèi)存空間往往比較大。深度優(yōu)先搜索所求得的是僅僅是目前第一條從起點(diǎn)至目標(biāo)節(jié)點(diǎn)的樹枝路徑，而 不是所有通向目標(biāo)節(jié)點(diǎn)的樹枝節(jié)點(diǎn)的路徑中最短的路徑。適用范圍：適用于求解一條從初始節(jié)點(diǎn)至目標(biāo)節(jié)點(diǎn)的可能路徑的試題。若要存 儲(chǔ)所有解答路徑，可以再建立其它空間，用來存儲(chǔ)每個(gè)已求得的解。若要求得最 優(yōu)解，必須記下達(dá)到目前目標(biāo)的路徑和相應(yīng)的路程值，并與前面已記錄的值進(jìn)行 比較，保留其中最優(yōu)解，等全部搜索完成后，把保留的最優(yōu)解輸出。四、算法數(shù)據(jù)結(jié)構(gòu)描述深度優(yōu)先搜索時(shí)，最關(guān)鍵的是結(jié)點(diǎn)擴(kuò)展（OPEN ）表的生成，它是一個(gè)棧, 用于存放目前搜索到待擴(kuò)展的結(jié)點(diǎn)，當(dāng)結(jié)點(diǎn)

4、到達(dá)深度界限或結(jié)點(diǎn)不能再擴(kuò)展時(shí), 棧頂結(jié)點(diǎn)出棧放入CLOSE表存放已擴(kuò)展節(jié)點(diǎn)）蘭圈賣生成新的結(jié)點(diǎn)入棧OPEN 表，直到搜索到目標(biāo)結(jié)點(diǎn)或OPEN棧空為止。具體算法如下：把起始結(jié)點(diǎn)S放到非擴(kuò)展結(jié)點(diǎn)OPEN表中（后進(jìn)先出的堆棧），如果此結(jié)點(diǎn)為 一目標(biāo)結(jié)點(diǎn)，則得到一個(gè)解。如果OPEN為一空表，則搜索失敗退出。取OPEN表最前面（棧頂）的結(jié)點(diǎn)，并把它放入CLOSED的擴(kuò)展結(jié)點(diǎn)表中，并 冠以順序編號(hào)n。如果結(jié)點(diǎn)n的深度等于最大深度，則轉(zhuǎn)向2。否則，擴(kuò)展結(jié)點(diǎn)n z產(chǎn)生其全部子結(jié)點(diǎn)，把它們放入OPEN表的前頭（入棧）， 并配上指向n的返回指針;如果沒有后裔，則轉(zhuǎn)向2。如果后繼結(jié)點(diǎn)中有任一個(gè)為目標(biāo)結(jié)點(diǎn)，則求得一

5、個(gè)解，成功退出；否則，轉(zhuǎn) 向2。2、算法程序描述：遞歸遞歸過程為：Procedure DEF-GO(step)for i:=l to max doif子結(jié)點(diǎn)符合條件then產(chǎn)生新的子結(jié)點(diǎn)入棧；if子結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)then輸出else DEF-GO(step + l);棧頂結(jié)點(diǎn)出棧；endif;enddo ;主程序?yàn)?Program DFS ;初始狀態(tài)入棧；DEF-GO(l)非遞歸Program DEF(step);step:=0 ;repeat step:=step+1 ;j:=0 ; p:=falserepeat j:=j+l;if結(jié)點(diǎn)符合條件then產(chǎn)生子結(jié)點(diǎn)入棧；if子結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)then輸出else p:二true ;elseif j=max then 回:朔 p:=false ;endif ;until p二true ;until step=O ;回溯過程如下：Procedure BACK ;step:二step-1 ;if step0 then棧頂結(jié)點(diǎn)出棧else p:=true ;總結(jié)在