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

1、搜索是人工智能中的一個(gè)根本問題，并與推理親密相關(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)成的算法可供求解運(yùn)用。算法可供求解運(yùn)用。概念：概念： 依托閱歷，利用已有知識(shí)，根據(jù)問題的實(shí)踐情況，不斷尋覓可利用知識(shí)，依托閱歷，利用已有知識(shí)，根據(jù)問題的實(shí)踐

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

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

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

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

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

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

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

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

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

12、請(qǐng)規(guī)劃一個(gè)確保修道士和野人都能過河，且沒有修道士被野人吃掉的平安過河方案。和野人都能過河，且沒有修道士被野人吃掉的平安過河方案。 4.1.2 形狀空間法形狀空間法3. 形狀空間的例子形狀空間的例子(5/11) 解：首先選取描畫問題形狀的方法。在這個(gè)問題中，需求解：首先選取描畫問題形狀的方法。在這個(gè)問題中，需求思索兩岸的修道士人數(shù)和野人數(shù)，還需求思索船在左岸還是在思索兩岸的修道士人數(shù)和野人數(shù)，還需求思索船在左岸還是在右岸。從而可用一個(gè)三元組來表示形狀右岸。從而可用一個(gè)三元組來表示形狀 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)有了這些形狀，還需求思索可進(jìn)展的操作。有了這些形狀，還需求思索可進(jìn)展的操作。 操作是指用船把修道士或野人從河的左岸運(yùn)到右岸，或從河的右岸運(yùn)到左岸。操作是指用船

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

16、劃了運(yùn)用此操作所產(chǎn)生的結(jié)果。 操作的表示：操作的表示： 用符號(hào)用符號(hào)Pij表示從左岸到右岸的運(yùn)人操作表示從左岸到右岸的運(yùn)人操作 用符號(hào)用符號(hào)Qij表示從右岸到左岸的操作表示從右岸到左岸的操作其中：其中： i表示船上的修道士人數(shù)表示船上的修道士人數(shù) j表示船上的野人數(shù)表示船上的野人數(shù)操作集操作集 本問題有本問題有10種操作可供選擇：種操作可供選擇： F=P01, P10, P11, P02, P20,Q01, Q10, Q11, Q02, Q20 下面以下面以P01和和Q01為例來闡明這些操作的條件和動(dòng)作。為例來闡明這些操作的條件和動(dòng)作。 操作符號(hào)操作符號(hào) 條件條件 動(dòng)作動(dòng)作 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 猴子摘香蕉問題。在討論謂詞邏輯知識(shí)表示時(shí)，我們?cè)岬竭^這一問題，如今用形狀空間法來處理這一問題。解：?jiǎn)栴}的形狀可用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 形狀空間法形狀空間法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) 這個(gè)問題的形狀空間圖如以下圖所示。不難看出，由初始這個(gè)問題的形狀空間圖如以下圖所示。不難看出，由初始形狀變?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)根本思想根本思想 當(dāng)一問題較復(fù)雜時(shí)，可經(jīng)過分解或變換，將其轉(zhuǎn)化為一系列較簡(jiǎn)當(dāng)一問題較復(fù)雜時(shí)，可經(jīng)過分解或變換，將其轉(zhuǎn)化為一系列較簡(jiǎn)單的子問題，然后經(jīng)過對(duì)這些子問題的求解來實(shí)現(xiàn)對(duì)原問題的求解。單的子問題，然后經(jīng)過對(duì)這些子問題的求解來實(shí)現(xiàn)對(duì)原問題的求解。 分解分解 假設(shè)一個(gè)問題假設(shè)一個(gè)問題P P可以歸約為一組子問題可以歸約為一組子問題P1,P2,PnP1,P2,Pn，并且只需當(dāng)一，并且只需當(dāng)一切子問題切子問題PiPi都有解時(shí)原問題都有解時(shí)原問題P P才有解，任何一個(gè)子問題才有解，任何

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

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

