1、1搜索是人工智能中的一個基本問題，并與推理密切相關，搜索是人工智能中的一個基本問題，并與推理密切相關，搜索策略的優(yōu)劣，將直接影響到智能系統(tǒng)的性能與推理效率。搜索策略的優(yōu)劣，將直接影響到智能系統(tǒng)的性能與推理效率。 狀態(tài)空間的盲目搜索狀態(tài)空間的盲目搜索狀態(tài)空間的啟發(fā)式搜索狀態(tài)空間的啟發(fā)式搜索與與/或樹的盲目搜索或樹的盲目搜索與與/或樹的啟發(fā)式搜索或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索第第4章章 搜索策略搜索策略24.1 搜索的基本概念搜索的基本概念搜索的含義搜索的含義狀態(tài)空間法狀態(tài)空間法問題歸約法問題歸約法34.1.1 搜索的含義搜索的含義適用情況：適用情況： 不良結構或非結構化問題

2、；難以獲得求解所需的全部信息；更沒有現(xiàn)成的不良結構或非結構化問題；難以獲得求解所需的全部信息；更沒有現(xiàn)成的算法可供求解使用。算法可供求解使用。概念：概念： 依靠經(jīng)驗，利用已有知識，根據(jù)問題的實際情況，不斷尋找可利用知識，依靠經(jīng)驗，利用已有知識，根據(jù)問題的實際情況，不斷尋找可利用知識，從而構造一條代價最小的推理路線，使問題得以解決的過程稱為搜索從而構造一條代價最小的推理路線，使問題得以解決的過程稱為搜索搜索的類型搜索的類型 按是否使用啟發(fā)式信息：按是否使用啟發(fā)式信息： 盲目搜索：按預定的控制策略進行搜索，在搜索過程中獲得的中間信息并盲目搜索：按預定的控制策略進行搜索，在搜索過程中獲得的中間信息并

3、不改變控制策略。不改變控制策略。 啟發(fā)式搜索：在搜索中加入了與問題有關的啟發(fā)性信息，用于指導搜索朝啟發(fā)式搜索：在搜索中加入了與問題有關的啟發(fā)性信息，用于指導搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優(yōu)解。著最有希望的方向前進，加速問題的求解過程并找到最優(yōu)解。 按問題的表示方式：按問題的表示方式： 狀態(tài)空間搜索：用狀態(tài)空間法來求解問題所進行的搜索狀態(tài)空間搜索：用狀態(tài)空間法來求解問題所進行的搜索 與或樹搜索：用問題歸約法來求解問題時所進行的搜索與或樹搜索：用問題歸約法來求解問題時所進行的搜索 44.1.2 狀態(tài)空間法狀態(tài)空間法1. 狀態(tài)空間表示方法狀態(tài)空間表示方法狀態(tài)狀態(tài)(state)

4、： 是表示問題求解過程中每一步問題狀況的數(shù)據(jù)結構，它可形式地表示為：是表示問題求解過程中每一步問題狀況的數(shù)據(jù)結構，它可形式地表示為： sk=sk0, sk1, 當對每一個分量都給以確定的值時，就得到了一個具體的狀態(tài)。當對每一個分量都給以確定的值時，就得到了一個具體的狀態(tài)。操作操作(operator) 也稱為算符，它是把問題從一種狀態(tài)變換為另一種狀態(tài)的手段。操作可以是也稱為算符，它是把問題從一種狀態(tài)變換為另一種狀態(tài)的手段。操作可以是一個機械步驟，一個運算，一條規(guī)則或一個過程。操作可理解為狀態(tài)集合上的一一個機械步驟，一個運算，一條規(guī)則或一個過程。操作可理解為狀態(tài)集合上的一個函數(shù)，它描述了狀態(tài)之間的

5、關系。個函數(shù)，它描述了狀態(tài)之間的關系。狀態(tài)空間狀態(tài)空間(state space) 用來描述一個問題的全部狀態(tài)以及這些狀態(tài)之間的相互關系。常用一個三元組用來描述一個問題的全部狀態(tài)以及這些狀態(tài)之間的相互關系。常用一個三元組表示為：表示為： (s, f, g)其中，其中，s為問題的所有初始狀態(tài)的集合；為問題的所有初始狀態(tài)的集合；f為操作的集合；為操作的集合；g為目標狀態(tài)的集合。為目標狀態(tài)的集合。 狀態(tài)空間也可用一個賦值的有向圖來表示，該有向圖稱為狀態(tài)空間圖。在狀態(tài)狀態(tài)空間也可用一個賦值的有向圖來表示，該有向圖稱為狀態(tài)空間圖。在狀態(tài)空間圖中，節(jié)點表示問題的狀態(tài)，有向邊表示操作。空間圖中，節(jié)點表示問題的

6、狀態(tài)，有向邊表示操作。5狀態(tài)空間法求解問題的基本過程：狀態(tài)空間法求解問題的基本過程： 首先為問題選擇適當?shù)氖紫葹閱栴}選擇適當?shù)摹盃顟B(tài)狀態(tài)”及及“操作操作”的形式化的形式化描述方法；描述方法； 然后從某個初始狀態(tài)出發(fā)，每次使用一個然后從某個初始狀態(tài)出發(fā)，每次使用一個“操作操作”，遞增地建立起操作序列，直到達到目標狀態(tài)為止；遞增地建立起操作序列，直到達到目標狀態(tài)為止； 此時，由初始狀態(tài)到目標狀態(tài)所使用的算符序列就是此時，由初始狀態(tài)到目標狀態(tài)所使用的算符序列就是該問題的一個解。該問題的一個解。 4.1.2 狀態(tài)空間法狀態(tài)空間法2. 狀態(tài)空間問題求解狀態(tài)空間問題求解6 例例4.1 二階梵塔問題。二階梵

