人工智能原理及其應(yīng)用編著電子教案ai4章

1、1搜索是人工智能中的一個(gè)基本問題，并與推理密切相關(guān)，搜索是人工智能中的一個(gè)基本問題，并與推理密切相關(guān)，搜索策略的優(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 搜索的含義搜索的含義適用情況：適用情況： 不良結(jié)構(gòu)或非結(jié)構(gòu)化問題

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

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

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

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

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

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

8、部可能所在的鋼針號(hào)。全部可能的問題狀態(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)和目標(biāo)狀態(tài)二階梵塔問題的初始狀態(tài)和目標(biāo)狀態(tài)問題的初始狀態(tài)集合問題的初始狀態(tài)集合為為S=S0 目標(biāo)狀態(tài)集合目標(biāo)狀態(tài)集合為為G=S4, S5 初始狀態(tài)初始狀態(tài)S0和目標(biāo)狀態(tài)和目標(biāo)狀態(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號(hào)鋼針移到號(hào)鋼針移到j(luò)號(hào)鋼針上；號(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)

10、B(3, 2) 根據(jù)上述根據(jù)上述9種可能的狀態(tài)和種可能的狀態(tài)和12種操作，可構(gòu)成二階梵塔問題的種操作，可構(gòu)成二階梵塔問題的狀態(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é)點(diǎn)從初始節(jié)點(diǎn)(1, 1)到目標(biāo)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)(2, 2)及及(3, 3)的任何一條路徑都是問題的一的任何一條路徑都是問題的一個(gè)解。其中，最短的路徑長度是個(gè)解。其中，最短的路徑長度是3，它由，它由3個(gè)操作組成。例如，從個(gè)操作組成。例如，從 (1, 1)開始，開始，通過使用操作通過使用操

11、作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)10 例例4.2 修道士修道士(Missionaries)和野人和野人(Cannibals)問題問題(簡稱簡稱M-C問題問題)。 設(shè)在河的一岸有三個(gè)野人、三個(gè)修道士和一條船，修道士想設(shè)在河的一岸有三個(gè)野人、三個(gè)修道士和一條船，修道士想用這條船把所有的人運(yùn)到河對(duì)岸，但受以下條件的約束：用這條船把所有的人運(yùn)到河對(duì)岸，但受以下條件的約束： 一是修道士和野人都會(huì)劃船，但每次船上至多可載兩個(gè)人；一是修道

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

13、慮船在左岸還是在考慮兩岸的修道士人數(shù)和野人數(shù)，還需要考慮船在左岸還是在右岸。從而可用一個(gè)三元組來表示狀態(tài)右岸。從而可用一個(gè)三元組來表示狀態(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)，還需要考慮可進(jìn)行的操作。有了這些狀態(tài)，還需要考慮可進(jìn)行的操作。 操作操作是指用船把修道士或野人從河的左岸運(yùn)到右岸，或從河的是指用船把修道士或野人從河的左岸運(yùn)到右岸，或從河的右岸運(yùn)到左岸。右岸運(yùn)到左岸。 每個(gè)操作都應(yīng)當(dāng)滿足如下條件：每個(gè)操作都應(yīng)當(dāng)滿足如下條件： 一是一是船至少有一個(gè)人（船至少有一個(gè)人（m或或c）操作，離開岸邊的）操作，離開岸邊的m和和c的減少數(shù)的減少數(shù)目應(yīng)該等于到達(dá)岸邊的目應(yīng)該等于到達(dá)岸邊的m和和c的增加數(shù)目；的增加數(shù)目； 二是二是每次操作船上人數(shù)不得超過每次操作船上人數(shù)不得超過2

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

17、擇： 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, m=0或或3, c1 b=0, c=c-1 Q01 b=0, m=0或或3，c2 b=1, c=c+1 14abc 例例4.3 猴子摘香蕉問題。猴子摘香蕉問題。在討論謂詞邏輯知識(shí)表示時(shí)，我們?cè)谟懻撝^詞邏輯知識(shí)表示時(shí)，我們?cè)岬竭^這一問題，現(xiàn)在用狀態(tài)空間法來解決這一問題。曾提到過這一問題，現(xiàn)在用狀態(tài)空間法來解決這一問題。 解：解：問題的狀態(tài)可用

