人工智能教程習(xí)題及答案第5章習(xí)題參考解答

1、 第五章搜索策略習(xí)題參考解答5.1練習(xí)題什么是搜索？有哪兩大類不同的搜索方法？?jī)烧叩膮^(qū)別是什么？用狀態(tài)空間法表示問(wèn)題時(shí)，什么是問(wèn)題的解？求解過(guò)程的本質(zhì)是什么？什么是最優(yōu)解？最優(yōu)解唯一嗎？5.3請(qǐng)寫出狀態(tài)空間圖的一般搜索過(guò)程。在搜索過(guò)程中OPEN表和CLOSE表的作用分別是什么？有何區(qū)別？什么是盲目搜索？主要有幾種盲目搜索策略？寬度優(yōu)先搜索與深度優(yōu)先搜索有何不同？在何種情況下，寬度優(yōu)先搜索優(yōu)于深度優(yōu)先搜索？在何種情況下，深度優(yōu)先搜索優(yōu)于寬度優(yōu)先搜索？用深度優(yōu)先搜索和寬度優(yōu)先搜索分別求圖5.10所示的迷宮出路。圖5.10習(xí)題5.6的圖5.7修道士和野人問(wèn)題。設(shè)有3個(gè)修道士和3個(gè)野人來(lái)到河邊，打算用

2、一條船從河的左岸渡到河的右岸去。但該船每次只能裝載兩個(gè)人，在任何岸邊野人的數(shù)目都不得超過(guò)修道士的人數(shù)，否則修道士就會(huì)被野人吃掉。假設(shè)野人服從任何一種過(guò)河安排，請(qǐng)使用狀態(tài)空間搜索法，規(guī)劃一使全部6人安全過(guò)河的方案。(提示：應(yīng)用狀態(tài)空間表示和搜索方法時(shí)，可用(Nm,Nc)來(lái)表示狀態(tài)描述，其中Nm和Nc分別為傳教士和野人的人數(shù)。初始狀態(tài)為(3,3),而可能的中間狀態(tài)為(0,1),(0,2),(0,3),(1,1),(2,1),(2,2),(3,0),(3,1),(3,2)等。58用狀態(tài)空間搜索法求解農(nóng)夫、狐貍、雞、小米問(wèn)題。農(nóng)夫、狐貍、雞、小米都在條河的左岸，現(xiàn)在要把它們?nèi)克偷接野度?。農(nóng)夫有一條船

3、，過(guò)河時(shí)，除農(nóng)夫外，船上至多能載狐貍、雞和小米中的一樣。狐貍要吃雞，雞要吃小米，除非農(nóng)夫在那里。試規(guī)劃出一個(gè)確保全部安全的過(guò)河計(jì)劃。（提示：a.用四元組（農(nóng)夫，狐貍，雞，米）表示狀態(tài)，其中每個(gè)元素都可為0或1，0表示在左岸，1表示在右岸；b.把每次過(guò)河的一種安排作為一個(gè)算符，每次過(guò)河都必須有農(nóng)夫，因?yàn)橹挥兴梢詣澊?9設(shè)有三個(gè)大小不等的圓盤A、B、C套在一根軸上，每個(gè)圓盤上都標(biāo)有數(shù)字1、2、3、4,并且每個(gè)圓盤都可以獨(dú)立地繞軸做逆時(shí)針轉(zhuǎn)動(dòng)，每次轉(zhuǎn)動(dòng)90，初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如圖5.11所示，用寬度優(yōu)先搜索法和深度優(yōu)先搜索法求從S0到路徑。OO：|圖5.11圓盤問(wèn)題510用有界深度優(yōu)先搜

