1、第3章圖搜索技術(shù)3.1問(wèn)題的提出3.2狀態(tài)圖搜索3.3與或圖搜索3.4博弈圖搜索3.1問(wèn)題的提出【例3-1】圖3-3兩個(gè)四邊形【例3-2】 有如圖3-3所示的兩個(gè)四邊形ABCD和ABCD，要求證明他們?nèi)?。我們將本例?wèn)題設(shè)為Q。為解決該問(wèn)題，分別在兩個(gè)圖形中做輔助線B、D和B、D，如果我們能證明問(wèn)題Q1：ABDABD，并且能證明問(wèn)題Q2： BCDBCD，則問(wèn)題Q得到證明?！纠?-3】3.2狀態(tài)圖搜索3.2.1狀態(tài)圖搜索分類3.2.2窮舉式搜索3.2.3啟發(fā)式搜索3.2.4A算法及A*算法3.2.1狀態(tài)圖搜索有兩種最基本的搜索方式：樹式搜索線式搜索3.2.1狀態(tài)圖搜索盲目搜索就是無(wú)向?qū)У乃阉?。?/p>

2、發(fā)式搜索就是有向?qū)У乃阉?。是利用“啟發(fā)性信息”引導(dǎo)的搜索。所謂啟發(fā)性信息就是與問(wèn)題有關(guān)的有利于盡快找到問(wèn)題解的信息或知識(shí)。3.2.1狀態(tài)圖搜索樹式搜索的一般算法：Step1 把初始節(jié)點(diǎn)S0 放入OPEN表中；Step2 若OPEN表為空，則搜索失敗，退出。Step3 移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中，并冠以順序編號(hào)n；Step4 若N是目標(biāo)節(jié)點(diǎn)，則搜索成功，結(jié)束。Step5 若N不可擴(kuò)展，則轉(zhuǎn)Step2；Step6 擴(kuò)展N，生成一組子節(jié)點(diǎn)，對(duì)這組子節(jié)點(diǎn)作如下處理：3.2.2窮舉式搜索1.廣度優(yōu)先搜索算法2.深度優(yōu)先搜索3.有界深度優(yōu)先搜索1.廣度優(yōu)先搜索算法廣度優(yōu)先搜索算法：S

3、tep1 把初始節(jié)點(diǎn)S0 放入OPEN表中；Step2 若OPEN表為空，則搜索失敗，退出；Step3 取OPEN表中前面第一個(gè)節(jié)點(diǎn)N放在CLOSED表中，并冠以順序編號(hào)n；Step4 若N為目標(biāo)節(jié)點(diǎn)，則搜索成功，結(jié)束。Step5 若N不可擴(kuò)展，則轉(zhuǎn)Step2；Step6 擴(kuò)展N，將其所有未在OPEN及CLOSED表中出現(xiàn)過(guò)的子節(jié)點(diǎn)針依次放入OPEN表尾部，轉(zhuǎn)Step2。【例3-4】 用廣度優(yōu)先算法，求解八數(shù)碼問(wèn)題。 初始狀態(tài)：S0 目標(biāo)：Sg2.深度優(yōu)先搜索深度優(yōu)先搜索算法：Step1 把初始節(jié)點(diǎn)S0 放入OPEN表中；Step2 若OPEN表為空，則搜索失敗，退出；Step3 取OPEN表

4、中前面第一個(gè)節(jié)點(diǎn)N放在CLOSED表中，并冠以順序編號(hào)n；Step4 若N是目標(biāo)節(jié)點(diǎn)Sg，則搜索成功，結(jié)束。Step5 若N不可擴(kuò)展，則轉(zhuǎn)Step2；Step6 擴(kuò)展N，將其所有未在OPEN及CLOSED表中出現(xiàn)過(guò)的子節(jié)點(diǎn)配上指向N的返回指針依次放入OPEN表的首部，轉(zhuǎn)Step2。2.深度優(yōu)先搜索【例3-5】 對(duì)于八數(shù)碼問(wèn)題，應(yīng)用深度優(yōu)先搜索策略，可得如圖3-8所示的部分搜索樹（由于篇幅限制，這里未給出完整的搜索樹）。OPEN表及CLOSED表的變化過(guò)程從略。2.深度優(yōu)先搜索3.有界深度優(yōu)先搜索有界深度優(yōu)先搜索就是給出了搜索樹深度限制，當(dāng)從初始節(jié)點(diǎn)出發(fā)沿某一分枝擴(kuò)展到一限定深度時(shí)，就不能再繼續(xù)