18、問題的狀態(tài)可用4元組元組 （w, x, y, z）表示。其中：表示。其中： w表示猴子的水平位置；表示猴子的水平位置； x表示箱子的水平位置；表示箱子的水平位置； y表示猴子是否在箱子上，表示猴子是否在箱子上，當(dāng)猴子在箱子上時(shí)，當(dāng)猴子在箱子上時(shí)，y取取1，否則否則y取取0； z表示猴子是否拿到香蕉，表示猴子是否拿到香蕉，當(dāng)拿到香蕉時(shí)當(dāng)拿到香蕉時(shí)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)

19、S3: (c, c, 1, 0) S4: (c, c, 1, 1) 目標(biāo)狀態(tài)目標(biāo)狀態(tài)允許的操作為允許的操作為 Goto(u)：猴子走到位置：猴子走到位置u，即，即 (w, x, 0, 0)(u, x, 0, 0) Pushbox(v): 猴子推著箱子到水平位置猴子推著箱子到水平位置v，即，即 (x, x, 0, 0)(v, v, 0, 0) Climbbox: 猴子爬上箱子，即猴子爬上箱子，即 (x, x, 0, 0)(x, x, 1, 0) Grasp；猴子拿到香蕉，即；猴子拿到香蕉，即 (c, c, 1, 0 )(c, c, 1, 1) 這個(gè)問題的狀態(tài)空間圖如下圖所示。不難看出，由初始狀這

20、個(gè)問題的狀態(tài)空間圖如下圖所示。不難看出，由初始狀態(tài)變?yōu)槟繕?biāo)狀態(tài)的操作序列為：態(tài)變?yōu)槟繕?biāo)狀態(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 目標(biāo)狀態(tài) 猴子摘香蕉問題的狀態(tài)空間圖解序列為：解序列為： Goto(b), Pushbox(c), Climbbox, GraspPushbox(c)ClimbboxClimbboxP

21、ushbox(c)Pushbox(a)Pushbox(a)17基本思想基本思想 當(dāng)一問題較復(fù)雜時(shí)，可通過分解或變換，將其轉(zhuǎn)化為一系列較簡當(dāng)一問題較復(fù)雜時(shí)，可通過分解或變換，將其轉(zhuǎn)化為一系列較簡單的子問題，然后通過對(duì)這些子問題的求解來實(shí)現(xiàn)對(duì)原問題的求解。單的子問題，然后通過對(duì)這些子問題的求解來實(shí)現(xiàn)對(duì)原問題的求解。 分解分解 如果一個(gè)問題如果一個(gè)問題P可以歸約為一組子問題可以歸約為一組子問題P1,P2,Pn，并且只有當(dāng)所有，并且只有當(dāng)所有子問題子問題Pi都有解時(shí)原問題都有解時(shí)原問題P才有解，任何一個(gè)子問題才有解，任何一個(gè)子問題Pi無解都會(huì)導(dǎo)致原無解都會(huì)導(dǎo)致原問題問題P無解，則稱此種歸約為問題的分解

22、。無解，則稱此種歸約為問題的分解。 即分解所得到的子問題的即分解所得到的子問題的“與與”與原問題與原問題P等價(jià)。等價(jià)。等價(jià)變換等價(jià)變換 如果一個(gè)問題如果一個(gè)問題P可以歸約為一組子問題可以歸約為一組子問題P1,P2,Pn，并且子問題，并且子問題Pi中只要有一個(gè)有解則原問題中只要有一個(gè)有解則原問題P就有解，只有當(dāng)所有子問題就有解，只有當(dāng)所有子問題Pi都無解時(shí)都無解時(shí)原問題原問題P才無解，稱此種歸約為問題的等價(jià)變換，簡稱變換。才無解，稱此種歸約為問題的等價(jià)變換，簡稱變換。 即變換所得到的子問題的即變換所得到的子問題的“或或”與原問題與原問題P等價(jià)。等價(jià)。4.1.3 問題歸約法問題歸約法1. 問題的分

23、解與等價(jià)變換問題的分解與等價(jià)變換18PP1 P2 P3 與樹與樹P1 P2 P3 或樹或樹PPP1 P2 P3 P12 P12 P31 P32 P33 與與/或樹或樹(1)與樹與樹 分解分解(2) 或樹或樹 等價(jià)變換等價(jià)變換(3) 與與/或樹或樹4.1.3 問題歸約法問題歸約法2. 問題的與問題的與/或樹表示或樹表示19(4) 端節(jié)點(diǎn)與終止節(jié)點(diǎn)端節(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ì)應(yīng)的節(jié)；本原問題所對(duì)應(yīng)的節(jié)點(diǎn)稱為點(diǎn)稱為終止節(jié)點(diǎn)終止節(jié)點(diǎn)?？梢?，終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)卻不一定是。可見，終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)卻不

