第4章圖搜索技術

4.1狀態圖搜索4.2狀態圖問題求解

4.3與或圖搜索

4.4與或圖問題求解4.5博弈樹搜索4.1狀態圖搜索

4.1.1狀態圖例4.1如圖是一個迷宮。將迷宮的每一個格子以及入口和出口都作為節點，把通道作為邊，則該迷宮可以由一個有向圖表示。走迷宮其實就是從該有向圖的初始節點(入口)出發，尋找目標節點(出口)的路徑的問題。

例4.2八個數碼問題。每個數碼占一格，有一個空格。數碼在棋盤上移動規則是：與空格相鄰的數碼方可移入空格。問題：對于指定的初始棋局和目標棋局，給出數碼的移動序列。2831476581324765

事實上，有許多問題(如梵塔問題、旅行商問題、八皇后問題、農夫過河問題、路徑規劃、定理證明、演繹推理、機器人行動規劃等）都可以歸結為在某一狀態圖中尋找目標或路徑的問題。4.1.2狀態圖搜索在狀態圖中尋找目標或路徑的基本方法就是搜索：從初始節點出發，沿著與之相連的邊試探地前進，尋找目標節點的過程(也可以反向進行)。

1.搜索方式計算機實現狀態圖搜索的兩種最基本方式：樹式搜索：從樹根出發，是以“畫樹”的方式進行搜索。線式搜索：在搜索過程中只記錄當前走過的節點和邊，所形成的軌跡是一條線。進一步可回溯/不可回溯搜索。2.搜索策略搜索具有探索性，要提高搜索效率(盡快地找到目標節點)，或要找最佳路徑(最佳解)就必須注意搜索策略。對于狀態圖搜索，已經提出了許多策略，它們大體可分為盲目搜索和啟發式（heuristic）搜索兩大類。盲目搜索：無向導啟發式搜索：有向導（全局最優/局部最優/最佳圖搜索…）對于類樹搜索：深度優先/廣度優先3.搜索算法框架由于搜索的目的是為了尋找初始節點到目標節點的路徑，所以在搜索過程中就得隨時記錄搜索軌跡。為此，用一個稱為CLOSED表的動態數據結構來專門記錄考查過的節點。對于樹式搜索來說，CLOSED表中存儲的是一棵不斷成長的搜索樹；而對于線式搜索來說，CLOSED表中存儲的是一條不斷伸長的折線，它可能本身就是所求的路徑(如果能找到目標節點的話)。編號節點父節點編號CLOSED表

另一方面，對于樹式搜索來說，還得不斷地把待考查的節點組織在一起，并做某種排列，以便控制搜索的方向和順序。為此，采用一個稱為OPEN表的動態數據結構，來專門登記當前待考查的節點。節點父節點編號OPEN表4.1.3窮舉式搜索為簡單起見，先討論樹型結構的狀態圖搜索，并僅限于樹式搜索。按搜索樹生成方式的不同，樹式窮舉搜索又分為廣度優先和深度優先兩種搜索方式。廣度優先(WSF)和深度優先(DSF)是最基本的樹式搜索策略，其他搜索策略都是建立在它們之上的。

1.廣度優先搜索廣度優先搜索始終先在同一級節點中考查，只有當同一級節點考查完之后，才考查下一級節點。或者說，是以初始節點為根節點，向下逐級擴展搜索樹。所以，廣度優先策略的搜索樹是自頂向下一層一層逐漸生成的。廣度優先搜索算法：步1把初始節點S0放入OPEN表中；步2若OPEN表為空，則搜索失敗，退出。步3取OPEN表中前面第一個節點N放入CLOSED表中，并冠以順序編號n；

步4若目標節點Sg=N，則搜索成功，結束。步5若N不可擴展，則轉步2；步6擴展N，將其所有子節點配上指向N的返回指針依次放入OPEN表的尾部，轉步2。

例4.3用廣度優先搜索策略解八數碼難題。由于把一個與空格相鄰的數碼移入空格，等價于把空格向數碼方向移動一位。所以，該題中給出的數碼走步規則也可以簡化為：對空格可施行左移、右移、上移和下移等四種操作。設初始節點S0和目標節點Sg分別如圖4—3的初始棋局和目標棋局所示，我們用廣度優先搜索策略，則可得到如圖4—5所示的搜索樹。圖4—5八數碼問題的廣度優先搜索2.深度優先搜索深度優先搜索就是在搜索樹的每一層始終先只擴展一個子節點，不斷地向縱深前進，直到不能再前進(到達葉子節點或受到深度限制)時，才從當前節點返回到上一級節點，沿另一方向又繼續前進。這種方法的搜索樹是從樹根開始一枝一枝逐漸形成的。深度優先搜索算法：步1把初始節點S0放入OPEN表中；步2若OPEN表為空，則搜索失敗，退出。步3取OPEN表頭節點N放入CLOSED表中，并冠以順序編號n；

步4若目標節點Sg=N，則搜索成功，結束。步5若N不可擴展，則轉步2；步6擴展N，將其所有子節點配上指向N的返回指針依次放入OPEN表的首部，轉步2。

例4.4對于八數碼問題，應用深度優先搜索策略，可得如圖4—6所示的搜索樹。深度優先搜索亦稱為縱向搜索。由于一個有解的問題樹可能含有無窮分枝，深度優先搜索如果誤入無窮分枝(即深度無限,但解不在該分支內)，則不可能找到目標節點。所以，深度優先搜索策略是不完備的。另外，應用此策略得到的解不一定是最佳解(最短路徑)。2178634512178634521786345217863452178634521786345217863452321786345421786345217863455217863456…3.有界深度優先搜索廣度優先和深度優先是兩種最基本的窮舉搜索方法，在此基礎上，根據需要再加上一定的限制條件，便可派生出許多特殊的搜索方法。例如有界深度優先搜索。有界深度優先搜索:

給出搜索樹深度限制，當從初始節點出發沿某一分枝擴展到一限定深度時，就不能再繼續向下擴展，而只能改變方向繼續搜索。節點x的深度(即其位于搜索樹的層數)通常用d(x)表示，則有界深度優先搜索算法如下：

步1把S0放入OPEN表中，置S0的深度d(S0)=0；步2若OPEN表為空，則失敗，退出。步3取OPEN表頭節點N，放入CLOSED表中，并冠以順序編號n；步4若目標節點Sg=N，則成功，結束。步5若N的深度d(N)=dm(深度限制值)，或者若N無子節點，則轉步2；步6擴展N，將其所有子節點Ni配上指向N的返回指針后依次放入OPEN表中前部，置d(Ni)=d(N)+1，轉步2。4.1.4啟發式搜索

1．問題的提出窮舉搜索法從理論上，似乎可以解決任何狀態空間的搜索問題，但實踐表明，窮舉搜索只能解決一些狀態空間很小的簡單問題，而對于那些大狀態空間問題，窮舉搜索就不能勝任了。因為大空間問題，往往會導致“組合爆炸”。2.啟發性信息啟發式搜索就是利用啟發性信息進行制導的搜索。啟發性信息就是有利于盡快找到問題之解的信息。按其用途劃分，啟發性信息一般可分為以下三類：

(1)用于擴展節點的選擇，即用于決定應先擴展哪一個節點，以免盲目擴展。

(2)用于生成節點的選擇，即用于決定應生成哪些后續節點，以免盲目地生成過多無用節點。

(3)用于刪除節點的選擇，即用于決定應刪除哪些無用節點，以免造成進一步的時空浪費。3.啟發函數在啟發式搜索中，通常用所謂啟發函數來表示啟發性信息。啟發函數是用來估計搜索樹上節點x與目標節點Sg接近程度的一種函數，通常記為h(x)。定義啟發函數：啟發函數并無固定的模式，需要具體問題具體分析。通常可以參考的思路有：一個節點到目標節點的某種距離或差異的度量；一個節點處在最佳路徑上的概率；或者根據經驗的主觀打分等等。例如，對于八數碼難題，用h(x)就可表示節點x的數碼格局同目標節點相比，數碼不同的位置個數。

4.啟發式搜索算法啟發式搜索要用啟發函數來導航，其搜索算法就要在狀態圖一般搜索算法基礎上再增加啟發函數值的計算與傳播過程，并且由啟發函數值來確定節點的擴展順序。1)全局擇優搜索全局擇優搜索就是利用啟發函數制導的一種啟發式搜索方法。該方法亦稱為最好優先搜索法，它的基本思想是：在OPEN表中保留所有已生成而未考察的節點，并用啟發函數h(x)對它們全部進行估價，從中選出最優節點進行擴展，而不管這個節點出現在搜索樹的什么地方。

