搜索習題

1、1、迷宮問題如下，F(xiàn)是入口，B是出口，試采用深度優(yōu)先搜索算法進行求解。,F,G,H,E,C,A,D,B,,,,,,,,,,,,深度優(yōu)先搜索結(jié)果：搜索到的路徑為粗線所示,F,G,H,E,C,A,B,,,,,,,1,2,3,4,5,6,OPEN:{G}CLOSED:{F},OPEN:{H,E}CLOSED:{F,G},OPEN:{E}CLOSED:{F,G,H},OPEN:{A,C}CLOSED:{F,G,H,E},OPEN:{B,

2、C}CLOSED:{F,G,H,E,A},OPEN:{C}CLOSED:{F,G,H,E,A},2、上述問題采用寬度優(yōu)先搜索算法進行求解。,F,G,H,E,C,A,D,B,,,,,,,,,,,,F,G,H,E,C,A,D,B,,,,,,,,1,2,3,4,5,6,7,寬度優(yōu)先搜索：搜索到的路徑為粗線所示。,8,OPEN:{G}CLOSED:{F},OPEN:{E,H}CLOSED:{F,G},OPEN:{H,C,A}CLOSE

3、D:{E,G,E},OPEN:{C,A}CLOSED:{F,G,E,H},OPEN:{A,D}CLOSED:{F,G,E,H,C},OPEN:{D,B}CLOSED:{F,G,E,H,C,A},OPEN:{B}CLOSED:{F,G,E,H,C,A,D},OPEN:{}CLOSED:{F,G,E,H,C,A,D},3、對左圖采用分支界限法(均一代價法)進行搜索求解。,LISP算法解析,分支界限搜索樹,分支搜索路徑過程,4、對上

4、題采用動態(tài)規(guī)劃法搜索解決。 ——動態(tài)規(guī)劃法實際上是分支界限法的改進。對某個中間節(jié)點來說，也許有多條路徑可達到它，但只保留耗散值最小的那條路徑。,3、用A*算法求解下列八數(shù)碼魔方，啟發(fā)函數(shù)h*(n)分別采用：1) h=0;2) h為放錯的棋子數(shù)；3) h為用曼哈頓距離的和。,5,6,7,4,8,1,3,,2,,,,,,,,,5,6,7,4,,8,3,2,1,,,,,,,,,解題分析：,由于A*算法的估價函數(shù)為：

5、 f*(n)=g*(n)+h*(n) 其中，g*(n)代表從初始點到n的路徑代價和； h*(n)代表從n開始到目標的距離估算值。當h*(n)=0時，則A*算法的估價函數(shù)只剩下g*(n)，即為均一代價算法。,1) h=0, 即為均一代價搜索算法(粗線表示搜索到的路徑，小括號內(nèi)的數(shù)字為該節(jié)點的代價值),,,,,,,,,,,1,,,,,,,,,A,2,3,4,5,6,7,8,9

6、,10,11,1,2,3,8,4,5,6,7,,,B,C,D,,目標,OPEN:{B,C,D}CLOSED:{A},2)h為放錯的棋子數(shù)，則f*(n)=g*(n)+h*(n)。,,,,,,,1,2,3,4,(3=0+3),(3=1+2),(5=1+4),(4=1+3),(3=2+1),(5=3+2),(3=3+0),,,,粗線表示搜索到的路徑，小括號內(nèi)的數(shù)字為該節(jié)點的估價函數(shù)值,A,OPEN:{B(3), D(4), C(5)}CL

7、OSED:{A(3)},OPEN:{E(3), D(4), C(5)}CLOSED:{A(3),B(3)},B,C,D,E,F,G,OPEN:{G(3), D(4), C(5),F(5)}CLOSED:{A(3),B(3),E(3)},OPEN:{D(4), C(5),F(5)}CLOSED:{A(3),B(3),E(3)},3) h是節(jié)點中每個棋子與目標位置的最短距離(曼哈頓距離)之和。,,,,,,,1,2,3,4,(3=0+

8、3),(3=1+2),(5=1+4),(5=1+4),(3=2+1),(5=3+2),(3=3+0),粗線表示搜索到的路徑，小括號內(nèi)的數(shù)字為該節(jié)點的估價函數(shù)值,OPEN:{B(3), D(4), C(5)}CLOSED:{A(3)},A,B,C,D,OPEN:{E(3),D(4), C(5)}CLOSED:{A(3),B(3)},OPEN:{G(3), D(4), C(5),F(5)}CLOSED:{A(3),B(3),E(3)}