24、一定是終止節(jié)點(diǎn)。終止節(jié)點(diǎn)。(5) 可解節(jié)點(diǎn)與不可解節(jié)點(diǎn)可解節(jié)點(diǎn)與不可解節(jié)點(diǎn) 在與在與/或樹中，滿足以下三個(gè)條件之一的節(jié)點(diǎn)為或樹中，滿足以下三個(gè)條件之一的節(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)，當(dāng)其子節(jié)點(diǎn)中至少有一個(gè)為可解節(jié)點(diǎn)時(shí)，則該或節(jié)點(diǎn)節(jié)點(diǎn)，當(dāng)其子節(jié)點(diǎn)中至少有一個(gè)為可解節(jié)點(diǎn)時(shí)，則該或節(jié)點(diǎn)就是可解節(jié)點(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)。 同樣，可用類似的方法定義同樣，可用類似的方法定義不可解節(jié)點(diǎn)：不可解節(jié)點(diǎn)： 不為終止節(jié)點(diǎn)

25、的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)。不為終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)。 對(duì)對(duì)“或或”節(jié)點(diǎn)，若其全部子節(jié)點(diǎn)都為不可解節(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)，只要其子節(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)。20Pt t t 解樹解樹(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)的子樹為解樹。始問題）為可解節(jié)點(diǎn)的子樹為解樹。在解樹中一定包含初始節(jié)點(diǎn)。在解樹中一

26、定包含初始節(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)的過程。這一過程涉及到搜索的問題，的過程。這一過程涉及到搜索的問題，對(duì)于與對(duì)于與/或樹的搜索將在后面詳細(xì)討論?；驑涞乃阉鲗⒃诤竺嬖敿?xì)

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

28、i 代表金片代表金片C所在的鋼針號(hào)所在的鋼針號(hào) j 代表金片代表金片B所在的鋼針號(hào)所在的鋼針號(hào) k 代表金片代表金片A所在的鋼針號(hào)所在的鋼針號(hào)1231234.1.3 問題歸約法問題歸約法2. 問題的與問題的與/或樹表示或樹表示22利用問題歸約方法，原問題可分解為以下利用問題歸約方法，原問題可分解為以下三個(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)問題。即號(hào)鋼針上的單金片移動(dòng)問題。即 (1, 2, 2)(3, 2, 2) (3) 把金

29、片把金片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) (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個(gè)終止節(jié)點(diǎn)，它們分別對(duì)應(yīng)著個(gè)終止節(jié)點(diǎn)，它們分別對(duì)應(yīng)著7個(gè)本原問題。如果把個(gè)本原問題。如果把這些本原問題從左至右排列起來，即得到了原始問題的解：這些本原問題從左至右排列起來，即得到了原始問題的解： (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)先搜索代價(jià)樹搜索代價(jià)樹搜索25狀態(tài)空間搜索的基本思想狀態(tài)空間搜索的基本思想 先把問題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對(duì)其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)，先把問題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對(duì)其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)，然后檢查問題的目標(biāo)狀態(tài)是否出現(xiàn)在這些

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