全局擇優搜索算法如下：步1把初始節點S0放入OPEN表中，計算h(So)；步2若OPEN表為空，則搜索失敗，退出。步3移出OPEN表中第一個節點N放入CLOSED表中，并冠以序號n；步4若目標節點Sg=N，則搜索成功，結束。步5若N不可擴展，則轉步2；步6擴展N，計算每個子節點x的函數值h(x)，并將所有子節點配以指向N的返回指針后放入OPEN表中，再對OPEN表中的所有子節點按其函數值大小以升序排序，轉步2。

例4.5用全局擇優搜索法解八數碼難題。初始棋局和目標棋局同例3。解設啟發函數h(x)為節點x的格局與目標格局相比數碼不同的位置個數。以這個函數制導的搜索樹如圖4—7所示。圖中節點旁的數字就是該節點的估價值。由圖可見此八數問題的解為：

八數碼問題的全局擇優搜索2)局部擇優搜索局部擇優搜索與全局擇優搜索的區別是，擴展節點N后僅對N的子節點按啟發函數值大小以升序排序，再將它們依次放入OPEN表的首部。21786345S02178634521786345217863452178634544S1552178634521786345542178634542178634521786345Sg542.分支界限法(最小代價優先法)g(x):從初始點S0到x的代價；其基本思想是：每次從OPEN表中選出g(x)值最小的節點進行考察，而不管這個節點在搜索樹的什么位置上。可以看出，這種搜索法與前面的最好優先法（即全局擇優法）的區別僅是選取擴展節點的標準不同，一個是代價值g(x)（最小），一個是啟發函數值h(x)（最小）。這就是說，把最好優先法算法中的h(x)換成g(x)即得分支界限法的算法。4.1.5加權狀態圖搜索