23、一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)卻不一定是點(diǎn)稱為終止節(jié)點(diǎn)?？梢?，終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)卻不一定是終止節(jié)點(diǎn)。終止節(jié)點(diǎn)。(5) 可解節(jié)點(diǎn)與不可解節(jié)點(diǎn)可解節(jié)點(diǎn)與不可解節(jié)點(diǎn) 在與在與/或樹中，滿足以下三個(gè)條件之一的節(jié)點(diǎn)為可解節(jié)點(diǎn)：或樹中，滿足以下三個(gè)條件之一的節(jié)點(diǎn)為可解節(jié)點(diǎn)： 任何終止節(jié)點(diǎn)都是可解節(jié)點(diǎn)。任何終止節(jié)點(diǎn)都是可解節(jié)點(diǎn)。 對(duì)對(duì)“或節(jié)點(diǎn)，當(dāng)其子節(jié)點(diǎn)中至少有一個(gè)為可解節(jié)點(diǎn)時(shí)，那么該或節(jié)或節(jié)點(diǎn)，當(dāng)其子節(jié)點(diǎn)中至少有一個(gè)為可解節(jié)點(diǎn)時(shí)，那么該或節(jié)點(diǎn)就是可解節(jié)點(diǎn)。點(diǎn)就是可解節(jié)點(diǎn)。 對(duì)對(duì)“與節(jié)點(diǎn)，只需當(dāng)其子節(jié)點(diǎn)全部為可解節(jié)點(diǎn)時(shí)，該與節(jié)點(diǎn)才是可與節(jié)點(diǎn)，只需當(dāng)其子節(jié)點(diǎn)全部為可解節(jié)點(diǎn)時(shí)，該與節(jié)點(diǎn)才是可解節(jié)點(diǎn)。解節(jié)點(diǎn)。

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

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

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

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

28、號(hào)鋼針上的單金片挪動(dòng)問題。即 (1, 2, 2)(3, 2, 2) (3) 把金片把金片A及及B移到移到3號(hào)鋼針的雙金片挪動(dòng)問題。即號(hào)鋼針的雙金片挪動(dòng)問題。即(3, 2, 2)( (3, 3, 3)其中，子問題其中，子問題(1)和和(3)都是一個(gè)二階梵塔問題，它們都還可以再繼續(xù)進(jìn)展分解；都是一個(gè)二階梵塔問題，它們都還可以再繼續(xù)進(jìn)展分解；子問題子問題(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個(gè)終止節(jié)點(diǎn)，它們分別對(duì)應(yīng)著個(gè)終止節(jié)點(diǎn)，它們分別對(duì)應(yīng)著7個(gè)本原問題。假設(shè)把個(gè)本原問題。假設(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 代價(jià)樹搜索代價(jià)樹搜索形狀空間搜索的根本思想形狀空間搜索的根本思想 先把問題的初始形狀

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

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

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

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

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

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

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

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

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

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

41、)調(diào)查節(jié)點(diǎn)調(diào)查節(jié)點(diǎn)n n能否為目的節(jié)點(diǎn)。假設(shè)是，那么得到問題的解，勝能否為目的節(jié)點(diǎn)。假設(shè)是，那么得到問題的解，勝利退出；利退出； (5)(5)假設(shè)節(jié)點(diǎn)假設(shè)節(jié)點(diǎn)n n不可擴(kuò)展，那么轉(zhuǎn)第不可擴(kuò)展，那么轉(zhuǎn)第(2)(2)步；步； (6)(6)擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n n，將其子節(jié)點(diǎn)放入，將其子節(jié)點(diǎn)放入OpenOpen表的尾部，并為每一個(gè)子節(jié)表的尾部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后轉(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ù)字?jǐn)?shù)字1、2、3、4、5、6、7、8的八張牌，初始形狀的八張牌，初始形狀S0，目的形，目的形狀狀Sg，如以下圖所示?？梢赃\(yùn)用的操作有，如以下圖所示?？梢赃\(yùn)用的操作有 空格左移，空格上移，空格右移，空格下移空格左移，空格上移，空格右移，空格下移即只允許把位于空格左、上、右、下方的牌移入空格。要求運(yùn)即只允許把位于空格左、上、右、下方的牌移入空格。要求運(yùn)用廣度優(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é)點(diǎn)把初始節(jié)點(diǎn)S0放入放入Open表中；表中； (2) 假設(shè)假設(shè)Open表為空，那么問題無解

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

