第3章 圖搜索及問(wèn)題求解

1、第 3 章 圖搜索與問(wèn)題求解 第 3 章 圖搜索與問(wèn)題求解 3.1 狀態(tài)圖搜索狀態(tài)圖搜索 3.2 狀態(tài)圖搜索問(wèn)題求解狀態(tài)圖搜索問(wèn)題求解 3.3 與或圖搜索與或圖搜索 3.4 與或圖搜索問(wèn)題求解與或圖搜索問(wèn)題求解 第 3 章 圖搜索與問(wèn)題求解 3.1 狀態(tài)圖搜索 3.1.1 狀態(tài)圖例例3.1 迷宮問(wèn)題。第 3 章 圖搜索與問(wèn)題求解 圖 3-2 迷宮的有向圖表示 第 3 章 圖搜索與問(wèn)題求解 圖 3-3 八數(shù)碼問(wèn)題示例 例例 3.2 3.2 八數(shù)碼問(wèn)題。第 3 章 圖搜索與問(wèn)題求解 3.1.2 狀態(tài)圖搜索1. 1. 搜索方式搜索方式樹(shù)式搜索 線(xiàn)式搜索 2. 2. 搜索策略搜索策略 盲目搜索 啟發(fā)式

2、(heuristic)搜索 第 3 章 圖搜索與問(wèn)題求解 圖 3-4 OPEN表與CLOSED表示例 3. 3. 搜索算法搜索算法第 3 章 圖搜索與問(wèn)題求解 樹(shù)式搜索算法：樹(shù)式搜索算法： 步1 把初始節(jié)點(diǎn)So放入OPEN表中。步2 若OPEN表為空, 則搜索失敗, 退出。 步3 移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中, 并冠以順序編號(hào)n。步4 若目標(biāo)節(jié)點(diǎn)Sg=N, 則搜索成功, 結(jié)束。 步5 若N不可擴(kuò)展, 則轉(zhuǎn)步2。 步6 擴(kuò)展N, 生成一組子節(jié)點(diǎn), 對(duì)這組子節(jié)點(diǎn)做如下處理：第 3 章 圖搜索與問(wèn)題求解 (1) 刪除N的先輩節(jié)點(diǎn)(如果有的話(huà))。 (2)對(duì)已存在于OPEN表的節(jié)點(diǎn)(

3、如果有的話(huà))也刪除之；但刪除之前要比較其返回初始節(jié)點(diǎn)的新路徑與原路徑,如果新路徑“短”, 則修改這些節(jié)點(diǎn)在OPEN表中的原返回指針,使其沿新路返回(如圖3-5所示 )。 (3)對(duì)已存在于CLOSED表的節(jié)點(diǎn)(如果有的話(huà)), 做與(2)同樣的處理, 并且再將其移出CLOSED表, 放入OPEN表重新擴(kuò)展(為了重新計(jì)算代價(jià))。 (4)對(duì)其余子節(jié)點(diǎn)配上指向N的返回指針后放入OPEN表中某處, 或?qū)PEN表進(jìn)行重新排序, 轉(zhuǎn)步2。 第 3 章 圖搜索與問(wèn)題求解 圖 3-5 修改返回指針示例 第 3 章 圖搜索與問(wèn)題求解 說(shuō)明： (1) 這里的返回指針也就是父節(jié)點(diǎn)在CLOSED表中的編號(hào)。 (2) 步

4、6中修改返回指針的原因是, 因?yàn)檫@些節(jié)點(diǎn)又被第二次生成, 所以它們返回初始節(jié)點(diǎn)的路徑已有兩條, 但這兩條路徑的“長(zhǎng)度”可能不同。 那么, 當(dāng)新路短時(shí)自然要走新路。(3) 這里對(duì)路徑的長(zhǎng)短是按路徑上的節(jié)點(diǎn)數(shù)來(lái)衡量的, 后面我們將會(huì)看到路徑的長(zhǎng)短也可以其“代價(jià)”(如距離、費(fèi)用、時(shí)間等)衡量。若按其代價(jià)衡量, 則在需修改返回指針的同時(shí)還要修改相應(yīng)的代價(jià)值, 或者不修改返回指針也要修改代價(jià)值(為了實(shí)現(xiàn)代價(jià)小者優(yōu)先擴(kuò)展)。 第 3 章 圖搜索與問(wèn)題求解 線(xiàn)式搜索算法： 不回溯的線(xiàn)式搜索不回溯的線(xiàn)式搜索 步1 把初始節(jié)點(diǎn)So放入CLOSED表中。步2 令NSo。步3 若N是目標(biāo)節(jié)點(diǎn),則搜索成功,結(jié)束。 步

5、4 若N不可擴(kuò)展,則搜索失敗,退出。 步5 擴(kuò)展N,選取其一個(gè)未在CLOSED表中出現(xiàn)過(guò)的子節(jié)點(diǎn)N1放入CLOSED表中, 令NN1, 轉(zhuǎn)步3。 第 3 章 圖搜索與問(wèn)題求解 可回溯的線(xiàn)式搜索可回溯的線(xiàn)式搜索 步1 把初始節(jié)點(diǎn)So放入CLOSED表中。步2令NSo。步3若N是目標(biāo)節(jié)點(diǎn), 則搜索成功, 結(jié)束。 步4 若N不可擴(kuò)展, 則移出CLOSED表的末端節(jié)點(diǎn)Ne,若NeSo,則搜索失敗, 退出。否則, 以CLOSED表新的末端節(jié)點(diǎn)Ne作為N,即令NNe, 轉(zhuǎn)步4。步5擴(kuò)展N, 選取其一個(gè)未在CLOSED表用出現(xiàn)過(guò)的子節(jié)點(diǎn)N1放入CLOSED表中, 令NN1,轉(zhuǎn)步3。 第 3 章 圖搜索與問(wèn)題

6、求解 3.1.3 窮舉式搜索1.1.廣度優(yōu)先搜索廣度優(yōu)先搜索圖 3-6 八數(shù)碼問(wèn)題的廣度優(yōu)先搜索第 3 章 圖搜索與問(wèn)題求解 廣度優(yōu)先搜索算法：廣度優(yōu)先搜索算法： 步1 把初始節(jié)點(diǎn)So放入OPEN表中。步2 若OPEN表為空, 則搜索失敗,退出。 步3 取OPEN表中前面第一個(gè)節(jié)點(diǎn)N放在CLOSED表中, 并冠以順序編號(hào)n。步4 若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功, 結(jié)束。 步5 若N不可擴(kuò)展, 則轉(zhuǎn)步2。步6 擴(kuò)展N, 將其所有子節(jié)點(diǎn)配上指向N的指針依次放入OPEN表尾部, 轉(zhuǎn)步2。 第 3 章 圖搜索與問(wèn)題求解 2 .2 . 深 度 優(yōu) 先 搜 索深 度 優(yōu) 先 搜 索第 3 章 圖搜索與問(wèn)題