7、塔問題。設有三根鋼針，它們的編號分別是設有三根鋼針，它們的編號分別是1號、號、2號和號和3號。在初始情況下，號。在初始情況下，1號鋼針上穿有號鋼針上穿有a、b兩個兩個金片，金片，a比比b小，小，a位于位于b的上面。要求把這兩個金片全部移的上面。要求把這兩個金片全部移到另一根鋼針上，而且規(guī)定每次只能移動一個金片，任何時到另一根鋼針上，而且規(guī)定每次只能移動一個金片，任何時刻都不能使大的位于小的上面刻都不能使大的位于小的上面。 解：解：設用設用sk=sk0, sk1表示問題的狀態(tài)，其中，表示問題的狀態(tài)，其中，sk0表示金表示金片片a所在的鋼針號，所在的鋼針號，sk1表示金片表示金片b所在的鋼針號。全

8、部可能所在的鋼針號。全部可能的問題狀態(tài)共有以下的問題狀態(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)空間法狀態(tài)空間法3. 狀態(tài)空間的例子狀態(tài)空間的例子7 ababab 1 2 3 1 2 3 1 2 3二階梵塔問題的初始狀態(tài)和目標狀態(tài)二階梵塔問題的初始狀態(tài)和目標狀態(tài)問題的初始狀態(tài)集合問題的初始狀態(tài)集合為為s=s0 目標狀態(tài)集合目標狀態(tài)集合為為g=s4, s5 初始狀態(tài)初始狀態(tài)s0和目標狀態(tài)和目標狀態(tài)s4、s8如圖所示如圖所示

9、 s0=(1, 1)s4=(2, 2)s8=(3, 3)4.1.2 狀態(tài)空間法狀態(tài)空間法3. 狀態(tài)空間的例子狀態(tài)空間的例子8 操作分別用操作分別用a(i, j)和和b(i, j)表示表示 a(i, j)表示把金片表示把金片a從第從第i號鋼針移到號鋼針移到j號鋼針上；號鋼針上； b(i, j)表示把金片表示把金片b從第從第i號鋼針一到第號鋼針一到第j號鋼針上。共有號鋼針上。共有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)

10、b(3, 2) 根據(jù)上述根據(jù)上述9種可能的狀態(tài)和種可能的狀態(tài)和12種操作，可構成二階梵塔問題的種操作，可構成二階梵塔問題的狀態(tài)空間圖，如下圖所示。狀態(tài)空間圖，如下圖所示。4.1.2 狀態(tài)空間法狀態(tài)空間法3. 狀態(tài)空間的例子狀態(tài)空間的例子9(3,3) (1,3) (1,2) (2,2) 二階梵塔的狀態(tài)空間圖 從初始節(jié)點從初始節(jié)點(1, 1)到目標節(jié)點到目標節(jié)點(2, 2)及及(3, 3)的任何一條路徑都是問題的一的任何一條路徑都是問題的一個解。其中，最短的路徑長度是個解。其中，最短的路徑長度是3，它由，它由3個操作組成。例如，從個操作組成。例如，從 (1, 1)開始，開始，通過使用操作通過使用操

11、作a(1, 3)、b(1, 2)及及a(3, 2)，可到達，可到達 (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)10 例例4.2 修道士修道士(missionaries)和野人和野人(cannibals)問題問題(簡稱簡稱m-c問題問題)。 設在河的一岸有三個野人、三個修道士和一條船，修道士想設在河的一岸有三個野人、三個修道士和一條船，修道士想用這條船把所有的人運到河對岸，但受以下條件的約束：用這條船把所有的人運到河對岸，但受以下條件的約束： 一是修道士和野人都會劃船，但每次船上至多可載兩個人；一是修道

12、士和野人都會劃船，但每次船上至多可載兩個人； 二是在河的任一岸，如果野人數(shù)目超過修道士數(shù)，修道士會二是在河的任一岸，如果野人數(shù)目超過修道士數(shù)，修道士會被野人吃掉。被野人吃掉。 如果野人會服從任何一次過河安排，請規(guī)劃一個確保修道士如果野人會服從任何一次過河安排，請規(guī)劃一個確保修道士和野人都能過河，且沒有修道士被野人吃掉的安全過河計劃。和野人都能過河，且沒有修道士被野人吃掉的安全過河計劃。 4.1.2 狀態(tài)空間法狀態(tài)空間法3. 狀態(tài)空間的例子狀態(tài)空間的例子11 解：解：首先選取描述問題狀態(tài)的方法。在這個問題中，需要首先選取描述問題狀態(tài)的方法。在這個問題中，需要考慮兩岸的修道士人數(shù)和野人數(shù)，還需要考

13、慮船在左岸還是在考慮兩岸的修道士人數(shù)和野人數(shù)，還需要考慮船在左岸還是在右岸。從而可用一個三元組來表示狀態(tài)右岸。從而可用一個三元組來表示狀態(tài) s=(m, c, b)其中，其中，m表示左岸的修道士人數(shù)，表示左岸的修道士人數(shù)，c表示左岸的野人數(shù)，表示左岸的野人數(shù)，b表示表示左岸的船數(shù)。左岸的船數(shù)。 右岸的狀態(tài)可由下式確定：右岸的狀態(tài)可由下式確定： 右岸修道士數(shù)右岸修道士數(shù) m=3-m 右岸野人數(shù)右岸野人數(shù) c=3-c 右岸船數(shù)右岸船數(shù) b=1-b 在這種表示方式下，在這種表示方式下，m和和c都可取都可取0、1、2、3中之一，中之一，b可取可取0和和1中之一。因此，共有中之一。因此，共有442=32種

14、狀態(tài)。種狀態(tài)。 4.1.2 狀態(tài)空間法狀態(tài)空間法3. 狀態(tài)空間的例子狀態(tài)空間的例子12 這這32種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士被野人吃種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士被野人吃掉的狀態(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

15、) s13=(0, 2, 0) s14=(0, 1, 0) s15=(0, 0, 0)有了這些狀態(tài)，還需要考慮可進行的操作。有了這些狀態(tài)，還需要考慮可進行的操作。 操作操作是指用船把修道士或野人從河的左岸運到右岸，或從河的是指用船把修道士或野人從河的左岸運到右岸，或從河的右岸運到左岸。右岸運到左岸。 每個操作都應當滿足如下條件：每個操作都應當滿足如下條件： 一是一是船至少有一個人（船至少有一個人（m或或c）操作，離開岸邊的）操作，離開岸邊的m和和c的減少數(shù)的減少數(shù)目應該等于到達岸邊的目應該等于到達岸邊的m和和c的增加數(shù)目；的增加數(shù)目； 二是二是每次操作船上人數(shù)不得超過每次操作船上人數(shù)不得超過2