——最近擇優法(瞎子爬山法)1.加權狀態圖與代價樹例4.6設A城是出發地，E城是目的地，邊上的數字代表兩城之間的交通費。試求從A到E最小費用的旅行路線。

交通圖及其代價樹

可以看出，這個圖與前面的狀態圖不同的地方是邊上附有數值。它表示邊的一種度量（此例中是交通費，當然也可以是距離）。一般地，稱這種數值為權值，而把邊上附有數值的狀態圖稱之為加權狀態圖或賦權狀態圖。

加權狀態圖的搜索與權值有關，并且要用權值來導航。具體來講，加權狀態圖的搜索算法，要在一般狀態圖搜索算法基礎上再增加權值的計算與傳播過程，并且要由權值來確定節點的擴展順序。為簡單起見，先考慮樹型的加權狀態圖——代價樹的搜索。所謂代價，可以是兩點之間的距離、交通費用或所需時間等等。用g(x)表示從初始節點S0到節點x的代價，用c(xi,xj)表示父節點xi到子節點xj的代價，即邊(xi,xj)的代價。從而有

g(xj)＝g(xi)＋c(xi,xj)

而g(S0)＝0

也可以將加權狀態圖轉換成代價樹來搜索，其轉換方法是，從初始節點起，先把每一個與初始節點相鄰的節點作為該節點的子節點；然后對其他節點依次類推，但對其他節點x，不能將其父節點及祖先再作為x的子節點。例如，把圖4—8(a)所示的交通圖轉換成代價樹如圖4—8(b)所示。

同上面的情形一樣，這種方法實際同局部擇優法類似，區別也僅是選取擴展節點的標準不同，一個是代價值g(x)（最小），一個是啟發函數值h(x)（最小）。這就是說，把局部擇優法算法中的h(x)換成g(x)就可得最近擇優法的算法。現在我們用代價樹搜索求解例4.6中給出的問題。我們用分支界限法得到的路徑為

A→C→D→E

這是一條最小費用路徑(費用為8)。4.1.6啟發式圖搜索的A算法和A*算法前面我們介紹了圖搜索的一般算法，并著重討論了樹型圖的各種搜索策略。本節給出圖搜索的兩種典型的啟發式搜索算法。

1.估價函數利用啟發函數h(x)制導的啟發式搜索，實際是一種深度優先的搜索策略。雖然它是很高效的，但也可能誤入歧途。

所以，為了更穩妥一些，人們把啟發函數擴充為估價函數。估價函數的一般形式為

f(x)＝g(x)＋h(x)

