搜索是人工智能中的一個基本問題并與推理密切相關(guān)搜ppt課件

1、搜索是人工智能中的一個根本問題，并與推理親密相關(guān)，搜索戰(zhàn)略的優(yōu)劣，將直接影響到智能系統(tǒng)的性能與推理效率。 第第4章章 搜索戰(zhàn)略搜索戰(zhàn)略4.1 搜索的根本概念搜索的根本概念4.1.1 搜索的含義搜索的含義4.1.2 形狀空間法形狀空間法4.1.3 問題歸約法問題歸約法4.1.1 搜索的含義搜索的含義適用情況：適用情況： 不良構(gòu)造或非構(gòu)造化問題；難以獲得求解所需的全部信息；更沒有現(xiàn)成的不良構(gòu)造或非構(gòu)造化問題；難以獲得求解所需的全部信息；更沒有現(xiàn)成的算法可供求解運用。算法可供求解運用。概念：概念： 依托閱歷，利用已有知識，根據(jù)問題的實踐情況，不斷尋覓可利用知識，依托閱歷，利用已有知識，根據(jù)問題的實踐

2、情況，不斷尋覓可利用知識，從而構(gòu)造一條代價最小的推理道路，使問題得以處理的過程稱為搜索從而構(gòu)造一條代價最小的推理道路，使問題得以處理的過程稱為搜索搜索的類型搜索的類型 按能否運用啟發(fā)式信息：按能否運用啟發(fā)式信息： 盲目搜索：按預(yù)定的控制戰(zhàn)略進展搜索，在搜索過程中獲得的中間信息并盲目搜索：按預(yù)定的控制戰(zhàn)略進展搜索，在搜索過程中獲得的中間信息并不改動控制戰(zhàn)略。不改動控制戰(zhàn)略。 啟發(fā)式搜索：在搜索中參與了與問題有關(guān)的啟發(fā)性信息，用于指點搜索朝啟發(fā)式搜索：在搜索中參與了與問題有關(guān)的啟發(fā)性信息，用于指點搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優(yōu)解。著最有希望的方向前進，加速問題的求解過程并

3、找到最優(yōu)解。 按問題的表示方式：按問題的表示方式： 形狀空間搜索：用形狀空間法來求解問題所進展的搜索形狀空間搜索：用形狀空間法來求解問題所進展的搜索 與或樹搜索：用問題歸約法來求解問題時所進展的搜索與或樹搜索：用問題歸約法來求解問題時所進展的搜索 4.1.2 形狀空間法形狀空間法1. 形狀空間表示方法形狀空間表示方法形狀形狀(State)： 是表示問題求解過程中每一步問題情況的數(shù)據(jù)構(gòu)造，它可方式地表示為：是表示問題求解過程中每一步問題情況的數(shù)據(jù)構(gòu)造，它可方式地表示為： Sk=Sk0, Sk1, 當對每一個分量都給以確定的值時，就得到了一個詳細的形狀。當對每一個分量都給以確定的值時，就得到了一個

4、詳細的形狀。操作操作(Operator) 也稱為算符，它是把問題從一種形狀變換為另一種形狀的手段。操作可以是也稱為算符，它是把問題從一種形狀變換為另一種形狀的手段。操作可以是一個機械步驟，一個運算，一條規(guī)那么或一個過程。操作可了解為形狀集合上的一個機械步驟，一個運算，一條規(guī)那么或一個過程。操作可了解為形狀集合上的一個函數(shù)，它描畫了形狀之間的關(guān)系。一個函數(shù)，它描畫了形狀之間的關(guān)系。形狀空間形狀空間(State space) 用來描畫一個問題的全部形狀以及這些形狀之間的相互關(guān)系。常用一個三元組用來描畫一個問題的全部形狀以及這些形狀之間的相互關(guān)系。常用一個三元組表示為：表示為： (S, F, G)其

5、中，其中，S為問題的一切初始形狀的集合；為問題的一切初始形狀的集合；F為操作的集合；為操作的集合；G為目的形狀的集合。為目的形狀的集合。 形狀空間也可用一個賦值的有向圖來表示，該有向圖稱為形狀空間圖。在形狀形狀空間也可用一個賦值的有向圖來表示，該有向圖稱為形狀空間圖。在形狀空間圖中，節(jié)點表示問題的形狀，有向邊表示操作。空間圖中，節(jié)點表示問題的形狀，有向邊表示操作。形狀空間法求解問題的根本過程：形狀空間法求解問題的根本過程： 首先為問題選擇適當?shù)氖紫葹閱栴}選擇適當?shù)摹靶螤罴靶螤罴啊安僮鞯姆绞交僮鞯姆绞交璁嫹椒?；描畫方法?然后從某個初始形狀出發(fā)，每次運用一個然后從某個初始形狀出發(fā)，每次運用一

6、個“操作，操作，遞增地建立起操作序列，直到到達目的形狀為止；遞增地建立起操作序列，直到到達目的形狀為止； 此時，由初始形狀到目的形狀所運用的算符序列就是此時，由初始形狀到目的形狀所運用的算符序列就是該問題的一個解。該問題的一個解。 4.1.2 形狀空間法形狀空間法2. 形狀空間問題求解形狀空間問題求解 例例4.1 二階梵塔問題。設(shè)有三根鋼針，它們的編號分別是二階梵塔問題。設(shè)有三根鋼針，它們的編號分別是1號、號、2號和號和3號。在初始情況下，號。在初始情況下，1號鋼針上穿有號鋼針上穿有A、B兩個兩個金片，金片，A比比B小，小，A位于位于B的上面。要求把這兩個金片全部移的上面。要求把這兩個金片全部

7、移到另一根鋼針上，而且規(guī)定每次只能挪動一個金片，任何時到另一根鋼針上，而且規(guī)定每次只能挪動一個金片，任何時辰都不能使大的位于小的上面。辰都不能使大的位于小的上面。 解：設(shè)用解：設(shè)用Sk=(Sk0, Sk1)表示問題的形狀，其中，表示問題的形狀，其中，Sk0表示表示金片金片A所在的鋼針號，所在的鋼針號，Sk1表示金片表示金片B所在的鋼針號。全部能所在的鋼針號。全部能夠的問題形狀共有以下夠的問題形狀共有以下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

