第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)題狀態(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)S12=(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表示船上除農(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)和操作，該問(wèn)題求解過(guò)程的狀態(tài)空間圖如下：4.7圓盤(pán)問(wèn)題。設(shè)有大小不等的三個(gè)圓盤(pán)A、B、C套在一根軸上，每個(gè)盤(pán)上都標(biāo)有數(shù)字1、2、3、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的路徑。初始狀態(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)90o，這些操作（算符）的排列順序是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í)。由該圖可以看出，從初始狀態(tài)S0到目標(biāo)狀態(tài)Sg的路徑是S0→2→5→13(Sg)深度優(yōu)先搜索略34.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)是否滿足單調(diào)限制？解：設(shè)h(x)=每個(gè)W左邊的B的個(gè)數(shù)，f(x)=d(x)+3*h(x)，其搜索樹(shù)如下：f(x)=0+12=12BBWWEBBEWWf(x)=1+12=13BBWEWf(x)=2+12=14BBEWWBEWBWEBWBWWBEBWf(x)=5+3=8WBWBEf(x)=6+3=9WBWEBWBWEB4.13設(shè)有如圖4-33所示的與/或樹(shù)，請(qǐng)分別用與/或樹(shù)的廣度優(yōu)先搜索和深度優(yōu)先搜索求出解樹(shù)。解：其廣度優(yōu)先搜索樹(shù)為：其深度優(yōu)先搜索樹(shù)為：4.14設(shè)有如圖4-34的與/或/樹(shù)，請(qǐng)分別按和代價(jià)法及最大代價(jià)法求解樹(shù)的代價(jià)。解：若按和代價(jià)法，則該解樹(shù)的代價(jià)為：h(A)=2+3+2+5+2+1+6=21若按最大代價(jià)法，則該解樹(shù)的代價(jià)為：h(A)=max{h(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