其中g(x)為從初始節點S0到節點x已經付出的代價，h(x)是啟發函數。即估價函數f(x)是從初始節點S0到達節點x處已付出的代價與節點x到達目標節點Sg的接近程度估計值之總和。有時估價函數還可以表示為

f(x)＝d(x)＋h(x)2.A算法

A算法是基于估價函數f(x)的一種加權狀態圖啟發式搜索算法。其具體步驟如下：

步1把附有f(S0)的初始節點S0放入OPEN表；步2若OPEN表為空，則搜索失敗，退出。步3移出OPEN表中第一個節點N放入CLOSED表中，并冠以順序編號n；步4若目標節點Sg=n，則搜索成功，結束。步5若n不可擴展，則轉步2；步6擴展n，生成一組附有f(n)的子節點,將所有子節點配以指向n的返回指針后放入OPEN表中，再對OPEN表中的所有子節點按其函數值大小以升序排序，轉步2。3.A*算法如果對上述A算法再限制其估價函數中的啟發函數h(x)滿足：對所有的節點x均有

h(x)≤h*(x)

其中h*(x)是從節點x到目標節點的最小代價(若有多個目標節點則為其中最小的一個)，則它就稱為A*算法。3.啟發函數：f(x)=d(x)+h(x)h(x)=不在目標位置的數符個數217863453217863452178634521786345217863455566217863452178634521786345217863455354S2217863452S32178634521786345Sg03

4.1.7狀態圖搜索策略小結上述的狀態圖搜索策略可歸納如下：樹式搜索——窮舉式——廣度優先深度優先—有界深度優先啟發式搜索——全局擇優（最好優先，基于啟發函數h(x)）

—局部擇優

—分支界限（全局最小代價優先，基于代價函數g(x)）

—最近擇優（瞎子爬山，局部最小代價優先，基于g(x)）

—A算法（基于估價函數f(x)＝g(x)＋h(x)）

A*算法（最佳圖搜索，h(x)≤h*(x)）：可以證明：如果解存在，A*一定能夠找到最優解

4.2狀態圖問題求解

4.2.1問題的狀態圖表示

1.狀態狀態就是問題在任一確定時刻的狀況，它表征了問題特征和結構等。狀態在狀態圖中表示為節點。狀態一般用一組數據表示。在程序中用字符、數字、記錄、數組、結構、對象等表示。2.狀態轉換規則狀態轉換規則就是能使問題狀態改變的某種操作、規則、行為、變換、關系、函數、算子、過程等等。狀態轉換規則也稱為操作，問題的狀態也只能經定義在其上的這種操作而改變。狀態轉換規則在狀態圖中表示為邊。在程序中狀態轉換規則可用數據對、條件語句、規則、函數、過程等表示。3.狀態圖表示一個問題的狀態圖是一個三元組（S,F,G）其中S是問題的初始狀態集合，F是問題的狀態轉換規則集合，G是問題的目標狀態集合。

一個問題的全體狀態及其關系，就構成一個空間，稱為狀態空間。所以，狀態圖也稱為狀態空間圖。

例：迷宮問題的狀態圖表示。以例迷宮為例。每個格子作為一個狀態，并用其標識符作為其表示。那么，兩個標識符組成的序對就是一個狀態轉換規則。于是，該迷宮的狀態圖表示為

S：S0F：｛(S0,S4),(S4,S0)(S4,S1),(S1,S4),(S1,S2),(S2,S1),(S2,S3),(S3,S2),(S4,S7),(S7,S4),(S4,S5),(S5,S4),(S5,S6),(S6,S5),(S5,S8),(S8,S5),(S8,S9),(S9,S8),(S9,Sg)｝

G：Sg

例4.8八數碼難題的狀態圖表示。我們將棋局X1X2X3X6X0X4X7X6X5

用向量

A＝(X0,X1,X2,X3,X4,X5,X6,X7,X8)

表示，Xi為變量，Xi的值就是方格Xi內的數字。于是，向量A就是該問題的狀態表達式。設初始狀態和目標狀態分別為

S0＝(0,2,8,3,4,5,6,7,1)Sg＝(0,1,2,3,4,5,6,7,8)