7、求解 深度優(yōu)先搜索算法：深度優(yōu)先搜索算法： 步1 把初始節(jié)點(diǎn)So放入OPEN表中。步2 若OPEN表為空, 則搜索失敗, 退出。 步3 取OPEN表中前面第一個(gè)節(jié)點(diǎn)N放入CLOSED表中,并冠以順序編號(hào)n。步4 若目標(biāo)節(jié)點(diǎn)Sg=N, 則搜索成功,結(jié)束。 步5 若N不可擴(kuò)展, 則轉(zhuǎn)步2。步6擴(kuò)展N, 將其所有子節(jié)點(diǎn)配上指向N的返回指針依次放入OPEN表的首部, 轉(zhuǎn)步2。 第 3 章 圖搜索與問(wèn)題求解 3. 有界深度優(yōu)先搜索有界深度優(yōu)先搜索 步1 把So放入OPEN表中,置So的深度d(So)=0。 步2 若OPEN表為空, 則失敗, 退出。 步3 取OPEN表中前面第一個(gè)節(jié)點(diǎn)N,放入CLOSED

8、表中, 并冠以順序編號(hào)n。步4 若目標(biāo)節(jié)點(diǎn)Sg=N, 則成功, 結(jié)束。 步5 若N的深度d(N)=dm(深度限制值), 或者若N無(wú)子節(jié)點(diǎn), 則轉(zhuǎn)步2。步6 擴(kuò)展N, 將其所有子節(jié)點(diǎn)Ni配上指向N的返回指針后依次放入OPEN表中前部, 置d(Ni)=d(N)+1,轉(zhuǎn)步2。 第 3 章 圖搜索與問(wèn)題求解 3.1.4 啟發(fā)式搜索1. 1. 問(wèn)題的提出問(wèn)題的提出 2. 2. 啟發(fā)性信息啟發(fā)性信息按其用途劃分, 啟發(fā)性信息可分為以下三類(lèi)： (1) 用于擴(kuò)展節(jié)點(diǎn)的選擇, 即用于決定應(yīng)先擴(kuò)展哪一個(gè)節(jié)點(diǎn), 以免盲目擴(kuò)展。 (2) 用于生成節(jié)點(diǎn)的選擇,即用于決定應(yīng)生成哪些后續(xù)節(jié)點(diǎn),以免盲目地生成過(guò)多無(wú)用節(jié)點(diǎn)。

9、(3) 用于刪除節(jié)點(diǎn)的選擇,即用于決定應(yīng)刪除哪些無(wú)用節(jié)點(diǎn), 以免造成進(jìn)一步的時(shí)空浪費(fèi)。 第 3 章 圖搜索與問(wèn)題求解 3.3.啟發(fā)函數(shù)啟發(fā)函數(shù)啟發(fā)函數(shù)是用來(lái)估計(jì)搜索樹(shù)上節(jié)點(diǎn)x與目標(biāo)節(jié)點(diǎn)Sg接近程度的一種函數(shù), 通常記為h(x)。4.4.啟發(fā)式搜索算法啟發(fā)式搜索算法1) 全局擇優(yōu)搜索2) 局部擇優(yōu)搜索 第 3 章 圖搜索與問(wèn)題求解 全局擇優(yōu)搜索算法： 步1 把初始節(jié)點(diǎn)So放入OPEN表中,計(jì)算h(So)。步2 若OPEN表為空,則搜索失敗, 退出。 步3 移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中, 并冠以序號(hào)n。步4 若目標(biāo)節(jié)點(diǎn)Sg=N, 則搜索成功, 結(jié)束。 步5 若N不可擴(kuò)展, 則轉(zhuǎn)

10、步2。步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)步2。 第 3 章 圖搜索與問(wèn)題求解 圖 3-8 八數(shù)碼問(wèn)題的全局擇優(yōu)搜索 第 3 章 圖搜索與問(wèn)題求解 例例 3.53.5 用全局擇優(yōu)搜索法解八數(shù)碼難題。初始棋局和目標(biāo)棋局同例3。 解解設(shè)啟發(fā)函數(shù)h(x)為節(jié)點(diǎn)x的格局與目標(biāo)格局相比數(shù)碼不同的位置個(gè)數(shù)。以這個(gè)函數(shù)制導(dǎo)的搜索樹(shù)如圖3-8所示。此八數(shù)問(wèn)題的解為：So, S1, S2, S3, Sg。 第 3 章 圖搜索與問(wèn)題求解 3.1.5 加權(quán)狀態(tài)圖搜索1.1.加權(quán)狀態(tài)圖與代價(jià)

11、樹(shù)加權(quán)狀態(tài)圖與代價(jià)樹(shù)例例3.63.6 圖3-9(a)是一個(gè)交通圖,設(shè)A城是出發(fā)地,E城是目的地, 邊上的數(shù)字代表兩城之間的交通費(fèi)。試求從A到E最小費(fèi)用的旅行路線(xiàn)。 第 3 章 圖搜索與問(wèn)題求解 圖 3-9 交通圖及其代價(jià)樹(shù) 第 3 章 圖搜索與問(wèn)題求解 代價(jià)樹(shù)的搜索。所謂代價(jià),可以是兩點(diǎn)之間的距離、交通費(fèi)用或所需時(shí)間等等。通常用g(x)表示從初始節(jié)點(diǎn)So到節(jié)點(diǎn)x的代價(jià), 用c(xi,xj)表示父節(jié)點(diǎn)xi到子節(jié)點(diǎn)xj的代價(jià),即邊(xi,xj)的代價(jià)。從而有 g(xj)g(xi)c(xi, xj) 而 g(So)0 第 3 章 圖搜索與問(wèn)題求解 2.2.分支界限法分支界限法( (最小代價(jià)優(yōu)先法最小

12、代價(jià)優(yōu)先法) ) 基本思想是：每次從OPEN表中選出g(x)值最小的節(jié)點(diǎn)進(jìn)行考察, 而不管這個(gè)節(jié)點(diǎn)在搜索樹(shù)的什么位置上。 算法與前面的“全局擇優(yōu)法” 僅有引導(dǎo)搜索的函數(shù)不同，前者為啟發(fā)函數(shù)h(x)，后者為代價(jià)g(x)。 但注意：代價(jià)值g(x)是從初始節(jié)點(diǎn)So方向計(jì)算而來(lái)的,而啟發(fā)函數(shù)值h(x)則是朝目標(biāo)節(jié)點(diǎn)方向計(jì)算的。 第 3 章 圖搜索與問(wèn)題求解 3. 3. 最近擇優(yōu)法最近擇優(yōu)法( (瞎子爬山法瞎子爬山法) ) 把局部擇優(yōu)法算法中的h(x)換成g(x)就可得最近擇優(yōu)法的算法。 例：例：用代價(jià)樹(shù)搜索求解例3.6中給出的問(wèn)題。 用分支界限法得到的路徑為ACDE這是一條最小費(fèi)用路徑(費(fèi)用為8)。