8、.1.2 形狀空間法形狀空間法3. 形狀空間的例子形狀空間的例子(1/11)ABABAB123123123二階梵塔問題的初始形狀和目的形狀二階梵塔問題的初始形狀和目的形狀問題的初始形狀集合為問題的初始形狀集合為S=S0 目的形狀集合為目的形狀集合為G=S4, S5 初始形狀初始形狀S0和目的形狀和目的形狀S4、S8如下圖如下圖 S0=(1, 1)S4=(2, 2)S8=(3, 3)4.1.2 形狀空間法形狀空間法3. 形狀空間的例子形狀空間的例子(2/11) 操作分別用操作分別用A(i, j)和和B(i, j)表示表示 A(i, j)表示把金片表示把金片A從第從第i號鋼針移到號鋼針移到j(luò)號鋼針

9、上；號鋼針上； 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) B(3, 2) 根據(jù)上述根據(jù)上述9種能夠的形狀和種能夠的形狀和12種操作，可構(gòu)成二階梵塔問題的種操作，可構(gòu)成二階梵塔問題的形狀空間圖，如以下圖所示。形狀空間圖，如以下圖所示。4.1.2 形狀空間法形狀空間法3. 形狀空間的例子形狀空間的例子(3/11)(3,3)

10、(1,3)(1,2)(2,2)二階梵塔的形狀空間圖 從初始節(jié)點從初始節(jié)點(1, 1)到目的節(jié)點到目的節(jié)點(2, 2)及及(3, 3)的任何一條途徑都是問題的一的任何一條途徑都是問題的一個解。其中，最短的途徑長度是個解。其中，最短的途徑長度是3，它由，它由3個操作組成。例如，從個操作組成。例如，從 (1, 1)開場，開場，經(jīng)過運用操作經(jīng)過運用操作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) 例例4.2 修道士修道士(Missionaries

11、)和野人和野人(Cannibals)問題問題(簡稱簡稱M-C問題問題)。 設(shè)在河的一岸有三個野人、三個修道士和一條船，修道士想設(shè)在河的一岸有三個野人、三個修道士和一條船，修道士想用這條船把一切的人運到河對岸，但受以下條件的約束：用這條船把一切的人運到河對岸，但受以下條件的約束： 一是修道士和野人都會劃船，但每次船上至多可載兩個人；一是修道士和野人都會劃船，但每次船上至多可載兩個人； 二是在河的任一岸，假設(shè)野人數(shù)目超越修道士數(shù)，修道士會二是在河的任一岸，假設(shè)野人數(shù)目超越修道士數(shù)，修道士會被野人吃掉。被野人吃掉。 假設(shè)野人會服從任何一次過河安排，請規(guī)劃一個確保修道士假設(shè)野人會服從任何一次過河安排，

12、請規(guī)劃一個確保修道士和野人都能過河，且沒有修道士被野人吃掉的平安過河方案。和野人都能過河，且沒有修道士被野人吃掉的平安過河方案。 4.1.2 形狀空間法形狀空間法3. 形狀空間的例子形狀空間的例子(5/11) 解：首先選取描畫問題形狀的方法。在這個問題中，需求解：首先選取描畫問題形狀的方法。在這個問題中，需求思索兩岸的修道士人數(shù)和野人數(shù)，還需求思索船在左岸還是在思索兩岸的修道士人數(shù)和野人數(shù)，還需求思索船在左岸還是在右岸。從而可用一個三元組來表示形狀右岸。從而可用一個三元組來表示形狀 S=(m, c, b)其中，其中，m表示左岸的修道士人數(shù)，表示左岸的修道士人數(shù)，c表示左岸的野人數(shù)，表示左岸的野

13、人數(shù)，b表示表示左岸的船數(shù)。左岸的船數(shù)。 右岸的形狀可由下式確定：右岸的形狀可由下式確定： 右岸修道士數(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種形狀。種形狀。 4.1.2 形狀空間法形狀空間法3. 形狀空間的例子形狀空間的例子(6/11) 這這32種形狀并非全有意義，除去不合法形狀和修道士被野人吃掉的形狀，有意義的種形狀并非全有意義，除去不合法形狀和修道士被野人吃掉的形狀，有意義的形狀只需形狀

14、只需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)有了這些形狀，還需求思索可進展的操作。有了這些形狀，還需求思索可進展的操作。 操作是指用船把修道士或野人從河的左岸運到右岸，或從河的右岸運到左岸。操作是指用船

15、把修道士或野人從河的左岸運到右岸，或從河的右岸運到左岸。 每個操作都該當滿足如下條件：每個操作都該當滿足如下條件： 一是船至少有一個人一是船至少有一個人m或或c操作，分開岸邊的操作，分開岸邊的m和和c的減少數(shù)目應(yīng)該等于到達岸邊的減少數(shù)目應(yīng)該等于到達岸邊的的m和和c的添加數(shù)目；的添加數(shù)目； 二是每次操作船上人數(shù)不得超越二是每次操作船上人數(shù)不得超越2個；個； 三是操作應(yīng)保證不產(chǎn)生非法形狀。三是操作應(yīng)保證不產(chǎn)生非法形狀。 因此，操作應(yīng)由條件部分和動作部分：因此，操作應(yīng)由條件部分和動作部分： 條件：只需當其條件具備時才干運用條件：只需當其條件具備時才干運用 動作：刻劃了運用此操作所產(chǎn)生的結(jié)果。動作：刻

16、劃了運用此操作所產(chǎn)生的結(jié)果。 操作的表示：操作的表示： 用符號用符號Pij表示從左岸到右岸的運人操作表示從左岸到右岸的運人操作 用符號用符號Qij表示從右岸到左岸的操作表示從右岸到左岸的操作其中：其中： i表示船上的修道士人數(shù)表示船上的修道士人數(shù) j表示船上的野人數(shù)表示船上的野人數(shù)操作集操作集 本問題有本問題有10種操作可供選擇：種操作可供選擇： F=P01, P10, P11, P02, P20,Q01, Q10, Q11, Q02, Q20 下面以下面以P01和和Q01為例來闡明這些操作的條件和動作。為例來闡明這些操作的條件和動作。 操作符號操作符號 條件條件 動作動作 P01 b=1,