16、個；個； 三是三是操作應保證不產(chǎn)生非法狀態(tài)。操作應保證不產(chǎn)生非法狀態(tài)。 因此，因此，操作應由條件部分和動作部分：操作應由條件部分和動作部分： 條件條件：只有當其條件具備時才能使用只有當其條件具備時才能使用 動作：動作：刻劃了應用此操作所產(chǎn)生的結果。刻劃了應用此操作所產(chǎn)生的結果。 13操作的表示：操作的表示： 用符號用符號pij表示從左岸到右岸的運人操作表示從左岸到右岸的運人操作 用符號用符號qij表示從右岸到左岸的操作表示從右岸到左岸的操作其中：其中： i表示表示船上的修道士人數(shù)船上的修道士人數(shù) j表示表示船上的野人數(shù)船上的野人數(shù)操作集操作集 本問題有本問題有10種操作可供選擇：種操作可供選擇

17、： 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 14abc 例例4.3 猴子摘香蕉問題。猴子摘香蕉問題。在討論謂詞邏輯知識表示時，我們在討論謂詞邏輯知識表示時，我們曾提到過這一問題，現(xiàn)在用狀態(tài)空間法來解決這一問題。曾提到過這一問題，現(xiàn)在用狀態(tài)空間法來解決這一問題。 解：解：問題的狀態(tài)可用問

18、題的狀態(tài)可用4元組元組 （w, x, y, z）表示。其中：表示。其中： w表示猴子的水平位置；表示猴子的水平位置； x表示箱子的水平位置；表示箱子的水平位置； y表示猴子是否在箱子上，表示猴子是否在箱子上，當猴子在箱子上時，當猴子在箱子上時，y取取1，否則否則y取取0； z表示猴子是否拿到香蕉，表示猴子是否拿到香蕉，當拿到香蕉時當拿到香蕉時z取取1，否則，否則z取取0。4.1.2 狀態(tài)空間法狀態(tài)空間法3. 狀態(tài)空間的例子狀態(tài)空間的例子15所有可能的狀態(tài)為所有可能的狀態(tài)為 s0: (a, b, 0, 0) 初始狀態(tài)初始狀態(tài) s1: (b, b, 0, 0) s2: (c, c, 0, 0) s

19、3: (c, c, 1, 0) s4: (c, c, 1, 1) 目標狀態(tài)目標狀態(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)空間圖如下圖所示。不難看出，由初始狀這個