13、第 3 章 圖搜索與問(wèn)題求解 3.1.6 A算法和A*算法1.1.估價(jià)函數(shù)估價(jià)函數(shù) f(x)g(x)h(x) 第 3 章 圖搜索與問(wèn)題求解 2. A算法算法 A 算法是基于估價(jià)函數(shù)f(x)的一種加權(quán)狀態(tài)圖啟發(fā)式搜索算法。其具體步驟如下： 步1 把附有f(So)的初始節(jié)點(diǎn)So放入OPEN表。步2 若OPEN表為空, 則搜索失敗, 退出。 步3 移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中, 并冠以順序編號(hào)n。步4 若目標(biāo)節(jié)點(diǎn)Sg=N, 則搜索成功, 結(jié)束。 步5 若N不可擴(kuò)展, 則轉(zhuǎn)步2。 第 3 章 圖搜索與問(wèn)題求解 步6 擴(kuò)展N,生成一組附有f(x)的子節(jié)點(diǎn),對(duì)這組子節(jié)點(diǎn)做如下處理： (

14、1)考察是否有已在OPEN表或CLOSED表中存在的節(jié)點(diǎn)；若有則再考察其中有無(wú)N的先輩節(jié)點(diǎn),若有則刪除之；對(duì)于其余節(jié)點(diǎn), 也刪除之,但由于它們又被第二次生成, 因而需考慮是否修改已經(jīng)存在于OPEN表或CLOSED表中的這些節(jié)點(diǎn)及其后裔的返回指針和f(x)值, 修改原則是“抄f(x)值小的路走”。 (2)對(duì)其余子節(jié)點(diǎn)配上指向N的返回指針后放入OPEN表中, 并對(duì)OPEN表按f(x)值以升序排序, 轉(zhuǎn)步2。 第 3 章 圖搜索與問(wèn)題求解 算法中節(jié)點(diǎn)x的估價(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ì)算公式

15、則需由具體問(wèn)題而定。 可以看出,A算法其實(shí)就是對(duì)于本節(jié)開(kāi)始給出的圖搜索一般算法中的樹(shù)式搜索算法, 再增加了估價(jià)函數(shù)f(x)的一種啟發(fā)式搜索算法。 第 3 章 圖搜索與問(wèn)題求解 3. A*算法算法 如果對(duì)上述A算法再限制其估價(jià)函數(shù)中的啟發(fā)函數(shù)h(x)滿(mǎn)足： 對(duì)所有的節(jié)點(diǎn)x均有 h(x)h*(x) 其中h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià), 即最佳路徑上的實(shí)際代價(jià)(若有多個(gè)目標(biāo)節(jié)點(diǎn)則為其中最小的一個(gè)),則它就稱(chēng)為A*算法。第 3 章 圖搜索與問(wèn)題求解 3.1.7 狀態(tài)圖搜索策略小結(jié) 第 3 章 圖搜索與問(wèn)題求解 3.2 狀態(tài)圖搜索問(wèn)題求解 3.2.1 問(wèn)題的狀態(tài)圖表示1. 1. 狀態(tài)狀態(tài) 狀態(tài)

16、就是問(wèn)題在任一確定時(shí)刻的狀況,它表征了問(wèn)題特征和結(jié)構(gòu)等。狀態(tài)在狀態(tài)圖中表示為節(jié)點(diǎn)。狀態(tài)一般用一組數(shù)據(jù)表示。在程序中用字符、數(shù)字、記錄、數(shù)組、結(jié)構(gòu)、對(duì)象等表示。 第 3 章 圖搜索與問(wèn)題求解 2. 2. 狀態(tài)轉(zhuǎn)換規(guī)則狀態(tài)轉(zhuǎn)換規(guī)則狀態(tài)轉(zhuǎn)換規(guī)則就是能使問(wèn)題狀態(tài)改變的某種操作、規(guī)則、 行為、變換、關(guān)系、函數(shù)、算子、過(guò)程等等。狀態(tài)轉(zhuǎn)換規(guī)則也稱(chēng)為操作,問(wèn)題的狀態(tài)也只能經(jīng)定義在其上的這種操作而改變。狀態(tài)轉(zhuǎn)換規(guī)則在狀態(tài)圖中表示為邊。在程序中狀態(tài)轉(zhuǎn)換規(guī)則可用數(shù)據(jù)對(duì)、條件語(yǔ)句、規(guī)則、函數(shù)、過(guò)程等表示。 第 3 章 圖搜索與問(wèn)題求解 3. 3. 狀態(tài)圖表狀態(tài)圖表示示一個(gè)問(wèn)題的狀態(tài)圖是一個(gè)三元組 (S, F, G)

17、其中S是問(wèn)題的初始狀態(tài)集合, F是問(wèn)題的狀態(tài)轉(zhuǎn)換規(guī)則集合, G是問(wèn)題的目標(biāo)狀態(tài)集合。 一個(gè)問(wèn)題的全體狀態(tài)及其關(guān)系就構(gòu)成一個(gè)空間, 稱(chēng)為狀態(tài)空間。所以,狀態(tài)圖也稱(chēng)為狀態(tài)空間圖。 第 3 章 圖搜索與問(wèn)題求解 例例 3.73.7 迷宮問(wèn)題的狀態(tài)圖表示。 S：SoF：(So, S4), (S4, So), (S4, S1), (S1, S4), (S1,S2), (S2, S1), (S2, S3), (S3, S2), (S4, S7), (S7, S4), (S4, S5), (S5, S4), (S5, S6), (S6, S5), (S5, S8), (S8, S5), (S8, S9),