17、m=0或或3, c1 b=0, c=c-1 Q01 b=0, m=0或或3，c2 b=1, c=c+1 abc 例4.3 猴子摘香蕉問題。在討論謂詞邏輯知識表示時，我們曾提到過這一問題，如今用形狀空間法來處理這一問題。解：問題的形狀可用4元組w,x,y,z表示。其中：w表示猴子的程度位置；x表示箱子的程度位置；y表示猴子能否在箱子上，當猴子在箱子上時，y取1，否那么y取0；z表示猴子能否拿到香蕉，當拿到香蕉時z取1，否那么z取0。4.1.2 形狀空間法形狀空間法3. 形狀空間的例子形狀空間的例子(9/11)一切能夠的形狀為一切能夠的形狀為 S0: (a, b, 0, 0) 初始形狀初始形狀 S

18、1: (b, b, 0, 0) S2: (c, c, 0, 0) S3: (c, c, 1, 0) S4: (c, c, 1, 1) 目的形狀目的形狀允許的操作為允許的操作為 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,

19、 1, 1) 這個問題的形狀空間圖如以下圖所示。不難看出，由初始這個問題的形狀空間圖如以下圖所示。不難看出，由初始形狀變?yōu)槟康男螤畹牟僮餍蛄袨椋盒螤钭優(yōu)槟康男螤畹牟僮餍蛄袨椋?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)初始形狀Goto(b)Goto(b)Pushbox(c)Grasp目的形狀猴子摘香蕉問題的形狀空間圖解序列為：解序列為： Goto(b), Pushbox(c), Climbbox, Gra

20、spPushbox(c)ClimbboxClimbboxPushbox(c)Pushbox(a)Pushbox(a)根本思想根本思想 當一問題較復(fù)雜時，可經(jīng)過分解或變換，將其轉(zhuǎn)化為一系列較簡當一問題較復(fù)雜時，可經(jīng)過分解或變換，將其轉(zhuǎn)化為一系列較簡單的子問題，然后經(jīng)過對這些子問題的求解來實現(xiàn)對原問題的求解。單的子問題，然后經(jīng)過對這些子問題的求解來實現(xiàn)對原問題的求解。 分解分解 假設(shè)一個問題假設(shè)一個問題P P可以歸約為一組子問題可以歸約為一組子問題P1,P2,PnP1,P2,Pn，并且只需當一，并且只需當一切子問題切子問題PiPi都有解時原問題都有解時原問題P P才有解，任何一個子問題才有解，任何

21、一個子問題PiPi無解都會導(dǎo)無解都會導(dǎo)致原問題致原問題P P無解，那么稱此種歸約為問題的分解。無解，那么稱此種歸約為問題的分解。 即分解所得到的子問題的即分解所得到的子問題的“與與原問題與與原問題P P等價。等價。等價變換等價變換 假設(shè)一個問題假設(shè)一個問題P P可以歸約為一組子問題可以歸約為一組子問題P1,P2,PnP1,P2,Pn，并且子問題，并且子問題PiPi中只需有一個有解那么原問題中只需有一個有解那么原問題P P就有解，只需當一切子問題就有解，只需當一切子問題PiPi都無都無解時原問題解時原問題P P才無解，稱此種歸約為問題的等價變換，簡稱變換。才無解，稱此種歸約為問題的等價變換，簡稱

22、變換。 即變換所得到的子問題的即變換所得到的子問題的“或與原問題或與原問題P P等價。等價。4.1.3 問題歸約法問題歸約法1. 問題的分解與等價變換問題的分解與等價變換PP1P2P3與樹P1P2P3或樹PPP1P2P3P12P12P31P32P33與/或樹(1)與樹與樹 分解分解(2) 或樹或樹 等價變換等價變換(3) 與與/或樹或樹4.1.3 問題歸約法問題歸約法2. 問題的與問題的與/或樹表示或樹表示(4) 端節(jié)點與終止節(jié)點端節(jié)點與終止節(jié)點 在與在與/或樹中，沒有子節(jié)點的節(jié)點稱為端節(jié)點；本原問題所對應(yīng)的節(jié)或樹中，沒有子節(jié)點的節(jié)點稱為端節(jié)點；本原問題所對應(yīng)的節(jié)點稱為終止節(jié)點。可見，終止節(jié)點

23、一定是端節(jié)點，但端節(jié)點卻不一定是點稱為終止節(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é)點才是可解節(jié)點。解節(jié)點。

24、 同樣，可用類似的方法定義不可解節(jié)點：同樣，可用類似的方法定義不可解節(jié)點： 不為終止節(jié)點的端節(jié)點是不可解節(jié)點。不為終止節(jié)點的端節(jié)點是不可解節(jié)點。 對對“或節(jié)點，假設(shè)其全部子節(jié)點都為不可解節(jié)點，那么該或節(jié)點是不或節(jié)點，假設(shè)其全部子節(jié)點都為不可解節(jié)點，那么該或節(jié)點是不可解節(jié)點?？山夤?jié)點。 對對“與節(jié)點，只需其子節(jié)點中有一個為不可解節(jié)點，那么該與節(jié)點是與節(jié)點，只需其子節(jié)點中有一個為不可解節(jié)點，那么該與節(jié)點是不可解節(jié)點。不可解節(jié)點。Pttt解樹(6) 解樹解樹 由可解節(jié)點構(gòu)成，并且由這些可解由可解節(jié)點構(gòu)成，并且由這些可解節(jié)點可以推出初始節(jié)點它對應(yīng)著原節(jié)點可以推出初始節(jié)點它對應(yīng)著原始問題為可解節(jié)點的子樹

25、為解樹。始問題為可解節(jié)點的子樹為解樹。在解樹中一定包含初始節(jié)點。在解樹中一定包含初始節(jié)點。 例如，右圖給出的與或樹中，用紅例如，右圖給出的與或樹中，用紅 線表示的子樹是一個解樹。在該圖中，線表示的子樹是一個解樹。在該圖中，節(jié)點節(jié)點P為原始問題節(jié)點，用為原始問題節(jié)點，用t標出的節(jié)標出的節(jié)點是終止節(jié)點。根據(jù)可解節(jié)點的定義，點是終止節(jié)點。根據(jù)可解節(jié)點的定義，很容易推出原始問題很容易推出原始問題P為可解節(jié)點。為可解節(jié)點。 問題歸約求解過程就實踐上就是生問題歸約求解過程就實踐上就是生成解樹，即證明原始節(jié)點是可解節(jié)點成解樹，即證明原始節(jié)點是可解節(jié)點的過程。這一過程涉及到搜索的問題，的過程。這一過程涉及到搜

