第4章 參考答案

1、-作者xxxx-日期xxxx第4章 參考答案【精品文檔】第4章 搜索策略部分參考答案4.5 有一農(nóng)夫帶一條狼，一只羊和一框青菜與從河的左岸乘船倒右岸，但受到下列條件的限制：(1) 船太小，農(nóng)夫每次只能帶一樣?xùn)|西過(guò)河；(2) 如果沒(méi)有農(nóng)夫看管，則狼要吃羊，羊要吃菜。請(qǐng)?jiān)O(shè)計(jì)一個(gè)過(guò)河方案，使得農(nóng)夫、浪、羊都能不受損失的過(guò)河，畫(huà)出相應(yīng)的狀態(tài)空間圖。題示：(1) 用四元組（農(nóng)夫，狼，羊，菜）表示狀態(tài)，其中每個(gè)元素都為0或1，用0表示在左岸，用1表示在右岸。(2) 把每次過(guò)河的一種安排作為一種操作，每次過(guò)河都必須有農(nóng)夫，因?yàn)橹挥兴梢詣澊＝猓旱谝徊?，定義問(wèn)題的描述形式用四元組S=（f，w，s，v）表示問(wèn)

2、題狀態(tài)，其中，f，w，s和v分別表示農(nóng)夫，狼，羊和青菜是否在左岸，它們都可以取1或0，取1表示在左岸，取0表示在右岸。第二步，用所定義的問(wèn)題狀態(tài)表示方式，把所有可能的問(wèn)題狀態(tài)表示出來(lái)，包括問(wèn)題的初始狀態(tài)和目標(biāo)狀態(tài)。由于狀態(tài)變量有4個(gè)，每個(gè)狀態(tài)變量都有2種取值，因此有以下16種可能的狀態(tài)：S0=(1,1,1,1)，S1=(1,1,1,0)，S2=(1,1,0,1)，S3=(1,1,0,0)S4=(1,0,1,1)，S5=(1,0,1,0)，S6=(1,0,0,1)，S7=(1,0,0,0)S8=(0,1,1,1)，S9=(0,1,1,0)，S10=(0,1,0,1)，S11=(0,1,0,0)S

3、12=(0,0,1,1)，S13=(0,0,1,0)，S14=(0,0,0,1)，S15=(0,0,0,0)其中，狀態(tài)S3，S6，S7，S8，S9，S12是不合法狀態(tài)，S0和S15分別是初始狀態(tài)和目標(biāo)狀態(tài)。第三步，定義操作，即用于狀態(tài)變換的算符組F由于每次過(guò)河船上都必須有農(nóng)夫，且除農(nóng)夫外船上只能載狼，羊和菜中的一種，故算符定義如下：L(i)表示農(nóng)夫從左岸將第i樣?xùn)|西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除農(nóng)夫外不載任何東西）。由于農(nóng)夫必須在船上，故對(duì)農(nóng)夫的表示省略。R (i)表示農(nóng)夫從右岸將第i樣?xùn)|西帶到左岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上

4、除農(nóng)夫外不載任何東西）。同樣，對(duì)農(nóng)夫的表示省略。這樣，所定義的算符組F可以有以下8種算符：L (0)，L (1)，L (2)，L (3)R(0)，R(1)，R (2)，R (3)第四步，根據(jù)上述定義的狀態(tài)和操作進(jìn)行求解。該問(wèn)題求解過(guò)程的狀態(tài)空間圖如下：(1,1,l,1)L(2)(0,1,0,1)R(0)(1,1,0,1)L(3)L(1)(0,1,0,0)(0,0,0,1)R(2)R(2)(1,1,1,0)(1,0,1,1)L(2)L(3)(0,0,1,0)R(0)(1,0,1,0)L(2)(0,0,0,0) 圓盤(pán)問(wèn)題。設(shè)有大小不等的三個(gè)圓盤(pán)A、B、C套在一根軸上，每個(gè)盤(pán)上都標(biāo)有數(shù)字1、2、3、

5、4，并且每個(gè)圓盤(pán)都可以獨(dú)立的繞軸做逆時(shí)針轉(zhuǎn)動(dòng)，每次轉(zhuǎn)動(dòng)90°，其初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如圖4-31所示，請(qǐng)用廣度優(yōu)先搜索和深度優(yōu)先搜索，求出從S0到Sg的路徑。CC12222222 BAAB42 234131231331414443 初始狀態(tài)S0 目標(biāo)狀態(tài)Sg 圖 431 圓盤(pán)問(wèn)題解：設(shè)用qA，qB和qC分別表示把A盤(pán)，B盤(pán)和C盤(pán)繞軸逆時(shí)針轉(zhuǎn)動(dòng)90º，這些操作（算符）的排列順序是qA，qB，qC。應(yīng)用廣度優(yōu)先搜索，可得到如下搜索樹(shù)。在該搜索樹(shù)中，重復(fù)出現(xiàn)的狀態(tài)不再劃出，節(jié)點(diǎn)旁邊的標(biāo)識(shí)Si，i=0,1,2,，為按節(jié)點(diǎn)被擴(kuò)展的順序給出的該節(jié)點(diǎn)的狀態(tài)標(biāo)識(shí)。由該圖可以看出，從初

