人工智能+搜索習(xí)題(學(xué)生).ppt

1、如下圖所示的迷宮問題，用橫向(寬度)搜索算法求出從入口(0,0)到出口(2,2)的一條路徑。,y,2,0,1,x,0,1,2,2、問題不變，采用縱向（深度）搜索算法求解。,y,2,0,1,x,0,1,2,3、迷宮問題如下，F(xiàn)是入口，B是出口，試采用縱向搜索算法進(jìn)行求解。,0,1,2,3,x,1,2,3,y,F,G,H,E,C,A,D,B,2,2,2,4,1,1,1,1,4、上述問題采用橫向搜索算法進(jìn)行求解。,0,1,2,3,x,1,2,3,y,F,G,H,E,C,A,D,B,2,2,2,4,1,1,1,1,5、問題如上，試采用均一代價(jià)（分支界限）搜索算法進(jìn)行求解。,0,1,2,3,x,1,2,3,y,F,G,H,E,C,A,D,B,2,2,2,4,1,1,1,1,6、上述問題采用最佳優(yōu)先（爬山法）搜索算法進(jìn)行求解。解：估價(jià)函數(shù)f(n)采用每個(gè)節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)在坐標(biāo)系上的距離來(lái)表示。例如，E點(diǎn)與目標(biāo)節(jié)點(diǎn)B之間的空間距離是2+2=4，兩個(gè)2分別是E與B在x軸及y軸上的距離。,7、上述問題采用A*算法進(jìn)行求解。解：估價(jià)函數(shù)f(n)由兩部分組成，即f(n)=g(n)+h(n)。其中，g(n)是從起始節(jié)點(diǎn)走到節(jié)點(diǎn)n所付出的代價(jià)，而h(n)是節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的估計(jì)距離值。例如，節(jié)點(diǎn)的估價(jià)函數(shù)f(H)=3+3=6，前面的是到的代價(jià)，后面的是到的空間距離的估算值。,8、用A算法求解下列八數(shù)碼魔方，啟發(fā)函數(shù)h(n)分別采用：1)h=0;2)h為放錯(cuò)的棋子數(shù)；3)h為用曼哈頓距離的和。,5,6,7,4,8,1,3,2,5,6,7,4,8,3,2,1,解題分析：,由于A算法的估價(jià)函數(shù)為：f(n)=g(n)+h(n)其中，g(n)代表從初始點(diǎn)到n的路徑代價(jià)和；h(n)代表從n開始到目標(biāo)的距離估算值。當(dāng)h(n)=0時(shí)，則A算法的估價(jià)函數(shù)只剩下g(n)，即為均一代價(jià)算法。,9、對(duì)右圖所示的狀態(tài)空間圖進(jìn)行：1)縱向搜索;2)橫向搜索；3)均一代價(jià)搜索；4)最佳優(yōu)先搜索；5)A*搜索。其中A為起始節(jié)點(diǎn)，E為目標(biāo)節(jié)點(diǎn)，各節(jié)點(diǎn)的啟發(fā)值表示在括號(hào)內(nèi)。,F,G,H,E,C,A,D,B,4,2,3,4,8,2,4,3,3,8,5,(15),(14),(10),(2),(11),(9),(5),(0),10、對(duì)右圖所示的狀態(tài)空間圖用A*算法進(jìn)行搜索。其中A為起始節(jié)點(diǎn)，E為目標(biāo)節(jié)點(diǎn)，各節(jié)點(diǎn)的啟發(fā)值表示在括號(hào)內(nèi)。寫出open表與c