第4章 參考答案

搜索方略部分參照答案4.5有一農(nóng)夫帶一條狼，一只羊和一框青菜與從河的左岸乘船倒右岸，但受到下列條件的限制：(1)船太小，農(nóng)夫每次只能帶同樣?xùn)|西過(guò)河；假如沒(méi)有農(nóng)夫看守，則狼要吃羊，羊要吃菜。請(qǐng)?jiān)O(shè)計(jì)一種過(guò)河方案，使得農(nóng)夫、浪、羊都能不受損失的過(guò)河，畫(huà)出對(duì)應(yīng)的狀態(tài)空間圖。題示：(1)用四元組（農(nóng)夫，狼，羊，菜）表達(dá)狀態(tài)，其中每個(gè)元素都為0或1，用0表達(dá)在左岸，用1表達(dá)在右岸。(2)把每次過(guò)河的一種安排作為一種操作，每次過(guò)河都必須有農(nóng)夫，由于只有他可以劃船。解：第一步，定義問(wèn)題的描述形式用四元組S=（f，w，s，v）表達(dá)問(wèn)題狀態(tài)，其中，f，w，s和v分別表達(dá)農(nóng)夫，狼，羊和青菜與否在左岸，它們都可以取1或0，取1表達(dá)在左岸，取0表達(dá)在右岸。第二步，用所定義的問(wèn)題狀態(tài)表達(dá)方式，把所有也許的問(wèn)題狀態(tài)表達(dá)出來(lái)，包括問(wèn)題的初始狀態(tài)和目的狀態(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)和目的狀態(tài)。第三步，定義操作，即用于狀態(tài)變換的算符組F由于每次過(guò)河船上都必須有農(nóng)夫，且除農(nóng)夫外船上只能載狼，羊和菜中的一種，故算符定義如下：L(i)表達(dá)農(nóng)夫從左岸將第i樣?xùn)|西送到右岸（i=1表達(dá)狼，i=2表達(dá)羊，i=3表達(dá)菜，i=0表達(dá)船上除農(nóng)夫外不載任何東西）。由于農(nóng)夫必須在船上，故對(duì)農(nóng)夫的表達(dá)省略。R(i)表達(dá)農(nóng)夫從右岸將第i樣?xùn)|西帶到左岸（i=1表達(dá)狼，i=2表達(dá)羊，i=3表達(dá)菜，i=0表達(dá)船上除農(nóng)夫外不載任何東西）。同樣，對(duì)農(nóng)夫的表達(dá)省略。這樣，所定義的算符組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)(1,1,l,1)L(2)L(2)(0,1,0,1)(0,1,0,1)R(0)R(0)(1,1,0,1)(1,1,0,1)L(3)L(1)L(3)L(1)(0,1,0,0)(0,0,0,1)(0,1,0,0)(0,0,0,1)R(2)R(2)R(2)R(2)(1,1,1,0)(1,0,1,1)(1,1,1,0)(1,0,1,1)L(2)L(2)L(3)L(3)(0,0,1,0)(0,0,1,0)R(0)R(0)(1,0,1,0)(1,0,1,0)L(2)L(2)(0,0,0,0)(0,0,0,0)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和目的狀態(tài)Sg如圖4-31所示，請(qǐng)用廣度優(yōu)先搜索和深度優(yōu)先搜索，求出從S0到Sg的途徑。CC12222222CC12222222BAAB42BAAB42234131231331412341312313314144444343初始狀態(tài)S0目的狀態(tài)Sg圖431圓盤(pán)問(wèn)題解：設(shè)用qA，qB和qC分別表達(dá)把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到目的狀態(tài)Sg的途徑是S0→2→5→13(Sg)323221113334444233132314122344323141212434233114242413ABCqAqBqC331311224244qA322441311324qBqC413412332334123331313124422412344123412313324112244qC334213112244qA314241231234qB132314242413qC4.7題的廣度優(yōu)先搜索樹(shù)S0S1S2S4S5S6S7S8S9S10S11S12即SgS3其深度優(yōu)先搜索略。4.8圖4-32是5個(gè)都市的交通圖，都市之間的連線旁邊的數(shù)字是都市之間旅程的費(fèi)用。規(guī)定從A城出發(fā)，通過(guò)其他各都市一次且僅一次，最終回到A城，請(qǐng)找出一條最優(yōu)線路。A10B289C1163128D9E432交通費(fèi)用圖解：這個(gè)問(wèn)題又稱為旅行商問(wèn)題（travellingsalesmanproblem,TSP）或貨郎擔(dān)問(wèn)題，是一種較有普遍性的實(shí)際應(yīng)用問(wèn)題。根據(jù)數(shù)學(xué)理論，對(duì)n個(gè)都市的旅行商問(wèn)題，其封閉途徑的排列總數(shù)為：(n!)/n=(n-1)!其計(jì)算量相稱大。例如，當(dāng)n=20時(shí)，要窮舉其所有途徑，雖然用一種每秒一億次的計(jì)算機(jī)來(lái)算也需要350年的時(shí)間。因此，對(duì)此類(lèi)問(wèn)題只能用搜索的措施來(lái)處理。下圖是對(duì)圖4-32按最小代價(jià)搜索所得到的搜索樹(shù)，樹(shù)中的節(jié)點(diǎn)為都市名稱，節(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à)。0A0A119210119210102119BDCE102119BDCE9869312838612898693128386128201917CDB181221ECB10105EDB1201917CDB181221ECB10105EDB16E2218DC331288933128892312386886896912612923123868868969126129883C32B222925DC2020EBB16D191622DE31C32B222925DC2020EBB16D191622DE31E25C9838E12912BD272426CB2720C1417BE2524DC2621DE9838E12912BD272426CB2720C1417BE2524DC2621DE68126666812666E3133E9328D31B926B26E831B28DD273E3133E9328D31B926B26E831B28DD27323E35ED27D32C34B30282023E35ED27D32C34B302820E28CBE28CB21021030A30A30A30A圖4.32的最小代價(jià)搜索樹(shù)圖4.32的最小代價(jià)搜索樹(shù)可以看出，其最短路經(jīng)是A-C-D-E-B-A或A-B-E-D-C-A其實(shí)，它們是同一條路經(jīng)。4.11設(shè)有如下構(gòu)造的移動(dòng)將牌游戲：BBWWE其中，B表達(dá)黑色將牌，W表是白色將牌，E表達(dá)空格。游戲的規(guī)定走法是：(1)任意一種將牌可移入相鄰的空格，規(guī)定其代價(jià)為1；(2)任何一種將牌可相隔1個(gè)其他的將牌跳入空格，其代價(jià)為跳過(guò)將牌的數(shù)目加1。游戲要到達(dá)的目的什是把所有W都移到B的左邊。對(duì)這個(gè)問(wèn)題，請(qǐng)定義一種啟發(fā)函數(shù)h(n)，并給出用這個(gè)啟發(fā)函數(shù)產(chǎn)生的搜索樹(shù)。你能否鑒別這個(gè)啟發(fā)函數(shù)與否滿足下解規(guī)定？再求出的搜索樹(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=12f(x)=0+12=12BBWWEf(x)=1+12=13f(x)=1+12=13BBEWWf(x)=1+12=13f(x)=1+12=13BBWEWf(x)=2+12=14f(x)=2+12=14f(x)=2+9=11f(x)=2+9=11BBEWWBEWBWf(x)=3+9=12f(x)=3+9=12EBWBWf(x)=4+6=10f(x)=4+6=10WBEBWf(x)=5+3=8f(x)=5+3=8WBWBEf(x)=6+3=9f(x)=6+3=9WBWEBf(x)=7+0=7f(x)=7+0=7WEWBB4.14設(shè)有如圖4-34的與/或/樹(shù)，請(qǐng)分別按和代價(jià)法及最大代價(jià)法求解樹(shù)的代價(jià)。AABCDt2t3t4t1圖4.34習(xí)題4.14的與/或樹(shù)56217223E解：若按和代價(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+6)=104.15設(shè)有如圖4-35所示的博弈樹(shù)，其中最下面的數(shù)字是假設(shè)的估值，請(qǐng)對(duì)該博弈樹(shù)作如下工作：(1)計(jì)算各節(jié)點(diǎn)的倒推值；運(yùn)用α