有界深度優(yōu)先搜索算法的實現(xiàn)

1、實驗報告有界深度優(yōu)先搜索算法的實現(xiàn)實驗目的（1）熟悉盲目搜索一有界深度優(yōu)先算法；（2）通過實驗實際操作有界深度優(yōu)先算法的運行，深入理解其內(nèi)涵；（3）掌握有界深度優(yōu)先算法，并會在其他問題中運用。實驗原理問題描述八數(shù)碼問題也稱為九宮問題。在3X3的棋盤，擺有八個棋子，每個 棋子上標有1至8的某一數(shù)字，不同棋子上標的數(shù)字不相同。棋盤上 還有一個空格（以數(shù)字0來表示），與空格相鄰的棋子可以移到空格 中。要求解決的問題是：給出一個初始狀態(tài)和一個目標狀態(tài)，找出一 種從初始轉(zhuǎn)變成目標狀態(tài)的移動棋子步數(shù)最少的移動步驟。所謂問題 的一個狀態(tài)就是棋子在棋盤上的一種擺法。解八數(shù)碼問題實際上就是 找出從初始狀態(tài)到達目

2、標狀態(tài)所經(jīng)過的一系列中間過渡狀態(tài)。（2）有界深度優(yōu)先算法原理它是從根節(jié)點開始，首先擴展最新產(chǎn)生的節(jié)點，即沿著搜索樹的深度 發(fā)展下去，一直到?jīng)]有后繼結(jié)點處時再返回，換一條路徑走下去。就 是在搜索樹的每一層始終先只擴展一個子節(jié)點，不斷地向縱深前進直 到不能再前進（到達葉子節(jié)點或受到深度限制）時，才從當前節(jié)點返 回到上一級節(jié)點，沿另一方向又繼續(xù)前進。這種方法的搜索樹是從樹 根開始一枝一枝逐漸形成的。由于一個有解的問題樹可能含有無窮分枝，深度優(yōu)先搜索如果誤入無 窮分枝(即深度無限)，則不可能找到目標節(jié)點。為了避免這種情況 的出現(xiàn)，在實施這一方法時，定出一個深度界限，在搜索達到這一深 度界限而且尚未找到

3、目標時，即返回重找，所以，深度優(yōu)先搜索策略 是不完備的。另外，應用此策略得到的解不一定是最佳解(最短路徑)。實驗內(nèi)容1、熟悉了解有界深度優(yōu)先算法；2、對課堂上講解的八數(shù)碼難題的例題(深度界限設為5)，編程求 解。實驗步驟設置深度界限，假設為5；判斷初始節(jié)點是否為目標節(jié)點，若初始節(jié)點是目標節(jié)點則搜索過 程結(jié)束；若不是則轉(zhuǎn)到第2步；由初始節(jié)點向第1層擴展，得到節(jié)點2,判斷節(jié)點2是否為目標節(jié) 點；若是則搜索過程結(jié)束；若不是，則將節(jié)點2向第2層擴展，得到 節(jié)點3；判斷節(jié)點3是否為目標節(jié)點，若是則搜索過程結(jié)束；若不是則將 節(jié)點3向第3層擴展，得到節(jié)點4；判斷節(jié)點4是否為目標節(jié)點，若是則搜索過程結(jié)束；若不

4、是則將 節(jié)點4向第4層擴展，得到節(jié)點5；判斷節(jié)點5是否為目標節(jié)點，若是則搜索過程結(jié)束；若不是則結(jié) 束此輪搜索，返回到第2層，將節(jié)點3向第3層擴展得到節(jié)點6；判斷節(jié)點6是否為目標節(jié)點，若是則搜索過程結(jié)束；若不是則將節(jié)點6向第4層擴展，得到節(jié)點7；判斷節(jié)點7是否為日標節(jié)點，若是則結(jié)束搜索過程；若不是則將節(jié)點6向第4層擴展得到節(jié)點8；依次類推，直到得到日標節(jié)點為止；搜索過程見附圖2所示。34534 5-873453452764S34334534583782/0J63453450J65534534334580J34586 734 56 345 860-4 3 P-8734 5 127 &34567 C

5、U&35 84 7 ocfe J4536 73B5 0J. -6 217345 87 ruBl276程序?qū)嶒灲Y(jié)果和分析通過這次實驗和以前做過的分析，在寬度優(yōu)先搜索過程中，擴展到第26個節(jié)點時找到了目標節(jié)點；而在深度優(yōu)先搜索過程中，擴展到第 18個節(jié)點時得到了目標節(jié)點。在寬度優(yōu)先搜索過程中，需要遍歷目標節(jié)點所在層之前每層的所有節(jié) 點，即需要遍歷所有的分支。而深度優(yōu)先搜索過程中，則不需要遍歷 這么多的節(jié)點。所以，冷八”數(shù)碼難題的求解過程中，深度優(yōu)先搜索 的效率明顯比寬度優(yōu)先搜索的效率要高。一般情況下，深度優(yōu)先適合深度大的樹，不適合廣度大的樹，廣度優(yōu) 先則正好相反。所謂深度大的樹就是指起始節(jié)點到目標節(jié)點的中間節(jié) 點多的樹（可以理解成問題有很多中間解，這些解都可以認為是部分 正確的，但要得到完全正確的結(jié)果目標節(jié)點，就必須先依次求出 這些中間解）。所謂廣度大的樹就是指起始節(jié)點到目標節(jié)點的可能節(jié) 點很多的樹（可以理解成問題有很多可能解，這些解要么正確，要么 錯誤。要得到完全正確的結(jié)果目標節(jié)點，就必