6、始狀態(tài)S0到目標(biāo)狀態(tài)Sg的路徑是S02513(Sg)3221113334444233132314122344323141212434233114242413ABCqAqBqC331311224244qA322441311324qBqC413412332334123331313124422412344123412313324112244qC334213112244qA314241231234qB132314242413qCS0S1S2S4S5S6S7S8S9S10S11S12即SgS3其深度優(yōu)先搜索略。4.8 圖4-32是5個(gè)城市的交通圖，城市之間的連線旁邊的數(shù)字是城市之間路程的費(fèi)用。要求從A城

7、出發(fā)，經(jīng)過(guò)其它各城市一次且僅一次，最后回到A城，請(qǐng)找出一條最優(yōu)線路。 A 10 B 2 8 9 C 11 6 3 12 8 D 9 E432 交通費(fèi)用圖解：這個(gè)問(wèn)題又稱為旅行商問(wèn)題（travelling salesman problem, TSP）或貨郎擔(dān)問(wèn)題，是一個(gè)較有普遍性的實(shí)際應(yīng)用問(wèn)題。根據(jù)數(shù)學(xué)理論，對(duì)n個(gè)城市的旅行商問(wèn)題，其封閉路徑的排列總數(shù)為： (n!)/n=(n-1)!其計(jì)算量相當(dāng)大。例如，當(dāng)n=20時(shí)，要窮舉其所有路徑，即使用一個(gè)每秒一億次的計(jì)算機(jī)來(lái)算也需要350年的時(shí)間。因此，對(duì)這類問(wèn)題只能用搜索的方法來(lái)解決。下圖是對(duì)圖4-32按最小代價(jià)搜索所得到的搜索樹(shù)，樹(shù)中的節(jié)點(diǎn)為城市名稱

8、，節(jié)點(diǎn)邊上的數(shù)字為該節(jié)點(diǎn)的代價(jià)g。其計(jì)算公式為 g(ni+1)=g(ni)+c(ni, ni+1)其中，c(ni,ni+1)為節(jié)點(diǎn)ni到ni+1節(jié)點(diǎn)的邊代價(jià)。0A119210102119BDCE98693128386128201917CDB181221ECB10105EDB16E2218DC331288923123868868969126129883C32B222925DC2020EBB16D191622DE31E25C9838E12912BD272426CB2720C1417BE2524DC2621DE6812666E3133E9328D31B926B26E831B28DD27323E35E

9、D27D32C34B302820E28CB21030A30A可以看出，其最短路經(jīng)是 A-C-D-E-B-A或 A-B-E-D-C-A其實(shí)，它們是同一條路經(jīng)。4.11 設(shè)有如下結(jié)構(gòu)的移動(dòng)將牌游戲：BBWWE其中，B表示黑色將牌，W表是白色將牌，E表示空格。游戲的規(guī)定走法是：(1) 任意一個(gè)將牌可移入相鄰的空格，規(guī)定其代價(jià)為1；(2) 任何一個(gè)將牌可相隔1個(gè)其它的將牌跳入空格，其代價(jià)為跳過(guò)將牌的數(shù)目加1。游戲要達(dá)到的目標(biāo)什是把所有W都移到B的左邊。對(duì)這個(gè)問(wèn)題，請(qǐng)定義一個(gè)啟發(fā)函數(shù)h(n)，并給出用這個(gè)啟發(fā)函數(shù)產(chǎn)生的搜索樹(shù)。你能否判別這個(gè)啟發(fā)函數(shù)是否滿足下解要求？再求出的搜索樹(shù)中，對(duì)所有節(jié)點(diǎn)是否滿足單

10、調(diào)限制？解：設(shè)h(x)=每個(gè)W左邊的B的個(gè)數(shù)，f(x)=d(x)+3*h(x)，其搜索樹(shù)如下：f(x)=0+12=12BBWWEf(x)=1+12=13BBE WWf(x)=1+12=13BBWE Wf(x)=2+12=14f(x)=2+9=11BBEWWBEWBWf(x)=3+9=12EBWBWf(x)=4+6=10WBE BWf(x)=5+3=8WBWBEf(x)=6+3=9WBWE Bf(x)=7+0=7WEWB B4.14 設(shè)有如圖4-34的與/或/樹(shù)，請(qǐng)分別按和代價(jià)法及最大代價(jià)法求解樹(shù)的代價(jià)。ABCDt2t3t4t156217223E解：若按和代價(jià)法，則該解樹(shù)的代價(jià)為： h(A)=2+3+2+5+2+1+6=21若按最大代價(jià)法，則該解樹(shù)的代價(jià)為： h(A)=maxh(B)+5, h(C)+6 = max(h(E)+2)+5, h(C)+6 = max(max(2, 3)+2)+5, max(2, 1)+6=max(5+5, 2+6)=10 4.15 設(shè)有如圖4-35所示的博弈樹(shù)，其中最下面的數(shù)字是假設(shè)的估