搜索是人工智能中的一個(gè)基本問(wèn)題 課件

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

搜索的基本概念狀態(tài)空間的盲目搜索狀態(tài)空間的啟發(fā)式搜索與/或樹(shù)的盲目搜索與/或樹(shù)的啟發(fā)式搜索博弈樹(shù)的啟發(fā)式搜索第4章搜索策略1搜索是人工智能中的一個(gè)基本問(wèn)題，并與推理密切相關(guān)，搜索策4.1搜索的基本概念4.1.1搜索的含義4.1.2狀態(tài)空間法4.1.3問(wèn)題歸約法24.1搜索的基本概念4.1.1搜索的含義24.1.1搜索的含義適用情況：

不良結(jié)構(gòu)或非結(jié)構(gòu)化問(wèn)題；難以獲得求解所需的全部信息；更沒(méi)有現(xiàn)成的算法可供求解使用。概念：

依靠經(jīng)驗(yàn)，利用已有知識(shí)，根據(jù)問(wèn)題的實(shí)際情況，不斷尋找可利用知識(shí)，從而構(gòu)造一條代價(jià)最小的推理路線，使問(wèn)題得以解決的過(guò)程稱為搜索搜索的類型按是否使用啟發(fā)式信息：盲目搜索：按預(yù)定的控制策略進(jìn)行搜索，在搜索過(guò)程中獲得的中間信息并不改變控制策略。啟發(fā)式搜索：在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息，用于指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。按問(wèn)題的表示方式：狀態(tài)空間搜索：用狀態(tài)空間法來(lái)求解問(wèn)題所進(jìn)行的搜索與或樹(shù)搜索：用問(wèn)題歸約法來(lái)求解問(wèn)題時(shí)所進(jìn)行的搜索34.1.1搜索的含義適用情況：搜索的類型34.1.2狀態(tài)空間法1.狀態(tài)空間表示方法狀態(tài)(State)：是表示問(wèn)題求解過(guò)程中每一步問(wèn)題狀況的數(shù)據(jù)結(jié)構(gòu)，它可形式地表示為：Sk={Sk0,Sk1,…}當(dāng)對(duì)每一個(gè)分量都給以確定的值時(shí)，就得到了一個(gè)具體的狀態(tài)。操作(Operator)也稱為算符，它是把問(wèn)題從一種狀態(tài)變換為另一種狀態(tài)的手段。。操作可以是一個(gè)機(jī)械步驟，一個(gè)運(yùn)算，一條規(guī)則或一個(gè)過(guò)程。操作可理解為狀態(tài)集合上的一個(gè)函數(shù)，它描述了狀態(tài)之間的關(guān)系。狀態(tài)空間(Statespace)用來(lái)描述一個(gè)問(wèn)題的全部狀態(tài)以及這些狀態(tài)之間的相互關(guān)系。常用一個(gè)三元組表示為：(S,F,G)其中，S為問(wèn)題的所有初始狀態(tài)的集合；F為操作的集合；G為目標(biāo)狀態(tài)的集合。狀態(tài)空間也可用一個(gè)賦值的有向圖來(lái)表示，該有向圖稱為狀態(tài)空間圖。在狀態(tài)空間圖中，節(jié)點(diǎn)表示問(wèn)題的狀態(tài)，有向邊表示操作。44.1.2狀態(tài)空間法狀態(tài)(State)：4狀態(tài)空間法求解問(wèn)題的基本過(guò)程：首先為問(wèn)題選擇適當(dāng)?shù)摹盃顟B(tài)”及“操作”的形式化描述方法；然后從某個(gè)初始狀態(tài)出發(fā)，每次使用一個(gè)“操作”，遞增地建立起操作序列，直到達(dá)到目標(biāo)狀態(tài)為止；此時(shí)，由初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是該問(wèn)題的一個(gè)解。

4.1.2狀態(tài)空間法2.狀態(tài)空間問(wèn)題求解5狀態(tài)空間法求解問(wèn)題的基本過(guò)程：4.1.2狀態(tài)空間法5例4.1二階梵塔問(wèn)題。設(shè)有三根鋼針，它們的編號(hào)分別是1號(hào)、2號(hào)和3號(hào)。在初始情況下，1號(hào)鋼針上穿有A、B兩個(gè)金片，A比B小，A位于B的上面。要求把這兩個(gè)金片全部移到另一根鋼針上，而且規(guī)定每次只能移動(dòng)一個(gè)金片，任何時(shí)刻都不能使大的位于小的上面。解：設(shè)用Sk=(Sk0,Sk1)表示問(wèn)題的狀態(tài)，其中，Sk0表示金片A所在的鋼針號(hào)，Sk1表示金片B所在的鋼針號(hào)。全部可能的問(wèn)題狀態(tài)共有以下9種：S0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)4.1.2狀態(tài)空間法3.狀態(tài)空間的例子(1/11)6例4.1二階梵塔問(wèn)題。設(shè)有三根鋼針，它們的編號(hào)分

ABABAB123123123二階梵塔問(wèn)題的初始狀態(tài)和目標(biāo)狀態(tài)問(wèn)題的初始狀態(tài)集合為S={S0}目標(biāo)狀態(tài)集合為G={S4,S5}

初始狀態(tài)S0和目標(biāo)狀態(tài)S4、S8如圖所示S0=(1,1)S4=(2,2)S8=(3,3)4.1.2狀態(tài)空間法3.狀態(tài)空間的例子(2/11)7