33、 一般圖搜索過程一般圖搜索過程算法的數(shù)據(jù)結(jié)構(gòu)和符號(hào)約定算法的數(shù)據(jù)結(jié)構(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：用表示問題的初始狀態(tài)：用表示問題的初始狀態(tài) G：表示搜索過程所得到的搜索圖：表示搜索過程所得到的搜索圖 M：表示當(dāng)前擴(kuò)展節(jié)點(diǎn)新生成的且不為自己先輩的子節(jié)點(diǎn)集。：表示當(dāng)前擴(kuò)展節(jié)點(diǎn)新生成的且不為自己先輩的子節(jié)點(diǎn)集。26一般圖搜索過程一般圖搜索過程 (1) 把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入Open表，并建立目前僅包含表，并建立目前僅包含S0的圖的圖G； (2) 檢查檢查Op

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

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

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

37、例如，廣度優(yōu)先搜索把先生成的子節(jié)點(diǎn)排在前面，而深度優(yōu)先搜索則把后生成的子節(jié)先搜索把先生成的子節(jié)點(diǎn)排在前面，而深度優(yōu)先搜索則把后生成的子節(jié)點(diǎn)排在前面。點(diǎn)排在前面。 (2) 在第在第(5)步對(duì)節(jié)點(diǎn)步對(duì)節(jié)點(diǎn)n擴(kuò)展后，生成并記入擴(kuò)展后，生成并記入M的子節(jié)點(diǎn)有以下三種的子節(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)

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

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

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

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

42、節(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)把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入Open表中；表中； (2)如果如果Open表為空，則問題無解，失敗退出；表為空，則問題無解，失敗退出； (3)把把Open表的第一個(gè)節(jié)點(diǎn)取出放入表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為表，并記該節(jié)點(diǎn)為n； (4)考察節(jié)點(diǎn)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問題的解，成功退出；是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問題的解，成功退出； (5)若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第(2)步；步； (6)擴(kuò)展節(jié)點(diǎn)

43、擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入，將其子節(jié)點(diǎn)放入Open表的尾部，并為每一個(gè)子節(jié)表的尾部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第(2)步。步。 4.2.2 廣度優(yōu)先和深度優(yōu)先搜索廣度優(yōu)先和深度優(yōu)先搜索1. 廣度優(yōu)先搜索廣度優(yōu)先搜索30 例例4.5 八數(shù)碼難題。在八數(shù)碼難題。在33的方格棋盤上，分別放置了表有的方格棋盤上，分別放置了表有數(shù)字?jǐn)?shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)的八張牌，初始狀態(tài)S0，目標(biāo)狀，目標(biāo)狀態(tài)態(tài)Sg，如下圖所示?？梢允褂玫牟僮饔?，如下圖所示?？梢允褂玫牟僮饔?空格左移，空格上移，空格右移，空格下移空格左移，空格上移，空格右移

44、，空格下移即只允許把位于空格左、上、右、下方的牌移入空格。要求應(yīng)即只允許把位于空格左、上、右、下方的牌移入空格。要求應(yīng)用廣度優(yōu)先搜索策略尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解路徑用廣度優(yōu)先搜索策略尋找從初始狀態(tài)到目標(biāo)狀態(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 3

45、1 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) (

46、1) 把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入Open表中；表中； (2) (2) 如果如果OpenOpen表為空，則問題無解表為空，則問題無解 ，失敗退出；，失敗退出； (3) (3) 把把OpenOpen表的第一個(gè)節(jié)點(diǎn)取出放入表的第一個(gè)節(jié)點(diǎn)取出放入ClosedClosed表，并記該節(jié)點(diǎn)為表，并記該節(jié)點(diǎn)為n n； (4) (4) 考察節(jié)點(diǎn)考察節(jié)點(diǎn)n n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問題的解，成功退出；是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問題的解，成功退出； (5) (5) 若節(jié)點(diǎn)若節(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)

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

48、最新生成的節(jié)點(diǎn)進(jìn)行考察，依此向下搜索，直到某個(gè)子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)，又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考個(gè)子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)，又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察察。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)先搜索如右圖 一種改進(jìn)的深度優(yōu)先算法是有界深度一

49、種改進(jìn)的深度優(yōu)先算法是有界深度優(yōu)先搜索算法，深度限制為優(yōu)先搜索算法，深度限制為dm例例4.6 八數(shù)碼難題八數(shù)碼難題34 在代價(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)的代價(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à)樹的

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