9、,E,F,G,OPEN:{ D(4), C(5),F(5)}CLOSED:{A(3),B(3),E(3)},4、對右圖所示的狀態(tài)空間圖進行：1) 深度優(yōu)先搜索;2) 寬度優(yōu)先搜索；3) 均一代價搜索；4) 最佳優(yōu)先搜索；5) A*搜索。其中A為起始節(jié)點，E為目標節(jié)點，各節(jié)點的啟發(fā)值表示在括號內(nèi)。,F,G,H,E,C,A,D,B,4,2,3,4,8,2,,,,,,,,4,3,,,3,,8,,5,(15),(14),(10),

10、(2),(11),(9),(5),(0),1) 深度優(yōu)先搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,,,,,,,,搜索出的路徑為： A?B?C?D?E,5,OPEN:{B,H}CLOSED:{A},OPEN:{C,H}CLOSED:{A,B},OPEN:{D,G,H}CLOSED:{A,B,C},OPEN:{E,F,G,H}CLOSED:{A,B,C,D},OPEN:{F,G,H}CLOSED:{A,B,C,D}

11、,2) 寬度優(yōu)先搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,,,,,,,,5,6,7,搜索到的路徑為：A?B?C? D?E,8,OPEN:{B,H}CLOSED:{A},OPEN:{H,C}CLOSED:{A,B},OPEN:{C,G}CLOSED:{A,B,H},OPEN:{G,D}CLOSED:{A,B,H,C},OPEN:{D,F}CLOSED:{A,B,H,C,G},OPEN:{F,E}CLOSED:{

12、A,B,H,C,G,D},OPEN:{E}CLOSED:{A,B,H,C,G,D,F},OPEN:{}CLOSED:{A,B,H,C,G,D,F},3) 均一代價搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,,,,,,,,,5,6,7,搜索出的路徑為： A?H?G?F?D?E，整條路徑的代價和為15。,8,OPEN:{B(3),H(4)}CLOSED:{A(0)},OPEN:{H(4),C(7)}CLOSED:{A(

13、0),B(3)},OPEN:{G(6),C(7)}CLOSED:{A(0),B(3),H(4)},OPEN:{C(7),F(10),D(14)}CLOSED:{A(0),B(3),H(4),G(6)},OPEN:{F(10),D(14)}CLOSED:{A(0),B(3), H(4),G(6),C(7)},OPEN:{D(14→13)}CLOSED:{A(0),B(3),H(4),G(6),C(7),F(10)},OPEN:

14、{E(15)}CLOSED:{A(0),B(3),H(4),G(6),C(7),F(10),D(14 →13)},OPEN:{}CLOSED:{A(0),B(3),H(4),G(6),C(7),F(10),D(14→13)},4) 最佳優(yōu)先搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,,,,,,,搜索出的路徑為： A?H?G?D?E，整條路徑的代價和為16。,OPEN:{H(11),B(14)}CLOSED:{A(15

15、)},OPEN:{G(9),B(14)}CLOSED:{A(15),H(11)},OPEN:{D(2),F(5),C(10),B(14)}CLOSED:{A(15),H(11),G(9)},OPEN:{E(0),F(5),C(10),B(14)}CLOSED:{A(15),H(11),G(9),D(2)},5,OPEN:{F(5),C(10),B(14)}CLOSED:{A(15),H(11),G(9),D(2)},,5) A*