AAA1231操作分別用A(i,j)和B(i,j)表示A(i,j)表示把金片A從第i號(hào)鋼針移到j(luò)號(hào)鋼針上；B(i,j)表示把金片B從第i號(hào)鋼針一到第j號(hào)鋼針上。共有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)根據(jù)上述9種可能的狀態(tài)和12種操作，可構(gòu)成二階梵塔問(wèn)題的狀態(tài)空間圖，如下圖所示。4.1.2狀態(tài)空間法3.狀態(tài)空間的例子(3/11)8操作分別用A(i,j)和B(i,j)表示4.1(3,3)(1,3)(1,2)(2,2)二階梵塔的狀態(tài)空間圖從初始節(jié)點(diǎn)(1,1)到目標(biāo)節(jié)點(diǎn)(2,2)及(3,3)的任何一條路徑都是問(wèn)題的一個(gè)解。其中，最短的路徑長(zhǎng)度是3，它由3個(gè)操作組成。例如，從(1,1)開(kāi)始，通過(guò)使用操作A(1,3)、B(1,2)及A(3,2)，可到達(dá)(3,3)。A(1,2)B(1,3)A(2,3)(1,1)(3,1)(3,2)(2,1)(2,3)A(1,3)B(1,2)A(3,2)9(3,3)(例4.2修道士(Missionaries)和野人(Cannibals)問(wèn)題(簡(jiǎn)稱M-C問(wèn)題)。

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

4.1.2狀態(tài)空間法3.狀態(tài)空間的例子(5/11)10例4.2修道士(Missionaries)和野人(解：首先選取描述問(wèn)題狀態(tài)的方法。在這個(gè)問(wèn)題中，需要考慮兩岸的修道士人數(shù)和野人數(shù)，還需要考慮船在左岸還是在右岸。從而可用一個(gè)三元組來(lái)表示狀態(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)空間的例子(6/11)11解：首先選取描述問(wèn)題狀態(tài)的方法。在這個(gè)問(wèn)題中，需

這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)，還需要考慮可進(jìn)行的操作。

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

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

12這32種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士操作的表示：

用符號(hào)Pij表示從左岸到右岸的運(yùn)人操作用符號(hào)Qij表示從右岸到左岸的操作其中：i表示船上的修道士人數(shù)j表示船上的野人數(shù)操作集本問(wèn)題有10種操作可供選擇：F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20}下面以P01和Q01為例來(lái)說(shuō)明這些操作的條件和動(dòng)作。操作符號(hào)條件動(dòng)作P01b=1,m=0或3,c≥1b=0,c=c-1Q01b=0,m=0或3，c≤2b=1,c=c+1

13操作的表示：13abc

例4.3猴子摘香蕉問(wèn)題。在討論謂詞邏輯知識(shí)表示時(shí)，我們?cè)岬竭^(guò)這一問(wèn)題，現(xiàn)在用狀態(tài)空間法來(lái)解決這一問(wèn)題。

解：?jiǎn)栴}的狀態(tài)可用4元組（w,x,y,z）表示。其中：w表示猴子的水平位置；x表示箱子的水平位置；y表示猴子是否在箱子上，當(dāng)猴子在箱子上時(shí)，y取1，否則y取0；z表示猴子是否拿到香蕉，當(dāng)拿到香蕉時(shí)z取1，否則z取0。4.1.2狀態(tài)空間法3.狀態(tài)空間的例子(9/11)14abc例4.3猴子摘香蕉問(wèn)題。在討論謂詞邏輯知識(shí)表所有可能的狀態(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)目標(biāo)狀態(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)這個(gè)問(wèn)題的狀態(tài)空間圖如下圖所示。不難看出，由初始狀態(tài)變?yōu)槟繕?biāo)狀態(tài)的操作序列為：{Goto(b),Pushbox(c),Climbbox,Grasp}15所有可能的狀態(tài)為15猴子摘香蕉問(wèn)題的解(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目標(biāo)狀態(tài)猴子摘香蕉問(wèn)題的狀態(tài)空間圖解序列為：{Goto(b),Pushbox(c),Climbbox,Grasp}Pushbox(c)ClimbboxClimbboxPushbox(c)Pushbox(a)Pushbox(a)16猴子摘香蕉問(wèn)題的解(a,b,0,0)(b,b,0,0)(c,基本思想當(dāng)一問(wèn)題較復(fù)雜時(shí)，可通過(guò)分解或變換，將其轉(zhuǎn)化為一系列較簡(jiǎn)單的子問(wèn)題，然后通過(guò)對(duì)這些子問(wèn)題的求解來(lái)實(shí)現(xiàn)對(duì)原問(wèn)題的求解。

分解如果一個(gè)問(wèn)題P可以歸約為一組子問(wèn)題P1,P2,…,Pn，并且只有當(dāng)所有子問(wèn)題Pi都有解時(shí)原問(wèn)題P才有解，任何一個(gè)子問(wèn)題Pi無(wú)解都會(huì)導(dǎo)致原問(wèn)題P無(wú)解，則稱此種歸約為問(wèn)題的分解。即分解所得到的子問(wèn)題的“與”與原問(wèn)題P等價(jià)。等價(jià)變換如果一個(gè)問(wèn)題P可以歸約為一組子問(wèn)題P1,P2,…,Pn，并且子問(wèn)題Pi中只要有一個(gè)有解則原問(wèn)題P就有解，只有當(dāng)所有子問(wèn)題Pi都無(wú)解時(shí)原問(wèn)題P才無(wú)解，稱此種歸約為問(wèn)題的等價(jià)變換，簡(jiǎn)稱變換。即變換所得到的子問(wèn)題的“或”與原問(wèn)題P等價(jià)。4.1.3問(wèn)題歸約法1.問(wèn)題的分解與等價(jià)變換17基本思想分解4.1.3問(wèn)題歸約法17PP1P2P3

與樹(shù)P1P2P3

或樹(shù)PPP1P2P3P12P12P31P32P33

與/或樹(shù)(1)與樹(shù)分解(2)或樹(shù)等價(jià)變換(3)與/或樹(shù)4.1.3問(wèn)題歸約法2.問(wèn)題的與/或樹(shù)表示18PP1P2P3P1(4)端節(jié)點(diǎn)與終止節(jié)點(diǎn)在與/或樹(shù)中，沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為端節(jié)點(diǎn)；本原問(wèn)題所對(duì)應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn)?？梢?jiàn)，終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)卻不一定是終止節(jié)點(diǎn)。(5)可解節(jié)點(diǎn)與不可解節(jié)點(diǎn)在與/或樹(shù)中，滿足以下三個(gè)條件之一的節(jié)點(diǎn)為可解節(jié)點(diǎn)：

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

②對(duì)“或”節(jié)點(diǎn)，當(dāng)其子節(jié)點(diǎn)中至少有一個(gè)為可解節(jié)點(diǎn)時(shí)，則該或節(jié)點(diǎn)就是可解節(jié)點(diǎn)。

③對(duì)“與”節(jié)點(diǎn)，只有當(dāng)其子節(jié)點(diǎn)全部為可解節(jié)點(diǎn)時(shí)，該與節(jié)點(diǎn)才是可解節(jié)點(diǎn)。同樣，可用類似的方法定義不可解節(jié)點(diǎn)：