26、索的問題，對于與對于與/或樹的搜索將在后面詳細討論?；驑涞乃阉鲗⒃诤竺嬖敿氂懻?。 例例4.4 三階梵塔問題。要求把三階梵塔問題。要求把1號鋼針上的號鋼針上的3個金片全部移到個金片全部移到3號鋼針號鋼針上，如以下圖所示。上，如以下圖所示。 解：這個問題也可用形狀空間法來解，不過本例主要用它來闡明如何解：這個問題也可用形狀空間法來解，不過本例主要用它來闡明如何用歸約法來處理問題。用歸約法來處理問題。 為了可以處理這一問題，首先需求定義該問題的方式化表示方法。設(shè)為了可以處理這一問題，首先需求定義該問題的方式化表示方法。設(shè)用三元組用三元組 (i, j, k)表示問題在任一時辰的形狀，用表示問題在任一時

27、辰的形狀，用“表示形狀的轉(zhuǎn)換。上述三元組中表示形狀的轉(zhuǎn)換。上述三元組中 i 代表金片代表金片C所在的鋼針號所在的鋼針號 j 代表金片代表金片B所在的鋼針號所在的鋼針號 k 代表金片代表金片A所在的鋼針號所在的鋼針號1231234.1.3 問題歸約法問題歸約法2. 問題的與問題的與/或樹表或樹表示示ABCABC利用問題歸約方法，原問題可分解為以下三個子問題：利用問題歸約方法，原問題可分解為以下三個子問題： (1) 把金片把金片A及及B移到移到2號鋼針上的雙金片挪動問題。即號鋼針上的雙金片挪動問題。即(1, 1, 1)(1, 2, 2) (2) 把金片把金片C移到移到3號鋼針上的單金片挪動問題。即

28、號鋼針上的單金片挪動問題。即 (1, 2, 2)(3, 2, 2) (3) 把金片把金片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

29、) (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)著個終止節(jié)點，它們分別對應(yīng)著7個本原問題。假設(shè)把個本原問題。假設(shè)把這些本原問題從左至右陳列起來，即得到了原始問題的解：這些本原問題從左至右陳列起來，即得到了原始問題的解： (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

30、, 2, 2)(3, 2, 1) (3, 2, 1)(3, 3, 1) (3, 3, 1)(3, 3, 3) v搜索的根本概念搜索的根本概念v 形狀空間的盲目搜索形狀空間的盲目搜索v形狀空間的啟發(fā)式搜索形狀空間的啟發(fā)式搜索v與與/或樹的盲目搜索或樹的盲目搜索v與與/或樹的啟發(fā)式搜索或樹的啟發(fā)式搜索v博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索第第4章章 搜索戰(zhàn)略搜索戰(zhàn)略4.2 形狀空間的盲目搜索形狀空間的盲目搜索4.2.1 普通圖搜索過程普通圖搜索過程4.2.2 廣度優(yōu)先和深度優(yōu)先搜索廣度優(yōu)先和深度優(yōu)先搜索4.2.3 代價樹搜索代價樹搜索形狀空間搜索的根本思想形狀空間搜索的根本思想 先把問題的初始形狀

31、作為當前擴展節(jié)點對其進展擴展，生成一組子節(jié)點，先把問題的初始形狀作為當前擴展節(jié)點對其進展擴展，生成一組子節(jié)點，然后檢查詢題的目的形狀能否出如今這些子節(jié)點中。假設(shè)出現(xiàn)，那么搜索然后檢查詢題的目的形狀能否出如今這些子節(jié)點中。假設(shè)出現(xiàn)，那么搜索勝利，找到了問題的解；假設(shè)沒出現(xiàn)，那么再按照某種搜索戰(zhàn)略從已生成勝利，找到了問題的解；假設(shè)沒出現(xiàn)，那么再按照某種搜索戰(zhàn)略從已生成的子節(jié)點中選擇一個節(jié)點作為當前擴展節(jié)點。反復(fù)上述過程，直到目的形的子節(jié)點中選擇一個節(jié)點作為當前擴展節(jié)點。反復(fù)上述過程，直到目的形狀出如今子節(jié)點中或者沒有可供操作的節(jié)點為止。所謂對一個節(jié)點進展狀出如今子節(jié)點中或者沒有可供操作的節(jié)點為止。

32、所謂對一個節(jié)點進展“擴展是指對該節(jié)點用某個可用操作進展作用，生成該節(jié)點的一組子節(jié)擴展是指對該節(jié)點用某個可用操作進展作用，生成該節(jié)點的一組子節(jié)點。點。 4.2.1 普通圖搜索過程普通圖搜索過程算法的數(shù)據(jù)構(gòu)造和符號商定算法的數(shù)據(jù)構(gòu)造和符號商定 Open表：用于存放剛生成的節(jié)點表：用于存放剛生成的節(jié)點 Closed表：用于存放曾經(jīng)擴展或?qū)⒁獢U展的節(jié)點表：用于存放曾經(jīng)擴展或?qū)⒁獢U展的節(jié)點 S0：用表示問題的初始形狀：用表示問題的初始形狀 G：表示搜索過程所得到的搜索圖：表示搜索過程所得到的搜索圖 M：表示當前擴展節(jié)點新生成的且不為本人先輩的子節(jié)點集。：表示當前擴展節(jié)點新生成的且不為本人先輩的子節(jié)點集。

33、普通圖搜索過程普通圖搜索過程 (1) (1) 把初始節(jié)點把初始節(jié)點S0S0放入放入OpenOpen表，并建立目前僅包含表，并建立目前僅包含S0S0的圖的圖G G； (2) (2) 檢查檢查OpenOpen表能否為空，假設(shè)為空，那么問題無解，失敗推出；表能否為空，假設(shè)為空，那么問題無解，失敗推出； (3) (3) 把把OpenOpen表的第一個節(jié)點取出放入表的第一個節(jié)點取出放入ClosedClosed表，并記該節(jié)點為節(jié)點表，并記該節(jié)點為節(jié)點n n； (4) (4)調(diào)查節(jié)點調(diào)查節(jié)點n n能否為目的節(jié)點。假設(shè)是那么得到了問題的解，勝利退能否為目的節(jié)點。假設(shè)是那么得到了問題的解，勝利退出；出； (5)