45、索廣度優(yōu)先和深度優(yōu)先搜索2. 深度優(yōu)先搜索深度優(yōu)先搜索根本思想根本思想 從初始節(jié)點(diǎn)從初始節(jié)點(diǎn)S0開場(chǎng)，在其子節(jié)點(diǎn)中選擇一個(gè)最新生成的節(jié)點(diǎn)進(jìn)展調(diào)查，開場(chǎng)，在其子節(jié)點(diǎn)中選擇一個(gè)最新生成的節(jié)點(diǎn)進(jìn)展調(diào)查，假設(shè)該子節(jié)點(diǎn)不是目的節(jié)點(diǎn)且可以擴(kuò)展，那么擴(kuò)展該子節(jié)點(diǎn)，然后再在此假設(shè)該子節(jié)點(diǎn)不是目的節(jié)點(diǎn)且可以擴(kuò)展，那么擴(kuò)展該子節(jié)點(diǎn)，然后再在此子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個(gè)最新生成的節(jié)點(diǎn)進(jìn)展調(diào)查，依此向下搜索，直子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個(gè)最新生成的節(jié)點(diǎn)進(jìn)展調(diào)查，依此向下搜索，直到某個(gè)子節(jié)點(diǎn)既不是目的節(jié)點(diǎn)，又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)到某個(gè)子節(jié)點(diǎn)既不是目的節(jié)點(diǎn)，又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)展調(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ù)碼難題 在代價(jià)樹中，可以用在代價(jià)樹中，可以用g(n)表示從初始節(jié)點(diǎn)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)到節(jié)點(diǎn)n的代價(jià)，用的代價(jià)，用c(n1, n2)表示從父節(jié)點(diǎn)表示從父節(jié)點(diǎn)n1到其子節(jié)點(diǎn)到其子節(jié)點(diǎn)n2的代價(jià)。這樣，對(duì)節(jié)點(diǎn)

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

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

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

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

51、節(jié)點(diǎn)n能否為目的節(jié)點(diǎn)。假設(shè)是，那么找到了問題的能否為目的節(jié)點(diǎn)。假設(shè)是，那么找到了問題的解，勝利退出；解，勝利退出； (5) 假設(shè)節(jié)點(diǎn)假設(shè)節(jié)點(diǎn)n不可擴(kuò)展，那么轉(zhuǎn)第不可擴(kuò)展，那么轉(zhuǎn)第(2)步；步； (6) 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，生成其子節(jié)點(diǎn)，生成其子節(jié)點(diǎn)ni(i=1, 2, )，將這些子節(jié)點(diǎn)，將這些子節(jié)點(diǎn)按邊代價(jià)由小到大放入按邊代價(jià)由小到大放入Open表的首部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置表的首部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針。然后轉(zhuǎn)第指向父節(jié)點(diǎn)的指針。然后轉(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ā)性信息和估價(jià)函數(shù)啟發(fā)性信息和估價(jià)函數(shù)4.3.2 A算法算法4.3.3 A*算法算法4.3.4 A*算法運(yùn)用舉例算法運(yùn)用舉例 啟發(fā)性信息的概念啟發(fā)性信息的概念 啟發(fā)性信息是指那種與詳細(xì)問題求解過程有關(guān)的，并啟發(fā)性信息是指那種與詳細(xì)問題求解過程有關(guān)的，并可指點(diǎn)搜索過程朝著最有希望方向前進(jìn)的控制信息?？芍更c(diǎn)搜索過程朝著最有希望方向前進(jìn)的控制信息。 啟發(fā)性信息的種類啟發(fā)性信息的種類 有效地協(xié)助確定擴(kuò)展節(jié)點(diǎn)的信息；

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