易見，數碼的移動規則就是該問題的狀態變換規則，即操作。經分析，該問題共有24條移碼規則，可分為9組。分別描述空格(X0)在不同位置時的移動規則:2831047651238047650組規則(空格在中央):r1(X0=0)∧(X2=n)→X0n∧X20;r2(X0=0)∧(X4=n)→X0n∧X40;r3(X0=0)∧(X6=n)→X0n∧X60;r4(X0=0)∧(X8=n)→X0n∧X80;1組規則:(空格左上角)r5(X1=0)∧(X2=n)→X1n∧X20;r6(X1=0)∧(X8=n)→X1n∧X80;X1X2X3X6X0X4X7X6X52組規則:r7(X2=0)∧(X1=n)→X2n∧X10;r8(X2=0)∧(X3=n)→X2n∧X30;r9(X2=0)∧(X0=n)→X2n∧X00;…8組規則:r22(X8=0)∧(X1=n)→X8n∧X10;r23(X8=0)∧(X0=n)→X8n∧X00;r24(X8=0)∧(X7=n)→X8n∧X70;

于是，八數碼問題的狀態圖可表示為（{S0},{r1,r2,…,r24},{Sg}）當然，上述24條規則也可以簡化為4條:即空格上移、下移、左移、右移。不過，這時狀態(即棋局)就需要用矩陣來表示：八數碼問題狀態圖初始僅給出了初始節點和目標節點，并未給出其余節點。而其余節點需用狀態轉換規則來產生。類似于這樣表示的狀態圖稱為隱式狀態圖，或者說狀態圖的隱式表示。例2階梵塔問題設用二元組(SA,SB)表示問題的狀態，SA表示金盤A所在的桿號，SB表示金盤B所在的桿號，這樣，全部可能的狀態有9種，可表示如下：

(1,1),(1,2),(1,3)(2,1),(2,2),(2,3)(3,1),(3,2),(3,3)

如圖所示。

這里的狀態轉換規則就是金盤的搬動規則，分別用A(i,j)及B(i,j)表示：A(i,j)表示把A盤從第i號桿移到第j號桿上;B(i,j)表示把B盤從第i號桿移到第j號桿上。經分析，共有12個操作，它們分別是：

A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)

二階梵塔問題可用狀態圖表示為（{(1,1)},{A(1,2),…,B(3,2)},{(3,3)})

由這9種可能的狀態和12種操作，二階梵塔問題的狀態空間如圖所示。

例4.10旅行商問題(TravelingSalesmanProblem，簡稱TSP)。設有n個互相可直達的城市，某推銷商準備從其中的A城出發，周游各城市一遍，最后又回到A城。要求為該推銷商規劃一條最短的旅行路線。該問題的狀態為以A打頭的已訪問過的城市序列:A…S0:A。

Sg:A,…,A。其中“…”為其余n-1個城市的一個序列。狀態轉換規則：規則1如果當前城市的下一個城市還未去過，則去該城市，并把該城市名排在已去過的城市名序列后端。規則2如果所有城市都去過一次，則從當前城市返回A城，把A也添在去過的城市名序列后端。4.3與或圖搜索

4.3.1與或圖例：如圖所示，設有四邊形ABCD和A′B′C′D′，要求證明它們全等。圖4—11四邊形ABCD和A′B′C′D′

分析：分別連接B、D和B′、D′，則原問題可分解為兩個子問題：

Q1：證明△ABD≌△A′B′D′Q2：證明△BCD≌△B′C′D′

于是，原問題的解決可歸結為這兩個子問題的解決。換句話說，原問題被解決當且僅當這兩個子問題都被解決。進一步，問題Q1還可再被分解為

Q11：證明AB＝A′B′Q12：證明AD＝A′D′Q13：證明∠A＝∠A′或Q11′：證明AB＝A′B′Q12′：證明AD＝A′D′Q13′：證明BD＝B′D′問題Q2還可再被分解為Q21：證明BC＝B′C′Q22：證明CD＝C′D′Q23：證明∠C＝∠C′或Q21′：證明BC＝B′C′Q22′：證明CD＝C′D′Q23′：證明BD＝B′D′

現在考慮原問題與這兩組子問題的關系，我們便得到下圖。圖中的弧線表示所連邊為“與”關系，不帶弧線的邊為或關系。這個圖中既有與關系又有或關系，因此被稱為與或圖。但這個與或圖是一種特殊的與或圖，稱為與或樹。圖一個典型的與或圖——未必是樹