18、(S9, S8), (S9, Sg)G：Sg 第 3 章 圖搜索與問(wèn)題求解 X1X2X3XX0X4X7X6X5例例 3.83.8八數(shù)碼難題的狀態(tài)圖表示。 用向量 A(X0, X1, X2, X3, X4, X5, X6, X7, X8)表示, Xi為變量,Xi的值就是所在方格內(nèi)的數(shù)字。于是,向量A就是該問(wèn)題的狀態(tài)表達(dá)式。我們將棋局第 3 章 圖搜索與問(wèn)題求解 設(shè)初始狀態(tài)和目標(biāo)狀態(tài)分別為 So(0, 2, 8, 3, 4, 5, 6, 7, 1) Sg(0, 1, 2, 3, 4, 5, 6, 7, 8) 第 3 章 圖搜索與問(wèn)題求解 0組規(guī)則: ; 0)()0(; 0)()0(; 0)()0(

19、; 0)()0(80804606034040220201XnXnXXrXnXnXXrXnXnXXrXnXnXXr 1組規(guī)則: ; 0)()0(; 0)()0(8181621215XnXnXXrXnXnXXr第 3 章 圖搜索與問(wèn)題求解 2組規(guī)則組規(guī)則: ; 0)()0(; 0)()0(; 0)()0(020293232812127XnXnXXrXnXnXXrXnXnXXr8組規(guī)則: ; 0)()0(; 0)()0(; 0)()0(787824080823181822XnXnXXrXnXnXXrXnXnXXr 于是, 八數(shù)碼問(wèn)題的狀態(tài)圖可表示為 (So, r1, r2, , r24, Sg) 第

20、 3 章 圖搜索與問(wèn)題求解 例例3.93.9 梵塔問(wèn)題。傳說(shuō)在印度的貝那勒斯的圣廟中,主神梵天做了一個(gè)由64個(gè)大小不同的金盤(pán)組成的“梵塔”, 并把它穿在一個(gè)寶石桿上。另外, 旁邊再插上兩個(gè)寶石桿。 然后, 他要求僧侶們把穿在第一個(gè)寶石桿上的64個(gè)金盤(pán)全部搬到第三個(gè)寶石桿上。 搬動(dòng)金盤(pán)的規(guī)則是：一次只能搬一個(gè)；不允許將較大的盤(pán)子放在較小的盤(pán)子上。于是,梵天預(yù)言：一旦64個(gè)盤(pán)子都搬到了3號(hào)桿上, 世界將在一聲霹靂中毀滅。 盤(pán)子的搬動(dòng)次數(shù)： 264-118 446 744 073 709 511 615 第 3 章 圖搜索與問(wèn)題求解 二階梵塔問(wèn)題 設(shè)有三根寶石桿,在1號(hào)桿上穿有A、B兩個(gè)金盤(pán), A小

21、于B, A位于B的上面。用二元組(SA,SB)表示問(wèn)題的狀態(tài), SA表示金盤(pán)A所在的桿號(hào), SB表示金盤(pán)B所在的桿號(hào), 這樣, 全部可能的狀態(tài)有9種, 可表示如下： (1, 1), (1, 2), (1, 3)(2, 1), (2, 2), (2, 3)(3, 1), (3, 2), (3, 3) 如圖3-10所示。 第 3 章 圖搜索與問(wèn)題求解 圖 3-10 二階梵塔的全部狀態(tài) 第 3 章 圖搜索與問(wèn)題求解 這里的狀態(tài)轉(zhuǎn)換規(guī)則就是金盤(pán)的搬動(dòng)規(guī)則，分別用A(i,j)及B(i,j)表示：A(i,j)表示把A盤(pán)從第i號(hào)桿移到第j號(hào)桿上;B(i,j)表示把B盤(pán)從第i號(hào)桿移到第j號(hào)桿上。經(jīng)分析，共有1

22、2個(gè)操作，它們分別是： 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)規(guī)則的具體形式應(yīng)是： IF條件THENA(i,j) IF條件THEN B(i, j)第 3 章 圖搜索與問(wèn)題求解 這樣由題意,問(wèn)題的初始狀態(tài)為(1, 1),目標(biāo)狀態(tài)為(3, 3), 則二階梵塔問(wèn)題可用狀態(tài)圖表示為 (1, 1), A(1, 2), , B(3, 2), (3, 3) 由這9種可能的狀態(tài)和12種操作, 二階梵塔問(wèn)題的狀態(tài)空間圖如圖3-11所示。 第 3 章 圖搜索與問(wèn)題求解 圖 3-11 二階

23、梵塔狀態(tài)空間圖 第 3 章 圖搜索與問(wèn)題求解 例例3.10 旅行商問(wèn)題(Traveling-Salesman Problem,TSP)。 設(shè)有n個(gè)互相可直達(dá)的城市, 某推銷(xiāo)商準(zhǔn)備從其中的A城出發(fā),周游各城市一遍, 最后又回到A城。要求為該推銷(xiāo)商規(guī)劃一條最短的旅行路線(xiàn)。 該問(wèn)題的狀態(tài)為以A打頭的已訪(fǎng)問(wèn)過(guò)的城市序列: A So: A。 Sg: A, , A。 其中“”為其余n-1個(gè)城市的一個(gè)序列。 第 3 章 圖搜索與問(wèn)題求解 狀態(tài)轉(zhuǎn)換規(guī)則：狀態(tài)轉(zhuǎn)換規(guī)則： 規(guī)則規(guī)則1 1 如果當(dāng)前城市的下一個(gè)城市還未去過(guò), 則去該城市,并把該城市名排在已去過(guò)的城市名序列后端。 規(guī)則規(guī)則2 2 如果所有城市都去過(guò)一