51、成其子節(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)的代價(jià)，并根據(jù)各子結(jié)點(diǎn)的代價(jià)對(duì)Open表中的全部結(jié)點(diǎn)按表中的全部結(jié)點(diǎn)按由小到大的順序排序。然后轉(zhuǎn)第由小到大的順序排序。然后轉(zhuǎn)第(2)步。步。35 例例4.7 城市交通問題。設(shè)有城市交通問題。設(shè)有5個(gè)城市，它們之間的交通線路如左圖個(gè)城市，它們之間的交通線路如左圖所示，圖中的數(shù)字表示兩個(gè)城市之間的交通費(fèi)用，即

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

53、初始節(jié)點(diǎn)S0放入放入Open表中，置表中，置S0的代價(jià)的代價(jià)g(S0)=0； (2) 如果如果Open表為空，則問題無解表為空，則問題無解 ，失敗退出；，失敗退出； (3) 把把Open表的第一個(gè)節(jié)點(diǎn)取出放入表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)表，并記該節(jié)點(diǎn)為為n； (4) 考察節(jié)點(diǎn)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則找到了問題的解，是否為目標(biāo)節(jié)點(diǎn)。若是，則找到了問題的解，成功退出；成功退出； (5) 若節(jié)點(diǎn)若節(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à)由小到大

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

55、啟發(fā)性信息是指那種與具體問題求解過程有關(guān)的，并可指導(dǎo)搜索過程朝著最有希望方向前進(jìn)的控制信息?？芍笇?dǎo)搜索過程朝著最有希望方向前進(jìn)的控制信息。 啟發(fā)性信息的種類啟發(fā)性信息的種類 有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息；有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息； 有效的幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成的信息；有效的幫助決定哪些后繼節(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ā)性信息和估

56、價(jià)函數(shù)1. 啟發(fā)性信息啟發(fā)性信息40 估價(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到達(dá)目標(biāo)節(jié)點(diǎn)到達(dá)目標(biāo)節(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到目標(biāo)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計(jì)代價(jià)。的最優(yōu)路徑的估計(jì)代價(jià)。 4.3.1 啟發(fā)性信息和估價(jià)函數(shù)啟發(fā)性信息和估價(jià)函數(shù)

57、2. 估價(jià)函數(shù)估價(jià)函數(shù) 例例4.8 八數(shù)碼難題。設(shè)問題的初始狀態(tài)八數(shù)碼難題。設(shè)問題的初始狀態(tài)S0和目標(biāo)狀態(tài)和目標(biāo)狀態(tài)Sg如下圖如下圖所示，且估價(jià)函數(shù)為所示，且估價(jià)函數(shù)為 f(n)=d(n)+W(n)其中：其中：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ì)算初始狀態(tài)請(qǐng)計(jì)算初始狀態(tài)S0的估價(jià)函數(shù)值的估價(jià)函數(shù)值f(S0)41 解：解：取取g(n)=d(n)，h(n)=W(n)。它說明是用從。它說明是用從S0到到n的路徑上的路徑上的單位代價(jià)表示實(shí)際代價(jià)，用結(jié)點(diǎn)的單位代價(jià)表示實(shí)際代價(jià)，用結(jié)點(diǎn)n中中“不在位不在位”的

58、數(shù)碼個(gè)數(shù)的數(shù)碼個(gè)數(shù)作為啟發(fā)信息。作為啟發(fā)信息。 一般來說，某節(jié)點(diǎn)中的一般來說，某節(jié)點(diǎn)中的“不在位不在位”的數(shù)碼個(gè)數(shù)越多，說明的數(shù)碼個(gè)數(shù)越多，說明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn)。它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn)。 對(duì)初始節(jié)點(diǎn)對(duì)初始節(jié)點(diǎn)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概念：概念： 在圖搜索算法中，如果能在搜索的每一步都利用估價(jià)函數(shù)在圖搜索算法中，如果能在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)對(duì)對(duì)Open表中的節(jié)點(diǎn)進(jìn)行排序，則該搜索算法為表中的節(jié)點(diǎn)進(jìn)行排序，則該搜索算法為A算法。算法。 由

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

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