可以看出，從與、或關系來看，前面的狀態圖，實際就是或圖。這就是說，與或圖是狀態圖的推廣，而狀態圖是與或圖的特例。為了敘述方便，引入以下概念：直接可解的簡單問題稱為本原問題，本原問題對應的節點稱為終止節點，在與或圖（樹）中無子節點的節點稱為端節點，一個節點的子節點如果是“與”關系，則該節點便稱為與節點，一個節點的子節點如果是“或”關系，則該節點便稱為或節點。注意，終止節點一定是端節點，但端節點不一定是終止節點。4.3.2與或圖搜索

1.搜索方式，解圖（樹）同狀態圖(即或圖)的搜索一樣，與或圖搜索也分為樹式和“線”式兩種類型。對于樹式搜索來講，其搜索過程也是不斷地擴展節點，并配以返回指針，而形成一棵不斷生長的搜索樹。

2.可解性判別判斷一個節點可解性的判別準則：

(1)一個節點是可解，則節點須滿足下列條件之一:①終止節點是可解節點；②一個與節點可解，當且僅當其子節點全都可解；③一個或節點可解，只要其子節點至少有一個可解。

(2)一個節點是不可解，則節點須滿足下列條件之一:①非終止節點的端節點是不可解節點；②一個與節點不可解，只要其子節點至少有一個不可解；③一個或節點不可解，當且僅當其子節點全都不可解。3.搜索策略與或圖搜索也分為盲目搜索和啟發式搜索兩大類。前者又分為窮舉搜索和盲目碰撞搜索。窮舉搜索又分為深度優先和廣度優先兩種基本策略。

4.搜索算法同一般狀態圖搜索一樣，一般與或圖搜索也涉及一些復雜的處理。這里僅討論特殊的與或圖——與或樹的搜索算法。與或樹的樹式搜索過程可概括為以下步驟：

步1把初始節點S0放入OPEN表；步2移出OPEN表的第一個節點N放入CLOSED表，并冠以序號n；步3若節點N可擴展，則做下列工作：

(1)擴展N,將其子節點配上指向父節點的指針后放入OPEN表；

(2)考察這些子節點中是否有終止節點。

(3)刪去OPEN表中那些具有可解先輩的節點（因為其先輩節點已經可解，故已無再考察該節點的必要），轉步2；

步4若N不可擴展，則做下列工作：

(1)標記N為不可解節點，然后由它的不可解返回推斷其先輩節點的可解性，并對其中的不可解節點進行標記。如果初始節點S0也被標記為不可解節點，則搜索失敗，退出。

(2)刪去OPEN表中那些具有不可解先輩的節點（因為其先輩節點已不可解，故已無再考察這些節點的必要），轉步2；同狀態圖搜索一樣，搜索成功后，解樹已經記錄在CLOSED表中。這時需按指向父節點的指針找出整個解樹。

其中1號節點為初始節點，t1、t2、t3、t4均為終止節點，A和B是不可解的端節點。采用廣度搜索策略，搜索過程如下：

(1)擴展1號節點，得2號和3號節點，依次放入OPEN表尾部。由于這兩個節點都非終止節點，所以接著擴展2號節點。此時OPEN表中只有3號節點。

(2)2號節點擴展后，得4號節點和t1節點。此時OPEN表中依次有3號、4號和t1節點。

(3)擴展3號節點，得5號節點和B節點。兩者均非終止節點，所以繼續擴展4號節點。例：設有與或樹如圖4-14，實施廣度優先搜索(4)4號節點擴展后得節點A和t2。t2是終止節點，標記為可解節點，放入CLOSED表。其先輩4,2均可解，但1未確定。A從OPEN表中刪除。

(5)擴展5號節點得t3和t4。由于t3和t4都為終止節點(放入CLOSED表)，故可推得節點5、3、1均為可解節點。搜索成功，結束。4.3.3啟發式與或樹搜索廣度優先搜索及深度優先搜索都是盲目搜索，其共同點是：

(1)搜索從初始節點開始，先自上而下地進行搜索，尋找終止節點及端節點，然后再自下而上地進行可解性標記，一旦初始節點被標記為可解節點或不可解節點，搜索就不再繼續進行。

(2)搜索都是按確定路線進行的，當要選擇一個節點進行擴展時，只是根據節點在與或樹中所處的位置，而沒有考慮要付出的代價，因而求得的解樹不一定是代價最小的解樹，即不一定是最優解樹。1.解樹的代價解樹的代價是樹根的代價。樹根的代價是從樹葉開始自下而上逐層計算而求得的。而解樹的根對應的是初始節點S0。這就是說，在與或樹的搜索過程中，代價的計算方向與搜索樹的生長方向相反，計算過程如下：設g(x)表示節點x的代價，c(x,y)表示節點x到其子節點y的代價(即邊<x,y>的代價)，則