24、次, 則從當(dāng)前城市返回A城, 把A也添在去過(guò)的城市名序列后端。 第 3 章 圖搜索與問(wèn)題求解 3.2.2 狀態(tài)圖問(wèn)題求解程序舉例 例例3.113.11 下面是一個(gè)通用的狀態(tài)圖搜索程序。對(duì)于求解的具體問(wèn)題，只需將其狀態(tài)圖的程序表示并入該程序即可。 第 3 章 圖搜索與問(wèn)題求解 /*狀態(tài)圖搜索通用程序*/ DOMAINS state= %例如:state=symbol DATABASE-mydatabase open(state,integer) %用動(dòng)態(tài)數(shù)據(jù)庫(kù)實(shí)現(xiàn)OPEN表 closed(integer,state,integer) %和CLOSED表 res(state) open1(stat

25、e,integer) min(state,integer) mark(state) fail_第 3 章 圖搜索與問(wèn)題求解 PREDICATES solve search(state,state) result searching step4(integer,state) step56(integer,state) equal(state,state) repeat resulting(integer) rule(state,state) 第 3 章 圖搜索與問(wèn)題求解 GOAL solve.CLAUSES solve: -search(,),result. /* 例如 solve: -sear

26、ch(st(0,1,2,3,4,5,6,7,8),st(0,2,8,3,4,5,6,7,1),result.*/search(Begin,End):- % 搜索 retractall(_,mydatabase), assert(closed(0,Begin,0), assert(open(Begin,0), %步1 將初始節(jié)點(diǎn)放入OPEN表 assert(mark(End), repeat, searching,!. 第 3 章 圖搜索與問(wèn)題求解 result: -% 輸出解 not(fail_), retract(closed(0,_,0), closed(M,_,_), resulting

27、(M),!.result: - beep,write(sorry dont find a road!).searching: - open(State,Pointer), %步2 若OPEN表空, 則失敗,退出 retract(open(State,Pointer), %步3 取出OPEN表中第一個(gè)節(jié)點(diǎn),給其 closed(No, _, _),No2=No+1, % 編號(hào) asserta(closed(No2,State,Pointer), %放入CLOSED表 !,step4(No2,State). searching: -assert(fail_). %步4 若當(dāng)前節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn), 則成功

28、 第 3 章 圖搜索與問(wèn)題求解 step4(_,State): -mark(End),equal(State,End). %轉(zhuǎn)步2step4(No,State): -step56(No,State),!,fail. step56(No,StateX): -%步5 若當(dāng)前節(jié)點(diǎn)不可擴(kuò)展, 轉(zhuǎn)步2 rule(StateX,StateY), %步6 擴(kuò)展當(dāng)前節(jié)點(diǎn)X得Y not(open(StateY,_), %考察Y是否已在OPEN表中 not(closed(_,StateY,_),%考察Y是否已在CLOSED表中 assertz(open(StateY,No), %可改變搜索策略 fail.step

29、56(_,_): -!. equal(X,X).repeat.repeat: -repeat. resulting(N): -closed(N,X,M),asserta(res(X),resulting(M).resulting(_): -res(X),write(X),nl,fail.resulting(_): -!.rule(X,Y): -. % 例如: rule(X,Y): -road(X,Y). 第 3 章 圖搜索與問(wèn)題求解 例例 3.123.12迷宮問(wèn)題程序。下面僅給出初始狀態(tài)、目標(biāo)狀態(tài)和狀態(tài)轉(zhuǎn)換規(guī)則集, 程序用例3.11的通用程序。 DOMAINS State=symbol CLA

30、USES solve:-search(a,e), result./*把該問(wèn)題的狀態(tài)轉(zhuǎn)換規(guī)則掛接在通用程序的規(guī)則上*/ rule(X,Y): -road(X,Y). /* 下面是該問(wèn)題的狀態(tài)轉(zhuǎn)換規(guī)則(其實(shí)也就是迷宮圖)集, 需并入通用程序后 */road(a,b). road(a,c). road(b,f). road(f,g).road(f,ff).road(g,h).road(g,i). road(b,d). road(c,d). road(d,e). road(e,b). 第 3 章 圖搜索與問(wèn)題求解 例例 3.133.13 八數(shù)碼問(wèn)題程序。我們把前面給出的該問(wèn)題的狀態(tài)圖表示, 用PROL

31、OG語(yǔ)言翻譯如下,搜索程序用通用程序。 DOMAINS state=st(integer,integer,integer,integer,integer,integer,integer,integer,integer)CLAUSESsolve:-search(st(0,1,2,3,4,5,6,7,8),st(0,2,8,3,4,5,6,7,1), result.rule(X,Y): -rule1(X,Y). /*把該問(wèn)題的狀態(tài)轉(zhuǎn)換規(guī)則掛接在通用程序的規(guī)則上*/ /* 下面是該問(wèn)題的狀態(tài)轉(zhuǎn)換規(guī)則(即走步規(guī)則)集,需并入通用程序后*/ rule1(st(X0,X1,X2,X3,X4,X5,X6,X

32、7,X8),st(X2,X1,X0,X3,X4,X5,X6,X7,X8): -X0=0.第 3 章 圖搜索與問(wèn)題求解 rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X4,X1,X2,X3,X0,X5,X6,X7,X8): -X0=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X6,X1,X2,X3,X4,X5,X0,X7,X8): -X0=0. rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X8,X1,X2,X3,X4,X5,X6,X7,X0): -X0=0.rule1(st(X0,X1,

33、X2,X3,X4,X5,X6,X7,X8),st(X0,X2,X1,X3,X4,X5,X6,X7,X8): -X1=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X2,X8,X3,X4,X5,X6,X7,X1): -X1=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X2,X1,X3,X4,X5,X6,X7,X8): -X2=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X3,X2,X4,X5,X6,X7,X8): -X2=0. 第 3 章 圖搜索與問(wèn)題求解

34、 rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X2,X1,X0,X3,X4,X5,X6,X7,X8): -X2=0. rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X3,X2,X4,X5,X6,X7,X8): -X3=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X4,X3,X5,X6,X7,X8): -X3=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X4,X3,X5,X6,X7,X8): -X4=

35、0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X4,X1,X2,X3,X0,X5,X6,X7,X8): -X4=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X3,X5,X4,X6,X7,X8): -X4=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X3,X5,X4,X6,X7,X8): -X5=0. 第 3 章 圖搜索與問(wèn)題求解 rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X3,X4,X6

36、,X5,X7,X8): -X5=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X6,X1,X2,X3,X4,X5,X0,X7,X8): -X6=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X3,X4,X6,X5,X7,X8): -X6=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X3,X4,X5,X7,X6,X8): -X6=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X3,X4,X5

37、,X7,X6,X8): -X7=0. rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X3,X4,X5,X6,X8,X7): -X7=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X8,X2,X3,X4,X5,X6,X7,X1): -X8=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X8,X1,X2,X3,X4,X5,X6,X7,X0): -X8=0.rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X3,X4,X

38、5,X6,X8,X7): -X8=0. 第 3 章 圖搜索與問(wèn)題求解 例例 3.143.14 旅行商問(wèn)題程序。 /* 旅行商問(wèn)題 */ DOMAINS State=st(lists,integer) lists=symbol* Gx,Grule,Fx=integer city1,city2=symbol distance=integer StartingCity=symbol CitySum=integer DATABASE-mydatabase open(State,integer,Gx,Fx) closed(integer,State,integer,Gx) 第 3 章 圖搜索與問(wèn)題求解

39、open1(State,integer,integer,integer) min(State,integer,integer,integer) mark(string,integer) minD(integer) fail_ PREDICATES road(city1,city2,distance) search(StartingCity,CitySum) searching step4(integer,State,Gx) step56(integer,State,Gx) calculator(integer,integer,integer,integer,integer) repeat so

40、rt p1 第 3 章 圖搜索與問(wèn)題求解 p12(State,integer,integer,integer) p2 rule(State,State,Grule) member(symbol,lists) append(lists,lists,lists) mindist(integer) mindist1 pa(integer) result GOAL clearwindow, write(Please inout starting city name:), readln(Start), write(Please input the sum of citys in the map:), r