20、問題的狀態(tài)空間圖如下圖所示。不難看出，由初始狀態(tài)變?yōu)槟繕藸顟B(tài)的操作序列為：態(tài)變?yōu)槟繕藸顟B(tài)的操作序列為： goto(b), pushbox(c), climbbox, grasp16猴子摘香蕉問題的解猴子摘香蕉問題的解(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, grasppushbox(c)climbboxclimbboxpu

21、shbox(c)pushbox(a)pushbox(a)17基本思想基本思想 當一問題較復雜時，可通過分解或變換，將其轉化為一系列較簡當一問題較復雜時，可通過分解或變換，將其轉化為一系列較簡單的子問題，然后通過對這些子問題的求解來實現(xiàn)對原問題的求解。單的子問題，然后通過對這些子問題的求解來實現(xiàn)對原問題的求解。 分解分解 如果一個問題如果一個問題p可以歸約為一組子問題可以歸約為一組子問題p1,p2,pn，并且只有當所有，并且只有當所有子問題子問題pi都有解時原問題都有解時原問題p才有解，任何一個子問題才有解，任何一個子問題pi無解都會導致原無解都會導致原問題問題p無解，則稱此種歸約為問題的分解。

22、無解，則稱此種歸約為問題的分解。 即分解所得到的子問題的即分解所得到的子問題的“與與”與原問題與原問題p等價。等價。等價變換等價變換 如果一個問題如果一個問題p可以歸約為一組子問題可以歸約為一組子問題p1,p2,pn，并且子問題，并且子問題pi中只要有一個有解則原問題中只要有一個有解則原問題p就有解，只有當所有子問題就有解，只有當所有子問題pi都無解時都無解時原問題原問題p才無解，稱此種歸約為問題的等價變換，簡稱變換。才無解，稱此種歸約為問題的等價變換，簡稱變換。 即變換所得到的子問題的即變換所得到的子問題的“或或”與原問題與原問題p等價。等價。4.1.3 問題歸約法問題歸約法1. 問題的分解

23、與等價變換問題的分解與等價變換18pp1 p2 p3 與樹與樹p1 p2 p3 或樹或樹ppp1 p2 p3 p12 p12 p31 p32 p33 與與/或樹或樹(1)與樹與樹 分解分解(2) 或樹或樹 等價變換等價變換(3) 與與/或樹或樹4.1.3 問題歸約法問題歸約法2. 問題的與問題的與/或樹表示或樹表示19(4) 端節(jié)點與終止節(jié)點端節(jié)點與終止節(jié)點 在與在與/或樹中，沒有子節(jié)點的節(jié)點稱為或樹中，沒有子節(jié)點的節(jié)點稱為端節(jié)點端節(jié)點；本原問題所對應的節(jié)；本原問題所對應的節(jié)點稱為點稱為終止節(jié)點終止節(jié)點。可見，終止節(jié)點一定是端節(jié)點，但端節(jié)點卻不一定是?？梢?，終止節(jié)點一定是端節(jié)點，但端節(jié)點卻不一

24、定是終止節(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é)點才是可解節(jié)點。解節(jié)點。 同樣，可用類似的方法定義同樣，可用類似的方法定義不可解節(jié)點：不可解節(jié)點： 不為終止節(jié)點的

25、端節(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é)點。20pt t t 解樹解樹(6) 解樹解樹 由可解節(jié)點構成，并且由這些可解由可解節(jié)點構成，并且由這些可解節(jié)點可以推出初始節(jié)點（它對應著原節(jié)點可以推出初始節(jié)點（它對應著原始問題）為可解節(jié)點的子樹為解樹。始問題）為可解節(jié)點的子樹為解樹。在解樹中一定包含初始節(jié)點。在解樹中一定

26、包含初始節(jié)點。 例如，右圖給出的與或樹中，用紅例如，右圖給出的與或樹中，用紅 線表示的子樹是一個解樹。在該圖中，線表示的子樹是一個解樹。在該圖中，節(jié)點節(jié)點p為原始問題節(jié)點，用為原始問題節(jié)點，用t標出的節(jié)標出的節(jié)點是終止節(jié)點。根據(jù)可解節(jié)點的定義，點是終止節(jié)點。根據(jù)可解節(jié)點的定義，很容易推出原始問題很容易推出原始問題p為可解節(jié)點。為可解節(jié)點。 問題歸約求解過程就實際上就是生問題歸約求解過程就實際上就是生成解樹，即證明原始節(jié)點是可解節(jié)點成解樹，即證明原始節(jié)點是可解節(jié)點的過程。這一過程涉及到搜索的問題，的過程。這一過程涉及到搜索的問題，對于與對于與/或樹的搜索將在后面詳細討論?；驑涞乃阉鲗⒃诤竺嬖敿氂?/p>

27、論。21 例例4.4 三階梵塔問題。要求把三階梵塔問題。要求把1號鋼針上的號鋼針上的3個金片全部移到個金片全部移到3號鋼針號鋼針上，如下圖所示。上，如下圖所示。 解：解：這個問題也可用狀態(tài)空間法來解，不過本例主要用它來說明如何這個問題也可用狀態(tài)空間法來解，不過本例主要用它來說明如何用歸約法來解決問題。用歸約法來解決問題。 為了能夠解決這一問題，首先需要定義該問題的形式化表示方法。設為了能夠解決這一問題，首先需要定義該問題的形式化表示方法。設用三元組用三元組 (i, j, k)表示問題在任一時刻的狀態(tài)，用表示問題在任一時刻的狀態(tài)，用“”表示狀態(tài)的轉換。上述三元組中表示狀態(tài)的轉換。上述三元組中 i

28、 代表金片代表金片c所在的鋼針號所在的鋼針號 j 代表金片代表金片b所在的鋼針號所在的鋼針號 k 代表金片代表金片a所在的鋼針號所在的鋼針號1231234.1.3 問題歸約法問題歸約法2. 問題的與問題的與/或樹表示或樹表示22利用問題歸約方法，原問題可分解為以下利用問題歸約方法，原問題可分解為以下三個子問題：三個子問題： (1) 把金片把金片a及及b移到移到2號鋼針上的雙金片移動問題。即號鋼針上的雙金片移動問題。即(1, 1, 1)(1, 2, 2) (2) 把金片把金片c移到移到3號鋼針上的單金片移動問題。即號鋼針上的單金片移動問題。即 (1, 2, 2)(3, 2, 2) (3) 把金片

29、把金片a及及b移到移到3號鋼針的雙金片移動問題。即號鋼針的雙金片移動問題。即(3, 2, 2)( (3, 3, 3)其中，子問題其中，子問題(1)和和(3)都是一個二階梵塔問題，它們都還可以再繼續(xù)進行分解；都是一個二階梵塔問題，它們都還可以再繼續(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,

30、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é)點，它們分別對應著個終止節(jié)點，它們分別對應著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,

31、1)(3, 3, 3) 23v搜索的基本概念搜索的基本概念 v狀態(tài)空間的啟發(fā)式搜索狀態(tài)空間的啟發(fā)式搜索v與與/或樹的盲目搜索或樹的盲目搜索v與與/或樹的啟發(fā)式搜索或樹的啟發(fā)式搜索v博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索第第4章章 搜索策略搜索策略244.2 狀態(tài)空間的盲目搜索狀態(tài)空間的盲目搜索一般圖搜索過程一般圖搜索過程廣度優(yōu)先和深度優(yōu)先搜索廣度優(yōu)先和深度優(yōu)先搜索代價樹搜索代價樹搜索25狀態(tài)空間搜索的基本思想狀態(tài)空間搜索的基本思想 先把問題的初始狀態(tài)作為當前擴展節(jié)點對其進行擴展，生成一組子節(jié)點，先把問題的初始狀態(tài)作為當前擴展節(jié)點對其進行擴展，生成一組子節(jié)點，然后檢查問題的目標狀態(tài)是否出現(xiàn)在這些子

32、節(jié)點中。若出現(xiàn)，則搜索成功，然后檢查問題的目標狀態(tài)是否出現(xiàn)在這些子節(jié)點中。若出現(xiàn)，則搜索成功，找到了問題的解；若沒出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點中找到了問題的解；若沒出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點中選擇一個節(jié)點作為當前擴展節(jié)點。重復上述過程，直到目標狀態(tài)出現(xiàn)在子選擇一個節(jié)點作為當前擴展節(jié)點。重復上述過程，直到目標狀態(tài)出現(xiàn)在子節(jié)點中或者沒有可供操作的節(jié)點為止。所謂對一個節(jié)點進行節(jié)點中或者沒有可供操作的節(jié)點為止。所謂對一個節(jié)點進行“擴展擴展”是指是指對該節(jié)點用某個可用操作進行作用，生成該節(jié)點的一組子節(jié)點。對該節(jié)點用某個可用操作進行作用，生成該節(jié)點的一組子節(jié)點。 4.2.1

33、一般圖搜索過程一般圖搜索過程算法的數(shù)據(jù)結構和符號約定算法的數(shù)據(jù)結構和符號約定 open表：用于存放剛生成的節(jié)點表：用于存放剛生成的節(jié)點 closed表：用于存放已經(jīng)擴展或?qū)⒁獢U展的節(jié)點表：用于存放已經(jīng)擴展或?qū)⒁獢U展的節(jié)點 s0：用表示問題的初始狀態(tài)：用表示問題的初始狀態(tài) g：表示搜索過程所得到的搜索圖：表示搜索過程所得到的搜索圖 m：表示當前擴展節(jié)點新生成的且不為自己先輩的子節(jié)點集。：表示當前擴展節(jié)點新生成的且不為自己先輩的子節(jié)點集。26一般圖搜索過程一般圖搜索過程 (1) 把初始節(jié)點把初始節(jié)點s0放入放入open表，并建立目前僅包含表，并建立目前僅包含s0的圖的圖g； (2) 檢查檢查ope