(1)若x是終止節點，g(x)＝0；

(2)若x是或節點g(x)=min{c(x,y)+g(y)|y是x的子節點}(3)若x是與節點x，則有兩種計算公式:a.和代價：

b.最大代價：g(x)=max{c(x,y)+g(y)|y是x的子節點}(4)對非終止的端節點x，g(x)＝∞

例：如圖所示的與或樹，其中包括兩棵解樹，一棵解樹由S0,A,t1和t2組成；另一棵解樹由S0,B,D,G,t4和t5組成。在此與或樹中，t1,t2,t3,t4,t5為終止節點；E,F是端節點，其代價均為∞；邊上的數字是該邊的代價。由右邊的解樹可得：按和代價：g(A)=11,g(S0)=13

按最大代價：g(A)=6,g(S0)=8左邊的解樹可得：按和代價：g(G)=3,g(D)=4,g(B)=6,g(S0)=8

按最大代價：g(G)=2,g(D)=3,g(B)=5,g(S0)=7

按和代價計算，左邊的解樹是最優解樹，其代價為8;

按最大代價計算，左邊的解樹仍然是最優解樹，其代價是7。但有時用不同的計算代價方法得到的最優解樹不相同。

2.希望樹無論是用和代價法還是最大代價法，當要計算任一節點x的代價g(x)時，都要求已知其子節點yi的代價g(yi)。但是，搜索是自上而下進行的，即先有父節點，后有子節點，除非節點x的全部子節點都是不可擴展節點，否則子節點的代價是不知道的。解決方法：根據問題本身的啟發信息構造啟發函數對g(x)進行估計。設y是x的子節點，c(x,y)已知，則對g(x)的估計實際上是對x的所有子節點y的代價g(y)的估計。當y被擴展后，重新計算的g(y)值可能與原先的估計不同，這時應該用后計算的g(y)值取代之，從而導致y的所有先輩節點x的g(x)值重新計算。因此每擴展一個新節點時要求自下而上的重新計算該節點所有先輩節點的g值。最優樹：代價最小的解樹。要求搜索過程中任一步驟上求出的部分解樹都是最小的。因此每次應該挑選有希望成為最優樹組成的節點進行擴展。這種每次由最優樹部分節點擴展產生的與或樹稱為希望樹。希望樹的定義：(1)初始節點S0在希望樹T中;如果x是希望樹T中的節點，當x是具有子節點y1,..yn的或節點，則具有的節點也應該在希望樹T中；當x是與節點,則x的全部子節點也在希望樹T3.與或樹的有序搜索過程與或樹的有序搜索過程是一個不斷選擇、修正希望樹的過程。如果問題有解，則經有序搜索將找到最優解樹。其搜索過程如下：

(1)把初始節點S0放入OPEN表中。

(2)求出希望樹T，即根據當前搜索樹中節點的代價g求出以S0為根的希望樹T。

(3)依次把OPEN表中T的端節點N選出放入LOSED表中。(4)如果節點N是終止節點，則做下列工作：①標示N為可解節點。②對T應用可解標記過程，把N的先輩節點中的可解節點都標記為可解節點。③若初始節點S0能被標記為可解節點，則T就是最優解樹，成功退出。

④否則，從OPEN表中刪去具有可解先輩的所有節點。(5)如果節點N不是終止節點，且它不可擴展，則做下列工作：①標示N為不可解節點。②對T應用不可解標記過程，把N的先輩節點中的不可解節點都標記為不可解節點。③若初始節點S0也被標記為不可解節點，則失敗退出。④否則，從OPEN表中刪去具有不可解先輩的所有節點。(6)如果節點N不是終止節點，但它可擴展，則做下列工作：①擴展節點N，產生N的所有子節點。②把這些子節點都放入OPEN表中，并為每一個子節點配置指向父節點（節點N）的指針。③計算這些子節點的g值及其先輩節點的g值。

(7)轉(2)。

例4.18舉例說明上述搜索過程。設初始節點為S0，每次擴展兩層，并設S0經擴展后得到如圖4—16(a)所示的與或樹，其中子節點B，C，E，F用啟發函數估算出的g值分別是