54、到達(dá)目的節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)Sg的一切途徑的一切途徑中最小途徑代價(jià)的估計(jì)值。它的普通方式為：中最小途徑代價(jià)的估計(jì)值。它的普通方式為： f(n)=g(n)+h(n)其中，其中，g(n)是從初始節(jié)點(diǎn)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)到節(jié)點(diǎn)n的實(shí)踐代價(jià)；的實(shí)踐代價(jià)；h(n)是從節(jié)點(diǎn)是從節(jié)點(diǎn)n到目的節(jié)點(diǎn)到目的節(jié)點(diǎn)Sg的最優(yōu)途徑的估計(jì)代價(jià)。的最優(yōu)途徑的估計(jì)代價(jià)。 4.3.1 啟發(fā)性信息和估價(jià)函數(shù)啟發(fā)性信息和估價(jià)函數(shù)2. 估價(jià)函數(shù)估價(jià)函數(shù) 例例4.8 八數(shù)碼難題。設(shè)問題的初始形狀八數(shù)碼難題。設(shè)問題的初始形狀S0和目的形狀和目的形狀Sg如以下如以下圖所示，且估價(jià)函數(shù)為圖所示，且估價(jià)函數(shù)為 f(n)=d(n)+W(n)其中：

55、其中：d(n)表示節(jié)點(diǎn)表示節(jié)點(diǎn)n在搜索樹中的深度在搜索樹中的深度 W(n)表示節(jié)點(diǎn)表示節(jié)點(diǎn)n中中“不在位的數(shù)碼個(gè)數(shù)。不在位的數(shù)碼個(gè)數(shù)。請(qǐng)計(jì)算初始形狀請(qǐng)計(jì)算初始形狀S0的估價(jià)函數(shù)值的估價(jià)函數(shù)值f(S0) 解：取解：取g(n)=d(n)，h(n)=W(n)。它闡明是用從。它闡明是用從S0到到n的途徑的途徑上的單位代價(jià)表示實(shí)踐代價(jià)，用結(jié)點(diǎn)上的單位代價(jià)表示實(shí)踐代價(jià)，用結(jié)點(diǎn)n中中“不在位的數(shù)碼個(gè)不在位的數(shù)碼個(gè)數(shù)作為啟發(fā)信息。數(shù)作為啟發(fā)信息。 普通來說，某節(jié)點(diǎn)中的普通來說，某節(jié)點(diǎn)中的“不在位的數(shù)碼個(gè)數(shù)越多，闡明不在位的數(shù)碼個(gè)數(shù)越多，闡明它離目的節(jié)點(diǎn)越遠(yuǎn)。它離目的節(jié)點(diǎn)越遠(yuǎn)。 對(duì)初始節(jié)點(diǎn)對(duì)初始節(jié)點(diǎn)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è)能在搜索的每一步都利用估價(jià)函數(shù)在圖搜索算法中，假設(shè)能在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)f(n)=g(n)+h(n)對(duì)對(duì)OpenOpen表中的節(jié)點(diǎn)進(jìn)展排序，那么該搜索算法表中的節(jié)點(diǎn)進(jìn)展排序，那么該搜索算法為為A A算法。算法。 由于估價(jià)函數(shù)中帶有問題本身的啟發(fā)性信息，因此，由于估價(jià)函數(shù)中帶有問題本身的啟發(fā)性信息，因此，A A算算法也被稱為啟發(fā)式搜索算法。法也被稱為啟發(fā)式搜索算法。類型：類型： 可根據(jù)搜

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

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

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

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