①不為終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)。②對(duì)“或”節(jié)點(diǎn)，若其全部子節(jié)點(diǎn)都為不可解節(jié)點(diǎn)，則該或節(jié)點(diǎn)是不可解節(jié)點(diǎn)。③對(duì)“與”節(jié)點(diǎn)，只要其子節(jié)點(diǎn)中有一個(gè)為不可解節(jié)點(diǎn)，則該與節(jié)點(diǎn)是不可解節(jié)點(diǎn)。19(4)端節(jié)點(diǎn)與終止節(jié)點(diǎn)(5)可解節(jié)點(diǎn)與不可解節(jié)點(diǎn)19Pttt

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

例如，右圖給出的與或樹(shù)中，用紅線表示的子樹(shù)是一個(gè)解樹(shù)。在該圖中，節(jié)點(diǎn)P為原始問(wèn)題節(jié)點(diǎn)，用t標(biāo)出的節(jié)點(diǎn)是終止節(jié)點(diǎn)。根據(jù)可解節(jié)點(diǎn)的定義，很容易推出原始問(wèn)題P為可解節(jié)點(diǎn)。問(wèn)題歸約求解過(guò)程就實(shí)際上就是生成解樹(shù)，即證明原始節(jié)點(diǎn)是可解節(jié)點(diǎn)的過(guò)程。這一過(guò)程涉及到搜索的問(wèn)題，對(duì)于與/或樹(shù)的搜索將在后面詳細(xì)討論。20Ptt例4.4三階梵塔問(wèn)題。要求把1號(hào)鋼針上的3個(gè)金片全部移到3號(hào)鋼針上，如下圖所示。

解：這個(gè)問(wèn)題也可用狀態(tài)空間法來(lái)解，不過(guò)本例主要用它來(lái)說(shuō)明如何用歸約法來(lái)解決問(wèn)題。為了能夠解決這一問(wèn)題，首先需要定義該問(wèn)題的形式化表示方法。設(shè)用三元組(i,j,k)表示問(wèn)題在任一時(shí)刻的狀態(tài)，用“→”表示狀態(tài)的轉(zhuǎn)換。上述三元組中i代表金片C所在的鋼針號(hào)j代表金片B所在的鋼針號(hào)k代表金片A所在的鋼針號(hào)1231234.1.3問(wèn)題歸約法2.問(wèn)題的與/或樹(shù)表示ABCABC21例4.4三階梵塔問(wèn)題。要求把1號(hào)鋼針上的3利用問(wèn)題歸約方法，原問(wèn)題可分解為以下三個(gè)子問(wèn)題：(1)把金片A及B移到2號(hào)鋼針上的雙金片移動(dòng)問(wèn)題。即(1,1,1)→(1,2,2)(2)把金片C移到3號(hào)鋼針上的單金片移動(dòng)問(wèn)題。即(1,2,2)→(3,2,2)(3)把金片A及B移到3號(hào)鋼針的雙金片移動(dòng)問(wèn)題。即(3,2,2)→((3,3,3)其中，子問(wèn)題(1)和(3)都是一個(gè)二階梵塔問(wèn)題，它們都還可以再繼續(xù)進(jìn)行分解；子問(wèn)題(2)是本原問(wèn)題，它已不需要再分解。三階梵塔問(wèn)題的分解過(guò)程可用如下圖與/或樹(shù)來(lái)表示

(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)

在該與/或樹(shù)中，有7個(gè)終止節(jié)點(diǎn)，它們分別對(duì)應(yīng)著7個(gè)本原問(wèn)題。如果把這些本原問(wèn)題從左至右排列起來(lái)，即得到了原始問(wèn)題的解：(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)

22利用問(wèn)題歸約方法，原問(wèn)題可分解為以下三個(gè)子問(wèn)題：在該搜索的基本概念

狀態(tài)空間的盲目搜索狀態(tài)空間的啟發(fā)式搜索與/或樹(shù)的盲目搜索與/或樹(shù)的啟發(fā)式搜索博弈樹(shù)的啟發(fā)式搜索第4章搜索策略23搜索的基本概念第4章搜索策略234.2狀態(tài)空間的盲目搜索4.2.1一般圖搜索過(guò)程4.2.2廣度優(yōu)先和深度優(yōu)先搜索4.2.3代價(jià)樹(shù)搜索244.2狀態(tài)空間的盲目搜索4.2.1一般圖搜索過(guò)程24狀態(tài)空間搜索的基本思想先把問(wèn)題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對(duì)其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)，然后檢查問(wèn)題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。若出現(xiàn)，則搜索成功，找到了問(wèn)題的解；若沒(méi)出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)。重復(fù)上述過(guò)程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒(méi)有可供操作的節(jié)點(diǎn)為止。所謂對(duì)一個(gè)節(jié)點(diǎn)進(jìn)行“擴(kuò)展”是指對(duì)該節(jié)點(diǎn)用某個(gè)可用操作進(jìn)行作用，生成該節(jié)點(diǎn)的一組子節(jié)點(diǎn)。

