人工智能第四章

搜索是人工智能中的一個基本問題，并與推理密切相關(guān)，搜索策略的優(yōu)劣，將直接影響到智能系統(tǒng)的性能與推理效率。

搜索的基本概念狀態(tài)空間的盲目搜索狀態(tài)空間的啟發(fā)式搜索與/或樹的盲目搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索第4章搜索策略4.1搜索的基本概念搜索的含義狀態(tài)空間法問題歸約法4.1.1搜索的含義概念：

依靠經(jīng)驗，利用已有知識，根據(jù)問題的實際情況，不斷尋找可利用知識，從而構(gòu)造一條代價最小的推理路線，使問題得以解決的過程搜索的類型

按是否使用啟發(fā)式信息：盲目搜索：按預(yù)定的控制策略進行搜索，在搜索過程中獲得的中間信息并不改變控制策略。啟發(fā)式搜索：在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用于指導(dǎo)搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優(yōu)解。按問題的表示方式：狀態(tài)空間搜索：用狀態(tài)空間法來求解問題所進行的搜索與或樹搜索：用問題歸約法來求解問題時所進行的搜索4.1.2狀態(tài)空間法1.狀態(tài)空間表示方法狀態(tài)(State)：是表示問題求解過程中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)，它可形式地表示為：

Sk={Sk0,Sk1,…}當對每一個分量都給以確定的值時，就得到了一個具體的狀態(tài)。操作(Operator)

也稱為算符，它是把問題從一種狀態(tài)變換為另一種狀態(tài)的手段。操作可以是一個機械步驟，一個運算，一條規(guī)則或一個過程。操作可理解為狀態(tài)集合上的一個函數(shù)，它描述了狀態(tài)之間的關(guān)系。狀態(tài)空間(Statespace)

用來描述一個問題的全部狀態(tài)以及這些狀態(tài)之間的相互關(guān)系。常用一個三元組表示為：(S,F,G)其中，S為問題的所有初始狀態(tài)的集合；F為操作的集合；G為目標狀態(tài)的集合。狀態(tài)空間也可用一個賦值的有向圖來表示，該有向圖稱為狀態(tài)空間圖。在狀態(tài)空間圖中，節(jié)點表示問題的狀態(tài)，有向邊表示操作。狀態(tài)空間法求解問題的基本過程：首先為問題選擇適當?shù)摹盃顟B(tài)”及“操作”的形式化描述方法；然后從某個初始狀態(tài)出發(fā)，每次使用一個“操作”，遞增地建立起操作序列，直到達到目標狀態(tài)為止；此時，由初始狀態(tài)到目標狀態(tài)所使用的算符序列就是該問題的一個解。

4.1.2狀態(tài)空間法2.狀態(tài)空間問題求解例4.1修道士(Missionaries)和野人(Cannibals)問題(簡稱M-C問題)。

設(shè)在河的一岸有三個野人、三個修道士和一條船，修道士想用這條船把所有的人運到河對岸，但受以下條件的約束：一是修道士和野人都會劃船，但每次船上至多可載兩個人；二是在河的任一岸，如果野人數(shù)目超過修道士數(shù)，修道士會被野人吃掉。如果野人會服從任何一次過河安排，請規(guī)劃一個確保修道士和野人都能過河，且沒有修道士被野人吃掉的安全過河計劃。

4.1.2狀態(tài)空間法3.狀態(tài)空間的例子解：首先選取描述問題狀態(tài)的方法。在這個問題中，需要考慮兩岸的修道士人數(shù)和野人數(shù)，還需要考慮船在左岸還是在右岸。從而可用一個三元組來表示狀態(tài)

S=(m,c,b)其中，m表示左岸的修道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)。右岸的狀態(tài)可由下式確定：右岸修道士數(shù)m'=3-m

右岸野人數(shù)c'=3-c

右岸船數(shù)b'=1-b

在這種表示方式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因此，共有4×4×2=32種狀態(tài)。4.1.2狀態(tài)空間法3.狀態(tài)空間的例子

這32種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士被野人吃掉的狀態(tài)，有意義的狀態(tài)只有16種：

S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(2,2,1)S4=(1,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)S8=(3,2,0)S9=(3,1,0)S10=(3,0,0)S11=(2,2,0)S12=(1,1,0)S13=(0,2,0)S14=(0,1,0)S15=(0,0,0)有了這些狀態(tài)，還需要考慮可進行的操作。

操作是指用船把修道士或野人從河的左岸運到右岸。每個操作都應(yīng)當滿足如下條件：

一是船至少有一個人（m或c）操作，離開岸邊的m和c的減少數(shù)目應(yīng)該等于到達岸邊的m和c的增加數(shù)目；二是每次操作船上人數(shù)不得超過2個；三是操作應(yīng)保證不產(chǎn)生非法狀態(tài)。因此，操作應(yīng)由條件部分和動作部分：條件：只有當其條件具備時才能使用動作：刻劃了應(yīng)用此操作所產(chǎn)生的結(jié)果。

操作的表示：

用符號Pij表示從左岸到右岸的運人操作用符號Qij表示從右岸到左岸的操作其中：

i表示船上的修道士人數(shù)

j表示船上的野人數(shù)操作集本問題有10種操作可供選擇：

F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20}

下面以P01和Q01為例來說明這些操作的條件和動作。操作符號條件動作

P01b=1,m=0或3,c≥1b=0,c=c-1Q01b=0,m=0或3，c≤2b=1,c=c+1

abc

例4.2猴子摘香蕉問題。在討論謂詞邏輯知識表示時，我們曾提到過這一問題，現(xiàn)在用狀態(tài)空間法來解決這一問題。

解：問題的狀態(tài)可用4元組（w,x,y,z）表示。其中：

w表示猴子的水平位置；

x表示箱子的水平位置；

y表示猴子是否在箱子上，當猴子在箱子上時，y取1，否則y取0；

z表示猴子是否拿到香蕉，當拿到香蕉時z取1，否則z取0。4.1.2狀態(tài)空間法3.狀態(tài)空間的例子所有可能的狀態(tài)為