5、向下擴(kuò)展，而只能改變方向繼續(xù)搜索。節(jié)點(diǎn)x的深度（即其位于搜索樹的層數(shù)）通常用d(x)表示，則有界深度優(yōu)先搜索算法如下：3.有界深度優(yōu)先搜索Step1 把S0 放入OPEN表中，置S0 的深度d(S0 )=0；Step2 若OPEN表為空，則搜索失敗，退出；Step3 取OPEN表中前面第一個(gè)節(jié)點(diǎn)N，放在CLOSED表中，并冠以順序編號(hào)n；Step4 若N是目標(biāo)節(jié)點(diǎn)，則搜索成功，結(jié)束。Step5 若N的深度d(N)=dm(深度限制值)，或N無(wú)子節(jié)點(diǎn)，則轉(zhuǎn)Step2；Step6 擴(kuò)展N，將其所有子節(jié)點(diǎn)Ni配上指向N的返回指針后依次放入OPEN表中前部，置d(Ni )=d(N)+1，轉(zhuǎn)Step2。3

6、.2.3啟發(fā)式搜索1.全局擇優(yōu)搜索2.局部擇優(yōu)搜索算法3.分支界限搜索算法4.最近擇優(yōu)1.全局擇優(yōu)搜索全局擇優(yōu)搜索算法如下：Step1 把初始節(jié)點(diǎn)S0 放入OPEN表中，計(jì)算h(S0 )；Step2 若OPEN表為空，則搜索失敗，退出；Step 3 移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中，并冠以序號(hào)n；Step 4 若N是目標(biāo)節(jié)點(diǎn)，則搜索成功，結(jié)束。Step 5 若N不可擴(kuò)展，則轉(zhuǎn)Step 2；Step 6 擴(kuò)展N，計(jì)算每個(gè)子節(jié)點(diǎn)x的函數(shù)值h(x)，并將所有子節(jié)點(diǎn)配以指向N的返回指針后放入OPEN表中，再對(duì)OPEN表中的所有子節(jié)點(diǎn)按其函數(shù)值大小以升序排序，轉(zhuǎn)Step 2。1.全局擇優(yōu)

7、搜索【例3-6】 用全局擇優(yōu)搜索法解八數(shù)碼難題。初始棋局S0，目標(biāo)棋局Sg.解 設(shè)啟發(fā)函數(shù)h(x)為節(jié)點(diǎn)x的格局與目標(biāo)格局相比數(shù)碼位置不同的個(gè)數(shù)。 由圖可見(jiàn)此八數(shù)問(wèn)題的解為：S0 S1 S2 S3Sg圖3-9全局擇優(yōu)搜索法搜索樹2.局部擇優(yōu)搜索算法擴(kuò)展節(jié)點(diǎn)N 后僅對(duì)N的子節(jié)點(diǎn)按啟發(fā)函數(shù)值大小以升序排序，再將它們依次放入OPEN表的首部。即：Step 1 把初始節(jié)點(diǎn)S0 放入OPEN表中，計(jì)算h(S0 )；Step 2 若OPEN表為空，則搜索失敗，退出；Step 3 移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中，并冠以序號(hào)n；Step 4 若N是目標(biāo)節(jié)點(diǎn)，則搜索成功，結(jié)束。Step 5 若

8、N不可擴(kuò)展，則轉(zhuǎn)Step 2；Step 6 擴(kuò)展N，計(jì)算每個(gè)子節(jié)點(diǎn)x的函數(shù)值h(x)，并將N所有子節(jié)點(diǎn)配以指向N的返回指針，按函數(shù)值大小以升序排序，依次放入OPEN表首部，轉(zhuǎn)Step 2。3.分支界限搜索算法如圖3-10是一個(gè)交通圖，設(shè)A城是出發(fā)地，E城是目的地，邊上的數(shù)字代表兩城之間的交通費(fèi)。試求從A到E最小費(fèi)用的旅行路線。ABCE324643D3.分支界限搜索算法分支界限搜索算法步驟描述如下：Step 1 把初始節(jié)點(diǎn)S0 放入OPEN表中，計(jì)算h (S0 )；Step 2 若OPEN表為空，則搜索失敗，退出；Step 3 移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中，并冠以序號(hào)n；St