4.2.1一般圖搜索過(guò)程算法的數(shù)據(jù)結(jié)構(gòu)和符號(hào)約定Open表：用于存放剛生成的節(jié)點(diǎn)Closed表：用于存放已經(jīng)擴(kuò)展或?qū)⒁獢U(kuò)展的節(jié)點(diǎn)S0：用表示問(wèn)題的初始狀態(tài)G：表示搜索過(guò)程所得到的搜索圖M：表示當(dāng)前擴(kuò)展節(jié)點(diǎn)新生成的且不為自己先輩的子節(jié)點(diǎn)集。25狀態(tài)空間搜索的基本思想4.2.1一般圖搜索過(guò)程算法的數(shù)據(jù)一般圖搜索過(guò)程(1)把初始節(jié)點(diǎn)S0放入Open表，并建立目前僅包含S0的圖G；(2)檢查Open表是否為空，若為空，則問(wèn)題無(wú)解，失敗推出；(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n；(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問(wèn)題的解，成功退出；(5)擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把這些子節(jié)點(diǎn)中不是節(jié)點(diǎn)n先輩的那部分子節(jié)點(diǎn)記入集合M，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)加入G中

(6)針對(duì)M中子節(jié)點(diǎn)的不同情況，分別作如下處理：①對(duì)那些沒(méi)有在G中出現(xiàn)過(guò)的M成員設(shè)置一個(gè)指向其父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，并把它放入Open表。（新生成的）②對(duì)那些原來(lái)已在G中出現(xiàn)過(guò)，但還沒(méi)有被擴(kuò)展的M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針。（原生成但未擴(kuò)展的）③對(duì)于那些先前已在G中出現(xiàn)過(guò)，并已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。（原生成也擴(kuò)展過(guò)的）(7)按某種策略對(duì)Open表中的節(jié)點(diǎn)進(jìn)行排序。(8)轉(zhuǎn)第(2)步。

26一般圖搜索過(guò)程26算法的幾點(diǎn)說(shuō)明：(1)上述過(guò)程是狀態(tài)空間的一般圖搜索算法，它具有通用性，后面所要討論的各種狀態(tài)空間搜索策略都是上述過(guò)程的一個(gè)特例。各種搜索策略的主要區(qū)別在于對(duì)Open表中節(jié)點(diǎn)的排列順序不同。例如，廣度優(yōu)先搜索把先生成的子節(jié)點(diǎn)排在前面，而深度優(yōu)先搜索則把后生成的子節(jié)點(diǎn)排在前面。(2)在第(5)步對(duì)節(jié)點(diǎn)n擴(kuò)展后，生成并記入M的子節(jié)點(diǎn)有以下三種情況：①該子節(jié)點(diǎn)來(lái)從未被任何節(jié)點(diǎn)生成過(guò)，由n第一次生成；②該子節(jié)點(diǎn)原來(lái)被其他節(jié)點(diǎn)生成過(guò)，但還沒(méi)有被擴(kuò)展，這一次又被n再次生成；③該子節(jié)點(diǎn)原來(lái)被其他節(jié)點(diǎn)生成過(guò)，并且已經(jīng)被擴(kuò)展過(guò)，這一次又被n再次生成。以上三種情況是對(duì)一般圖搜索算法而言的。對(duì)于盲目搜索，由于其狀態(tài)空間是樹(shù)狀結(jié)構(gòu)，因此不會(huì)出現(xiàn)后兩種情況，每個(gè)節(jié)點(diǎn)經(jīng)擴(kuò)展后生成的子節(jié)點(diǎn)都是第一次出現(xiàn)的節(jié)點(diǎn)，不必檢查并修改指向父節(jié)點(diǎn)的指針。27算法的幾點(diǎn)說(shuō)明：27

(3)在第(6)步針對(duì)M中子節(jié)點(diǎn)的不同情況進(jìn)行處理時(shí)，如果發(fā)生當(dāng)?shù)冖诜N情況，那么，這個(gè)M中的節(jié)點(diǎn)究竟應(yīng)該作為哪一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)呢？一般是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所付出的代價(jià)來(lái)決定的，哪一條路經(jīng)付出的代價(jià)小，相應(yīng)的節(jié)點(diǎn)就作為它的父節(jié)點(diǎn)。所謂由原始節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上的代價(jià)是指這條路經(jīng)上的所有有向邊的代價(jià)之和。如果發(fā)生第③種情況，除了需要確定該子節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針外，還需要確定其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。其依據(jù)也是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑上的代價(jià)。

(4)在搜索圖中，除初始節(jié)點(diǎn)外，任意一個(gè)節(jié)點(diǎn)都含有且只含有一個(gè)指向其父節(jié)點(diǎn)的指針。因此，由所有節(jié)點(diǎn)及其指向父節(jié)點(diǎn)的指針?biāo)鶚?gòu)成的集合是一棵樹(shù)，稱為搜索樹(shù)。(5)在搜索過(guò)程的第(4)步，一旦某個(gè)被考察的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則搜索過(guò)程成功結(jié)束。由初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)路徑上的所有操作就構(gòu)成了該問(wèn)題的解，而路徑由第(6)步所形成的指向父節(jié)點(diǎn)的指針來(lái)確定。(6)如果搜索過(guò)程終止在第(2)步，即沒(méi)有達(dá)到目標(biāo)，且Open表中已無(wú)可供擴(kuò)展的節(jié)點(diǎn)，則失敗結(jié)束。

28(3)在第(6)步針對(duì)M中子節(jié)點(diǎn)的不同情況進(jìn)行處理時(shí)，基本思想

