人工智能 第4章 圖搜索技術(shù)

第4章圖搜索技術(shù)

4.1狀態(tài)圖搜索4.2狀態(tài)圖問題求解

4.3與或圖搜索

4.4與或圖問題求解4.5博弈樹搜索4.1狀態(tài)圖搜索

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

交通圖及其代價樹

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

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

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

而g(S0)＝0

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

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

A→C→D→E

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

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

所以，為了更穩(wěn)妥一些，人們把啟發(fā)函數(shù)擴充為估價函數(shù)。估價函數(shù)的一般形式為

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

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

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

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

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

h(x)≤h*(x)

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

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

—局部擇優(yōu)

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

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

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

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

4.2狀態(tài)圖問題求解

4.2.1問題的狀態(tài)圖表示

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

一個問題的全體狀態(tài)及其關(guān)系，就構(gòu)成一個空間，稱為狀態(tài)空間。所以，狀態(tài)圖也稱為狀態(tài)空間圖。

例：迷宮問題的狀態(tài)圖表示。以例迷宮為例。每個格子作為一個狀態(tài)，并用其標(biāo)識符作為其表示。那么，兩個標(biāo)識符組成的序?qū)褪且粋€狀態(tài)轉(zhuǎn)換規(guī)則。于是，該迷宮的狀態(tài)圖表示為

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八數(shù)碼難題的狀態(tài)圖表示。我們將棋局X1X2X3X6X0X4X7X6X5

用向量

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

表示，Xi為變量，Xi的值就是方格Xi內(nèi)的數(shù)字。于是，向量A就是該問題的狀態(tài)表達(dá)式。設(shè)初始狀態(tài)和目標(biāo)狀態(tài)分別為

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

易見，數(shù)碼的移動規(guī)則就是該問題的狀態(tài)變換規(guī)則，即操作。經(jīng)分析，該問題共有24條移碼規(guī)則，可分為9組。分別描述空格(X0)在不同位置時的移動規(guī)則:2831047651238047650組規(guī)則(空格在中央):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組規(guī)則:(空格左上角)r5(X1=0)∧(X2=n)→X1n∧X20;r6(X1=0)∧(X8=n)→X1n∧X80;X1X2X3X6X0X4X7X6X52組規(guī)則:r7(X2=0)∧(X1=n)→X2n∧X10;r8(X2=0)∧(X3=n)→X2n∧X30;r9(X2=0)∧(X0=n)→X2n∧X00;…8組規(guī)則:r22(X8=0)∧(X1=n)→X8n∧X10;r23(X8=0)∧(X0=n)→X8n∧X00;r24(X8=0)∧(X7=n)→X8n∧X70;

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

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

如圖所示。

這里的狀態(tài)轉(zhuǎn)換規(guī)則就是金盤的搬動規(guī)則，分別用A(i,j)及B(i,j)表示：A(i,j)表示把A盤從第i號桿移到第j號桿上;B(i,j)表示把B盤從第i號桿移到第j號桿上。經(jīng)分析，共有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)

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

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

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

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

4.3.1與或圖例：如圖所示，設(shè)有四邊形ABCD和A′B′C′D′，要求證明它們?nèi)取D4—11四邊形ABCD和A′B′C′D′

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

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

于是，原問題的解決可歸結(jié)為這兩個子問題的解決。換句話說，原問題被解決當(dāng)且僅當(dāng)這兩個子問題都被解決。進(jìn)一步，問題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′

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

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

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

2.可解性判別判斷一個節(jié)點可解性的判別準(zhǔn)則：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例：如圖所示的與或樹，其中包括兩棵解樹，一棵解樹由S0,A,t1和t2組成；另一棵解樹由S0,B,D,G,t4和t5組成。在此與或樹中，t1,t2,t3,t4,t5為終止節(jié)點；E,F是端節(jié)點，其代價均為∞；邊上的數(shù)字是該邊的代價。由右邊的解樹可得：按和代價：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

按和代價計算，左邊的解樹是最優(yōu)解樹，其代價為8;

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

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

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

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

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

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

(7)轉(zhuǎn)(2)。

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

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

若按和代價計算，則得到

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

此時，S0的右子樹是希望樹。下面將對此希望樹的節(jié)點進(jìn)行擴展。

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

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

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

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

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

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

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

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

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

4.4與或圖問題求解

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

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

例4.19三階梵塔問題。對于梵塔問題，可以這樣考慮：為把1號桿上的n個盤子搬到3號桿，可先把上面的n-1個盤子搬到2號桿上；再把剩下的一個大盤子搬到3號桿；然后再將2號桿上的n-1個盤子搬到3號桿。這樣，就把原來的一個問題分解為三個子問題。這三個子問題都比原問題簡單，其中第二個子問題已是直接可解的問題。對于第一和第三兩個子問題，可用上面n個盤子的方法，做同樣的處理。根據(jù)這一思想，我們可把三階梵塔問題分解為下面的三個子問題：(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所在的桿號。上圖所示的與或樹中，共有七個終止節(jié)點，對應(yīng)于七個本原問題，它們是通過“分解”得到的。若把這些本原問題的解按從左至右的順序排列，就得到了原始問題的解：(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博弈樹搜索

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

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

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