4、索方法求解圖5.12所示八數(shù)碼難題。初始狀態(tài)為S0，目標(biāo)狀態(tài)S,要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑。g2128316834757645S0gS圖5.12八數(shù)碼難題圖5.13推銷員旅行交通費(fèi)用圖5.11推銷員旅行問(wèn)題。設(shè)有五個(gè)相互可直達(dá)的城市A、B、C、D、E,如圖5.13所示,各城市間的交通費(fèi)用已在圖中標(biāo)出。推銷員從城市A出發(fā)，去每個(gè)城市各旅行一次，最后到達(dá)城市E,請(qǐng)找出一條費(fèi)用最省的旅行路線。5.12什么是啟發(fā)式搜索？什么是啟發(fā)信息？5.13什么是估價(jià)函數(shù)？在估價(jià)函數(shù)中，g(x)和h(x)各起什么作用？什么是最佳優(yōu)先搜索？局部最佳優(yōu)先搜索與全局最佳優(yōu)先搜索有何異同？用全局最佳優(yōu)先搜索方法求解

5、八數(shù)碼難題。如果八數(shù)碼難題的初始狀態(tài)圖及目標(biāo)狀態(tài)圖如圖5.14所示，請(qǐng)利用全局最佳優(yōu)先搜索算法求取由S0轉(zhuǎn)換為Sg的路徑，并畫出它的全局最佳優(yōu)先搜索樹。746圖5.14八數(shù)碼難題5.16什么是A*算法？它的估價(jià)函數(shù)是如何確定的？A*算法與A算法的區(qū)別是什么？5.17A*算法有哪些性質(zhì)？它們的意義如何?5.18證明單調(diào)性啟發(fā)策略是可米納的。5.19如圖5.37是一棵“與/或”樹，請(qǐng)分別用“與/或”樹的廣度優(yōu)先搜索及深度優(yōu)先搜索求出其解樹。圖5.38習(xí)題5.20的與或樹5.205.21圖5.37習(xí)題5.19的與或樹設(shè)有“與/或”樹如圖5.38所示，請(qǐng)分別按和代價(jià)法以及最大代價(jià)法求出解樹的代價(jià)。設(shè)有

6、如圖5.39所示的博弈樹，其中個(gè)葉子節(jié)點(diǎn)下的數(shù)值為假設(shè)的估值，請(qǐng)對(duì)該博弈樹做如下工作：（1）計(jì)算各節(jié)點(diǎn)的倒推值；（2）利用a-B剪枝技術(shù)剪去不必要的分枝。5.2習(xí)題參考解答5.1答：（略）答：用狀態(tài)空間法表示問(wèn)題時(shí)，問(wèn)題的解就是有向圖中從某一節(jié)點(diǎn)（初始狀態(tài)節(jié)點(diǎn)）到另一節(jié)點(diǎn)（目標(biāo)狀態(tài)節(jié)點(diǎn)）的路徑。求解過(guò)程的本質(zhì)就是對(duì)狀態(tài)空間圖的搜索，即在狀態(tài)空間圖上尋找一條從初始狀態(tài)到目標(biāo)狀態(tài)的路徑。在不考慮搜索的代價(jià)時(shí)，即假設(shè)狀態(tài)空間圖中各節(jié)點(diǎn)之間的有向邊的代價(jià)相同時(shí)，最優(yōu)解就是解路徑中長(zhǎng)度最短的那條路徑，在考慮搜索代價(jià)時(shí)，最優(yōu)解則是解路徑中代價(jià)最小的那條路徑。因?yàn)樵跔顟B(tài)空間圖中，可能存在幾條長(zhǎng)度或代價(jià)相等的

7、最短解路徑，所以，最優(yōu)解可能會(huì)不唯一。答：（略）答：盲目搜索又稱無(wú)信息搜索，即在搜索過(guò)程中，只按預(yù)先規(guī)定的搜索控制策略進(jìn)行搜索，而沒(méi)有任何中間信息來(lái)改變這些控制策略。主要的盲目搜索策略有：寬度優(yōu)先搜索、深度優(yōu)先搜索、有界深度優(yōu)先搜索、代價(jià)數(shù)的寬度優(yōu)先搜索和代價(jià)樹的深度優(yōu)先搜索。答：深度優(yōu)先搜索與寬度優(yōu)先搜索的區(qū)別就在于：在對(duì)節(jié)點(diǎn)n進(jìn)行擴(kuò)展時(shí)，其后繼結(jié)點(diǎn)在OPEN表中的存放位置。寬度優(yōu)先搜索是將后繼節(jié)點(diǎn)放入OPEN表的末端，而深度優(yōu)先搜索則是將后繼節(jié)點(diǎn)放入OPEN表的前端。即寬度優(yōu)先搜索按照“先擴(kuò)展出的節(jié)點(diǎn)先被考察”的原則進(jìn)行搜索，而深度優(yōu)先搜索則按照“后擴(kuò)展出的節(jié)點(diǎn)先被考察”的原則進(jìn)行搜索。寬