9、ep 4 若N是目標(biāo)節(jié)點(diǎn)，則搜索成功，結(jié)束。Step 5 若N不可擴(kuò)展，則轉(zhuǎn)Step 2；Step 6 擴(kuò)展N，計(jì)算每個(gè)子節(jié)點(diǎn)x的函數(shù)值g (x) ，并將所有子節(jié)點(diǎn)配以指向N的返回指針后放入OPEN表中，再對(duì)OPEN表中的所有子節(jié)點(diǎn)按其函數(shù)值大小以升序排序，轉(zhuǎn)Step2。3.分支界限搜索算法在搜索過(guò)程中會(huì)產(chǎn)生一顆不斷增長(zhǎng)的搜索樹，一個(gè)節(jié)點(diǎn)x的代價(jià)值g(x)是從該樹初始節(jié)點(diǎn)S0方向計(jì)算而來(lái)的，其計(jì)算方法為：g(S0)=0g(xj)=g(xi)+ c (xi，xj) 其中xj是xi的子節(jié)點(diǎn)，c (xi，xj)表示節(jié)點(diǎn)xi到節(jié)點(diǎn)xj的代價(jià)。代價(jià)又稱為耗散。3.分支界限搜索算法【例3-7】 如圖3-1

10、0是一個(gè)五城市交通圖，設(shè)A城是出發(fā)地，E城是目的地，用分支界限搜索算法求A到E的最小費(fèi)用路徑。解：根據(jù)算法可得如圖3-11所示的搜索樹，可見(jiàn)最小費(fèi)用路徑為：A C D E。OPEN表及CLOSED表的變化過(guò)程從略。解路徑為A C DE。BABCDEEG=3G=4G=5G=10G=8G=9G=04.最近擇優(yōu)算法步驟描述如下：Step 1 把初始節(jié)點(diǎn)S0 放入OPEN表中，計(jì)算h (S0 )；Step 2 若OPEN表為空，則搜索失敗，退出；Step 3 移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中，并冠以序號(hào)n；Step 4 若N是目標(biāo)節(jié)點(diǎn)，則搜索成功，結(jié)束。Step 5 若N不可擴(kuò)展，則轉(zhuǎn)

11、Step 2；Step 6 擴(kuò)展N，計(jì)算每個(gè)子節(jié)點(diǎn)x的函數(shù)值g(x) ，并將N所有子節(jié)點(diǎn)配以指向N的返回指針，按g(x)函數(shù)值大小以升序排序，依次放入OPEN表首部，轉(zhuǎn)Step 2。3.2.4A算法及A*算法1.估價(jià)函數(shù)2.A算法3.A*算法1.估價(jià)函數(shù)估價(jià)函數(shù)的一般形式為：f(x)=g(x)+h(x)當(dāng)狀態(tài)圖中所有邊的代價(jià)都是1（單位耗散）時(shí)，估價(jià)函數(shù)還可以表示為：f(x)=d(x)+h(x)2.A算法A算法是基于估價(jià)函數(shù)f(x)的一種加權(quán)狀態(tài)圖啟發(fā)式搜索算法。算法描述如下：Step 1 把附有f(S0)的初始節(jié)點(diǎn)S0 放入OPEN表；Step 2 若OPEN表為空，則搜索失敗，退出；Ste

12、p 3 移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中，并冠以順序編號(hào)n；Step 4 若N是目標(biāo)節(jié)點(diǎn)，則搜索成功，結(jié)束。Step 5 若N不可擴(kuò)展，則轉(zhuǎn)Step 2；Step 6 擴(kuò)展N，生成一組附有f(x)的子節(jié)點(diǎn)，對(duì)這組子節(jié)點(diǎn)作如下處理：2.A算法(1)考察是否有已在OPEN表或CLOSED表中存在的節(jié)點(diǎn)；由于它們被第二次生成，因而需要考慮是否修改已經(jīng)存在于OPEN表或COLSED表中的這些節(jié)點(diǎn)及其后裔的返回指針和f(x)值，修改原則是“抄f(x)值小的路走”； (2)對(duì)其余子節(jié)點(diǎn)配上指向N的返回指針后放入OPEN表中，并對(duì)OPEN表按f(x)值以升序排序，轉(zhuǎn)Step2。 算法中節(jié)點(diǎn)x