從初始節(jié)點(diǎn)S0開(kāi)始逐層向下擴(kuò)展，在第n層節(jié)點(diǎn)還沒(méi)有全部搜索完之前，不進(jìn)入第n+1層節(jié)點(diǎn)的搜索。Open表中的節(jié)點(diǎn)總是按進(jìn)入的先后排序，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面。搜索算法(1)把初始節(jié)點(diǎn)S0放入Open表中；(2)如果Open表為空，則問(wèn)題無(wú)解，失敗退出；(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n；(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問(wèn)題的解，成功退出；(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第(2)步；(6)擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的尾部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第(2)步。

4.2.2廣度優(yōu)先和深度優(yōu)先搜索1.廣度優(yōu)先搜索29基本思想4.2.2廣度優(yōu)先和深度優(yōu)先搜索29例4.5

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

831476512384765S0Sg30例4.5八數(shù)碼難題。在3×3的方格棋盤上，分別放283147652831476523184765283147652831647583214765283714652318476523184765281437652831457628316475283164758321476528371465832147658132476528374615283714651238476512378465123847652341876528143765283145762836417528316754S0123456789101112131415161718192021222324252627Sg31283283232算法描述(1)把初始節(jié)點(diǎn)S0放入Open表中；(2)如果Open表為空，則問(wèn)題無(wú)解，失敗退出；(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n；(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問(wèn)題的解，成功退出；(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第(2)步；(6)擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的首部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第(2)步。

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

從初始節(jié)點(diǎn)S0開(kāi)始，在其子節(jié)點(diǎn)中選擇一個(gè)最新生成的節(jié)點(diǎn)進(jìn)行考察，如果該子節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)且可以擴(kuò)展，則擴(kuò)展該子節(jié)點(diǎn)，然后再在此子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個(gè)最新生成的節(jié)點(diǎn)進(jìn)行考察，依此向下搜索，直到某個(gè)子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)，又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察。32算法描述4.2.2廣度優(yōu)先和深度優(yōu)先搜索基本思想322831476528314765231847652831476528316475283164752831647528316754283167542816375428163754S0123456八數(shù)碼難題的深度優(yōu)先搜索如右圖一種改進(jìn)的深度優(yōu)先算法是有界深度優(yōu)先搜索算法，深度限制為dm例4.6

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

4.2.3代價(jià)樹(shù)搜索1.代價(jià)樹(shù)的廣度優(yōu)先搜索代價(jià)樹(shù)的廣度優(yōu)先搜索算法：(1)把初始節(jié)點(diǎn)S0放入Open表中，置S0的代價(jià)g(S0)=0；(2)如果Open表為空，則問(wèn)題無(wú)解，失敗退出；(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n；(4)考察節(jié)點(diǎn)n是否為目標(biāo)。若是，則找到了問(wèn)題的解，成功退出；(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第(2)步；(6)擴(kuò)展節(jié)點(diǎn)n，生成其子節(jié)點(diǎn)ni(i=1,2,…)，將這些子節(jié)點(diǎn)放入Open表中，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針。按如下公式：g(ni)=g(n)+c(ni)i=1,2,...計(jì)算各子結(jié)點(diǎn)的代價(jià)，并根據(jù)各子結(jié)點(diǎn)的代價(jià)對(duì)Open表中的全部結(jié)點(diǎn)按由小到大的順序排序。然后轉(zhuǎn)第(2)步。34在代價(jià)樹(shù)中，可以用g(n)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)例4.7

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

ABCDE434523245AC1B1D1D2E1E2B2C2E3343423城市交通圖城市交通圖的代價(jià)樹(shù)解：代價(jià)樹(shù)如右圖所示。其中，紅線為最優(yōu)解，其代價(jià)為835例4.7城市交通問(wèn)題。設(shè)有5個(gè)城市，它們之間的交通線4.2.3代價(jià)樹(shù)搜索2.代價(jià)樹(shù)的深度優(yōu)先搜索代價(jià)樹(shù)的深度優(yōu)先搜索算法：(1)把初始節(jié)點(diǎn)S0放入Open表中，置S0的代價(jià)g(S0)=0；(2)如果Open表為空，則問(wèn)題無(wú)解，失敗退出；(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n；(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則找到了問(wèn)題的解，成功退出；(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第(2)步；(6)擴(kuò)展節(jié)點(diǎn)n，生成其子節(jié)點(diǎn)ni(i=1,2,…)，將這些子節(jié)點(diǎn)按邊代價(jià)由小到大放入Open表的首部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針。然后轉(zhuǎn)第(2)步。364.2.3代價(jià)樹(shù)搜索代價(jià)樹(shù)的深度優(yōu)先搜索算法：36搜索的基本概念狀態(tài)空間的盲目搜索狀態(tài)空間的啟發(fā)式搜索與/或樹(shù)的盲目搜索與/或樹(shù)的啟發(fā)式搜索博弈樹(shù)的啟發(fā)式搜索第4章搜索策略37搜索的基本概念第4章搜索策略374.3狀態(tài)空間的啟發(fā)式搜索4.3.1啟發(fā)性信息和估價(jià)函數(shù)4.3.2A算法4.3.3A*算法4.3.4A*算法應(yīng)用舉例384.3狀態(tài)空間的啟發(fā)式搜索4.3.1啟發(fā)性信息和估價(jià)函啟發(fā)性信息的概念

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

能決定在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)哪些節(jié)點(diǎn)應(yīng)從搜索樹(shù)上刪除的信息。

啟發(fā)性信息的作用啟發(fā)信息的啟發(fā)能力越強(qiáng)，擴(kuò)展的無(wú)用結(jié)點(diǎn)越少。4.3.1啟發(fā)性信息和估價(jià)函數(shù)1.啟發(fā)性信息39啟發(fā)性信息的概念4.3.1啟發(fā)性信息和估價(jià)函數(shù)估價(jià)函數(shù)用來(lái)估計(jì)節(jié)點(diǎn)重要性的函數(shù)。估價(jià)函數(shù)f(n)被定義為從初始節(jié)點(diǎn)S0出發(fā)，約束經(jīng)過(guò)節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)Sg的所有路徑中最小路徑代價(jià)的估計(jì)值。它的一般形式為：f(n)=g(n)+h(n)其中，g(n)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的實(shí)際代價(jià)；h(n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計(jì)代價(jià)。

4.3.1啟發(fā)性信息和估價(jià)函數(shù)2.估價(jià)函數(shù)例4.8八數(shù)碼難題。設(shè)問(wèn)題的初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如下圖所示，且估價(jià)函數(shù)為f(n)=d(n)+W(n)其中：d(n)表示節(jié)點(diǎn)n在搜索樹(shù)中的深度W(n)表示節(jié)點(diǎn)n中“不在位”的數(shù)碼個(gè)數(shù)。請(qǐng)計(jì)算初始狀態(tài)S0的估價(jià)函數(shù)值f(S0)40估價(jià)函數(shù)用來(lái)估計(jì)節(jié)點(diǎn)重要性的函數(shù)。估價(jià)函數(shù)f(n)被解：取g(n)=d(n)，h(n)=W(n)。它說(shuō)明是用從S0到n的路徑上的單位代價(jià)表示實(shí)際代價(jià)，用結(jié)點(diǎn)n中“不在位”的數(shù)碼個(gè)數(shù)作為啟發(fā)信息。一般來(lái)說(shuō)，某節(jié)點(diǎn)中的“不在位”的數(shù)碼個(gè)數(shù)越多，說(shuō)明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn)。對(duì)初始節(jié)點(diǎn)S0，由于d(S0)=0，W(S0)=3，因此有f(S0)=0+3=32

831476512384765S0Sg41解：取g(n)=d(n)，h(n)=W(n)。它說(shuō)明概念：在圖搜索算法中，如果能在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)對(duì)Open表中的節(jié)點(diǎn)進(jìn)行排序，則該搜索算法為A算法。

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

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

(2)如果Open表為空，則問(wèn)題無(wú)解

，失敗退出；

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

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

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

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

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

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

4.3.2A算法43全局擇優(yōu)搜索A算法描述：4.3.2A算法43例4.9

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

2831476512384765S0Sg44例4.9八數(shù)碼難題。設(shè)問(wèn)題的初始狀態(tài)S0和目標(biāo)狀2831476528314765231

847652831476528316475S0

832147652837146523184765231847651238476512378465123

847654455564644SgS1S2八數(shù)碼難題的全局擇優(yōu)搜索樹(shù)該問(wèn)題的解為：S0→S1→S2→S3→SgS3645283283232

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

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

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

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

對(duì)無(wú)限圖，如果從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)點(diǎn)Sg有路徑存在，則算法A*算法不終止的話，則從Open表中選出的節(jié)點(diǎn)必將具有任意大的f值。證明：設(shè)d*(n)是A*生成的從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的最短路經(jīng)長(zhǎng)度，由于搜索圖中每條邊的代價(jià)都是一個(gè)正數(shù)，令這些正數(shù)中的最小的一個(gè)數(shù)是e，則有g(shù)*(n)≥d*(n)×e因?yàn)間*(n)是最佳路徑的代價(jià)，故有g(shù)(n)≥g*(n)≥d*(n)×e又因?yàn)閔(n)≥0，故有f(n)=g(n)+h(n)≥g(n)≥d*(n)×e如果A*算法不終止的話，從Open表中選出的節(jié)點(diǎn)必將具有任意大的d*(n)值，因此，也將具有任意大的f值。

4.3.3A*算法1.A*算法的可納性(2/6)48引理4.1對(duì)無(wú)限圖，如果從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)引理4.2

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

證明：設(shè)從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)點(diǎn)t的一條最佳路徑序列為S0=n0,n1,…,nk=Sg算法開(kāi)始時(shí)，節(jié)點(diǎn)S0在Open表中，當(dāng)節(jié)點(diǎn)S0離開(kāi)Open表進(jìn)入Closed表時(shí)，節(jié)點(diǎn)n1進(jìn)入Open表。因此，A*沒(méi)有結(jié)束以前，在Open表中必存在最佳路徑上的節(jié)點(diǎn)。設(shè)這些節(jié)點(diǎn)中排在最前面的節(jié)點(diǎn)為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')因?yàn)樵谧罴崖窂缴系乃泄?jié)點(diǎn)的f*值都應(yīng)相等，因此有f(n')≤f*(S0)4.3.3A*算法1.A*算法的可納性(3/6)49引理4.2在A*算法終止前的任何時(shí)刻，Open表中總存定理4.2

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