8、度優(yōu)先搜索是一種完備搜索，即只要問(wèn)題有解就一定能夠求出，而深度優(yōu)先搜索是不完備搜索。在不要求求解速度且目標(biāo)節(jié)點(diǎn)的層次較深的情況下，寬度優(yōu)先搜索優(yōu)于深度優(yōu)先搜索因?yàn)閷挾葍?yōu)先搜索效率低，但卻一定能夠求得問(wèn)題的解；在要求求解速度且目標(biāo)節(jié)點(diǎn)的層次較淺的情況下，深度優(yōu)先搜索優(yōu)于寬度優(yōu)先搜索。因?yàn)楫?dāng)搜索算法在一個(gè)擴(kuò)展的很深但又沒(méi)有解的分支上，進(jìn)行搜索是一種無(wú)效搜索，降低了求解的效率，有時(shí)甚至不一定能求得問(wèn)題的解。解：在這個(gè)迷宮中，S是源節(jié)點(diǎn)，F(xiàn)是目標(biāo)節(jié)點(diǎn)，A,B,C,D,E是五個(gè)具有二叉分枝的節(jié)點(diǎn)，在每個(gè)節(jié)點(diǎn)處，都可能會(huì)出現(xiàn)兩種路線，要么向左拐要么向右拐，我們?cè)诿總€(gè)二叉節(jié)點(diǎn)處設(shè)立兩個(gè)虛節(jié)點(diǎn)，以表示到該節(jié)點(diǎn)

9、后的走向，向右拐為第一個(gè)虛節(jié)點(diǎn)，用下標(biāo)1表示，向左拐為第二個(gè)虛節(jié)點(diǎn)，用下標(biāo)2表示。例如，A節(jié)點(diǎn)處向右拐的虛節(jié)點(diǎn)用舛表示，向左圖中，除F節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)外，其余沒(méi)有后繼節(jié)點(diǎn)的虛節(jié)點(diǎn)都說(shuō)明走入了死胡同。利用深度優(yōu)先搜索，其搜索樹如圖5.16所示，圖中節(jié)點(diǎn)旁所標(biāo)數(shù)字為節(jié)點(diǎn)擴(kuò)展次序。所得到的解路徑為：S一AA廠BT廠CC廠F也就是說(shuō)，從S出發(fā)，在A節(jié)點(diǎn)處不能左拐，而是直行，到B節(jié)點(diǎn)處右拐，到C節(jié)點(diǎn)也右拐，即可到達(dá)出口F。利用寬度優(yōu)先搜索，其搜索樹如圖5.17所示，圖中節(jié)點(diǎn)旁所標(biāo)數(shù)字為節(jié)點(diǎn)擴(kuò)展次序。所得到的解路徑也為：S一AA廠BB廠CC廠F由搜索過(guò)程可以看出，寬度優(yōu)先搜索的效率低于深度優(yōu)先搜索。Ann1