13、估價(jià)函數(shù)f(x)的計(jì)算方法是f(xj)=g(xj)+h(xj) =g(xi)+c(xi，xj)+h(xj) (xj是xi的子節(jié)點(diǎn)) 至于h(x)的計(jì)算公式則需由具體問(wèn)題而定。2.A算法【例3-8】 使用A算法求解八數(shù)碼問(wèn)題。取f(x)=d(x)+h(x)。其中d(x)為節(jié)點(diǎn)深度，h(x)為不在位數(shù)碼個(gè)數(shù)。初始狀態(tài)為S0，目標(biāo)狀態(tài)為Sg（如圖3-12）。解路徑為S0S2S5S9S11Sg2.A算法3.A*算法如果對(duì)A算法限制其估價(jià)函數(shù)中的啟發(fā)函數(shù)h(x)滿足：對(duì)所有的節(jié)點(diǎn)x均有： h(x)h*(x)其中h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià)。此時(shí)的A算法就稱為A*算法，A*算法是完備的。A*算

14、法也稱為最佳圖搜索算法。它是著名的人工智能學(xué)者Nilsson提出的。3.3與或圖搜索3.3.1與或圖3.3.2與或圖搜索舉例3.3.1與或圖因此，一般稱這種路徑為解圖或解樹。所以，求解與或圖問(wèn)題就是在與或圖中搜索解圖或解樹的問(wèn)題。N1N4N3N5N7N0N2N63.3.1與或圖為了敘述方便，下面引入一些新概念：本原問(wè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)。K連接符3.3.1與或圖例如，圖3-13中節(jié)點(diǎn)n2有兩個(gè)連接符， 1連接符指向n3，2連接符指向節(jié)點(diǎn)集n1，n5可解節(jié)點(diǎn)：不可解節(jié)點(diǎn)：與圖：3.3.2與或圖搜索舉例1.基本概念2.AO*搜索算法1.基

15、本概念解圖（樹）的代價(jià)：分為和代價(jià)和最大代價(jià)兩種。c(x,y)表示節(jié)點(diǎn)x到其子節(jié)點(diǎn)y的代價(jià)（即邊xy的代價(jià)），則節(jié)點(diǎn)x到節(jié)點(diǎn)集N的解圖G的代價(jià)記為g(x)，則和代價(jià)可遞歸定義如下：（1）若x是終止節(jié)點(diǎn)，g(n)=0；（2）若x是與節(jié)點(diǎn)，有一個(gè)外向n連接符連至y1、y2、yn，則有兩種計(jì)算公式： c(x,yi) +g(yi) 上式稱為和代價(jià)； g(x)=MAXc(x,yi)+g(yi) 1in 上式稱為最大代價(jià)。對(duì)非終止的端節(jié)點(diǎn)x，g(x)=解圖（樹）的代價(jià)定義為樹根S0的代價(jià)。最佳（優(yōu)）解圖：是具有最小代價(jià)的解圖。【例3-9】1.基本概念解：由右邊的解樹：按和代價(jià)：g(A)=11，g(S0)=

16、13按最大代價(jià)：g(A)=6，g(S0)=8由左邊的解樹：按和代價(jià)：g(G)=3，g(D)=4，g(B)=6，g(S0)=8按最大代價(jià)：g(G)=2，g(D)=3，g(B)=5，g(S0)=7顯然，若按和代價(jià)計(jì)算，左邊的解樹是最優(yōu)解樹，其代價(jià)為8；若按最大代價(jià)計(jì)算，左邊的解樹仍然是最優(yōu)解樹，其代價(jià)是7。但使用不同的計(jì)算代價(jià)方法得到的最優(yōu)解樹有可能不相同。1.基本概念下面給出希望樹的定義：（1） 初始節(jié)點(diǎn)S0在希望樹T中。（2） 如果節(jié)點(diǎn)x在T中，則：如果x只有一個(gè)k連接符，則k連接符所連接的所有子節(jié)點(diǎn)都在T中如果x具有多個(gè)k連接符k1，k2，kn，設(shè)kj所連接的子節(jié)點(diǎn)為yj1， ，yjkj則：