Open表中任一具有f(n)<f*(S0)的節(jié)點(diǎn)n，最終都被A*算法選作為擴(kuò)展的節(jié)點(diǎn)。(證明略)下面給出A*算法的可納性4.3.3A*算法1.A*算法的可納性(4/6)50定理4.2對(duì)無(wú)限圖，若從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)點(diǎn)Sg4.3.3A*算法1.A*算法的可納性(5/6)定理4.3

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

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

再證明A*算法只能終止在最佳路徑上。（反證法）假設(shè)A*算法未能終止在最佳路徑上，而是終止在某個(gè)目標(biāo)節(jié)點(diǎn)t處，則有f(t)=g(t)>f*(S0)但由引理4.2可知，在A*算法結(jié)束前，必有最佳路徑上的一個(gè)節(jié)點(diǎn)n'在Open表中，且有f(n’)≤f*(S0)<f(t)這時(shí)，A*算法一定會(huì)選擇n'來(lái)擴(kuò)展，而不可能選擇Sg，從而也不會(huì)去測(cè)試目標(biāo)節(jié)點(diǎn)Sg，這就與假設(shè)A*算法終止在目標(biāo)節(jié)點(diǎn)t相矛盾。因此，A*算法只能終止在最佳路徑上。514.3.3A*算法定理4.3A*算法是可推論4.2

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

證明：令n是由A*選作擴(kuò)展的任一節(jié)點(diǎn)，因此n不會(huì)是目標(biāo)節(jié)點(diǎn)，且搜索沒(méi)有結(jié)束。由引理4.2可知，在Open表中有滿足f(n')≤f*(S0)的節(jié)點(diǎn)n'。若n=n'，則有f(n)≤f*(S0)；否則，選擇n擴(kuò)展，必有f(n)≤f(n')所以有f(n)≤f*(S0)4.3.3A*算法1.A*算法的可納性(6/6)52推論4.2在A*算法中，對(duì)任何被擴(kuò)展的節(jié)點(diǎn)n，

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

設(shè)有兩個(gè)A*算法A1*和A2*，它們有A1*:f1(n)=g1(n)+h1(n)A2*:f2(n)=g2(n)+h2(n)如果A2*比A1*有更多的啟發(fā)性信息，即對(duì)所有非目標(biāo)節(jié)點(diǎn)均有h2(n)>h1(n)則在搜索過(guò)程中，被A2*擴(kuò)展的節(jié)點(diǎn)也必然被A1*擴(kuò)展，即A1*擴(kuò)展的節(jié)點(diǎn)不會(huì)比A2*擴(kuò)展的節(jié)點(diǎn)少，亦即A2*擴(kuò)展的節(jié)點(diǎn)集是A1*擴(kuò)展的節(jié)點(diǎn)集的子集。

4.3.3A*算法2.A*算法的最優(yōu)性(1/2)53A*算法的搜索效率很大程度上取決于估價(jià)函數(shù)h(n

4.3.3A*算法2.A*算法的最優(yōu)性(2/2)證明：（用數(shù)學(xué)歸納法）(1)對(duì)深度d(n)=0的節(jié)點(diǎn)，即n為初始節(jié)點(diǎn)S0，如n為目標(biāo)節(jié)點(diǎn)，則A1*和A2*都不擴(kuò)展n；如果n不是目標(biāo)節(jié)點(diǎn)，則A1*和A2*都要擴(kuò)展n。(2)假設(shè)對(duì)A2*中d(n)=k的任意節(jié)點(diǎn)n結(jié)論成立，即A1*也擴(kuò)展了這些節(jié)點(diǎn)。(3)證明A2*中d(n)=k+1的任意節(jié)點(diǎn)n，也要由A1*擴(kuò)展。（用反證法）假設(shè)A2搜索樹(shù)上有一個(gè)滿足d(n)=k+1的節(jié)點(diǎn)n，A2*擴(kuò)展了該節(jié)點(diǎn)，但A1*沒(méi)有擴(kuò)展它。根據(jù)第(2)條的假設(shè)，知道A1*擴(kuò)展了節(jié)點(diǎn)n的父節(jié)點(diǎn)。因此，n必定在A1*的Open表中。既然節(jié)點(diǎn)n沒(méi)有被A1*擴(kuò)展，則有f1(n)≥f*(S0)即g1(n)+h1(n)≥f*(S0)。但由于d=k時(shí)，A2*擴(kuò)展的節(jié)點(diǎn)A1*也一定擴(kuò)展，故有g(shù)1(n)≤g2(n)因此有h1(n)≥f*(S0)-g2(n)另一方面，由于A2*擴(kuò)展了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è)不成立。544.3.3A*算法證明：（用數(shù)學(xué)歸納法）54在A*算法中，每當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn)n時(shí)，都需要檢查其子節(jié)點(diǎn)是否已在Open表或Closed表中。對(duì)已在Open表中的子節(jié)點(diǎn)，需要決定是否調(diào)整指向其父節(jié)點(diǎn)的指針；對(duì)已在Closed表中的子節(jié)點(diǎn)，除需要決定是否調(diào)整其指向父節(jié)點(diǎn)的指針外，還需要決定是否調(diào)整其子節(jié)點(diǎn)的后繼節(jié)點(diǎn)的父指針。如果能夠保證，每當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)就已經(jīng)找到了通往這個(gè)節(jié)點(diǎn)的最佳路徑，就沒(méi)有必要再去作上述檢查為滿足這一要求，我們需要對(duì)啟發(fā)函數(shù)h(n)增加單調(diào)性限制。定義4.1