10、3oo圖5.16深度優(yōu)先搜索樹圖5.17寬度優(yōu)先搜索樹解：（略）解：（略）解:設(shè)rA，rB，rC分別為將盤子A,B,C逆時(shí)針旋轉(zhuǎn)90的操作，在運(yùn)用這些操作符時(shí)的順序?yàn)閞A，rB，rC應(yīng)用寬度優(yōu)先搜索的搜索樹如圖5.18所示。從圖中可以看出，從初始狀態(tài)S0到目標(biāo)狀態(tài)S的路徑是：gS廠2TH2（Sg）應(yīng)用深度優(yōu)先搜索的搜索樹如圖5.19所示。這里要指出的是，我們?cè)趹?yīng)用深度優(yōu)先搜索算法時(shí)，稍微作了一些改進(jìn)，即不是只對(duì)當(dāng)前節(jié)點(diǎn)判斷其是否為目標(biāo)節(jié)點(diǎn)，而是對(duì)當(dāng)前節(jié)點(diǎn)的擴(kuò)展節(jié)點(diǎn)進(jìn)行判斷，如果擴(kuò)展節(jié)點(diǎn)中含有目標(biāo)節(jié)點(diǎn)，則搜索停止，求解成功。這有利于提高求解效率。從圖中可以看出，從初始狀態(tài)s0到目標(biāo)狀態(tài)Sg的路徑

11、是：Sm一s0g圖5.18圓盤問(wèn)題的寬度優(yōu)先搜索圖5.19圓盤問(wèn)題的深度優(yōu)先搜索解：用有界深度優(yōu)先搜索策略求解問(wèn)題的搜索樹如圖5.20所示。這里設(shè)深度界限dm=5,在這種情況下，該問(wèn)題無(wú)解。由此可以看出，在有界深度優(yōu)先搜索算法中，深度界限的選擇很重要。選擇過(guò)大，可能會(huì)影響搜索的效率；選擇的過(guò)小，有可能求不到解。所以，有界深度優(yōu)先搜索策略是不完備的。0i2dfiraiij|82i|i2Ofl351-Il：圖5.20有界深度優(yōu)先搜索活陽(yáng)淞7|1：R134113-；|巳054?4750IIA1mK13:丨；I1MITaMJ也16$Uthli754IllTn解：由于涉及旅行費(fèi)用，所以利用代價(jià)樹寬度優(yōu)先

12、搜索方法求解。為此，首先將旅行交通圖轉(zhuǎn)換為代價(jià)樹如圖5.21所示。轉(zhuǎn)換的方法如下：從初始節(jié)點(diǎn)A開(kāi)始，把與它直接相鄰的節(jié)點(diǎn)作為它的后繼節(jié)點(diǎn)，對(duì)其他節(jié)點(diǎn)也作同樣的擴(kuò)展，但若一個(gè)節(jié)點(diǎn)已作為某節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的話，則它就不能再作為該節(jié)點(diǎn)的后繼節(jié)點(diǎn)。由于要求從A出發(fā)后，到每個(gè)城市各旅行一次，因此，每條到達(dá)E的路徑上都包含了所有的節(jié)點(diǎn)，不包含所有節(jié)點(diǎn)而到達(dá)節(jié)點(diǎn)E路徑無(wú)效。另外，圖中的節(jié)點(diǎn)除了初始節(jié)點(diǎn)A夕卜，其他的節(jié)點(diǎn)都有可能在代價(jià)樹中多次出現(xiàn)，為了區(qū)分它的多次出現(xiàn)，分別用下標(biāo)標(biāo)出，以區(qū)別它們?cè)诓煌种Ъ安煌瑢哟蔚某霈F(xiàn)，但它們卻代表著旅行圖中的同一個(gè)節(jié)點(diǎn)，例如，C12和C21分別表示代價(jià)數(shù)中第一分枝第二層和第

13、二分支第一層的C節(jié)點(diǎn)，是旅行圖中的同一節(jié)點(diǎn)C。由于要求每個(gè)城市各旅行一次，因此，本題的代價(jià)樹搜索算法如圖5.22所示A,B11,C21,E12,E41,D31A,B11,c21,E12,E41,D31,D22D12（180）心2（190）月22（200）月22（230）也2（250）&32（255）月232（255）月32（270）月23（275）A,B11,C21,E12,E41,D31,D22,D125（190）旦2（200）衛(wèi)22（230）也2（250）2（255）衛(wèi)232（255）,片32（260）心3（265）總2（270）A,B11,C21,E12,E41,D31,D22,D12,