16、算法,F,G,H,E,A,B,1,2,3,4,C,D,,,,,,,,5,搜索出的路徑為： A?H?G?D?E，整條路徑的代價和為15。,6,OPEN:{H(15),B(17)}CLOSED:{A(15)},OPEN:{G(15),B(17)}CLOSED:{A(15),H(15)},OPEN:{F(15),D(16),B(17),C(19)}CLOSED:{A(15),H(15),G(15)},OPEN:{D(16→15),B(1

17、7),C(19)}CLOSED:{A(15),H(15),G(15),F(15)},OPEN:{E(15),B(17),C(19)}CLOSED:{A(15),H(15),G(15),F(15), D(16→15)},OPEN:{B(17),C(19)}CLOSED:{A(15),H(15),G(15),F(15), D(16→15)},,5、對右圖所示的狀態(tài)空間圖用A*算法進行搜索。 其中A為起始節(jié)點，E為目標節(jié)點，各節(jié)點的啟

18、發(fā)值表示在括號內(nèi)。,E,C,A,D,B,1,1,9,6,1,20,(14),(20),(4),(8),,,,,,,,4,OPEN表,CLOSED表,A(20),B(15),1,C(14),D(13),,,,OPEN表,CLOSED表,A(20),B(15),1,C(14),D(13),,,,E(29),,2,OPEN表,CLOSED表,,A(20),B(15),1,C(14),D(13→11),,,,E(29),,2,3,,OPEN表,

19、CLOSED表,,A(20),B(15),1,C(14),D(13→11),,,,E(29→27),,2,3,,4,OPEN表,CLOSED表,,,,A(20),B(15),1,C(14→10),D(13→11→9),,,,E(29→27),,2,3,,4,,5,,OPEN表,CLOSED表,,,,A(20),B(15),1,C(14→10),D(13→11→9),,,,E(29→27→25),,2,3,,4,,5,,6,OPEN表,C

20、LOSED表,,,,,A(20),B(15),1,C(14→10),D(13→11→9),,,,E(29→27→25),,2,3,,4,,5,,6,7,,OPEN表,CLOSED表,,,,,E(29?27?25?23),A(20),B(15),1,2,C(14?10),D(13?11?9?7),,,,,,3,4,,5,6,7,8,搜索出的路徑為： A?B?C?D?E，整條路徑的代價和為23。,,,9,對下圖所示的狀態(tài)空間圖進行：(1)

21、深度優(yōu)先搜索；(2) 寬度優(yōu)先搜索；（3）均一代價搜索；(4) A*算法搜索。（圖中A為初始節(jié)點，F(xiàn) 為目標節(jié)點，各節(jié)點的啟發(fā)值標注在小括號內(nèi)）。給出搜索過程及搜索出的最佳路徑，并標注各節(jié)點的估價函數(shù)值。,6. 利用?-?剪枝法對下圖的博弈樹進行搜索。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,6,1,2,5,3,4,1,6,5,1,1,7,2,4,3,2,,,,,,,,,,,,

22、,,,,,,,,,,,,,,,,,,,,,,,6,1,2,5,3,4,1,6,(-?,1),,,(1,+?),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,6,1,2,5,3,4,1,6,(-?,1),,,,,,,,,(1→2,+?),(-?,2),(-?,2),,,,,,,,,,,,,,,,,,,,,,,,6,1,2,5,3,4,1,6,(-?,1),,,,,,,,,(1→2,+?),(-?,2),(-?,2),?剪枝,,

23、,(-?,3),(-?,3),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,5,1,1,7,2,4,3,2,(-?,2),(-?,1),(-?,1),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,5,1,1,7,2,4,3,2,(-?,2),(-?,1),(-?,1),,,,,,(-?,1),(-?,1),,,,,?剪枝,(-?,1),,,,,,,,,,,,,,,,,,,,,,,,,,,,,5,1,

24、1,7,2,4,3,2,(-?,2),(-?,1),(-?,1),,,,,,(-?,1),(-?,1),,,,,?剪枝,(-?,1),,,,,,,,,,,,,?剪枝,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,6,1,2,5,3,4,1,6,5,1,1,7,2,4,3,2,(-?,1),(-?,2),(1→2,+?),(-?,2),(-?,3),(3,+?),,?剪枝,(2,+?)