17、kjc(x，yji) +g(yji) j=1ni=1 1.基本概念2.AO*搜索算法Step1 把初始節(jié)點(diǎn)S0放入OPEN表；Step2 從當(dāng)前生成的搜索樹(圖) ，構(gòu)造以S0為根的希望樹(圖) T。Step3 選一個(gè)OPEN表和T共有的節(jié)點(diǎn)N，并將N從OPEN表移出放入CLOSED表(即選中T中的待擴(kuò)展節(jié)點(diǎn)進(jìn)行擴(kuò)展)；Step4 若N為終止節(jié)點(diǎn)，則做下列工作：（1）標(biāo)記N為可解節(jié)點(diǎn)；（2）把N的先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)標(biāo)記為可解.（3）如果初始節(jié)點(diǎn)S0被標(biāo)記為可解，則T為最優(yōu)解樹(圖)，成功退出。（4）刪去OPEN表中這樣的節(jié)點(diǎn):其先輩節(jié)點(diǎn)已經(jīng)可解；Step5 若N不是終止節(jié)點(diǎn)且不可擴(kuò)展，則做下

18、列工作：（1）標(biāo)記N為不可解節(jié)點(diǎn)。（2）把N的先輩節(jié)點(diǎn)中的不可解節(jié)點(diǎn)標(biāo)記為不可解（3）如果初始節(jié)點(diǎn)S0被標(biāo)記為不可解，失敗退出。（4）刪去OPEN表中這樣的節(jié)點(diǎn)：其先輩節(jié)點(diǎn)中存在不可解節(jié)點(diǎn)；Step6 若N不是終止節(jié)點(diǎn)但可擴(kuò)展，則做下列工作:（1）擴(kuò)展N，產(chǎn)生N的所有子節(jié)點(diǎn)。（2）把這些子節(jié)點(diǎn)放入OPEN表中，并為每個(gè)子節(jié)點(diǎn)配以指向父節(jié)點(diǎn)的指針.（3）計(jì)算這些子節(jié)點(diǎn)的g值及先輩節(jié)點(diǎn)的g值(遞歸地)Step7 轉(zhuǎn)Step2；同狀態(tài)圖搜索一樣，搜索成功后，解樹已經(jīng)記錄在CLOSED表中。這時(shí)需按指向父節(jié)點(diǎn)的指針找出整個(gè)解樹。【例3-10】如圖3-16中（1）所示的與或圖，設(shè)初始節(jié)點(diǎn)為N0，目標(biāo)節(jié)點(diǎn)

19、為N6、N7。假設(shè)在擴(kuò)展過(guò)程中生成的各節(jié)點(diǎn)的啟發(fā)函數(shù)值分別是：g(N0)=3、g(N1)=1、g(N2)=2、g(N3)=3、g(N4)=1、g(N5)=2、g(N6)=0 、g(N7)=0，邊為單位耗散，請(qǐng)使用AO*搜索算法求解最佳解圖。解：第一次循環(huán)：第二次循環(huán)：第三次循環(huán)：第四次循環(huán)：第五次循環(huán)：第六次循環(huán)：通過(guò)本例我們可以看出，在本算法生成希望圖的過(guò)程中，希望圖是動(dòng)態(tài)變化的（如圖3-16中（3）和（4）。另外，根據(jù)本算法所得到的最佳解圖也不一定是唯一的，這可以留給讀者思考。3.4博弈圖搜索3.4.1博弈圖3.4.2極大極小分析法3.4.3剪枝技術(shù)3.4.1博弈圖3.4.1博弈圖（1）博弈的初始格局是初始節(jié)點(diǎn)。（2）博弈樹中，“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)是逐層交替出現(xiàn)的。自己一方擴(kuò)展的節(jié)點(diǎn)之間是“或”關(guān)系，對(duì)方擴(kuò)展的節(jié)點(diǎn)之間是“與”關(guān)系。雙方輪流地?cái)U(kuò)展節(jié)點(diǎn)。（3）max必勝的節(jié)點(diǎn)對(duì)應(yīng)的是終止節(jié)點(diǎn)（本原問(wèn)題），即可解節(jié)點(diǎn)；