14、C12B22（200）,E22（230）,E32（250）,C32（255）,E232（255）,E132（260）,C13（265）,B32（270）,B23（275），Di3（275）耳3i（330）A,B11,C21,E12,E41,D31,D22,D12,C12,B22E22（230），E32（250）,C32（255）,E232（255）,E132（260）,C13（265）,B32（270）,B23（275）,D13（275）,E231（280）,D23（300）,E131（330）A,B11,C21,E12,E41,D31,D22,D12,C12,B22,E22,E32,C32E

15、232（255）,E132（260）,C13（265）,B32（270）,B23（275）,D13（275）,E231（280）,D23（300）,E131（330）,B33（365）,E332（395）A,B11,C21,E12,E41,D31,D22,D12,C12,B22,E22,E32,C32,B32（270）,B23（275）,Di3（275）,E23i（280）,D23（300）,Ei3i（330）,B33（365）,E332（395）,E142（40E232,E132,C13A,B11,C21,E12,E41,D31,D22,D12,C12,B22,E22,E32,C32,B23

16、（275）,Di3（275）,E23i（280）,D23（300）,Ei3i（330）,E33i（335）,B33（365）,C33（380）,E332（39応32斗32心3,B325）耳42（405）A,B11,C21,E12,E41,D31,D22,D12,C12,B22,E22,E32,C32,Di3（275）,E23i（280）,D23（300）,Ei3i（330）,E33i（335）,E242（340）,B33（365）,C33（380）,E332（3232斗32心3,B32,B2395）,E142（405）A,B11,C21,E12,E41,D31,D22,D12,C12,B22,

17、E22,E32,C32,E231（280）,D23（300）,Ei3i（330）,E33i（335）,E242（340）,Ei4i（355）,B33（365）,C33（380），E332（3E232,E132,C13,B32,B23,D1395）,E142（405）A,B11,C21,E12,E41,D31,D22,D12,C12,B22,E22,E32,C32,Ei3i（330）,E33i（335）,E242（340）,Ei4i（355）,B33（365）,C33（380）,E24i（380）,E332（395）,Ei42（4F232,F132,c13,B32,B23,D13,F231,D2

18、3A,B11,C21,E12,E41,D31,D22,D12,C12,B22,E22,E32,C32,E141（355）,B33（365）,C33（380）,E241（380）,E332（395）,E142（405）EECBBDEDEEE2321321332231323123131331242OPEN表中節(jié)點(diǎn)右邊括號(hào)中的數(shù)字為該節(jié)點(diǎn)代價(jià)。當(dāng)E242節(jié)點(diǎn)移入CLOSED表之后,因?yàn)樗褪悄繕?biāo)節(jié)點(diǎn)，且回溯路徑中含有所有城市節(jié)點(diǎn)，因而成功退出。所求得的最小代價(jià)路徑為A-C21-D22-B23-E242，其代價(jià)是340。因而，從城市A出發(fā)，經(jīng)過(guò)各城市一次隨后到大城市e的費(fèi)用最省路線為:ACDBE。no

19、90H0a31帥IIDSOtlOhl40no/im圖5.21推銷員旅行問(wèn)題代價(jià)樹箱;細(xì)標(biāo)節(jié)點(diǎn)移人eg曲D我勇涇中電潴了宙和城市時(shí)；丘布點(diǎn)臨日標(biāo)節(jié)點(diǎn)嗎?節(jié)底”可片展吁Vh1卸題無(wú)絹退岀幵血對(duì)*虎”進(jìn)行擴(kuò)鳥，并時(shí)毎于?延節(jié)點(diǎn)對(duì)算其代價(jià)刈丿尸閾？廠HI,H梅它衍就扎ortN蛙”為郵牛石強(qiáng)節(jié)向節(jié)點(diǎn)”的冋腑冰卜蘭/&由侶曲對(duì)OPI盞中的陽(yáng)右節(jié)貞捲其代倚從小到大神作耙OPE乂尿叫啲第牛節(jié)點(diǎn)籟ACLOSED(記為版帥)加送AOPEN.gH同禪求取解環(huán)徑圖5.22推銷員旅行問(wèn)題代價(jià)樹寬度優(yōu)先搜索算法框圖答：(略)答：估價(jià)函數(shù)是一種用來(lái)表示和度量搜索樹中節(jié)點(diǎn)的“希望”程度的一種的函數(shù)，其任務(wù)是估計(jì)待搜索節(jié)點(diǎn)的重

