1、搜索是人工智能中的一個基本問題，并與推理密切相關(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ā)式搜索：在搜索中加入了與

2、問題有關(guān)的啟發(fā)性信息，用于指導搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優(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ù)

3、，它描述了狀態(tài)之間的關(guān)系。 狀態(tài)空間(State space) 用來描述一個問題的全部狀態(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

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

5、，還需要考慮船在左岸還是在右岸。從而可用一個三元組來表示狀態(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中之一。因此，共有442=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)

6、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)生非法狀

7、態(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為例來說明這些操作的條件和動作。 操作符號 條件 動作 P01 b=1, m=0或3, c1 b=0, c=c-1 Q01 b=0, m=0或3，c2 b=1, c=c+1,a,b,c,

8、例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) 允許

9、的操作為 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

10、,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),Climbbox,Climbbox,Pushbox(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) A

11、T(monkey, a) AT(box, b) ONBOX ， HB 問題的目標狀態(tài) AT(monkey, c) ，AT(box, c) ONBOX ， HB,a,b,c,描述操作的謂詞 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(b

12、ox, v) 動作：刪除表：AT(monkey, v)，AT(box, v) 添加表：AT(monkey, w)，AT(box,w),回顧第二章-猴子摘香蕉問題(2/3),Climbbox 條件： ONBOX ，AT(monkey, w)，AT(box,w) 動作：刪除表： ONBOX 添加表：ONBOX Grasp 條件：ONBOX，AT(box, c) 動作：刪除表： HB 添加表：HB,回顧第二章-猴子摘香蕉問題(3/3),基本思想 當一問題較復雜時，可通過分解或變換，將其轉(zhuǎn)化為一系列較簡單的子問題，然后通過對這些子問題的求解來實現(xiàn)對原問題的求解。,分解 如果一個問題P可以歸約為一組子問

13、題P1,P2,Pn，并且只有當所有子問題Pi都有解時原問題P才有解，任何一個子問題Pi無解都會導致原問題P無解，則稱此種歸約為問題的分解。 即分解所得到的子問題的“與”與原問題P等價。 等價變換 如果一個問題P可以歸約為一組子問題P1,P2,Pn，并且子問題Pi中只要有一個有解則原問題P就有解，只有當所有子問題Pi都無解時原問題P才無解，稱此種歸約為問題的等價變換，簡稱變換。 即變換所得到的子問題的“或”與原問題P等價。,4.1.3 問題歸約法 1. 問題的分解與等價變換,(1)與樹 分解,(2) 或樹 等價變換,(3) 與/或樹,4.1.3 問題歸約法 2. 問題的與/或樹表示,(4) 端節(jié)

14、點與終止節(jié)點 在與/或樹中，沒有子節(jié)點的節(jié)點稱為端節(jié)點；本原問題所對應(yīng)的節(jié)點稱為終止節(jié)點?？梢姡K止節(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é)點，則

15、該與節(jié)點是不可解節(jié)點。,(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)空間法來解，不過本例主要用它來說

16、明如何用歸約法來解決問題。 為了能夠解決這一問題，首先需要定義該問題的形式化表示方法。設(shè)用三元組 (i, j, k) 表示問題在任一時刻的狀態(tài)，用“”表示狀態(tài)的轉(zhuǎn)換。上述三元組中 i 代表金片C所在的鋼針號 j 代表金片B所在的鋼針號 k 代表金片A所在的鋼針號,1,2,3,1,2,3,4.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號鋼

17、針的雙金片移動問題。即(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個本原問題。如果把這

18、些本原問題從左至右排列起來，即得到了原始問題的解： (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é)點還沒有全部搜索完之前，不進

19、入第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ù)碼難題。在33的方格棋盤上，分別

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

21、8 4 7 6 5,2 8 1 4 3 7 6 5,2 8 3 1 4 5 7 6,2 8 3 1 6 4 7 5,2 8 3 1 6 4 7 5,8 3 2 1 4 7 6 5,2 8 3 7 1 4 6 5,8 3 2 1 4 7 6 5,8 1 3 2 4 7 6 5,2 8 3 7 4 6 1 5,2 8 3 7 1 4 6 5,1 2 3 8 4 7 6 5,1 2 3 7 8 4 6 5,1 2 3 8 4 7 6 5,2 3 4 1 8 7 6 5,2 8 1 4 3 7 6 5,2 8 3 1 4 5 7 6,2 8 3 6 4 1 7 5,2 8 3 1 6 7 5 4,S0

