人工智能 第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如圖是一個(gè)迷宮。將迷宮的每一個(gè)格子以及入口和出口都作為節(jié)點(diǎn)，把通道作為邊，則該迷宮可以由一個(gè)有向圖表示。走迷宮其實(shí)就是從該有向圖的初始節(jié)點(diǎn)(入口)出發(fā)，尋找目標(biāo)節(jié)點(diǎn)(出口)的路徑的問題。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

交通圖及其代價(jià)樹

可以看出，這個(gè)圖與前面的狀態(tài)圖不同的地方是邊上附有數(shù)值。它表示邊的一種度量（此例中是交通費(fèi)，當(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)值的計(jì)算與傳播過程，并且要由權(quán)值來確定節(jié)點(diǎn)的擴(kuò)展順序。為簡(jiǎn)單起見，先考慮樹型的加權(quán)狀態(tài)圖——代價(jià)樹的搜索。所謂代價(jià)，可以是兩點(diǎn)之間的距離、交通費(fèi)用或所需時(shí)間等等。用g(x)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的代價(jià)，用c(xi,xj)表示父節(jié)點(diǎn)xi到子節(jié)點(diǎn)xj的代價(jià)，即邊(xi,xj)的代價(jià)。從而有

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

而g(S0)＝0

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

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

A→C→D→E

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

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

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

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

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

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

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

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

h(x)≤h*(x)

其中h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià)(若有多個(gè)目標(biāo)節(jié)點(diǎn)則為其中最小的一個(gè))，則它就稱為A*算法。3.啟發(fā)函數(shù)：f(x)=d(x)+h(x)h(x)=不在目標(biāo)位置的數(shù)符個(gè)數(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)

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

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

—A算法（基于估價(jià)函數(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)就是問題在任一確定時(shí)刻的狀況，它表征了問題特征和結(jié)構(gòu)等。狀態(tài)在狀態(tài)圖中表示為節(jié)點(diǎn)。狀態(tài)一般用一組數(shù)據(jù)表示。在程序中用字符、數(shù)字、記錄、數(shù)組、結(jié)構(gòu)、對(duì)象等表示。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ù)對(duì)、條件語句、規(guī)則、函數(shù)、過程等表示。3.狀態(tài)圖表示一個(gè)問題的狀態(tài)圖是一個(gè)三元組（S,F,G）其中S是問題的初始狀態(tài)集合，F(xiàn)是問題的狀態(tài)轉(zhuǎn)換規(guī)則集合，G是問題的目標(biāo)狀態(tài)集合。

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

例：迷宮問題的狀態(tài)圖表示。以例迷宮為例。每個(gè)格子作為一個(gè)狀態(tài)，并用其標(biāo)識(shí)符作為其表示。那么，兩個(gè)標(biāo)識(shí)符組成的序?qū)褪且粋€(gè)狀態(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ù)碼的移動(dòng)規(guī)則就是該問題的狀態(tài)變換規(guī)則，即操作。經(jīng)分析，該問題共有24條移碼規(guī)則，可分為9組。分別描述空格(X0)在不同位置時(shí)的移動(dòng)規(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ī)則也可以簡(jiǎn)化為4條:即空格上移、下移、左移、右移。不過，這時(shí)狀態(tài)(即棋局)就需要用矩陣來表示：八數(shù)碼問題狀態(tài)圖初始僅給出了初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，并未給出其余節(jié)點(diǎn)。而其余節(jié)點(diǎn)需用狀態(tài)轉(zhuǎn)換規(guī)則來產(chǎn)生。類似于這樣表示的狀態(tài)圖稱為隱式狀態(tài)圖，或者說狀態(tài)圖的隱式表示。例2階梵塔問題設(shè)用二元組(SA,SB)表示問題的狀態(tài)，SA表示金盤A所在的桿號(hào)，SB表示金盤B所在的桿號(hào)，這樣，全部可能的狀態(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ī)則就是金盤的搬動(dòng)規(guī)則，分別用A(i,j)及B(i,j)表示：A(i,j)表示把A盤從第i號(hào)桿移到第j號(hào)桿上;B(i,j)表示把B盤從第i號(hào)桿移到第j號(hào)桿上。經(jīng)分析，共有12個(gè)操作，它們分別是：

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

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

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

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

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

于是，原問題的解決可歸結(jié)為這兩個(gè)子問題的解決。換句話說，原問題被解決當(dāng)且僅當(dāng)這兩個(gè)子問題都被解決。進(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)系。這個(gè)圖中既有與關(guān)系又有或關(guān)系，因此被稱為與或圖。但這個(gè)與或圖是一種特殊的與或圖，稱為與或樹。圖一個(gè)典型的與或圖——未必是樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)擴(kuò)展1號(hào)節(jié)點(diǎn)，得2號(hào)和3號(hào)節(jié)點(diǎn)，依次放入OPEN表尾部。由于這兩個(gè)節(jié)點(diǎn)都非終止節(jié)點(diǎn)，所以接著擴(kuò)展2號(hào)節(jié)點(diǎn)。此時(shí)OPEN表中只有3號(hào)節(jié)點(diǎn)。

(2)2號(hào)節(jié)點(diǎn)擴(kuò)展后，得4號(hào)節(jié)點(diǎn)和t1節(jié)點(diǎn)。此時(shí)OPEN表中依次有3號(hào)、4號(hào)和t1節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

若按和代價(jià)計(jì)算，則得到

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

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

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

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

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

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

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

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

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

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

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

4.4與或圖問題求解

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

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

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

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

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

三元組(i,j,k)：

i代表金盤C所在的桿號(hào);j代表金盤B所在的桿號(hào)，

k代表金盤A所在的桿號(hào)。上圖所示的與或樹中，共有七個(gè)終止節(jié)點(diǎn)，對(duì)應(yīng)于七個(gè)本原問題，它們是通過“分解”得到的。若把這些本原問題的解按從左至右的順序排列，就得到了原始問題的解：(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博弈樹搜索

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

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

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