S0:(a,b,0,0)初始狀態(tài)

S1:(b,b,0,0)S2:(c,c,0,0)S3:(c,c,1,0)S4:(c,c,1,1)目標狀態(tài)允許的操作為

Goto(u)：猴子走到位置u，即

(w,x,0,0)→(u,x,0,0)Pushbox(v):猴子推著箱子到水平位置v，即

(x,x,0,0)→(v,v,0,0)Climbbox:猴子爬上箱子，即

(x,x,0,0)→(x,x,1,0)Grasp；猴子拿到香蕉，即

(c,c,1,0)→(c,c,1,1)

這個問題的狀態(tài)空間圖如下圖所示。操作序列為：

{Goto(b),Pushbox(c),Climbbox,Grasp}猴子摘香蕉問題的解(a,b,0,0)(b,b,0,0)(c,c,0,0)(b,b,1,0)(c,c,1,0)(a,a,0,0)(c,c,1,1)初始狀態(tài)Goto(b)Goto(b)Pushbox(c)Grasp目標狀態(tài)猴子摘香蕉問題的狀態(tài)空間圖解序列為：{Goto(b),Pushbox(c),Climbbox,Grasp}Pushbox(c)ClimbboxClimbboxPushbox(c)Pushbox(a)Pushbox(a)回顧第二章-猴子摘香蕉問題(1/3)描述狀態(tài)的謂詞：AT(x,y)：x在y處ONBOX：猴子在箱子上HB：猴子得到香蕉個體域：x：{monkey,box,banana}Y：{a,b,c}問題的初始狀態(tài)AT(monkey,a)AT(box,b)?ONBOX，?HB問題的目標狀態(tài)AT(monkey,c)，AT(box,c)ONBOX，HBabc描述操作的謂詞Goto(u,v)：猴子從u處走到v處Pushbox(v,w)：猴子推著箱子從v處移到w處Climbbox：猴子爬上箱子Grasp：猴子摘取香蕉各操作的條件和動作Goto(u,v)條件：?ONBOX，AT(monkey,u)，動作：刪除表：AT(monkey,u)添加表：AT(monkey,v)Pushbox(v,w)條件：?ONBOX，AT(monkey,v)，AT(box,v)動作：刪除表：AT(monkey,v)，AT(box,v)添加表：AT(monkey,w)，AT(box,w)回顧第二章-猴子摘香蕉問題(2/3)Climbbox條件：?ONBOX，AT(monkey,w)，AT(box,w)動作：刪除表：?ONBOX添加表：ONBOXGrasp條件：ONBOX，AT(box,c)動作：刪除表：?HB添加表：HB回顧第二章-猴子摘香蕉問題(3/3)基本思想當一問題較復(fù)雜時，可通過分解或變換，將其轉(zhuǎn)化為一系列較簡單的子問題，然后通過對這些子問題的求解來實現(xiàn)對原問題的求解。

分解如果一個問題P可以歸約為一組子問題P1,P2,…,Pn，并且只有當所有子問題Pi都有解時原問題P才有解，任何一個子問題Pi無解都會導(dǎo)致原問題P無解，則稱此種歸約為問題的分解。即分解所得到的子問題的“與”與原問題P等價。等價變換如果一個問題P可以歸約為一組子問題P1,P2,…,Pn，并且子問題Pi中只要有一個有解則原問題P就有解，只有當所有子問題Pi都無解時原問題P才無解，稱此種歸約為問題的等價變換，簡稱變換。即變換所得到的子問題的“或”與原問題P等價。4.1.3問題歸約法1.問題的分解與等價變換PP1P2P3

與樹P1P2P3

或樹PPP1P2P3

P11P12P31P32P33

與/或樹(1)與樹分解(2)或樹等價變換(3)與/或樹4.1.3問題歸約法2.問題的與/或樹表示(4)端節(jié)點與終止節(jié)點在與/或樹中，沒有子節(jié)點的節(jié)點稱為端節(jié)點；本原問題所對應(yīng)的節(jié)點稱為終止節(jié)點。可見，終止節(jié)點一定是端節(jié)點，但端節(jié)點卻不一定是終止節(jié)點。(5)可解節(jié)點與不可解節(jié)點在與/或樹中，滿足以下三個條件之一的節(jié)點為可解節(jié)點：

①任何終止節(jié)點都是可解節(jié)點。

②對“或”節(jié)點，當其子節(jié)點中至少有一個為可解節(jié)點時，則該或節(jié)點就是可解節(jié)點。

③對“與”節(jié)點，只有當其子節(jié)點全部為可解節(jié)點時，該與節(jié)點才是可解節(jié)點。同樣，可用類似的方法定義不可解節(jié)點：

①不為終止節(jié)點的端節(jié)點是不可解節(jié)點。②對“或”節(jié)點，若其全部子節(jié)點都為不可解節(jié)點，則該或節(jié)點是不可解節(jié)點。③對“與”節(jié)點，只要其子節(jié)點中有一個為不可解節(jié)點，則該與節(jié)點是不可解節(jié)點。Pt

tt

解樹(6)解樹由可解節(jié)點構(gòu)成，并且由這些可解節(jié)點可以推出初始節(jié)點（它對應(yīng)著原始問題）為可解節(jié)點的子樹為解樹。在解樹中一定包含初始節(jié)點。

例如，右圖給出的與或樹中，用紅線表示的子樹是一個解樹。在該圖中，節(jié)點P為原始問題節(jié)點，用t標出的節(jié)點是終止節(jié)點。根據(jù)可解節(jié)點的定義，很容易推出原始問題P為可解節(jié)點。問題歸約求解過程就實際上就是生成解樹，即證明原始節(jié)點是可解節(jié)點的過程。這一過程涉及到搜索的問題，對于與/或樹的搜索將在后面詳細討論。例4.4

三階梵塔問題。要求把1號鋼針上的3個金片全部移到3號鋼針上，如下圖所示。

解：這個問題也可用狀態(tài)空間法來解，不過本例主要用它來說明如何用歸約法來解決問題。為了能夠解決這一問題，首先需要定義該問題的形式化表示方法。設(shè)用三元組(i,j,k)表示問題在任一時刻的狀態(tài)，用“→”表示狀態(tài)的轉(zhuǎn)換。上述三元組中