22、 1,2 3 4 5,6 7 8 9 10 11 12 13,14 15 16 17 18 19 20 21,22 23 24 25 26 27,Sg,算法描述 (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. 深

23、度優(yōu)先搜索,基本思想 從初始節(jié)點S0開始，在其子節(jié)點中選擇一個最新生成的節(jié)點進行考察，如果該子節(jié)點不是目標節(jié)點且可以擴展，則擴展該子節(jié)點，然后再在此子節(jié)點的子節(jié)點中選擇一個最新生成的節(jié)點進行考察，依此向下搜索，直到某個子節(jié)點既不是目標節(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進行考察。,2 8 3 1 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,2 8 3 1 6 4 7 5,2 8 3 1 6 4 7 5,2 8 3 1 6 4 7 5,2 8 3 1 6 7 5 4,2 8 3 1 6 7 5 4,2 8 1 6 3 7 5

24、 4,2 8 1 6 3 7 5 4,S0 1,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) 如果O

25、pen表為空，則問題無解 ，失敗退出； (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ù)字表

26、示兩個城市之間的交通費用，即代價。用代價樹的廣度優(yōu)先搜索，求從A市出發(fā)到E市，費用最小的交通路線。,城市交通圖 城市交通圖的代價樹,解：代價樹如右圖所示。其中，紅線為最優(yōu)解，其代價為8,4.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，生成

27、其子節(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)的，并可指導搜索過程朝著最有希望方向前進的控制信息。 啟發(fā)性信息的種類 有效地幫助確定擴展節(jié)點的信息； 有效的幫助決定哪些后繼節(jié)點應(yīng)被生成的信息； 能決定在擴展一個節(jié)點時哪些

28、節(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

29、) 其中：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=3,2 8 3 1 4 7 6 5,1 2 3 8 4 7 6 5,S0 Sg,概念： 在圖搜索算法中，如果能在搜索的每一步都利用估價函數(shù)f(n)=g(n)+h(n)對Ope

30、n表中的節(jié)點進行排序，則該搜索算法為A算法。 由于估價函數(shù)中帶有問題自身的啟發(fā)性信息，因此，A算法也被稱為啟發(fā)式搜索算法。 類型： 可根據(jù)搜索過程中選擇擴展節(jié)點的范圍，將啟發(fā)式搜索算法分為全局擇優(yōu)搜索算法和局部擇優(yōu)搜索算法。 全局擇優(yōu)： 從Open表的所有節(jié)點中選擇一個估價函數(shù)值最小的一個進行擴展。 局部擇優(yōu)：僅從剛生成的子節(jié)點中選擇一個估價函數(shù)值最小的一個進行擴展。,4.3.2 A算法,全局擇優(yōu)搜索A算法描述： (1)把初始節(jié)點S0放入Open表中，f(S0)=g(S0)+h(S0)； (2)如果Open表為空，則問題無解 ，失敗退出； (3)把Open表的第一個節(jié)點取出放入Closed表，

31、并記該節(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.2 A算法,例4.9 八數(shù)碼難題。設(shè)問題的初始狀態(tài)S0和目標狀態(tài)Sg如圖所示，估價函數(shù)與例4.8相同。請用全局擇優(yōu)搜索解決該問題。 解：該問題的全局擇優(yōu)搜索樹如下圖所示。

32、在該圖中，每個節(jié)點旁邊的數(shù)字是該節(jié)點的估價函數(shù)值。 例如，對節(jié)點S2，其估價函數(shù)值的計算為：f(S2)=d(S2)+W(S2) =1+3=4,2 8 3 1 4 7 6 5,1 2 3 8 4 7 6 5,S0 Sg,2 8 3 1 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,2 8 3 1 6 4 7 5,S0,8 3 2 1 4 7 6 5,2 8 3 7 1 4 6 5,2 3 1 8 4 7 6 5,2 3 1 8 4 7 6 5,1 2 3 8 4 7 6 5,1 2 3 7 8 4 6 5,1 2 3 8 4 7

33、6 5,4 4 5 5,5 6 4 6,4,4,Sg,S1,S2,八數(shù)碼難題的全局擇優(yōu)搜索樹,該問題的解為： S0S1S2S3Sg,S3,6,4.3.3 A*算法,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)的下界，即

34、對任意節(jié)點n均有h(n)h*(n)。 即滿足上述兩條限制的A算法稱為A*算法。,4.3.3 A*算法 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é)束；如果算法找不到解，則

35、必然會由于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)長度，由于