41、eadint(Sum), search(Start,Sum), result. 第 3 章 圖搜索與問(wèn)題求解 CLAUSESsearch(StartingCity,CitySum): - retractall(_,mydatabase),assert(closed(0,st(,0),0,0), assert(open(st(StartingCity,0),0,0,0), assert(mark(StartingCity,CitySum), repeat, searching,!.searching: - open(State,BackPointer,Gx,_), retract(open(St

42、ate,_,_,_), closed(No,_,_,_),No2=No+1, asserta(closed(No2,State,BackPointer,Gx), !,step4(No2,State,Gx). 第 3 章 圖搜索與問(wèn)題求解 searching: -assert(fail_). result: -not(fail_),closed(_,st(L,_),_,G),write(L,G). result: -beep,write(sorry dont find a road!). step4(_,st(L,N),_): -mark(_,StateSum),N=StateSum. step

43、4(No,State,Gx): -step56(No,State,Gx),!,fail. step56(No,st(L,N),Gx): - %Gx為當(dāng)前節(jié)點(diǎn)的代價(jià) rule(st(L,N),StateY,Grule),%Grule為規(guī)則的代價(jià)(即邊代價(jià)) not(open(StateY,_,_,_), %StateY為擴(kuò)展得到的子節(jié)點(diǎn) not(closed(_,StateY,_,_), calculator(N,Gx,Grule,Gy,Fy), asserta(open(StateY,No,Gy,Fy), fail. 第 3 章 圖搜索與問(wèn)題求解 step56(_, _, _): -sort,

44、!. % 按估價(jià)函數(shù)值對(duì)OPEN表以升序排序calculator(N,Gx,Grule,Gy,Fy): - Gy=Gx+Grule, %計(jì)算子節(jié)點(diǎn)的代價(jià)值g(y) mark(_,CitySum), mindist(MinD), Hy=(CitySum-N-1)*MinD, %計(jì)算子節(jié)點(diǎn)的啟發(fā)函數(shù)值h(y) Fy=Gy+Hy,!. %計(jì)算子節(jié)點(diǎn)的估價(jià)函數(shù)值f(y)=g(y)+h(y)mindist(MinD): -road(_,_,D1),assert(minD(D1),mindist1,minD(MinD),!.mindist1: -road(_,_,D),pa(D),fail.mindist

45、1: -!. pa(D): -minD(Do),DoD,retract(minD(_),assert(minD(D),!.pa(_): -!. 第 3 章 圖搜索與問(wèn)題求解 sort: -not(open(_,_,_,_),!.sort: -repeat,open(X,N,G,F),assert(min(X,N,G,F),p1,not(open(_,_,_,_),p2.p1: -open(X,N,G,F),p12(X,N,G,F),fail.p1: -min(X,N,G,F), assertz(open1(X,N,G,F),retract(open(X,N,G,F),retract(min(_

46、,_,_,_),!.p12(_,_,G,Fn): -min(_,_,_,Fo),Fo=Fn,!.p12(X,N,G,Fn): -retract(min(_,_,_,_),assert(min(X,N,G,Fn),!.p2: -open1(X,N,G,F),assertz(open(X,N,G,F),fail.p2: -retractall(open1(_,_,_,_),!.repeat.repeat: -repeat. member(X,X|_).member(X,_|Y): -member(X,Y). 第 3 章 圖搜索與問(wèn)題求解 append(,L,L).append(H|T,L,H|Tn

47、): -append(T,L,Tn).KH*2rule(st(H|T,IN),st(OL,ON),Grule): - %狀態(tài)變換規(guī)則1 mark(StartingCity,StateSum), IN=StateSum-1, road(H,StartingCity,D), append(StartingCity,H|T,OL), ON=IN+1, Grule=D.rule(st(H|T,IN),st(OL,ON),Grule): - %狀態(tài)變換規(guī)則2第 3 章 圖搜索與問(wèn)題求解 road(H,Y,D), not(member(Y,H|T), append(Y,H|T,OL), ON=IN+1,

48、Grule=D. /* 交通圖 (如)road(xian,beijing,1165).road(xian,shanghai,1511). */ 第 3 章 圖搜索與問(wèn)題求解 估價(jià)函數(shù)f(x)為代價(jià)函數(shù)g(x)和啟發(fā)函數(shù)h(x)之和。 其中代價(jià)函數(shù)的計(jì)算公式為節(jié)點(diǎn)(AXY)的代價(jià)起始城市到X城的代價(jià)X城到Y(jié)城的代價(jià)其中的代價(jià)可以是距離、 費(fèi)用或時(shí)間等(下同)。 啟發(fā)函數(shù)值的計(jì)算公式為 節(jié)點(diǎn)(AXY)的啟發(fā)值(城市總數(shù)-已訪(fǎng)問(wèn)過(guò)的城市數(shù)-1)min所有兩城間的代價(jià) 第 3 章 圖搜索與問(wèn)題求解 該程序?qū)嶋H是一個(gè)旅行商問(wèn)題的通用程序。 對(duì)于一個(gè)具體的旅行路徑規(guī)劃, 還需也只需把具體的“地圖”用謂詞r

49、oad(City1, City2, Cost)描述出來(lái), 并作為事實(shí)并入該程序。 該程序還有一個(gè)特點(diǎn)是, 它實(shí)際是進(jìn)行雙重搜索： 一方面在顯式圖(地圖)上進(jìn)行搜索,同時(shí)又在由此產(chǎn)生的隱式圖(以訪(fǎng)問(wèn)過(guò)的城市序列為狀態(tài)節(jié)點(diǎn)的狀態(tài)圖)上進(jìn)行搜索。而該問(wèn)題的解, 并不是隱式圖中的路徑,而是路徑中的最后一個(gè)節(jié)點(diǎn)。 這個(gè)節(jié)點(diǎn)恰好是地圖上的一條路徑。 第 3 章 圖搜索與問(wèn)題求解 3.3 與或圖搜索 3.3.1 與或圖例例3.15 如圖3-12所示,設(shè)有四邊形ABCD和ABCD, 要求證明它們?nèi)?。圖3-12 四邊形ABCD和ABCD第 3 章 圖搜索與問(wèn)題求解 分析：分別連接B、D和B、D, 則原問(wèn)題可分

50、解為兩個(gè)子問(wèn)題： Q1：證明 ABD ABD Q2：證明 BCD BCD于是, 原問(wèn)題的解決可歸結(jié)為這兩個(gè)子問(wèn)題的解決。 換句話(huà)說(shuō),原問(wèn)題被解決當(dāng)且僅當(dāng)這兩個(gè)子問(wèn)題都被解決。第 3 章 圖搜索與問(wèn)題求解 進(jìn)一步,問(wèn)題Q1還可再被分解為 Q11：證明ABAB Q12：證明ADAD Q13：證明AA或 Q11： 證明ABAB Q12： 證明ADAD Q13： 證明 BDBD 第 3 章 圖搜索與問(wèn)題求解 問(wèn)題Q2還可再被分解為 Q21：證明 BCBC Q22：證明 CDCD Q23：證明 CC或 Q21：證明 BCBC Q22：證明 CDCD Q23：證明 BDBD 第 3 章 圖搜索與問(wèn)題求解

51、圖 3-13 問(wèn)題的分解與變換 第 3 章 圖搜索與問(wèn)題求解 圖 3-14 一個(gè)典型的與或圖 第 3 章 圖搜索與問(wèn)題求解 3.3.2 與或圖搜索1. 1. 搜索方式搜索方式, ,解圖解圖( (樹(shù)樹(shù)) )第 3 章 圖搜索與問(wèn)題求解 2. 2. 可解性判別可解性判別一個(gè)節(jié)點(diǎn)的可解性判別準(zhǔn)：。 (1) 一個(gè)節(jié)點(diǎn)是可解, 則節(jié)點(diǎn)須滿(mǎn)足下列條件之一: 終止節(jié)點(diǎn)是可解節(jié)點(diǎn)。 一個(gè)與節(jié)點(diǎn)可解, 當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全都可解。 一個(gè)或節(jié)點(diǎn)可解, 只要其子節(jié)點(diǎn)至少有一個(gè)可解。 (2) 一個(gè)節(jié)點(diǎn)是不可解, 則節(jié)點(diǎn)須滿(mǎn)足下列條件之一: 非終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)。 一個(gè)與節(jié)點(diǎn)不可解, 只要其子節(jié)點(diǎn)至少有一個(gè)不可

52、解。 一個(gè)或節(jié)點(diǎn)不可解, 當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全都不可解。 第 3 章 圖搜索與問(wèn)題求解 3. 3. 搜索策略搜索策略與或圖搜索也分為盲目搜索和啟發(fā)式搜索兩大類(lèi)。前者又分為窮舉搜索和盲目碰撞搜索。窮舉搜索又分為深度優(yōu)先和廣度優(yōu)先兩種基本策略。 第 3 章 圖搜索與問(wèn)題求解 4. 4. 搜索算法搜索算法與或樹(shù)的樹(shù)式搜索過(guò)程： 步1 把初始節(jié)點(diǎn)Qo放入OPEN表。 步2 移出OPEN表的第一個(gè)節(jié)點(diǎn)N放入CLOSED表, 并冠以序號(hào)n。 步3 若節(jié)點(diǎn)N可擴(kuò)展, 則做下列工作： (1) 擴(kuò)展N, 將其子節(jié)點(diǎn)配上指向父節(jié)點(diǎn)的指針后放入OPEN表。 (2)考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。 若有, 則標(biāo)記它們?yōu)?/p>

53、可解節(jié)點(diǎn), 并將它們也放入CLOSED表, 然后由它們的可解反向推斷其先輩節(jié)點(diǎn)的可解性, 并對(duì)其中的可解節(jié)點(diǎn)進(jìn)行標(biāo)記。 如果初始節(jié)點(diǎn)也被標(biāo)記為可解節(jié)點(diǎn), 則搜索成功,結(jié)束。第 3 章 圖搜索與問(wèn)題求解 (3)刪去OPEN表中那些具有可解先輩的節(jié)點(diǎn)(因?yàn)槠湎容吂?jié)點(diǎn)已經(jīng)可解, 故已無(wú)再考察該節(jié)點(diǎn)的必要), 轉(zhuǎn)步2。 步4 若N不可擴(kuò)展, 則做下列工作： (1)標(biāo)記N為不可解節(jié)點(diǎn), 然后由它的不可解反向推斷其先輩節(jié)點(diǎn)的可解性, 并對(duì)其中的不可解節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始節(jié)點(diǎn)So也被標(biāo)記為不可解節(jié)點(diǎn), 則搜索失敗, 退出。(2)刪去OPEN表中那些具有不可解先輩的節(jié)點(diǎn)(因?yàn)槠湎容吂?jié)點(diǎn)已不可解,故已無(wú)再考察

54、這些節(jié)點(diǎn)的必要), 轉(zhuǎn)步2。 第 3 章 圖搜索與問(wèn)題求解 例例 3.16設(shè)有與或樹(shù)如圖3-15所示, 其中1號(hào)節(jié)點(diǎn)為初始節(jié)點(diǎn),t1、t2、t3、t4均為終止節(jié)點(diǎn), A和B是不可解的端節(jié)點(diǎn)。 采用廣度(優(yōu)先)搜索策略, 搜索過(guò)程如下： (1) 擴(kuò)展1號(hào)節(jié)點(diǎn), 得2號(hào)和3號(hào)節(jié)點(diǎn), 依次放入OPEN表尾部。由于這兩個(gè)節(jié)點(diǎn)都非終止節(jié)點(diǎn), 所以接著擴(kuò)展2號(hào)節(jié)點(diǎn)。 此時(shí)OPEN表中只有3號(hào)節(jié)點(diǎn)。 (2) 2號(hào)節(jié)點(diǎn)擴(kuò)展后,得4號(hào)節(jié)點(diǎn)和t1節(jié)點(diǎn)。此時(shí)OPEN表中依次有3號(hào)、4號(hào)和t1節(jié)點(diǎn)。由于t1是終止節(jié)點(diǎn),故標(biāo)記它為可解節(jié)點(diǎn), 并將它放入CLOSED表, 再判斷其先輩節(jié)點(diǎn)的可解性,但t1的父節(jié)點(diǎn)2是一個(gè)與

55、節(jié)點(diǎn), 故僅由t1的可解還不能確定2號(hào)節(jié)點(diǎn)可解。所以, 就繼續(xù)搜索。 第 3 章 圖搜索與問(wèn)題求解 圖 3-15 與或樹(shù)及其解樹(shù) 第 3 章 圖搜索與問(wèn)題求解 (3) 擴(kuò)展3號(hào)節(jié)點(diǎn),得5號(hào)節(jié)點(diǎn)和B節(jié)點(diǎn)。兩者均非終止節(jié)點(diǎn), 所以繼續(xù)擴(kuò)展4號(hào)節(jié)點(diǎn)。 (4) 4號(hào)節(jié)點(diǎn)擴(kuò)展后得節(jié)點(diǎn)A和t2。t2是終止節(jié)點(diǎn),標(biāo)記為可解節(jié)點(diǎn), 放入CLOSED表。這時(shí)其先輩節(jié)點(diǎn)4和2也為可解節(jié)點(diǎn), 但1號(hào)節(jié)點(diǎn)還不能確定。這時(shí)從OPEN表中刪去節(jié)點(diǎn)A,因?yàn)槠涓腹?jié)點(diǎn)4已經(jīng)可解。 () 擴(kuò)展5號(hào)節(jié)點(diǎn)得t3和t4。由于t3和t4都為終止節(jié)點(diǎn)(放入CLOSED表), 故可推得節(jié)點(diǎn)5、3、1均為可解節(jié)點(diǎn)。 搜索成功, 結(jié)束。 這時(shí),

56、由CLOSED表便得到由節(jié)點(diǎn)1、2、3、4、5和t1、t2、 t3、t4構(gòu)成的解樹(shù)，如圖3-15 中的粗線(xiàn)所示。 第 3 章 圖搜索與問(wèn)題求解 3.3.3 啟發(fā)式與或樹(shù)搜索1. 1. 解樹(shù)的代價(jià)解樹(shù)的代價(jià)解樹(shù)的代價(jià)就是樹(shù)根的代價(jià)。計(jì)算方法如下：設(shè)g(x)表示節(jié)點(diǎn)x的代價(jià),c(x,y)表示節(jié)點(diǎn)x到其子節(jié)點(diǎn)y的代價(jià)(即邊xy的代價(jià)), 則 (1) 若x是終止節(jié)點(diǎn), 則 g(x)0。 第 3 章 圖搜索與問(wèn)題求解 (2) 若x是或節(jié)點(diǎn), 。其中y1, y2, , yn是x的子節(jié)點(diǎn)。 (3) 若x是與節(jié)點(diǎn)x, 則有兩種計(jì)算公式。 和代價(jià)法： 。 最大代價(jià)法： 。其中y1, y2, , yn是x的子節(jié)點(diǎn)

57、。 (4) 對(duì)非終止的端節(jié)點(diǎn)x, g(x)。 )(),(min)(1iiniygyxcxg)(),()(1iiniygyxcxg)(),(max)(1iiniygyxcxg第 3 章 圖搜索與問(wèn)題求解 例例3.17 如圖3-16所示的與或樹(shù), 其中包括兩棵解樹(shù), 一棵解樹(shù)由Qo,A,t1和t2組成；另一棵解樹(shù)由Qo,B,D,G,t4和t5組成。 在此與或樹(shù)中,t1,t2,t3,t4,t5為終止節(jié)點(diǎn)；E,F是非終止的端節(jié)點(diǎn), 其代價(jià)均為；邊上的數(shù)字是該邊的代價(jià)。 由右邊的解樹(shù)可得： 按和代價(jià)： g(A)=11,g(Qo)=13 按最大代價(jià)：g(A)=6, g(Qo)=8 由左邊的解樹(shù)可得： 按和

58、代價(jià)： g(G)=3, g(D)=4, g(B)=6, g(Qo)=8 按最大代價(jià)： g(G)=2, g(D)=3, g(B)=5, g(Qo)=7 第 3 章 圖搜索與問(wèn)題求解 圖 3-16 含代價(jià)的與或樹(shù) 第 3 章 圖搜索與問(wèn)題求解 2. 希望樹(shù)希望樹(shù) 希望樹(shù)的定義： (1) 初始節(jié)點(diǎn)Qo在希望樹(shù)T中。 (2) 如果節(jié)點(diǎn)x在希望樹(shù)T中, 則一定有： 如果x是具有子節(jié)點(diǎn)y1,y2, ,yn的“或”節(jié)點(diǎn),則具有值的那個(gè)子節(jié)點(diǎn)yi也應(yīng)在T中。 如果x是“與”節(jié)點(diǎn), 則它的全部子節(jié)點(diǎn)都應(yīng)在T中。 )(),(min1iiniygyxc第 3 章 圖搜索與問(wèn)題求解 3. 3. 與或樹(shù)的有序搜索過(guò)程與

59、或樹(shù)的有序搜索過(guò)程與或樹(shù)的有序搜索過(guò)程是一個(gè)不斷選擇、修正希望樹(shù)的過(guò)程。如果問(wèn)題有解, 則經(jīng)有序搜索將找到最優(yōu)解樹(shù)。 其搜索過(guò)程如下： 步1 把初始節(jié)點(diǎn)Qo放入OPEN表中。 步2 求出希望樹(shù)T, 即根據(jù)當(dāng)前搜索樹(shù)中節(jié)點(diǎn)的代價(jià)g求出以Qo為根的希望樹(shù)T。 步3 依次把OPEN表中T的端節(jié)點(diǎn)N選出放入CLOSED表中。 第 3 章 圖搜索與問(wèn)題求解 步4 如果節(jié)點(diǎn)N是終止節(jié)點(diǎn), 則做下列工作： (1) 標(biāo)示N為可解節(jié)點(diǎn)。 (2) 對(duì)T應(yīng)用可解標(biāo)記過(guò)程, 把N的先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)都標(biāo)記為可解節(jié)點(diǎn)。 (3) 若初始節(jié)點(diǎn)Qo能被標(biāo)記為可解節(jié)點(diǎn), 則T就是最優(yōu)解樹(shù),成功退出。 (4) 否則, 從OPE

60、N表中刪去具有可解先輩的所有節(jié)點(diǎn)。 第 3 章 圖搜索與問(wèn)題求解 步5 如果節(jié)點(diǎn)N不是終止節(jié)點(diǎn), 且它不可擴(kuò)展, 則做下列工作： (1) 標(biāo)示N為不可解節(jié)點(diǎn)。 (2) 對(duì)T應(yīng)用不可解標(biāo)記過(guò)程, 把N的先輩節(jié)點(diǎn)中的不可解節(jié)點(diǎn)都標(biāo)記為不可解節(jié)點(diǎn)。 (3) 若初始節(jié)點(diǎn)Qo也被標(biāo)記為不可解節(jié)點(diǎn), 則失敗退出。 (4) 否則, 從OPEN表中刪去具有不可解先輩的所有節(jié)點(diǎn)。 第 3 章 圖搜索與問(wèn)題求解 步6 如果節(jié)點(diǎn)N不是終止節(jié)點(diǎn), 但它可擴(kuò)展, 則可做下列工作： (1) 擴(kuò)展節(jié)點(diǎn)N, 產(chǎn)生N的所有子節(jié)點(diǎn)。 (2)把這些子節(jié)點(diǎn)都放入OPEN表中, 并為每一個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)(節(jié)點(diǎn)N)的指針。 (3)