34、n表是否為空，若為空，則問題無解，失敗推出；表是否為空，若為空，則問題無解，失敗推出； (3) 把把open表的第一個節(jié)點取出放入表的第一個節(jié)點取出放入closed表，并記該節(jié)點為節(jié)點表，并記該節(jié)點為節(jié)點n； (4)考察節(jié)點考察節(jié)點n是否為目標節(jié)點。若是則得到了問題的解，成功退出；是否為目標節(jié)點。若是則得到了問題的解，成功退出； (5) 擴展節(jié)點擴展節(jié)點n，生成一組子節(jié)點。把這些子節(jié)點中不是節(jié)點，生成一組子節(jié)點。把這些子節(jié)點中不是節(jié)點n先輩的那先輩的那部分子節(jié)點記入集合部分子節(jié)點記入集合m，并把這些子節(jié)點作為節(jié)點，并把這些子節(jié)點作為節(jié)點n的子節(jié)點加入的子節(jié)點加入g中中 (6) 針對針對m中子節(jié)

35、點的不同情況，分別作如下處理：中子節(jié)點的不同情況，分別作如下處理： 對那些沒有在對那些沒有在g中出現(xiàn)過的中出現(xiàn)過的m成員設置一個指向其父節(jié)點（即節(jié)點成員設置一個指向其父節(jié)點（即節(jié)點n）的指針，并把它放入的指針，并把它放入open表。（新生成的）表。（新生成的） 對那些原來已在對那些原來已在g中出現(xiàn)過，但還沒有被擴展的中出現(xiàn)過，但還沒有被擴展的m成員，確定是否需成員，確定是否需要修改它指向父節(jié)點的指針。（原生成但未擴展的）要修改它指向父節(jié)點的指針。（原生成但未擴展的） 對于那些先前已在對于那些先前已在g中出現(xiàn)過，并已經(jīng)擴展了的中出現(xiàn)過，并已經(jīng)擴展了的m成員，確定是否需成員，確定是否需要修改其后繼

36、節(jié)點指向父節(jié)點的指針。（原生成也擴展過的）要修改其后繼節(jié)點指向父節(jié)點的指針。（原生成也擴展過的） (7) 按某種策略對按某種策略對open表中的節(jié)點進行排序。表中的節(jié)點進行排序。 (8) 轉第轉第(2)步。步。 27算法的幾點說明：算法的幾點說明： (1) 上述過程是狀態(tài)空間的一般圖搜索算法，它具有通用性，后面上述過程是狀態(tài)空間的一般圖搜索算法，它具有通用性，后面所要討論的各種狀態(tài)空間搜索策略都是上述過程的一個特例。各種搜索所要討論的各種狀態(tài)空間搜索策略都是上述過程的一個特例。各種搜索策略的主要區(qū)別在于對策略的主要區(qū)別在于對open表中節(jié)點的排列順序不同。例如，廣度優(yōu)表中節(jié)點的排列順序不同。例

37、如，廣度優(yōu)先搜索把先生成的子節(jié)點排在前面，而深度優(yōu)先搜索則把后生成的子節(jié)先搜索把先生成的子節(jié)點排在前面，而深度優(yōu)先搜索則把后生成的子節(jié)點排在前面。點排在前面。 (2) 在第在第(5)步對節(jié)點步對節(jié)點n擴展后，生成并記入擴展后，生成并記入m的子節(jié)點有以下三種的子節(jié)點有以下三種情況：情況： 該子節(jié)點來從未被任何節(jié)點生成過，由該子節(jié)點來從未被任何節(jié)點生成過，由n第一次生成；第一次生成； 該子節(jié)點原來被其他節(jié)點生成過，但還沒有被擴展，這一次又被該子節(jié)點原來被其他節(jié)點生成過，但還沒有被擴展，這一次又被n再次生成；再次生成； 該子節(jié)點原來被其他節(jié)點生成過，并且已經(jīng)被擴展過，這一次又該子節(jié)點原來被其他節(jié)點生

38、成過，并且已經(jīng)被擴展過，這一次又被被n再次生成。再次生成。 以上三種情況是對一般圖搜索算法而言的。對于盲目搜索，由于其以上三種情況是對一般圖搜索算法而言的。對于盲目搜索，由于其狀態(tài)空間是樹狀結構，因此不會出現(xiàn)后兩種情況，每個節(jié)點經(jīng)擴展后生狀態(tài)空間是樹狀結構，因此不會出現(xiàn)后兩種情況，每個節(jié)點經(jīng)擴展后生成的子節(jié)點都是第一次出現(xiàn)的節(jié)點，不必檢查并修改指向父節(jié)點的指針。成的子節(jié)點都是第一次出現(xiàn)的節(jié)點，不必檢查并修改指向父節(jié)點的指針。 28 (3) 在第在第(6)步針對步針對m中子節(jié)點的不同情況進行處理時，如果發(fā)生當?shù)谥凶庸?jié)點的不同情況進行處理時，如果發(fā)生當?shù)诜N情況，那么，這個種情況，那么，這個m中的節(jié)

39、點究竟應該作為哪一個節(jié)點的后繼節(jié)點呢？中的節(jié)點究竟應該作為哪一個節(jié)點的后繼節(jié)點呢？一般是由原始節(jié)點到該節(jié)點路徑上所付出的代價來決定的，哪一條路經(jīng)一般是由原始節(jié)點到該節(jié)點路徑上所付出的代價來決定的，哪一條路經(jīng)付出的代價小，相應的節(jié)點就作為它的父節(jié)點。所謂由原始節(jié)點到該節(jié)付出的代價小，相應的節(jié)點就作為它的父節(jié)點。所謂由原始節(jié)點到該節(jié)點路徑上的代價是指這條路經(jīng)上的所有有向邊的代價之和。點路徑上的代價是指這條路經(jīng)上的所有有向邊的代價之和。 如果發(fā)生第如果發(fā)生第種情況，除了需要確定該子節(jié)點指向父節(jié)點的指針外，種情況，除了需要確定該子節(jié)點指向父節(jié)點的指針外，還需要確定其后繼節(jié)點指向父節(jié)點的指針。其依據(jù)也是