i代表金片C所在的鋼針號

j代表金片B所在的鋼針號

k代表金片A所在的鋼針號1231234.1.3問題歸約法2.問題的與/或樹表示利用問題歸約方法，原問題可分解為以下三個子問題：

(1)把金片A及B移到2號鋼針上的雙金片移動問題。即(1,1,1)→(1,2,2)(2)把金片C移到3號鋼針上的單金片移動問題。即(1,2,2)→(3,2,2)(3)把金片A及B移到3號鋼針的雙金片移動問題。即(3,2,2)→((3,3,3)其中，子問題(1)和(3)都是一個二階梵塔問題，它們都還可以再繼續(xù)進行分解；子問題(2)是本原問題，它已不需要再分解。三階梵塔問題的分解過程可用如下圖與/或樹來表示

(1,1,1)→(3,3,3)

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

在該與/或樹中，有7個終止節(jié)點，它們分別對應(yīng)著7個本原問題。如果把這些本原問題從左至右排列起來，即得到了原始問題的解：

(1,1,1)→(1,3,3)(1,3,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)

搜索的基本概念

狀態(tài)空間的盲目搜索狀態(tài)空間的啟發(fā)式搜索與/或樹的盲目搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索第4章搜索策略4.2狀態(tài)空間的盲目搜索廣度優(yōu)先和深度優(yōu)先搜索代價樹搜索基本思想

從初始節(jié)點S0開始逐層向下擴展，在第n層節(jié)點還沒有全部搜索完之前，不進入第n+1層節(jié)點的搜索。Open表中的節(jié)點總是按進入的先后排序，先進入的節(jié)點排在前面，后進入的節(jié)點排在后面。搜索算法

(1)把初始節(jié)點S0放入Open表中；

(2)如果Open表為空，則問題無解，失敗退出；

(3)把Open表的第一個節(jié)點取出放入Closed表，并記該節(jié)點為n；

(4)考察節(jié)點n是否為目標節(jié)點。若是，則得到問題的解，成功退出；

(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；

(6)擴展節(jié)點n，將其子節(jié)點放入Open表的尾部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針，然后轉(zhuǎn)第(2)步。

4.2.2廣度優(yōu)先和深度優(yōu)先搜索1.廣度優(yōu)先搜索例4.5

八數(shù)碼難題。在3×3的方格棋盤上，分別放置了表有數(shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)S0，目標狀態(tài)Sg，如下圖所示?？梢允褂玫牟僮饔锌崭褡笠?，空格上移，空格右移，空格下移即只允許把位于空格左、上、右、下方的牌移入空格。要求應(yīng)用廣度優(yōu)先搜索策略尋找從初始狀態(tài)到目標狀態(tài)的解路徑。

831476512384765S0Sg2831476528314765231847652831476528316475

8321476528371465

2318476523184765281437652831457628316475283164758321476528371465832147658132476528374615283714651238476512378465123847652341876528143765283145762836417528316754S0123456789101112131415161718192021222324252627Sg算法描述

(1)把初始節(jié)點S0放入Open表中；

(2)如果Open表為空，則問題無解，失敗退出；

(3)把Open表的第一個節(jié)點取出放入Closed表，并記該節(jié)點為n；

(4)考察節(jié)點n是否為目標節(jié)點。若是，則得到問題的解，成功退出；

(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；

(6)擴展節(jié)點n，將其子節(jié)點放入Open表的首部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針，然后轉(zhuǎn)第(2)步。

4.2.2廣度優(yōu)先和深度優(yōu)先搜索2.深度優(yōu)先搜索基本思想

從初始節(jié)點S0開始，在其子節(jié)點中選擇一個最新生成的節(jié)點進行考察，如果該子節(jié)點不是目標節(jié)點且可以擴展，則擴展該子節(jié)點，然后再在此子節(jié)點的子節(jié)點中選擇一個最新生成的節(jié)點進行考察，依此向下搜索，直到某個子節(jié)點既不是目標節(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進行考察。2831476528314765231847652831476528316475283164752831647528316754283167542816375428163754S01

2

3

4

5

6八數(shù)碼難題的深度優(yōu)先搜索如右圖一種改進的深度優(yōu)先算法是有界深度優(yōu)先搜索算法，深度限制為dm例4.6

八數(shù)碼難題在代價樹中，可以用g(n)表示從初始節(jié)點S0到節(jié)點n的代價，用c(n1,n2)表示從父節(jié)點n1到其子節(jié)點n2的代價。這樣，對節(jié)點n2的代價有：g(n2)=g(n1)+c(n1,n2)。代價樹搜索的目的是為了找到最佳解，即找到一條代價最小的解路徑。

4.2.3代價樹搜索1.代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索算法：

(1)把初始節(jié)點S0放入Open表中，置S0的代價g(S0)=0；

(2)如果Open表為空，則問題無解，失敗退出；

(3)把Open表的第一個節(jié)點取出放入Closed表，并記該節(jié)點為n；

(4)考察節(jié)點n是否為目標。若是，則找到了問題的解，成功退出；

(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；

(6)擴展節(jié)點n，生成其子節(jié)點ni(i=1,2,…)，將這些子節(jié)點放入Open表中，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針。按如下公式：

g(ni)=g(n)+c(ni)i=1,2,...計算各子結(jié)點的代價，并根據(jù)各子結(jié)點的代價對Open表中的全部結(jié)點按由小到大的順序排序。然后轉(zhuǎn)第(2)步。例4.7

城市交通問題。設(shè)有5個城市，它們之間的交通線路如左圖所示，圖中的數(shù)字表示兩個城市之間的交通費用，即代價。用代價樹的廣度優(yōu)先搜索，求從A市出發(fā)到E市，費用最小的交通路線。

ABCDE434523245AC1B1D1D2E1E2B2C2E3E43434235城市交通圖城市交通圖的代價樹解：代價樹如右圖所示。其中，紅線為最優(yōu)解，其代價為84.2.3代價樹搜索2.代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索算法：

(1)把初始節(jié)點S0放入Open表中，置S0的代價g(S0)=0；

(2)如果Open表為空，則問題無解，失敗退出；

(3)把Open表的第一個節(jié)點取出放入Closed表，并記該節(jié)點為n；

(4)考察節(jié)點n是否為目標節(jié)點。若是，則找到了問題的解，成功退出；

(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；

(6)擴展節(jié)點n，生成其子節(jié)點ni(i=1,2,…)，將這些子節(jié)點按邊代價由小到大放入Open表的首部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針。然后轉(zhuǎn)第(2)步。搜索的基本概念狀態(tài)空間的盲目搜索狀態(tài)空間的啟發(fā)式搜索與/或樹的盲目搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索第4章搜索策略4.3狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價函數(shù)A算法A*算法A*算法應(yīng)用舉例啟發(fā)性信息的概念

啟發(fā)性信息是指那種與具體問題求解過程有關(guān)的，并可指導(dǎo)搜索過程朝著最有希望方向前進的控制信息。啟發(fā)性信息的種類①有效地幫助確定擴展節(jié)點的信息；②有效的幫助決定哪些后繼節(jié)點應(yīng)被生成的信息；③

能決定在擴展一個節(jié)點時哪些節(jié)點應(yīng)從搜索樹上刪除的信息。

啟發(fā)性信息的作用啟發(fā)信息的啟發(fā)能力越強，擴展的無用結(jié)點越少。4.3.1啟發(fā)性信息和估價函數(shù)1.啟發(fā)性信息估價函數(shù)用來估計節(jié)點重要性的函數(shù)。估價函數(shù)f(n)被定義為從初始節(jié)點S0出發(fā)，約束經(jīng)過節(jié)點n到達目標節(jié)點Sg的所有路徑中最小路徑代價的估計值。它的一般形式為：

f(n)=g(n)+h(n)其中，g(n)是從初始節(jié)點S0到節(jié)點n的實際代價；h(n)是從節(jié)點n到目標節(jié)點Sg的最優(yōu)路徑的估計代價。

4.3.1啟發(fā)性信息和估價函數(shù)2.估價函數(shù)例4.8

八數(shù)碼難題。設(shè)問題的初始狀態(tài)S0和目標狀態(tài)Sg如下圖所示，且估價函數(shù)為

f(n)=d(n)+W(n)其中：d(n)表示節(jié)點n在搜索樹中的深度

W(n)表示節(jié)點n中“不在位”的數(shù)碼個數(shù)。請計算初始狀態(tài)S0的估價函數(shù)值f(S0)解：取g(n)=d(n)，h(n)=W(n)。它說明是用從S0到n的路徑上的單位代價表示實際代價，用結(jié)點n中“不在位”的數(shù)碼個數(shù)作為啟發(fā)信息。一般來說，某節(jié)點中的“不在位”的數(shù)碼個數(shù)越多，說明它離目標節(jié)點越遠。對初始節(jié)點S0，由于d(S0)=0，W(S0)=3，因此有

f(S0)=0+3=32

831476512384765S0Sg概念：在圖搜索算法中，如果能在搜索的每一步都利用估價函數(shù)f(n)=g(n)+h(n)對Open表中的節(jié)點進行排序，則該搜索算法為A算法。

由于估價函數(shù)中帶有問題自身的啟發(fā)性信息，因此，A算法也被稱為啟發(fā)式搜索算法。類型：可根據(jù)搜索過程中選擇擴展節(jié)點的范圍，將啟發(fā)式搜索算法分為全局擇優(yōu)搜索算法和局部擇優(yōu)搜索算法。全局擇優(yōu)：從Open表的所有節(jié)點中選擇一個估價函數(shù)值最小的一個進行擴展。局部擇優(yōu)：僅從剛生成的子節(jié)點中選擇一個估價函數(shù)值最小的一個進行擴展。4.3.2A算法全局擇優(yōu)搜索A算法描述：

(1)把初始節(jié)點S0放入Open表中，f(S0)=g(S0)+h(S0)；

(2)如果Open表為空，則問題無解

，失敗退出；

(3)把Open表的第一個節(jié)點取出放入Closed表，并記該節(jié)點為n；

(4)考察節(jié)點n是否為目標節(jié)點。若是，則找到了問題的解，成功退出；

(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；

(6)擴展節(jié)點n，生成其子節(jié)點ni(i=1,2,…)，計算每一個子節(jié)點的估價值f(ni)(i=1,2,…)，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針，然后將這些子節(jié)點放入Open表中；

(7)根據(jù)各節(jié)點的估價函數(shù)值，對Open表中的全部節(jié)點按從小到大的順序重新進行排序；

(8)轉(zhuǎn)第(2)步。

4.3.2A算法例4.9

八數(shù)碼難題。設(shè)問題的初始狀態(tài)S0和目標狀態(tài)Sg如圖所示，估價函數(shù)與例4.8相同。請用全局擇優(yōu)搜索解決該問題。解：該問題的全局擇優(yōu)搜索樹如下圖所示。在該圖中，每個節(jié)點旁邊的數(shù)字是該節(jié)點的估價函數(shù)值。例如，對節(jié)點S2，其估價函數(shù)值的計算為：f(S2)=d(S2)+W(S2)=1+3=4

2831476512384765S0Sg2831476528314765231

847652831476528316475S0

8321476528371465

23184765231847651238476512378465123

847654455564644SgS1S2八數(shù)碼難題的全局擇優(yōu)搜索樹該問題的解為：

S0→S1→S2→S3→SgS36

4.3.3A*算法

A*算法是對A算法的估價函數(shù)f(n)=g(n)+h(n)加上某些限制后得到的一種啟發(fā)式搜索算法假設(shè)f*(n)是從初始節(jié)點出發(fā)，約束經(jīng)過節(jié)點n達到目標節(jié)點的最小代價，估價函數(shù)f(n)是對f*(n)的估計值。且

f*(n)=g*(n)+h*(n)A*算法對A算法（全局擇優(yōu)的啟發(fā)式搜索算法）中的g(n)和h(n)分別提出如下限制：第一，g(n)是對最小代價g*(n)的估計，且g(n)>0；第二，h(n)是最小代價h*(n)的下界，即對任意節(jié)點n均有h(n)≤h*(n)。即滿足上述兩條限制的A算法稱為A*算法。

4.3.3A*算法1.A*算法的可納性(1)可納性的含義：對任一狀態(tài)空間圖，當從初始節(jié)點到目標節(jié)點有路經(jīng)存在時，如果搜索算法總能在有限步驟內(nèi)找到一條從初始節(jié)點到目標節(jié)點的最佳路徑，并在此路徑上結(jié)束，則稱該搜索算法是可采納的。A*算法可納性的證明以下分三步（定理4.1、定理4.2、定理4.3，即引理）進行證明。定理4.1對有限圖，如果從初始節(jié)點S0到目標節(jié)點Sg有路徑存在，則算法A*一定成功結(jié)束。

證明：首先證明算法必然會結(jié)束。由于搜索圖為有限圖，如果算法能找到解，則成功結(jié)束；如果算法找不到解，則必然會由于Open表變空而結(jié)束。因此，A*算法必然會結(jié)束。然后證明算法一定會成功結(jié)束。由于至少存在一條有初始節(jié)點到目標節(jié)點的路徑，設(shè)此路徑為S0=n0,n1,…,nk=Sg算法開始時，節(jié)點n0在Open表中，而且路徑中任一節(jié)點ni離開Open表后，其后繼節(jié)點ni+1必然進入Open表，這樣，在Open表變?yōu)榭罩?，目標?jié)點必然出現(xiàn)在Open表中。因此，算法一定會成功結(jié)束。引理4.1

對無限圖，如果從初始節(jié)點S0到目標節(jié)點Sg有路徑存在，則算法A*算法不終止的話，則從Open表中選出的節(jié)點必將具有任意大的f值。證明：設(shè)d*(n)是A*生成的從初始節(jié)點S0到節(jié)點n的最短路經(jīng)長度，由于搜索圖中每條邊的代價都是一個正數(shù)，令這些正數(shù)中的最小的一個數(shù)是e，則有

g*(n)≥d*(n)×e因為g*(n)是最佳路徑的代價，故有

g(n)≥g*(n)≥d*(n)×e又因為h(n)≥0，故有

f(n)=g(n)+h(n)≥g(n)≥d*(n)×e

如果A*算法不終止的話，從Open表中選出的節(jié)點必將具有任意大的d*(n)值，因此，也將具有任意大的f值。

4.3.3A*算法1.A*算法的可納性(2)引理4.2

在A*算法終止前的任何時刻，Open表中總存在節(jié)點n’，它是從初始節(jié)點S0到目標節(jié)點的最佳路徑上的一個節(jié)點，且滿足f(n’)≤f*(S0)。

證明：設(shè)從初始節(jié)點S0到目標節(jié)點t的一條最佳路徑序列為

S0=n0,n1,…,nk=Sg算法開始時，節(jié)點S0在Open表中，當節(jié)點S0離開Open表進入Closed表時，節(jié)點n1進入Open表。因此，A*沒有結(jié)束以前，在Open表中必存在最佳路徑上的節(jié)點。設(shè)這些節(jié)點中排在最前面的節(jié)點為n'，則有

f(n')=g(n')+h(n')由于n'在最佳路徑上，故有g(shù)(n')=g*(n')，從而

f(n')=g*(n')+h(n')又由于A*算法滿足h(n')≤h*(n')，故有

f(n')≤g*(n')+h*(n')=f*(n')因為在最佳路徑上的所有節(jié)點的f*值都應(yīng)相等，因此有

f(n')≤f*(S0)4.3.3A*算法1.A*算法的可納性(3)定理4.2

對無限圖，若從初始節(jié)點S0到目標節(jié)點t有路徑存在，則A*算法必然會結(jié)束。證明：（反證法）假設(shè)A*不結(jié)束，由引理4.1知Open表中的節(jié)點有任意大的f值，這與引理4.2的結(jié)論相矛盾，因此，A*算法只能成功結(jié)束。推論4.1

Open表中任一具有f(n)<f*(S0)的節(jié)點n，最終都被A*算法選作為擴展的節(jié)點。

(證明略)

下面給出A*算法的可納性4.3.3A*算法1.A*算法的可納性(4)4.3.3A*算法1.A*算法的可納性(5)定理4.3

A*算法是可采納的，即若存在從初始節(jié)點S0到目標節(jié)點Sg的路徑，則A*算法必能結(jié)束在最佳路徑上。證明：證明過程分以下兩步進行：

先證明A*算法一定能夠終止在某個目標節(jié)點上。由定理4.1和定理4.2可知，無論是對有限圖還是無限圖，A*算法都能夠找到某個目標節(jié)點而結(jié)束。

再證明A*算法只能終止在最佳路徑上。（反證法）假設(shè)A*算法未能終止在最佳路徑上，而是終止在某個目標節(jié)點t處，則有

f(t)=g(t)>f*(S0)但由引理4.2可知，在A*算法結(jié)束前，必有最佳路徑上的一個節(jié)點n'在Open表中，且有

f(n’)≤f*(S0)<f(t)這時，A*算法一定會選擇n'來擴展，而不可能選擇t，從而也不會去測試目標節(jié)點t，這就與假設(shè)A*算法終止在目標節(jié)點t相矛盾。因此，A*算法只能終止在最佳路徑上。推論4.2

在A*算法中，對任何被擴展的節(jié)點n，都有f(n)≤f*(S0)。

證明：令n是由A*選作擴展的任一節(jié)點，因此n不會是目標節(jié)點，且搜索沒有結(jié)束。由引理4.2可知，在Open表中有滿足

f(n')≤f*(S0)的節(jié)點n'。若n=n'，則有f(n)≤f*(S0)；否則，選擇n擴展，必有

f(n)≤f(n')所以有

f(n)≤f*(S0)4.3.3A*算法1.A*算法的可納性(6)

A*算法的搜索效率很大程度上取決于估價函數(shù)h(n)。一般來說，在滿足h(n)≤h*(n)的前提下，h(n)的值越大越好。h(n)的值越大，說明它攜帶的啟發(fā)性信息越多，A*算法搜索時擴展的節(jié)點就越少，搜索效率就越高。下面通過一個定理來描述這一特性。定理4.4

設(shè)有兩個A*算法A1*和A2*，它們有

A1*:f1(n)=g1(n)+h1(n)A2*:f2(n)=g2(n)+h2(n)如果A2*比A1*有更多的啟發(fā)性信息，即對所有非目標節(jié)點均有

h2(n)>h1(n)則在搜索過程中，被A2*擴展的節(jié)點也必然被A1*擴展，即A1*擴展的節(jié)點不會比A2*擴展的節(jié)點少，亦即A2*擴展的節(jié)點集是A1*擴展的節(jié)點集的子集。

4.3.3A*算法2.A*算法的最優(yōu)性(1)

4.3.3A*算法2.A*算法的最優(yōu)性(2)證明：（用數(shù)學(xué)歸納法）

(1)

對深度d(n)=0的節(jié)點，即n為初始節(jié)點S0，如n為目標節(jié)點，則A1*和A2*都不擴展n；如果n不是目標節(jié)點，則A1*和A2*都要擴展n。

(2)假設(shè)對A2*中d(n)=k的任意節(jié)點n結(jié)論成立，即A1*也擴展了這些節(jié)點。

(3)證明A2*中d(n)=k+1的任意節(jié)點n，也要由A1*擴展。（用反證法）假設(shè)A2搜索樹上有一個滿足d(n)=k+1的節(jié)點n，A2*擴展了該節(jié)點，但A1*沒有擴展它。根據(jù)第(2)條的假設(shè)，知道A1*擴展了節(jié)點n的父節(jié)點。因此，n必定在A1*的Open表中。既然節(jié)點n沒有被A1*擴展，則有

f1(n)≥f*(S0)即g1(n)+h1(n)≥f*(S0)。但由于d=k時，A2*擴展的節(jié)點A1*也一定擴展，故有

g1(n)≤g2(n)因此有h1(n)≥f*(S0)-g2(n)

另一方面，由于A2*擴展了n，因此有

f2(n)≤f*(0)即g2(n)+h2(n)≤f*(S0)，亦即h2(n)≤f*(S0)-g2(n)，所以有h1(n)≥h2(n)

這與我們最初假設(shè)的h1(n)<h2(n)矛盾，因此反證法的假設(shè)不成立。在A*算法中，每當擴展一個節(jié)點n時，都需要檢查其子節(jié)點是否已在Open表或Closed表中。對已在Open表中的子節(jié)點，需要決定是否調(diào)整指向其父節(jié)點的指針；對已在Closed表中的子節(jié)點，除需要決定是否調(diào)整其指向父節(jié)點的指針外，還需要決定是否調(diào)整其子節(jié)點的后繼節(jié)點的父指針。如果能夠保證，每當擴展一個節(jié)點時就已經(jīng)找到了通往這個節(jié)點的最佳路徑，就沒有必要再去作上述檢查為滿足這一要求，我們需要對啟發(fā)函數(shù)h(n)增加單調(diào)性限制。定義4.1

如果啟發(fā)函數(shù)滿足以下兩個條件:(1)h(Sg)=0;(2)對任意節(jié)點ni及其任一子節(jié)點nj，都有

0≤h(ni)-h(nj)≤c(ni,nj)其中c(ni,nj)是ni到其子節(jié)點nj的邊代價，則稱h(n)滿足單調(diào)限制。4.3.3A*算法3.h(n)的單調(diào)限制(1)定理4.5

如果h滿足單調(diào)條件，則當A*算法擴展節(jié)點n時，該節(jié)點就已經(jīng)找到了通往它的最佳路徑，即g(n)=g*(n)。證明：設(shè)A*正要擴展節(jié)點n，而節(jié)點序列

S0=n0,n1,…,nk=n是由初始節(jié)點S0到節(jié)點n的最佳路徑。其中，ni是這個序列中最后一個位于Closed表中的節(jié)點，則上述節(jié)點序列中的ni+1節(jié)點必定在Open表中，則有

g*(ni)+h(ni)≤g*(ni)+c(ni,ni+1)+h(ni+1)由于節(jié)點ni和ni+1都在最佳路徑上，故有g(shù)*(ni+1)=g*(ni)+c(ni,ni+1)所以g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)一直推導(dǎo)下去可得g*(ni+1)+h(ni+1)≤g*(nk)+h(nk)由于節(jié)點ni+1在最佳路徑上，故有f(ni+1)≤g*(n)+h(n)因為這時A*擴展節(jié)點n而不擴展節(jié)點ni+1，則有

f(n)=g(n)+h(n)≤f(ni+1)≤g*(n)+h(n)即g(n)≤g*(n)但是g*(n)是最小代價值，應(yīng)當有

g(n)≥g*(n)所以有g(shù)(n)=g*(n)4.3.3A*算法3.h(n)的單調(diào)限制(2)定理4.6

如果h(n)滿足單調(diào)限制，則A*算法擴展的節(jié)點序列的f值是非遞減的，即f(ni)≤f(ni+1)。

證明：假設(shè)節(jié)點ni+1在節(jié)點ni之后立即擴展，由單調(diào)限制條件可知

h(ni)-h(ni+1)≤c(ni,ni+1)即f(ni)-g(ni)-f(ni+1)+g(ni+1)≤c(ni,ni+1)亦即f(ni)-g(ni)-f(ni+1)+g(ni)+c(ni,ni+1)≤c(ni,ni+1)所以f(ni)-f(ni+1)≤0即f(ni)≤f(ni+1)

以上兩個定理都是在h(n)滿足單調(diào)性限制的前提下才成立的。如果h(n)不滿足單調(diào)性限制，則它們不一定成立。在h(n)滿足單調(diào)性限制下的A*算法常被稱為改進的A*算法。4.3.3A*算法3.h(n)的單調(diào)限制(2)例4.10

八數(shù)碼難題。

2831476528314765231847652831476528316475

2318476523184765123847651237846512384765S0f=6g*=1h*=3f=6f=6

g*=2h*=2f=6f=4g*=3h*=1f=4g*=4h*=0f=4f=6Sg八數(shù)碼難題h(n)=P(n)的搜索樹f(n)=d(n)+P(n)d(n)深度P(n)與目標距離f*=g*+h*f=44.3.4A*算法應(yīng)用舉例h*=4f=4例4.11修道士和野人問題。解：用m表示左岸的修道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)，用三元組(m,c,b)表示問題的狀態(tài)。對A*算法，首先需要確定估價函數(shù)。設(shè)g(n)=d(n)，h(n)=m+c-2b，則有

f(n)=g(n)+h(n)=d(n)+m+c-2b其中，d(n)為節(jié)點的深度。通過分析可知h(n)≤h*(n)，滿足A*算法的限制條件。

M-C問題的搜索過程如下圖所示。4.3.4A*算法應(yīng)用舉例(3,3,1)h=4f=4(3,2,0)(3,1,0)(2,2,0)(3,2,1)(2,1,0)(3,0,0)(2,2,1)(3,1,1)(0,2,0)(1,1,0)(0,3,1)(0,1,0)(0,2,1)(0,0,0)h=5f=6h=3f=5h=3f=6h=3f=6h=2f=6h=2f=7h=1f=7h=1f=8h=0f=8傳教士和野人問題的搜索圖h(n)=m+c-2bh=4f=5h=4f=5h=2f=6h=2f=7本章要點搜索的基本概念狀態(tài)空間的盲目搜索狀態(tài)空間的啟發(fā)式搜索與/或樹的盲目搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索與/或樹的搜索過程實際上是一個不斷尋找解樹的過程。其一般搜索過程如下：

(1)把原始問題作為初始節(jié)點S0，并把它作為當前節(jié)點；

(2)應(yīng)用分解或等價變換操作對當前節(jié)點進行擴展；

(3)為每個子節(jié)點設(shè)置指向父節(jié)點的指針；

(4)選擇合適的子節(jié)點作為當前節(jié)點，反復(fù)執(zhí)行第(2)步和第(3)步，在此期間需要多次調(diào)用可解標記過程或不可解標記過程，直到初始節(jié)點被標記為可解節(jié)點或不可解節(jié)點為止。上述搜索過程將形成一顆與/或樹，這種由搜索過程所形成的與/或樹稱為搜索樹。

4.4.1與/或樹的一般搜索

與/或樹的廣度優(yōu)先搜索與狀態(tài)空間的廣度優(yōu)先搜索的主要差別是，需要在搜索過程中需要多次調(diào)用可解標識過程或不可解標識過程。其搜索算法如下：

(1)把初始節(jié)點S0放入Open表中；

(2)把Open表的第一個節(jié)點取出放入Closed表，并記該節(jié)點為n；

(3)如果節(jié)點n可擴展，則做下列工作：①擴展節(jié)點n，將其子節(jié)點放入Open表的尾部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針；4.4.1與/或樹的廣度優(yōu)先和深度優(yōu)先搜索1.廣度優(yōu)先搜索②考察這些子節(jié)點中有否終止節(jié)點。若有，則標記這些終止節(jié)點為可解節(jié)點，并用可解標記過程對其父節(jié)點及先輩節(jié)點中的可解解節(jié)點進行標記。如果初始解節(jié)點S0能夠被標記為可解節(jié)點，就得到了解樹，搜索成功，退出搜索過程；如果不能確定S0為可解節(jié)點，則從Open表中刪去具有可解先輩的節(jié)點。③轉(zhuǎn)第(2)步。

(4)如果節(jié)點n不可擴展，則作下列工作：①標記節(jié)點n為不可解節(jié)點；②應(yīng)用不可解標記過程對節(jié)點n的先輩中不可解解的節(jié)點進行標記。如果初始解節(jié)點S0也被標記為不可解節(jié)點，則搜索失敗，表明原始問題無解，退出搜索過程；如果不能確定S0為不可解節(jié)點，則從Open表中刪去具有不可解先輩的節(jié)點。

③轉(zhuǎn)第(2)步。例4.13設(shè)有下圖所示的與/或樹，節(jié)點按標注順序進行擴展，其中表有t1、t2、t3的節(jié)點是終止節(jié)點，A、B、C為不可解的端節(jié)點。

123A4t15

t2Bt3C與/或樹的廣度優(yōu)先搜索搜索過程為：

(1)先擴展1號節(jié)點，生成2號節(jié)點和3號節(jié)點。

(2)擴展2號節(jié)點，生成A節(jié)點和4號節(jié)點。

(3)擴展3號節(jié)點，生成t1節(jié)點和5號節(jié)點。由于t1為終止節(jié)點，則標記它為可解節(jié)點，并應(yīng)用可解標記過程，不能確定3號節(jié)點是否可節(jié)。

(6)擴展5號節(jié)點，生成t3節(jié)點和C節(jié)點。由于t3為終止節(jié)點，則標記它為可解節(jié)點，并應(yīng)用可解標記過程，可標記1號節(jié)點為可解節(jié)點。

(7)搜索成功，得到由1、2、3、4、5號節(jié)點即t1、t2、t3節(jié)點構(gòu)成的解樹。

(4)擴展節(jié)點A，由于A是端節(jié)點，因此不可擴展。調(diào)用不可解標記過程…。

(5)擴展4號節(jié)點，生成t2節(jié)點和B節(jié)點。由于t2為終止節(jié)點，則標記它為可解節(jié)點，并應(yīng)用可解標記過程，可標記2號節(jié)點為可解，但不能標記1號節(jié)點為可解。

與/或樹的深度優(yōu)先搜索和與/或樹的廣度優(yōu)先搜索過程基本相同，其主要區(qū)別在于Open表中節(jié)點的排列順序不同。在擴展節(jié)點時，與/或樹的深度優(yōu)先搜索過程總是把剛生成的節(jié)點放在Open表的首部。與/或樹的深度優(yōu)先搜索也可以帶有深度限制dm，其搜索算法如下：

(1)把初始節(jié)點S0放入Open表中；

(2)把Open表第一個節(jié)點取出放入Closed表，并記該節(jié)點為n；

(3)如果節(jié)點n的深度等于dm，則轉(zhuǎn)第(5)步的第①點；

(4)如果節(jié)點n可擴展，則做下列工作：①擴展節(jié)點n，將其子節(jié)點放入Open表的首部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針；4.4.1與/或樹的廣度優(yōu)先和深度優(yōu)先搜索2.深度優(yōu)先搜索②考察這些子節(jié)點中是否有終止節(jié)點。若有，則標記這些終止節(jié)點為可解節(jié)點，并用可解標記過程對其父節(jié)點及先輩節(jié)點中的可解解節(jié)點進行標記。如果初始解節(jié)點S0能夠被標記為可解節(jié)點，就得到了解樹，搜索成功，退出搜索過程；如果不能確定S0為可解節(jié)點，則從Open表中刪去具有可解先輩的節(jié)點。③轉(zhuǎn)第(2)步。

(5)如果節(jié)點n不可擴展，則作下列工作：①標記節(jié)點n為不可解節(jié)點；②應(yīng)用不可解標記過程對節(jié)點n的先輩中不可解解的節(jié)點進行標記。如果初始解節(jié)點S0也被標記為不可解節(jié)點，則搜索失敗，表明原始問題無解，退出搜索過程；如果不能確定S0為不可解節(jié)點，則從Open表中刪去具有不可解先輩的節(jié)點。③轉(zhuǎn)第(2)步。對上例，若按有界深度優(yōu)先，且設(shè)dm=4，則其節(jié)點擴展順序為：1，3，5，2，4。

123A4t15

t2Bt3C與/或樹的有界深度優(yōu)先搜索搜索過程為：

(1)先擴展1號節(jié)點，生成2號節(jié)點和3號節(jié)點。

(2)擴展3號節(jié)點，生成t1節(jié)點和5號節(jié)點。由于t1為終止節(jié)點，則標記它為可解節(jié)點，并應(yīng)用可解標記過程，不能確定3號節(jié)點是否可解。

(6)搜索成功，得到由1、3、5、2、4號節(jié)點即t1、t2、t3節(jié)點構(gòu)成的解樹。

(4)擴展2號節(jié)點，生成A節(jié)點和4號節(jié)點。

(5)擴展4號節(jié)點，生成t2節(jié)點和B節(jié)點。由于t2為終止節(jié)點，則標記它為可解節(jié)點，并應(yīng)用可解標記過程，可標記2號節(jié)點為可解，再往上又可標記1號節(jié)點為可解。

(3)擴展5號節(jié)點，生成t3節(jié)點和C節(jié)點。由于t3為終止節(jié)點，則標記它為可解節(jié)點，并應(yīng)用可解標記過程，可標記3號節(jié)點為可解節(jié)點，但不能標記1號為可解。本章要點搜索的基本概念狀態(tài)空間的盲目搜索狀態(tài)空間的啟發(fā)式搜索與/或樹的盲目搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索與/或樹的啟發(fā)式搜索過程實際上是一種利用搜索過程所得到的啟發(fā)性信息尋找最優(yōu)解樹的過程。算法的每一步都試圖找到一個最有希望成為最優(yōu)解樹的子樹。最優(yōu)解樹是指代價最小的那棵解樹。它涉及到解樹的代價與希望樹。4.5與/或樹的啟發(fā)式搜索解樹的代價可按如下規(guī)則計算：

(1)若n為終止節(jié)點，則其代價b(n)=0；

(2)若n為或節(jié)點，且子節(jié)點為n1,n2,…,nk，則n的代價為：其中，c(n,ni)是節(jié)點n到其子節(jié)點ni的邊代價。

(3)若n為與節(jié)點，且子節(jié)點為n1,n2,…,nk，則n的代價可用和代價法或最大代價法。若用和代價法，則其計算公式為：若用最大代價法，則其計算公式為：

(4)若n是端節(jié)點，但又不是終止節(jié)點，則n不可擴展，其代價定義為h(n)=∝。

(5)根節(jié)點的代價即為解樹的代價。4.4.1解樹的代價與希望樹1.解樹的代價4635例4.13

設(shè)下圖是一棵與/或樹，它包括兩可解樹，左邊的解樹由S0、A、t1、C及t2組成；右邊的解樹由S0、B、t2、D及t4組成。在此與或樹中，t1、t2、t3、t4為終止節(jié)點；E、F是端節(jié)點；邊上的數(shù)字是該邊的代價。請計算解樹的代價。解：先計算左邊的解樹按和代價：h(S0)=2+4+6+2=14按最大代價：h(S0)=(2+6)+2=10再計算右邊的解樹按和代價：h(S0)=1+5+3+2=11按最大代價：h(S0)=(1+5)+2=8

S022ABt1Ct2D21t3Et4F

與/或樹的代價希望樹是指搜索過程中最有可能成為最優(yōu)解樹的那棵樹。

與/或樹的啟發(fā)式搜索過程就是不斷地選擇、修正希望樹的過程，在該過程中，希望樹是不斷變化的。定義4.2

希望解樹

(1)初始節(jié)點S0在希望樹T(2)如果n是具有子節(jié)點n1,n2,…,nk的或節(jié)點，則n的某個子節(jié)點ni在希望樹T中的充分必要條件是

(3)如果n是與節(jié)點，則n的全部子節(jié)點都在希望樹T中。

4.4.1解樹的代價與希望樹2.希望樹與/或樹的啟發(fā)式搜索過程如下：

(1)把初始節(jié)點S0放入Open表中，計算h(S0)；

(2)計算希望樹T；

(3)依次在Open表中取出T的端節(jié)點放入Closed表，并記該節(jié)點為n；

(4)如果節(jié)點n為終止節(jié)點，則做下列工作：①標記節(jié)點n為可解節(jié)點；②在T上應(yīng)用可解標記過程，對n的先輩節(jié)點中的所有可解解節(jié)點進行標記；

③如果初始解節(jié)點S0能夠被標記為可