第4章 參考答案

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