40、由原始節(jié)點到該還需要確定其后繼節(jié)點指向父節(jié)點的指針。其依據(jù)也是由原始節(jié)點到該節(jié)點的路徑上的代價。節(jié)點的路徑上的代價。 (4) 在搜索圖中，除初始節(jié)點外，任意一個節(jié)點都含有且只含有一在搜索圖中，除初始節(jié)點外，任意一個節(jié)點都含有且只含有一個指向其父節(jié)點的指針。因此，由所有節(jié)點及其指向父節(jié)點的指針所構個指向其父節(jié)點的指針。因此，由所有節(jié)點及其指向父節(jié)點的指針所構成的集合是一棵樹，稱為搜索樹。成的集合是一棵樹，稱為搜索樹。 (5) 在搜索過程的第在搜索過程的第(4)步，一旦某個被考察的節(jié)點是目標節(jié)點，則步，一旦某個被考察的節(jié)點是目標節(jié)點，則搜索過程成功結束。由初始節(jié)點到目標節(jié)點路徑上的所有操作就構成了

41、搜索過程成功結束。由初始節(jié)點到目標節(jié)點路徑上的所有操作就構成了該問題的解，而路徑由第該問題的解，而路徑由第(6)步所形成的指向父節(jié)點的指針來確定。步所形成的指向父節(jié)點的指針來確定。 (6) 如果搜索過程終止在第如果搜索過程終止在第(2)步，即沒有達到目標，且步，即沒有達到目標，且open表中已表中已無可供擴展的節(jié)點，則失敗結束。無可供擴展的節(jié)點，則失敗結束。 29基本思想基本思想 從初始節(jié)點從初始節(jié)點s0開始逐層向下擴展，在第開始逐層向下擴展，在第n層節(jié)點還沒有全部搜索完層節(jié)點還沒有全部搜索完之前，不進入第之前，不進入第n+1層節(jié)點的搜索。層節(jié)點的搜索。open表中的節(jié)點總是按進入的先表中的節(jié)

42、點總是按進入的先后排序，先進入的節(jié)點排在前面，后進入的節(jié)點排在后面。后排序，先進入的節(jié)點排在前面，后進入的節(jié)點排在后面。搜索算法搜索算法 (1)把初始節(jié)點把初始節(jié)點s0放入放入open表中；表中； (2)如果如果open表為空，則問題無解，失敗退出；表為空，則問題無解，失敗退出； (3)把把open表的第一個節(jié)點取出放入表的第一個節(jié)點取出放入closed表，并記該節(jié)點為表，并記該節(jié)點為n； (4)考察節(jié)點考察節(jié)點n是否為目標節(jié)點。若是，則得到問題的解，成功退出；是否為目標節(jié)點。若是，則得到問題的解，成功退出； (5)若節(jié)點若節(jié)點n不可擴展，則轉第不可擴展，則轉第(2)步；步； (6)擴展節(jié)點擴

43、展節(jié)點n，將其子節(jié)點放入，將其子節(jié)點放入open表的尾部，并為每一個子節(jié)表的尾部，并為每一個子節(jié)點設置指向父節(jié)點的指針，然后轉第點設置指向父節(jié)點的指針，然后轉第(2)步。步。 4.2.2 廣度優(yōu)先和深度優(yōu)先搜索廣度優(yōu)先和深度優(yōu)先搜索1. 廣度優(yōu)先搜索廣度優(yōu)先搜索30 例例4.5 八數(shù)碼難題。在八數(shù)碼難題。在33的方格棋盤上，分別放置了表有的方格棋盤上，分別放置了表有數(shù)字數(shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)的八張牌，初始狀態(tài)s0，目標狀，目標狀態(tài)態(tài)sg，如下圖所示。可以使用的操作有，如下圖所示。可以使用的操作有 空格左移，空格上移，空格右移，空格下移空格左移，空格上移，空格右移，

44、空格下移即只允許把位于空格左、上、右、下方的牌移入空格。要求應即只允許把位于空格左、上、右、下方的牌移入空格。要求應用廣度優(yōu)先搜索策略尋找從初始狀態(tài)到目標狀態(tài)的解路徑用廣度優(yōu)先搜索策略尋找從初始狀態(tài)到目標狀態(tài)的解路徑。 2 8 31 47 6 5 1 2 38 47 6 5 s0 sg312 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 52 8 1 4 37 6 52 8 31 4 57 6 2 8 31

45、 6 4 7 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 46 58 3 2 1 47 6 58 1 32 47 6 52 8 37 46 1 52 8 37 1 46 5 1 2 38 47 6 51 2 37 8 4 6 51 2 3 8 47 6 52 3 41 8 7 6 52 81 4 37 6 52 8 31 4 57 62 8 3 6 41 7 52 8 31 6 7 5 4s0 12 3 4 56 7 8 9 10 11 12 1314 15 16 17 18 19 20 2122 23 24 25 26 27sg32算法描述算法描述 (1) (1

46、) 把初始節(jié)點把初始節(jié)點s0放入放入open表中；表中； (2) (2) 如果如果openopen表為空，則問題無解表為空，則問題無解 ，失敗退出；，失敗退出； (3) (3) 把把openopen表的第一個節(jié)點取出放入表的第一個節(jié)點取出放入closedclosed表，并記該節(jié)點為表，并記該節(jié)點為n n； (4) (4) 考察節(jié)點考察節(jié)點n n是否為目標節(jié)點。若是，則得到問題的解，成功退出；是否為目標節(jié)點。若是，則得到問題的解，成功退出； (5) (5) 若節(jié)點若節(jié)點n n不可擴展，則轉第不可擴展，則轉第(2)(2)步；步； (6) (6) 擴展節(jié)點擴展節(jié)點n n，將其子節(jié)點放入，將其子節(jié)點放