20、要程度，為它們排定次序。在估價(jià)函數(shù)中，g(x)為初始節(jié)點(diǎn)So到節(jié)點(diǎn)x已實(shí)際付出的代價(jià)。h(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計(jì)代價(jià)，搜索的啟發(fā)信息O主要由h(x)來(lái)體現(xiàn)，所以h(x)稱作啟發(fā)函數(shù)。g(x)項(xiàng)體現(xiàn)了搜索的寬度優(yōu)先趨勢(shì)，這有利于搜索算法的完備性，但影響算法的搜索效率。h(x)項(xiàng)體現(xiàn)了搜索的深度優(yōu)先趨勢(shì)，這會(huì)有利于搜索效率的提高，但影響搜索算法的完備性。答：最佳優(yōu)先搜索總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)，而這種最有希望的節(jié)點(diǎn)是按估價(jià)函數(shù)f(x)的值來(lái)挑選的，一般估價(jià)函數(shù)的值越小，它的希望程度越大。局部最佳優(yōu)先搜索是一種類似于深度優(yōu)先搜索的啟發(fā)式搜索方法，在對(duì)某一個(gè)節(jié)

21、點(diǎn)擴(kuò)展之后，只在后繼節(jié)點(diǎn)的范圍內(nèi)選擇下一個(gè)要考察的節(jié)點(diǎn)，范圍比較小，所以稱為局部最佳優(yōu)先搜索。全局最佳優(yōu)先搜索是一種類似于寬度優(yōu)先搜索的啟發(fā)式搜索方法，在確定下一個(gè)擴(kuò)展節(jié)點(diǎn)時(shí)，選擇的范圍是OPEN表中的全部節(jié)點(diǎn)，所以稱為全局最佳優(yōu)先搜索。解：首先定義一個(gè)估價(jià)函數(shù)：f(x)=d(x)+h(x)其中，d(x)表示節(jié)點(diǎn)x在搜索樹中的深度；h(x)表示與節(jié)點(diǎn)x對(duì)應(yīng)的棋盤中，與目標(biāo)節(jié)點(diǎn)所對(duì)應(yīng)的棋盤中棋子位置不同的個(gè)數(shù)。例如，對(duì)于節(jié)點(diǎn)S0，其在搜索樹中位于0層，所以d(x)=0,而它中的與Sg中棋子位置不同的個(gè)數(shù)是3，即h(x)=3，所以節(jié)點(diǎn)S0的估價(jià)函數(shù)值f(S0)=0+3=3,再如節(jié)點(diǎn)S其估價(jià)函數(shù)f(S)=d(S)+h(S)=l+3=4。搜索樹如圖5.23所示。圖中，節(jié)點(diǎn)旁邊圓圈內(nèi)的數(shù)字表示該節(jié)點(diǎn)的f(x)值，Si表示節(jié)點(diǎn)擴(kuò)展的順序。所以問(wèn)題的解路徑是S廠S廠S|圖5.23八數(shù)碼難題的全局擇優(yōu)搜索樹答：A*算法是一種啟發(fā)式搜索方法，利用這種算法進(jìn)行搜索時(shí)，對(duì)擴(kuò)展節(jié)點(diǎn)的選擇方法做了一些限制，依據(jù)估價(jià)函數(shù)f(x)=g(x)+h(x)對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序，并且要求啟發(fā)函數(shù)h(x)是h*(x)的一個(gè)下界，即h(x)Wh*(x)。h*(x)則是從x節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最小代價(jià)路徑上的