g(B)=3，g(C)=3，g(E)=3，g(F)=2

若按和代價計算，則得到

g(A)=8，g(D)=7，g(S0)=8(注:邊代價按1計算，下同)

此時，S0的右子樹是希望樹。下面將對此希望樹的節點進行擴展。

設對節點E擴展兩層后得到如圖4—16(b)所示的與或樹，節點旁的數字為用啟發函數估算出的g值。則按和代價法計算得到

g(G)=7,g(H)=6,g(E)=7,g(D)=11

此時，由S0的右子樹算出的g(S0)=12。但是，由左子樹算出的g(S0)=9。顯然，左子樹的代價小，所以現在改取左子樹作為當前的希望樹。

假設對節點B擴展兩層后得到如圖4—16(c)所示的與或樹，節點旁的數字是對相應節點的估算值，節點L的兩個子節點是終止節點，則按和代價法計算得到

g(L)=2,g(M)=6,g(B)=3,g(A)=8

由此可推算出g(S0)=9。這時，左子樹仍然是希望樹，繼續對其擴展。該擴展節點C。

假設節點C擴展兩層后得到如圖4—16(d)所示的與或樹，節點旁的數字是對相應節點的估算值，節點N的兩個子節點是終止節點。按和代價計算得到

g(N)=2,g(P)=7,g(C)=3,g(A)=8

由此可推算出g(S0)=9。另外，由于N的兩個子節點都是終止節點，所以N和C都是可解節點。再由前面推出的B是可解節點，可推出A和S0都是可解節點。這樣就求出了代價最小的解樹，即最優解樹——圖4—16(d)中粗線部分所示。該最優解樹是用和代價法求出來的，解樹的代價為9。圖4—16與或樹有序搜索

4.4與或圖問題求解

4.4.1問題的與或圖表示與或圖是描述問題求解的另一種有向圖。與或圖一般表示問題的變換過程（而不是狀態變換）。具體講，它是從原問題出發，通過運用某些規則不斷進行問題分解（得到與分支）和變換（得到或分支），而得到一個與或圖。換句話說，與或圖的節點一般代表問題。那么，整個圖也就表示問題空間。與或圖中的父節點

與其子節點之間服從邏輯上的與、或運算關系。所以，與或圖表示的問題是否有解，要進行邏輯判斷，與或圖的搜索也受邏輯的制約。與或圖也是一個三元組（Q0,F,Qn）

例4.19三階梵塔問題。對于梵塔問題，可以這樣考慮：為把1號桿上的n個盤子搬到3號桿，可先把上面的n-1個盤子搬到2號桿上；再把剩下的一個大盤子搬到3號桿；然后再將2號桿上的n-1個盤子搬到3號桿。這樣，就把原來的一個問題分解為三個子問題。這三個子問題都比原問題簡單，其中第二個子問題已是直接可解的問題。對于第一和第三兩個子問題，可用上面n個盤子的方法，做同樣的處理。根據這一思想，我們可把三階梵塔問題分解為下面的三個子問題：(1)把A、B盤從1號桿移到2號桿。

(2)把C盤從1號桿移到3號桿。

(3)把A、B盤從2號桿移到3號桿。其中子問題(1)、(3)又分別可分解為三個子問題。于是，我們可得到三階梵塔問題的與或樹表示：

三元組(i,j,k)：

i代表金盤C所在的桿號;j代表金盤B所在的桿號，

k代表金盤A所在的桿號。上圖所示的與或樹中，共有七個終止節點，對應于七個本原問題，它們是通過“分解”得到的。若把這些本原問題的解按從左至右的順序排列，就得到了原始問題的解：(1,1,1)(1,1,3)(1,1,3)(1,2,3)(1,2,3)(1,2,2)(1,2,2)(3,2,2)(3,2,2)(3,2,1)(3,2,1)(3,3,1)(3,3,1)(3,3,3)

4.5博弈樹搜索

諸如下棋、打牌、競技、戰爭等一類競爭性智能活動稱為博弈。其中最簡單的一種稱為“二人零和、全信息、非偶然”博弈。

(1)對壘的A，B雙方輪流采取行動，博弈的結果只有三種情況：A方勝，B方敗；B方勝，A方敗；雙方戰成平局。

(2)在對壘過程中，任何一方都了解當前的格局及過去