34、 (5) 擴展節(jié)點擴展節(jié)點n n，生成一組子節(jié)點。把這些子節(jié)點中不是節(jié)點，生成一組子節(jié)點。把這些子節(jié)點中不是節(jié)點n n先輩的先輩的那部分子節(jié)點記入集合那部分子節(jié)點記入集合M M，并把這些子節(jié)點作為節(jié)點，并把這些子節(jié)點作為節(jié)點n n的子節(jié)點參與的子節(jié)點參與G G中中 (6) (6) 針對針對M M中子節(jié)點的不同情況，分別作如下處置：中子節(jié)點的不同情況，分別作如下處置： 對那些沒有在對那些沒有在G G中出現(xiàn)過的中出現(xiàn)過的M M成員設(shè)置一個指向其父節(jié)點即節(jié)點成員設(shè)置一個指向其父節(jié)點即節(jié)點n n的指針，并把它放入的指針，并把它放入OpenOpen表。新生成的表。新生成的 對那些原來已在對那些原來已在G

35、 G中出現(xiàn)過，但還沒有被擴展的中出現(xiàn)過，但還沒有被擴展的M M成員，確定能否成員，確定能否需求修正它指向父節(jié)點的指針。原生成但未擴展的需求修正它指向父節(jié)點的指針。原生成但未擴展的 對于那些先前已在對于那些先前已在G G中出現(xiàn)過，并曾經(jīng)擴展了的中出現(xiàn)過，并曾經(jīng)擴展了的M M成員，確定能否成員，確定能否需求修正其后繼節(jié)點指向父節(jié)點的指針。原生成也擴展過的需求修正其后繼節(jié)點指向父節(jié)點的指針。原生成也擴展過的 (7) (7) 按某種戰(zhàn)略對按某種戰(zhàn)略對OpenOpen表中的節(jié)點進展排序。表中的節(jié)點進展排序。 (8) (8) 轉(zhuǎn)第轉(zhuǎn)第(2)(2)步。步。 算法的幾點闡明：算法的幾點闡明： (1) 上述過程

36、是形狀空間的普通圖搜索算法，它具有通用性，后面所要討上述過程是形狀空間的普通圖搜索算法，它具有通用性，后面所要討論的各種形狀空間搜索戰(zhàn)略都是上述過程的一個特例。各種搜索戰(zhàn)略的主要區(qū)論的各種形狀空間搜索戰(zhàn)略都是上述過程的一個特例。各種搜索戰(zhàn)略的主要區(qū)別在于對別在于對Open表中節(jié)點的陳列順序不同。例如，廣度優(yōu)先搜索把先生成的子節(jié)表中節(jié)點的陳列順序不同。例如，廣度優(yōu)先搜索把先生成的子節(jié)點排在前面，而深度優(yōu)先搜索那么把后生成的子節(jié)點排在前面。點排在前面，而深度優(yōu)先搜索那么把后生成的子節(jié)點排在前面。 (2) 在第在第(5)步對節(jié)點步對節(jié)點n擴展后，生成并記入擴展后，生成并記入M的子節(jié)點有以下三種情況：

37、的子節(jié)點有以下三種情況： 該子節(jié)點來從未被任何節(jié)點生成過，由該子節(jié)點來從未被任何節(jié)點生成過，由n第一次生成；第一次生成； 該子節(jié)點原來被其他節(jié)點生成過，但還沒有被擴展，這一次又被該子節(jié)點原來被其他節(jié)點生成過，但還沒有被擴展，這一次又被n再次再次生成；生成； 該子節(jié)點原來被其他節(jié)點生成過，并且曾經(jīng)被擴展過，這一次又被該子節(jié)點原來被其他節(jié)點生成過，并且曾經(jīng)被擴展過，這一次又被n再再次生成。次生成。 以上三種情況是對普通圖搜索算法而言的。對于盲目搜索，由于其形狀空以上三種情況是對普通圖搜索算法而言的。對于盲目搜索，由于其形狀空間是樹狀構(gòu)造，因此不會出現(xiàn)后兩種情況，每個節(jié)點經(jīng)擴展后生成的子節(jié)點都間是樹

38、狀構(gòu)造，因此不會出現(xiàn)后兩種情況，每個節(jié)點經(jīng)擴展后生成的子節(jié)點都是第一次出現(xiàn)的節(jié)點，不用檢查并修正指向父節(jié)點的指針。是第一次出現(xiàn)的節(jié)點，不用檢查并修正指向父節(jié)點的指針。 (3) 在第(6)步針對M中子節(jié)點的不同情況進展處置時，假設(shè)發(fā)生當?shù)诜N情況，那么，這個M中的節(jié)點終究應(yīng)該作為哪一個節(jié)點的后繼節(jié)點呢？普通是由原始節(jié)點到該節(jié)點途徑上所付出的代價來決議的，哪一條路經(jīng)付出的代價小，相應(yīng)的節(jié)點就作為它的父節(jié)點。所謂由原始節(jié)點到該節(jié)點途徑上的代價是指這條路經(jīng)上的一切有向邊的代價之和。 假設(shè)發(fā)生第種情況，除了需求確定該子節(jié)點指向父節(jié)點的指針外，還需求確定其后繼節(jié)點指向父節(jié)點的指針。其根據(jù)也是由原始節(jié)點到該節(jié)

39、點的途徑上的代價。 (4) 在搜索圖中，除初始節(jié)點外，恣意一個節(jié)點都含有且只含有一個指向其父節(jié)點的指針。因此，由一切節(jié)點及其指向父節(jié)點的指針所構(gòu)成的集合是一棵樹，稱為搜索樹。 (5) 在搜索過程的第(4)步，一旦某個被調(diào)查的節(jié)點是目的節(jié)點，那么搜索過程勝利終了。由初始節(jié)點到目的節(jié)點途徑上的一切操作就構(gòu)成了該問題的解，而途徑由第(6)步所構(gòu)成的指向父節(jié)點的指針來確定。 (6) 假設(shè)搜索過程終止在第(2)步，即沒有到達目的，且Open表中已無可供擴展的節(jié)點，那么失敗終了。 根本思想根本思想 從初始節(jié)點從初始節(jié)點S0S0開場逐層向下擴展，在第開場逐層向下擴展，在第n n層節(jié)點還沒有全部搜索完層節(jié)點還