47、入openopen表的首部，并為每一個子節(jié)點設置表的首部，并為每一個子節(jié)點設置 指向父節(jié)點的指針，然后轉第指向父節(jié)點的指針，然后轉第(2)(2)步。步。 4.2.2 廣度優(yōu)先和深度優(yōu)先搜索廣度優(yōu)先和深度優(yōu)先搜索2. 深度優(yōu)先搜索深度優(yōu)先搜索基本思想基本思想 從初始節(jié)點從初始節(jié)點s0開始，在其子節(jié)點中選擇一個最新生成的節(jié)點進行考察，如開始，在其子節(jié)點中選擇一個最新生成的節(jié)點進行考察，如果該子節(jié)點不是目標節(jié)點且可以擴展，則擴展該子節(jié)點，然后再在此子節(jié)果該子節(jié)點不是目標節(jié)點且可以擴展，則擴展該子節(jié)點，然后再在此子節(jié)點的子節(jié)點中選擇一個最新生成的節(jié)點進行考察，依此向下搜索，直到某點的子節(jié)點中選擇一個最

48、新生成的節(jié)點進行考察，依此向下搜索，直到某個子節(jié)點既不是目標節(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進行考個子節(jié)點既不是目標節(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進行考察察。332 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 31 6 47 5 2 8 31 6 7 5 42 8 31 67 5 42 8 1 6 37 5 42 81 6 37 5 4s0 12 3 4 5 6八數(shù)碼難題的深度優(yōu)先搜索如右圖八數(shù)碼難題的深度優(yōu)先搜索如右圖 一種改進的深度優(yōu)先算法是有界深度一種

49、改進的深度優(yōu)先算法是有界深度優(yōu)先搜索算法，深度限制為優(yōu)先搜索算法，深度限制為dm例例4.6 八數(shù)碼難題八數(shù)碼難題34 在代價樹中，可以用在代價樹中，可以用g(n)表示從初始節(jié)點表示從初始節(jié)點s0到節(jié)點到節(jié)點n的代價，用的代價，用c(n1, n2)表示從父節(jié)點表示從父節(jié)點n1到其子節(jié)點到其子節(jié)點n2的代價。這樣，對節(jié)點的代價。這樣，對節(jié)點n2的代價有：的代價有：g(n2)=g(n1)+c(n1, n2)。代價樹搜索的目的是為了找到最佳解，即找到一代價樹搜索的目的是為了找到最佳解，即找到一條代價最小的解路徑。條代價最小的解路徑。 4.2.3 代價樹搜索代價樹搜索1. 代價樹的廣度優(yōu)先搜索代價樹的廣

50、度優(yōu)先搜索代價樹的廣度優(yōu)先搜索算法：代價樹的廣度優(yōu)先搜索算法： (1) 把初始節(jié)點把初始節(jié)點s0放入放入open表中，置表中，置s0的代價的代價g(s0)=0； (2) 如果如果open表為空，則問題無解表為空，則問題無解 ，失敗退出；，失敗退出； (3) 把把open表的第一個節(jié)點取出放入表的第一個節(jié)點取出放入closed表，并記該節(jié)點為表，并記該節(jié)點為n； (4) 考察節(jié)點考察節(jié)點n是否為目標。若是，則找到了問題的解，成功退出；是否為目標。若是，則找到了問題的解，成功退出； (5) 若節(jié)點若節(jié)點n不可擴展，則轉第不可擴展，則轉第(2)步；步； (6) 擴展節(jié)點擴展節(jié)點n，生成其子節(jié)點，生成

51、其子節(jié)點ni(i=1, 2, )，將這些子節(jié)點放入，將這些子節(jié)點放入open表表中，并為每一個子節(jié)點設置指向父節(jié)點的指針。按如下公式：中，并為每一個子節(jié)點設置指向父節(jié)點的指針。按如下公式： g(ni)=g(n)+c(ni) i=1,2,.計算各子結點的代價，并根據(jù)各子結點的代價對計算各子結點的代價，并根據(jù)各子結點的代價對open表中的全部結點按表中的全部結點按由小到大的順序排序。然后轉第由小到大的順序排序。然后轉第(2)步。步。35 例例4.7 城市交通問題。設有城市交通問題。設有5個城市，它們之間的交通線路如左圖個城市，它們之間的交通線路如左圖所示，圖中的數(shù)字表示兩個城市之間的交通費用，即代

52、價。用代價所示，圖中的數(shù)字表示兩個城市之間的交通費用，即代價。用代價樹的廣度優(yōu)先搜索，求從樹的廣度優(yōu)先搜索，求從a市出發(fā)到市出發(fā)到e市，費用最小的交通路線。市，費用最小的交通路線。 abcde43 4 5232 4 5ac1b1d1d2e1e2b2c2e3e43 43 4 2 35城市交通圖城市交通圖 城市交通圖的代價樹城市交通圖的代價樹 解：解：代價樹如右圖所示。其中，代價樹如右圖所示。其中，紅線為最優(yōu)解，其代價為紅線為最優(yōu)解，其代價為8364.2.3 代價樹搜索代價樹搜索2.代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索算法：代價樹的深度優(yōu)先搜索算法： (1) 把初始節(jié)點把初

53、始節(jié)點s0放入放入open表中，置表中，置s0的代價的代價g(s0)=0； (2) 如果如果open表為空，則問題無解表為空，則問題無解 ，失敗退出；，失敗退出； (3) 把把open表的第一個節(jié)點取出放入表的第一個節(jié)點取出放入closed表，并記該節(jié)點表，并記該節(jié)點為為n； (4) 考察節(jié)點考察節(jié)點n是否為目標節(jié)點。若是，則找到了問題的解，是否為目標節(jié)點。若是，則找到了問題的解，成功退出；成功退出； (5) 若節(jié)點若節(jié)點n不可擴展，則轉第不可擴展，則轉第(2)步；步； (6) 擴展節(jié)點擴展節(jié)點n，生成其子節(jié)點，生成其子節(jié)點ni(i=1, 2, )，將這些子節(jié)點，將這些子節(jié)點按邊代價由小到大放

54、入按邊代價由小到大放入open表的首部，并為每一個子節(jié)點設置表的首部，并為每一個子節(jié)點設置指向父節(jié)點的指針。然后轉第指向父節(jié)點的指針。然后轉第(2)步。步。37v搜索的基本概念搜索的基本概念v狀態(tài)空間的盲目搜索狀態(tài)空間的盲目搜索v與與/或樹的盲目搜索或樹的盲目搜索v與與/或樹的啟發(fā)式搜索或樹的啟發(fā)式搜索v博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索第第4章章 搜索策略搜索策略384.3 狀態(tài)空間的啟發(fā)式搜索狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價函數(shù)啟發(fā)性信息和估價函數(shù)a算法算法a*算法算法a*算法應用舉例算法應用舉例39 啟發(fā)性信息的概念啟發(fā)性信息的概念 啟發(fā)性信息是指那種與具體問題求解過程有關的，并啟

55、發(fā)性信息是指那種與具體問題求解過程有關的，并可指導搜索過程朝著最有希望方向前進的控制信息?？芍笇阉鬟^程朝著最有希望方向前進的控制信息。 啟發(fā)性信息的種類啟發(fā)性信息的種類 有效地幫助確定擴展節(jié)點的信息；有效地幫助確定擴展節(jié)點的信息； 有效的幫助決定哪些后繼節(jié)點應被生成的信息；有效的幫助決定哪些后繼節(jié)點應被生成的信息； 能決定在擴展一個節(jié)點時哪些節(jié)點應從搜索樹上刪能決定在擴展一個節(jié)點時哪些節(jié)點應從搜索樹上刪除的信息。除的信息。 啟發(fā)性信息的作用啟發(fā)性信息的作用 啟發(fā)信息的啟發(fā)能力越強，擴展的無用結點越少。啟發(fā)信息的啟發(fā)能力越強，擴展的無用結點越少。4.3.1 啟發(fā)性信息和估價函數(shù)啟發(fā)性信息和估價

56、函數(shù)1. 啟發(fā)性信息啟發(fā)性信息40 估價函數(shù)用來估計節(jié)點重要性的函數(shù)。估價函數(shù)估價函數(shù)用來估計節(jié)點重要性的函數(shù)。估價函數(shù)f(n)被定義為被定義為從初始節(jié)點從初始節(jié)點s0出發(fā)，約束經(jīng)過節(jié)點出發(fā)，約束經(jīng)過節(jié)點n到達目標節(jié)點到達目標節(jié)點sg的所有路徑的所有路徑中最小路徑代價的估計值。它的一般形式為：中最小路徑代價的估計值。它的一般形式為： f(n)=g(n)+h(n)其中，其中，g(n)是從初始節(jié)點是從初始節(jié)點s0到節(jié)點到節(jié)點n的實際代價；的實際代價；h(n)是從節(jié)點是從節(jié)點n到目標節(jié)點到目標節(jié)點sg的最優(yōu)路徑的估計代價。的最優(yōu)路徑的估計代價。 4.3.1 啟發(fā)性信息和估價函數(shù)啟發(fā)性信息和估價函數(shù)2

57、. 估價函數(shù)估價函數(shù) 例例4.8 八數(shù)碼難題。設問題的初始狀態(tài)八數(shù)碼難題。設問題的初始狀態(tài)s0和目標狀態(tài)和目標狀態(tài)sg如下圖如下圖所示，且估價函數(shù)為所示，且估價函數(shù)為 f(n)=d(n)+w(n)其中：其中：d(n)表示節(jié)點表示節(jié)點n在搜索樹中的深度在搜索樹中的深度 w(n)表示節(jié)點表示節(jié)點n中中“不在位不在位”的數(shù)碼個數(shù)。的數(shù)碼個數(shù)。請計算初始狀態(tài)請計算初始狀態(tài)s0的估價函數(shù)值的估價函數(shù)值f(s0)41 解：解：取取g(n)=d(n)，h(n)=w(n)。它說明是用從。它說明是用從s0到到n的路徑上的路徑上的單位代價表示實際代價，用結點的單位代價表示實際代價，用結點n中中“不在位不在位”的數(shù)

58、碼個數(shù)的數(shù)碼個數(shù)作為啟發(fā)信息。作為啟發(fā)信息。 一般來說，某節(jié)點中的一般來說，某節(jié)點中的“不在位不在位”的數(shù)碼個數(shù)越多，說明的數(shù)碼個數(shù)越多，說明它離目標節(jié)點越遠。它離目標節(jié)點越遠。 對初始節(jié)點對初始節(jié)點s0，由于，由于d(s0)=0，w(s0)=3，因此有，因此有 f(s0)=0+3=3 2 8 31 47 6 5 1 2 38 47 6 5 s0 sg42概念：概念： 在圖搜索算法中，如果能在搜索的每一步都利用估價函數(shù)在圖搜索算法中，如果能在搜索的每一步都利用估價函數(shù)f(n)=g(n)+h(n)對對open表中的節(jié)點進行排序，則該搜索算法為表中的節(jié)點進行排序，則該搜索算法為a算法。算法。 由于

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

60、擴展。的一個進行擴展。4.3.2 a算法算法43全局擇優(yōu)搜索全局擇優(yōu)搜索a a算法描述：算法描述： (1)(1)把初始節(jié)點把初始節(jié)點s0放入放入open表中，表中，f(s0)=g(s0)+h(s0)； (2)(2)如果如果open表為空，則問題無解表為空，則問題無解 ，失敗退出；，失敗退出； (3)(3)把把open表的第一個節(jié)點取出放入表的第一個節(jié)點取出放入closed表，并記該節(jié)點為表，并記該節(jié)點為n； (4)(4)考察節(jié)點考察節(jié)點n是否為目標節(jié)點。若是，則找到了問題的解，成功退是否為目標節(jié)點。若是，則找到了問題的解，成功退出；出； (5)(5)若節(jié)點若節(jié)點n不可擴展，則轉第不可擴展，則轉