如果啟發(fā)函數(shù)滿足以下兩個(gè)條件:(1)h(Sg)=0;(2)對(duì)任意節(jié)點(diǎn)ni及其任一子節(jié)點(diǎn)nj，都有0≤h(ni)-h(nj)≤c(ni,nj)其中c(ni,nj)是ni到其子節(jié)點(diǎn)nj的邊代價(jià)，則稱h(n)滿足單調(diào)限制。4.3.3A*算法3.h(n)的單調(diào)限制(1/3)55在A*算法中，每當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn)n時(shí)，都需要檢查其子節(jié)定理4.5

如果h滿足單調(diào)條件，則當(dāng)A*算法擴(kuò)展節(jié)點(diǎn)n時(shí)，該節(jié)點(diǎn)就已經(jīng)找到了通往它的最佳路徑，即g(n)=g*(n)。證明：設(shè)A*正要擴(kuò)展節(jié)點(diǎn)n，而節(jié)點(diǎn)序列S0=n0,n1,…,nk=n是由初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的最佳路徑。其中，ni是這個(gè)序列中最后一個(gè)位于Closed表中的節(jié)點(diǎn)，則上述節(jié)點(diǎn)序列中的ni+1節(jié)點(diǎn)必定在Open表中，則有

g*(ni)+h(ni)≤g*(ni)+c(ni,ni+1)+h(ni+1)由于節(jié)點(diǎn)ni和ni+1都在最佳路徑上，故有

g*(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é)點(diǎn)ni+1在最佳路徑上，故有f(ni+1)≤g*(n)+h(n)因?yàn)檫@時(shí)A*擴(kuò)展節(jié)點(diǎn)n而不擴(kuò)展節(jié)點(diǎn)ni+1，則有f(n)=g(n)+h(n)≤f(ni+1)≤g*(n)+h(n)即g(n)≤g*(n)但是g*(n)是最小代價(jià)值，應(yīng)當(dāng)有g(shù)(n)≥g*(n)所以有g(shù)(n)=g*(n)4.3.3A*算法3.h(n)的單調(diào)限制(2/3)56定理4.5如果h滿足單調(diào)條件，則當(dāng)A*算法擴(kuò)展節(jié)定理4.6

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

證明：假設(shè)節(jié)點(diǎn)ni+1在節(jié)點(diǎn)ni之后立即擴(kuò)展，由單調(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)以上兩個(gè)定理都是在h(n)滿足單調(diào)性限制的前提下才成立的。如果h(n)不滿足單調(diào)性限制，則它們不一定成立。在h(n)滿足單調(diào)性限制下的A*算法常被稱為改進(jìn)的A*算法。4.3.3A*算法3.h(n)的單調(diào)限制(3/3)57定理4.6如果h(n)滿足單調(diào)限制，則A*算法擴(kuò)例4.10

八數(shù)碼難題。

28314765283147652318476528314765283164752318476523184765123847651237846512384765S0f=6g*=1h*=3f=6f=6g*=2h*=2f=6f=4g*=3h*=1f=4g*=4h*=0f=4f=6Sg八數(shù)碼難題h(n)=P(n)的搜索樹(shù)f(n)=d(n)+P(n)d(n)深度P(n)與目標(biāo)距離顯然滿足P(n)≤h*(n)即f*=g*+h*f=44.3.4A*算法應(yīng)用舉例h*=4f=458例4.10八數(shù)碼難題。28328例4.11修道士和野人問(wèn)題。解：用m表示左岸的修道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)，用三元組(m,c,b)表示問(wèn)題的狀態(tài)。對(duì)A*算法，首先需要確定估價(jià)函數(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é)點(diǎn)的深度。通過(guò)分析可知h(n)≤h*(n)，滿足A*算法的限制條件。M-C問(wèn)題的搜索過(guò)程如下圖所示。4.3.4A*算法應(yīng)用舉例59例4.11修道士和野人問(wèn)題。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傳教士和野人問(wèn)題的搜索圖問(wèn)題狀態(tài)：(m,c,b)估價(jià)函數(shù)：h(n)=m+c-2bh=4f=5h=4f=5h=2f=6h=2f=760(3,3,1)h=4f=4(3,2,0)本章要點(diǎn)搜索的基本概念狀態(tài)空間的盲目搜索狀態(tài)空間的啟發(fā)式搜索與/或樹(shù)的盲目搜索與/或樹(shù)的啟發(fā)式搜索博弈樹(shù)的啟發(fā)式搜索61本章要點(diǎn)搜索的基本概念61與/或樹(shù)的搜索過(guò)程實(shí)際上是一個(gè)不斷尋找解樹(shù)的過(guò)程。其一般搜索過(guò)程如下：(1)把原始問(wèn)題作為初始節(jié)點(diǎn)S0，并把它作為當(dāng)前節(jié)點(diǎn)；(2)應(yīng)用分解或等價(jià)變換操作對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展；(3)為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；(4)選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第(2)步和第(3)步，在此期間需要多次調(diào)用可解標(biāo)記過(guò)程或不可解標(biāo)記過(guò)程，直到初始節(jié)點(diǎn)被標(biāo)記為可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)為止。上述搜索過(guò)程將形成一顆與/或樹(shù)，這種由搜索過(guò)程所形成的與/或樹(shù)稱為搜索樹(shù)。

4.4.1與/或樹(shù)的一般搜索62與/或樹(shù)的搜索過(guò)程實(shí)際上是一個(gè)不斷尋找解樹(shù)的過(guò)程。其一