40、沒有全部搜索完之前，不進入第之前，不進入第n+1n+1層節(jié)點的搜索。層節(jié)點的搜索。OpenOpen表中的節(jié)點總是按進入的先表中的節(jié)點總是按進入的先后排序，先進入的節(jié)點排在前面，后進入的節(jié)點排在后面。后排序，先進入的節(jié)點排在前面，后進入的節(jié)點排在后面。搜索算法搜索算法 (1)(1)把初始節(jié)點把初始節(jié)點S0S0放入放入OpenOpen表中；表中； (2)(2)假設(shè)假設(shè)OpenOpen表為空，那么問題無解，失敗退出；表為空，那么問題無解，失敗退出； (3)(3)把把OpenOpen表的第一個節(jié)點取出放入表的第一個節(jié)點取出放入ClosedClosed表，并記該節(jié)點為表，并記該節(jié)點為n n； (4)(4

41、)調(diào)查節(jié)點調(diào)查節(jié)點n n能否為目的節(jié)點。假設(shè)是，那么得到問題的解，勝能否為目的節(jié)點。假設(shè)是，那么得到問題的解，勝利退出；利退出； (5)(5)假設(shè)節(jié)點假設(shè)節(jié)點n n不可擴展，那么轉(zhuǎn)第不可擴展，那么轉(zhuǎn)第(2)(2)步；步； (6)(6)擴展節(jié)點擴展節(jié)點n n，將其子節(jié)點放入，將其子節(jié)點放入OpenOpen表的尾部，并為每一個子節(jié)表的尾部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針，然后轉(zhuǎn)第點設(shè)置指向父節(jié)點的指針，然后轉(zhuǎn)第(2)(2)步。步。 4.2.2 廣度優(yōu)先和深度優(yōu)先搜索廣度優(yōu)先和深度優(yōu)先搜索1. 廣度優(yōu)先搜索廣度優(yōu)先搜索 例例4.5 八數(shù)碼難題。在八數(shù)碼難題。在33的方格棋盤上，分別放置了表有的

42、方格棋盤上，分別放置了表有數(shù)字數(shù)字1、2、3、4、5、6、7、8的八張牌，初始形狀的八張牌，初始形狀S0，目的形，目的形狀狀Sg，如以下圖所示。可以運用的操作有，如以下圖所示?？梢赃\用的操作有 空格左移，空格上移，空格右移，空格下移空格左移，空格上移，空格右移，空格下移即只允許把位于空格左、上、右、下方的牌移入空格。要求運即只允許把位于空格左、上、右、下方的牌移入空格。要求運用廣度優(yōu)先搜索戰(zhàn)略尋覓從初始形狀到目的形狀的解途徑。用廣度優(yōu)先搜索戰(zhàn)略尋覓從初始形狀到目的形狀的解途徑。 8 31 47 6 5 1 2 38 47 6 5 S0 Sg283147652831476523184765283

43、147652831647583214765283714652318476523184765281437652831457628316475283164758321476528371465832147658132476528374615283714651238476512378465123847652341876528143765283145762836417528316754S0123456789101112131415161718192021222324252627Sg算法描畫算法描畫 (1) 把初始節(jié)點把初始節(jié)點S0放入放入Open表中；表中； (2) 假設(shè)假設(shè)Open表為空，那么問題無解

44、表為空，那么問題無解 ，失敗退出；，失敗退出； (3) 把把Open表的第一個節(jié)點取出放入表的第一個節(jié)點取出放入Closed表，并記該節(jié)點為表，并記該節(jié)點為n； (4) 調(diào)查節(jié)點調(diào)查節(jié)點n能否為目的節(jié)點。假設(shè)是，那么得到問題的解，勝利退出；能否為目的節(jié)點。假設(shè)是，那么得到問題的解，勝利退出； (5) 假設(shè)節(jié)點假設(shè)節(jié)點n不可擴展，那么轉(zhuǎn)第不可擴展，那么轉(zhuǎn)第(2)步；步； (6) 擴展節(jié)點擴展節(jié)點n，將其子節(jié)點放入，將其子節(jié)點放入Open表的首部，并為每一個子節(jié)點設(shè)置表的首部，并為每一個子節(jié)點設(shè)置 指向父節(jié)點的指針，然后轉(zhuǎn)第指向父節(jié)點的指針，然后轉(zhuǎn)第(2)步。步。 4.2.2 廣度優(yōu)先和深度優(yōu)先搜