36、搜索圖中每條邊的代價都是一個正數(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.3 A*算法 1. A*算法的可納性(2),引理4.2 在A*算法終止前的任何時刻，Open表中總存在節(jié)點n，它是從初始節(jié)點S0到目標節(jié)點的最佳路徑上的一個節(jié)點，且滿足f(n)f*(S0)。 證明：設(shè)從初始節(jié)點S0到目標節(jié)點t的一條最佳路徑序列

37、為 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.3 A*算法 1. A*算法的可納性(3),定理4.2 對無限圖

38、，若從初始節(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.3 A*算法 1. A*算法的可納性(4),4.3.3 A*算法 1. A*算法的可納性(5),定理4.3 A*算法是可采納的，即若存在從初始節(jié)點S0到目標節(jié)點Sg的路徑，則A*算法必能結(jié)束在最佳路徑上。 證明：證明過程分以下兩步進行： 先證明A*算法

39、一定能夠終止在某個目標節(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，都

40、有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.3 A*算法 1. A*算法的可納性(6),A*算法的搜索效率很大程度上取決于估價函數(shù)h(n)。一般來說，在滿足h(n) h*(n)的前提下，h(n)的值越大越好。h(n)的值越大，說明它攜帶的啟發(fā)性信息越多，A*算法搜索時擴展的節(jié)點就越少，搜索效率就越高。 下面通過一個定理來描述這一特性。 定理4.4 設(shè)

41、有兩個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.3 A*算法 2. A*算法的最優(yōu)性(1),4.3.3 A*算法 2. A*算法的最優(yōu)性(2),證明：（用數(shù)學歸納法） (1) 對深度d(n)=0的節(jié)點，即n為初始節(jié)點S0，如n為目標節(jié)點，則A1*和A2*都不擴展n；如果n不是

42、目標節(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

43、)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)找到了通往

44、這個節(jié)點的最佳路徑，就沒有必要再去作上述檢查 為滿足這一要求，我們需要對啟發(fā)函數(shù)h(n)增加單調(diào)性限制。 定義4.1 如果啟發(fā)函數(shù)滿足以下兩個條件: (1) h(Sg)=0; (2) 對任意節(jié)點ni及其任一子節(jié)點nj，都有 0h(ni)-h(nj)c(ni, nj) 其中c(ni, nj)是ni到其子節(jié)點nj的邊代價，則稱h(n)滿足單調(diào)限制。,4.3.3 A*算法 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 是由

45、初始節(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*( ni+1)=g*(ni)+c(ni, ni+1) 所以 g*(ni)+h(ni)g*( ni+1) +h(ni+1) 一直推導下去可得 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

46、，則有 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(n)=g*(n),4.3.3 A*算法 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(n

47、i)+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.3 A*算法 3. h(n)的單調(diào)限制(2),例4.10 八數(shù)碼難題。,2 8 3 1 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,2 8 3 1 6 4 7 5,2 3 1 8 4 7 6 5,2 3 1 8 4 7 6 5,1 2

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

49、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.4 A*算法應(yīng)用舉例,(3,3,1) h=4 f=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=5 f=6,h=3 f=5,h=3 f=6 h=3 f=6,h=2 f=6,h=2 f

50、=7 h=1 f=7 h=1 f=8 h=0 f=8,傳教士和野人問題的搜索圖,h(n)=m+c-2b,h=4 f=5,h=4 f=5,h=2 f=6,h=2 f=7,本章要點,搜索的基本概念 狀態(tài)空間的盲目搜索 狀態(tài)空間的啟發(fā)式搜索 與/或樹的盲目搜索 與/或樹的啟發(fā)式搜索 博弈樹的啟發(fā)式搜索,與/或樹的搜索過程實際上是一個不斷尋找解樹的過程。其一般搜索過程如下： (1) 把原始問題作為初始節(jié)點S0，并把它作為當前節(jié)點； (2) 應(yīng)用分解或等價變換操作對當前節(jié)點進行擴展； (3) 為每個子節(jié)點設(shè)置指向父節(jié)點的指針； (4) 選擇合適的子節(jié)點作為當前節(jié)點，反復執(zhí)行第(2)步和第(3)步，在此期

51、間需要多次調(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 與/或樹的廣度

52、優(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表中刪去具有不

53、可解先輩的節(jié)點。 轉(zhuǎn)第(2)步。,例4.13 設(shè)有下圖所示的與/或樹，節(jié)點按標注順序進行擴展，其中表有t1、t2、t3的節(jié)點是終止節(jié)點，A、B、C為不可解的端節(jié)點。,1,2 3,A 4 t1 5,t2 B t3 C,與/或樹的廣度優(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é)

54、點為可解節(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放

55、入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表中刪去具有可解先

56、輩的節(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。,1,2 3,A 4 t1 5,t2 B t3 C,與/或樹的有界深度優(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é)點為可