與/或樹(shù)的廣度優(yōu)先搜索與狀態(tài)空間的廣度優(yōu)先搜索的主要差別是，需要在搜索過(guò)程中需要多次調(diào)用可解標(biāo)識(shí)過(guò)程或不可解標(biāo)識(shí)過(guò)程。其搜索算法如下：(1)把初始節(jié)點(diǎn)S0放入Open表中；(2)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n；(3)如果節(jié)點(diǎn)n可擴(kuò)展，則做下列工作：①擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的尾部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；4.4.1與/或樹(shù)的廣度優(yōu)先和深度優(yōu)先搜索1.廣度優(yōu)先搜索63與/或樹(shù)的廣度優(yōu)先搜索與狀態(tài)空間的廣度優(yōu)先搜索的主要②考察這些子節(jié)點(diǎn)中有否終止節(jié)點(diǎn)。若有，則標(biāo)記這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并用可解標(biāo)記過(guò)程對(duì)其父節(jié)點(diǎn)及先輩節(jié)點(diǎn)中的可解解節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始解節(jié)點(diǎn)S0能夠被標(biāo)記為可解節(jié)點(diǎn)，就得到了解樹(shù)，搜索成功，退出搜索過(guò)程；如果不能確定S0為可解節(jié)點(diǎn)，則從Open表中刪去具有可解先輩的節(jié)點(diǎn)。③轉(zhuǎn)第(2)步。(4)如果節(jié)點(diǎn)n不可擴(kuò)展，則作下列工作：①標(biāo)記節(jié)點(diǎn)n為不可解節(jié)點(diǎn)；②應(yīng)用不可解標(biāo)記過(guò)程對(duì)節(jié)點(diǎn)n的先輩中不可解解的節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始解節(jié)點(diǎn)S0也被標(biāo)記為不可解節(jié)點(diǎn)，則搜索失敗，表明原始問(wèn)題無(wú)解，退出搜索過(guò)程；如果不能確定S0為不可解節(jié)點(diǎn)，則從Open表中刪去具有不可解先輩的節(jié)點(diǎn)。

③轉(zhuǎn)第(2)步。64②考察這些子節(jié)點(diǎn)中有否終止節(jié)點(diǎn)。若有，則標(biāo)記這例4.13設(shè)有下圖所示的與/或樹(shù)，節(jié)點(diǎn)按標(biāo)注順序進(jìn)行擴(kuò)展，其中表有t1、t2、t3的節(jié)點(diǎn)是終止節(jié)點(diǎn)，A、B、C為不可解的端節(jié)點(diǎn)。

123A4t15t2Bt3C與/或樹(shù)的廣度優(yōu)先搜索搜索過(guò)程為：(1)先擴(kuò)展1號(hào)節(jié)點(diǎn)，生成2號(hào)節(jié)點(diǎn)和3號(hào)節(jié)點(diǎn)。(2)擴(kuò)展2號(hào)節(jié)點(diǎn)，生成A節(jié)點(diǎn)和4號(hào)節(jié)點(diǎn)。(3)擴(kuò)展3號(hào)節(jié)點(diǎn)，生成t1節(jié)點(diǎn)和5號(hào)節(jié)點(diǎn)。由于t1為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過(guò)程，不能確定3號(hào)節(jié)點(diǎn)是否可解。(6)擴(kuò)展5號(hào)節(jié)點(diǎn)，生成t3節(jié)點(diǎn)和C節(jié)點(diǎn)。由于t3為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過(guò)程，可標(biāo)記1號(hào)節(jié)點(diǎn)為可解節(jié)點(diǎn)。(7)搜索成功，得到由1、2、3、4、5號(hào)節(jié)點(diǎn)即t1、t2、t3節(jié)點(diǎn)構(gòu)成的解樹(shù)。(4)擴(kuò)展節(jié)點(diǎn)A，由于A是端節(jié)點(diǎn)，因此不可擴(kuò)展。調(diào)用不可解標(biāo)記過(guò)程…。(5)擴(kuò)展4號(hào)節(jié)點(diǎn)，生成t2節(jié)點(diǎn)和B節(jié)點(diǎn)。由于t2為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過(guò)程，可標(biāo)記2號(hào)節(jié)點(diǎn)為可解，但不能標(biāo)記1號(hào)節(jié)點(diǎn)為可解。65例4.13設(shè)有下圖所示的與/或樹(shù)，節(jié)點(diǎn)按標(biāo)注順序進(jìn)行

與/或樹(shù)的深度優(yōu)先搜索和與/或樹(shù)的廣度優(yōu)先搜索過(guò)程基本相同，其主要區(qū)別在于Open表中節(jié)點(diǎn)的排列順序不同。在擴(kuò)展節(jié)點(diǎn)時(shí)，與/或樹(shù)的深度優(yōu)先搜索過(guò)程總是把剛生成的節(jié)點(diǎn)放在Open表的首部。與/或樹(shù)的深度優(yōu)先搜索也可以帶有深度限制dm，其搜索算法如下：(1)把初始節(jié)點(diǎn)S0放入Open表中；(2)把Open表第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n；(3)如果節(jié)點(diǎn)n的深度等于dm，則轉(zhuǎn)第(5)步的第①點(diǎn)；(4)如果節(jié)點(diǎn)n可擴(kuò)展，則做下列工作：①擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的首部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；4.4.1與/或樹(shù)的廣度優(yōu)先和深度優(yōu)先搜索2.深度優(yōu)先搜索66與/或樹(shù)的深度優(yōu)先搜索和與/或樹(shù)的廣度優(yōu)先搜索過(guò)程基②考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。若有，則標(biāo)記這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并用可解標(biāo)記過(guò)程對(duì)其父節(jié)點(diǎn)及先輩節(jié)點(diǎn)中的可解解節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始解節(jié)點(diǎn)S0能夠被標(biāo)記為可解節(jié)點(diǎn)，就得到了解樹(shù)，搜索成功，退出搜索過(guò)程；如果不能確定S0為可解節(jié)點(diǎn)，則從Open表中刪去具有可解先輩的節(jié)點(diǎn)。③轉(zhuǎn)第(2)步。(5)如果節(jié)點(diǎn)n不可擴(kuò)展，則作下列工作：①標(biāo)記節(jié)點(diǎn)n為不可解節(jié)點(diǎn)；②應(yīng)用不可解標(biāo)記過(guò)程對(duì)節(jié)點(diǎn)n的先輩中不可解解的節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始解節(jié)點(diǎn)S0也被標(biāo)記為不可解節(jié)點(diǎn)，則搜索失敗，表明原始問(wèn)題無(wú)解，退出搜索過(guò)程；如果不能確定S0為不可解節(jié)點(diǎn)，則從Open表中刪去具有不可解先輩的節(jié)點(diǎn)。③轉(zhuǎn)第(2)步。67②考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。若有，則標(biāo)記這些對(duì)上例，若按有界深度優(yōu)先，且設(shè)dm=4，則其節(jié)點(diǎn)擴(kuò)展順序?yàn)椋?/p>