45、索廣度優(yōu)先和深度優(yōu)先搜索2. 深度優(yōu)先搜索深度優(yōu)先搜索根本思想根本思想 從初始節(jié)點從初始節(jié)點S0開場，在其子節(jié)點中選擇一個最新生成的節(jié)點進展調(diào)查，開場，在其子節(jié)點中選擇一個最新生成的節(jié)點進展調(diào)查，假設(shè)該子節(jié)點不是目的節(jié)點且可以擴展，那么擴展該子節(jié)點，然后再在此假設(shè)該子節(jié)點不是目的節(jié)點且可以擴展，那么擴展該子節(jié)點，然后再在此子節(jié)點的子節(jié)點中選擇一個最新生成的節(jié)點進展調(diào)查，依此向下搜索，直子節(jié)點的子節(jié)點中選擇一個最新生成的節(jié)點進展調(diào)查，依此向下搜索，直到某個子節(jié)點既不是目的節(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進到某個子節(jié)點既不是目的節(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進展調(diào)查。展調(diào)查。28

46、31476528314765231847652831476528316475283164752831647528316754283167542816375428163754S0123456八數(shù)碼難題的深度優(yōu)先搜索如右圖八數(shù)碼難題的深度優(yōu)先搜索如右圖 一種改良的深度優(yōu)先算法是有界深度一種改良的深度優(yōu)先算法是有界深度優(yōu)先搜索算法，深度限制為優(yōu)先搜索算法，深度限制為dm例例4.6 八數(shù)碼難題八數(shù)碼難題 在代價樹中，可以用在代價樹中，可以用g(n)表示從初始節(jié)點表示從初始節(jié)點S0到節(jié)點到節(jié)點n的代價，用的代價，用c(n1, n2)表示從父節(jié)點表示從父節(jié)點n1到其子節(jié)點到其子節(jié)點n2的代價。這樣，對節(jié)點

47、的代價。這樣，對節(jié)點n2的代價有：的代價有：g(n2)=g(n1)+c(n1, n2)。代價樹搜索的目的是為了找到最正確解，即找到。代價樹搜索的目的是為了找到最正確解，即找到一條代價最小的解途徑。一條代價最小的解途徑。 4.2.3 代價樹搜索代價樹搜索1. 代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索算法：代價樹的廣度優(yōu)先搜索算法： (1) 把初始節(jié)點把初始節(jié)點S0放入放入Open表中，置表中，置S0的代價的代價g(S0)=0； (2) 假設(shè)假設(shè)Open表為空，那么問題無解表為空，那么問題無解 ，失敗退出；，失敗退出； (3) 把把Open表的第一個節(jié)點取出放入表的第一個節(jié)點取

48、出放入Closed表，并記該節(jié)點為表，并記該節(jié)點為n； (4) 調(diào)查節(jié)點調(diào)查節(jié)點n能否為目的。假設(shè)是，那么找到了問題的解，勝利退出；能否為目的。假設(shè)是，那么找到了問題的解，勝利退出； (5) 假設(shè)節(jié)點假設(shè)節(jié)點n不可擴展，那么轉(zhuǎn)第不可擴展，那么轉(zhuǎn)第(2)步；步； (6) 擴展節(jié)點擴展節(jié)點n，生成其子節(jié)點，生成其子節(jié)點ni(i=1, 2, )，將這些子節(jié)點放入，將這些子節(jié)點放入Open表表中，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針。按如下公式：中，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針。按如下公式： g(ni)=g(n)+c(ni) i=1,2,.計算各子結(jié)點的代價，并根據(jù)各子結(jié)點的代價對計算各子結(jié)點

49、的代價，并根據(jù)各子結(jié)點的代價對Open表中的全部結(jié)點按表中的全部結(jié)點按由小到大的順序排序。然后轉(zhuǎn)第由小到大的順序排序。然后轉(zhuǎn)第(2)步。步。 例例4.7 4.7 城市交通問題。設(shè)有城市交通問題。設(shè)有5 5個城市，它們之間的交通線路如左個城市，它們之間的交通線路如左圖所示，圖中的數(shù)字表示兩個城市之間的交通費用，即代價。用代圖所示，圖中的數(shù)字表示兩個城市之間的交通費用，即代價。用代價樹的廣度優(yōu)先搜索，求從價樹的廣度優(yōu)先搜索，求從A A市出發(fā)到市出發(fā)到E E市，費用最小的交通道路。市，費用最小的交通道路。 ABCDE434523245AC1B1D1D2E1E2B2C2E3343423城市交通圖城市交

50、通圖 城市交通圖的代價樹城市交通圖的代價樹 解：代價樹如右圖所示。其中，解：代價樹如右圖所示。其中，紅線為最優(yōu)解，其代價為紅線為最優(yōu)解，其代價為84.2.3 代價樹搜索代價樹搜索2.代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索算法：代價樹的深度優(yōu)先搜索算法： (1) 把初始節(jié)點把初始節(jié)點S0放入放入Open表中，置表中，置S0的代價的代價g(S0)=0； (2) 假設(shè)假設(shè)Open表為空，那么問題無解表為空，那么問題無解 ，失敗退出；，失敗退出； (3) 把把Open表的第一個節(jié)點取出放入表的第一個節(jié)點取出放入Closed表，并記該節(jié)點表，并記該節(jié)點為為n； (4) 調(diào)查節(jié)點調(diào)查

51、節(jié)點n能否為目的節(jié)點。假設(shè)是，那么找到了問題的能否為目的節(jié)點。假設(shè)是，那么找到了問題的解，勝利退出；解，勝利退出； (5) 假設(shè)節(jié)點假設(shè)節(jié)點n不可擴展，那么轉(zhuǎn)第不可擴展，那么轉(zhuǎn)第(2)步；步； (6) 擴展節(jié)點擴展節(jié)點n，生成其子節(jié)點，生成其子節(jié)點ni(i=1, 2, )，將這些子節(jié)點，將這些子節(jié)點按邊代價由小到大放入按邊代價由小到大放入Open表的首部，并為每一個子節(jié)點設(shè)置表的首部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針。然后轉(zhuǎn)第指向父節(jié)點的指針。然后轉(zhuǎn)第(2)步。步。v搜索的根本概念搜索的根本概念v形狀空間的盲目搜索形狀空間的盲目搜索v 形狀空間的啟發(fā)式搜索形狀空間的啟發(fā)式搜索v與與/或樹的

52、盲目搜索或樹的盲目搜索v與與/或樹的啟發(fā)式搜索或樹的啟發(fā)式搜索v博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索第第4章章 搜索戰(zhàn)略搜索戰(zhàn)略4.3 形狀空間的啟發(fā)式搜索形狀空間的啟發(fā)式搜索4.3.1 啟發(fā)性信息和估價函數(shù)啟發(fā)性信息和估價函數(shù)4.3.2 A算法算法4.3.3 A*算法算法4.3.4 A*算法運用舉例算法運用舉例 啟發(fā)性信息的概念啟發(fā)性信息的概念 啟發(fā)性信息是指那種與詳細問題求解過程有關(guān)的，并啟發(fā)性信息是指那種與詳細問題求解過程有關(guān)的，并可指點搜索過程朝著最有希望方向前進的控制信息?？芍更c搜索過程朝著最有希望方向前進的控制信息。 啟發(fā)性信息的種類啟發(fā)性信息的種類 有效地協(xié)助確定擴展節(jié)點的信息；

53、有效地協(xié)助確定擴展節(jié)點的信息； 有效的協(xié)助決議哪些后繼節(jié)點應(yīng)被生成的信息；有效的協(xié)助決議哪些后繼節(jié)點應(yīng)被生成的信息； 能決議在擴展一個節(jié)點時哪些節(jié)點應(yīng)從搜索樹上刪能決議在擴展一個節(jié)點時哪些節(jié)點應(yīng)從搜索樹上刪除的信息。除的信息。 啟發(fā)性信息的作用啟發(fā)性信息的作用 啟發(fā)信息的啟發(fā)才干越強，擴展的無用結(jié)點越少。啟發(fā)信息的啟發(fā)才干越強，擴展的無用結(jié)點越少。4.3.1 啟發(fā)性信息和估價函數(shù)啟發(fā)性信息和估價函數(shù)1. 啟發(fā)性信息啟發(fā)性信息 估價函數(shù)用來估計節(jié)點重要性的函數(shù)。估價函數(shù)估價函數(shù)用來估計節(jié)點重要性的函數(shù)。估價函數(shù)f(n)被定義為被定義為從初始節(jié)點從初始節(jié)點S0出發(fā)，約束經(jīng)過節(jié)點出發(fā)，約束經(jīng)過節(jié)點n

54、到達目的節(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. 估價函數(shù)估價函數(shù) 例例4.8 八數(shù)碼難題。設(shè)問題的初始形狀八數(shù)碼難題。設(shè)問題的初始形狀S0和目的形狀和目的形狀Sg如以下如以下圖所示，且估價函數(shù)為圖所示，且估價函數(shù)為 f(n)=d(n)+W(n)其中：

55、其中：d(n)表示節(jié)點表示節(jié)點n在搜索樹中的深度在搜索樹中的深度 W(n)表示節(jié)點表示節(jié)點n中中“不在位的數(shù)碼個數(shù)。不在位的數(shù)碼個數(shù)。請計算初始形狀請計算初始形狀S0的估價函數(shù)值的估價函數(shù)值f(S0) 解：取解：取g(n)=d(n)，h(n)=W(n)。它闡明是用從。它闡明是用從S0到到n的途徑的途徑上的單位代價表示實踐代價，用結(jié)點上的單位代價表示實踐代價，用結(jié)點n中中“不在位的數(shù)碼個不在位的數(shù)碼個數(shù)作為啟發(fā)信息。數(shù)作為啟發(fā)信息。 普通來說，某節(jié)點中的普通來說，某節(jié)點中的“不在位的數(shù)碼個數(shù)越多，闡明不在位的數(shù)碼個數(shù)越多，闡明它離目的節(jié)點越遠。它離目的節(jié)點越遠。 對初始節(jié)點對初始節(jié)點S0，由于，

56、由于d(S0)=0，W(S0)=3，因此有，因此有 f(S0)=0+3=3 2 8 31 47 6 5 1 2 38 47 6 5 S0 Sg概念：概念： 在圖搜索算法中，假設(shè)能在搜索的每一步都利用估價函數(shù)在圖搜索算法中，假設(shè)能在搜索的每一步都利用估價函數(shù)f(n)=g(n)+h(n)f(n)=g(n)+h(n)對對OpenOpen表中的節(jié)點進展排序，那么該搜索算法表中的節(jié)點進展排序，那么該搜索算法為為A A算法。算法。 由于估價函數(shù)中帶有問題本身的啟發(fā)性信息，因此，由于估價函數(shù)中帶有問題本身的啟發(fā)性信息，因此，A A算算法也被稱為啟發(fā)式搜索算法。法也被稱為啟發(fā)式搜索算法。類型：類型： 可根據(jù)搜

57、索過程中選擇擴展節(jié)點的范圍，將啟發(fā)式搜索算可根據(jù)搜索過程中選擇擴展節(jié)點的范圍，將啟發(fā)式搜索算法分為全局擇優(yōu)搜索算法和部分擇優(yōu)搜索算法。法分為全局擇優(yōu)搜索算法和部分擇優(yōu)搜索算法。 全局擇優(yōu)：全局擇優(yōu)： 從從OpenOpen表的一切節(jié)點中選擇一個估價函數(shù)值表的一切節(jié)點中選擇一個估價函數(shù)值最小的一個進展擴展。最小的一個進展擴展。 部分擇優(yōu)：僅從剛生成的子節(jié)點中選擇一個估價函數(shù)值最部分擇優(yōu)：僅從剛生成的子節(jié)點中選擇一個估價函數(shù)值最小的一個進展擴展。小的一個進展擴展。4.3.2 A算法算法全局擇優(yōu)搜索全局擇優(yōu)搜索A A算法描畫：算法描畫： (1) (1)把初始節(jié)點把初始節(jié)點S0S0放入放入OpenOpe

58、n表中，表中，f(S0)=g(S0)+h(S0)f(S0)=g(S0)+h(S0)； (2) (2)假設(shè)假設(shè)OpenOpen表為空，那么問題無解表為空，那么問題無解 ，失敗退出；，失敗退出； (3) (3)把把OpenOpen表的第一個節(jié)點取出放入表的第一個節(jié)點取出放入ClosedClosed表，并記該節(jié)點為表，并記該節(jié)點為n n； (4) (4)調(diào)查節(jié)點調(diào)查節(jié)點n n能否為目的節(jié)點。假設(shè)是，那么找到了問題的解，勝能否為目的節(jié)點。假設(shè)是，那么找到了問題的解，勝利退出；利退出； (5) (5)假設(shè)節(jié)點假設(shè)節(jié)點n n不可擴展，那么轉(zhuǎn)第不可擴展，那么轉(zhuǎn)第(2)(2)步；步； (6) (6)擴展節(jié)點擴

59、展節(jié)點n n，生成其子節(jié)點，生成其子節(jié)點ni(i=1, 2, )ni(i=1, 2, )，計算每一個子節(jié)點，計算每一個子節(jié)點的估價值的估價值f(ni)(i=1, 2, )f(ni)(i=1, 2, )，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針，然后將這些子節(jié)點放入針，然后將這些子節(jié)點放入OpenOpen表中；表中； (7) (7)根據(jù)各節(jié)點的估價函數(shù)值，對根據(jù)各節(jié)點的估價函數(shù)值，對OpenOpen表中的全部節(jié)點按從小到大表中的全部節(jié)點按從小到大的順序重新進展排序；的順序重新進展排序； (8) (8)轉(zhuǎn)第轉(zhuǎn)第(2)(2)步。步。 4.3.2 A算法算法 例例4.9

60、 八數(shù)碼難題。設(shè)問題的初始形狀八數(shù)碼難題。設(shè)問題的初始形狀S0和目的形狀和目的形狀Sg如下如下圖，估價函數(shù)與例圖，估價函數(shù)與例4.8一樣。請用全局擇優(yōu)搜索處理該問題。一樣。請用全局擇優(yōu)搜索處理該問題。 解：該問題的全局擇優(yōu)搜索樹如以下圖所示。在該圖中，每解：該問題的全局擇優(yōu)搜索樹如以下圖所示。在該圖中，每個節(jié)點旁邊的數(shù)字是該節(jié)點的估價函數(shù)值。個節(jié)點旁邊的數(shù)字是該節(jié)點的估價函數(shù)值。 例 如 ， 對 節(jié) 點例 如 ， 對 節(jié) 點 S 2 ， 其 估 價 函 數(shù) 值 的 計 算 為 ：， 其 估 價 函 數(shù) 值 的 計 算 為 ：f(S2)=d(S2)+W(S2) =1+3=4 2 8 31 47