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

1、第 3 章 圖搜索與問(wèn)題求解 第第2篇篇 搜索與求解搜索與求解 搜索是人工智能技術(shù)中進(jìn)行問(wèn)題求解的基本技術(shù)，不管是符號(hào)智能還是計(jì)算智能，不管是解決具體應(yīng)用問(wèn)題（如證明、診斷、規(guī)劃、調(diào)度、配置、優(yōu)化）還是智能行為本身（如學(xué)習(xí)、識(shí)別），最終往往都?xì)w結(jié)為某種搜索，都要用某種搜索算法去實(shí)現(xiàn)。 兩種智能中的搜索互不相同。符號(hào)智能：采用圖搜索。圖搜索運(yùn)用領(lǐng)域知識(shí)，以符號(hào)推演的方式，順序地在問(wèn)題空間中進(jìn)行的，其中的問(wèn)題空間又可表示為某種狀態(tài)圖（空間）或者與或圖的形式。發(fā)展較早，如“啟發(fā)式”圖搜索。第 3 章 圖搜索與問(wèn)題求解 計(jì)算智能：采用智能算法。即以計(jì)算為主的算法，隨機(jī)地在問(wèn)題的及空間中進(jìn)行，這類(lèi)搜索算

2、法在解決優(yōu)化問(wèn)題中表現(xiàn)出了卓越的性能，使搜索技術(shù)達(dá)到了一個(gè)新的水平。例如：遺傳算法，免疫算法，粒群算法等。 圖搜索模擬人腦分析問(wèn)題、解決問(wèn)題的過(guò)程，基于領(lǐng)域知識(shí)。 搜索算法借鑒或模擬某些自然現(xiàn)象或生命現(xiàn)象而實(shí)現(xiàn)的搜索和問(wèn)題求解技術(shù)。第 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.5 博弈樹(shù)搜索博弈樹(shù)搜索 第 3 章 圖搜索與問(wèn)題求解 圖搜索中的圖是指由節(jié)點(diǎn)和有向邊（箭頭）組成的網(wǎng)絡(luò)。 連接同一個(gè)節(jié)點(diǎn)間的各邊（箭頭）的邏輯關(guān)系又可劃

3、分為“或”和“與”，則圖搜索就可分為或圖搜索和與或圖搜索兩大類(lèi)?；驁D通常稱(chēng)為狀態(tài)圖（這是因?yàn)楦鳡顟B(tài)之間沒(méi)有與的關(guān)系）。第 3 章 圖搜索與問(wèn)題求解 3.1 狀態(tài)圖搜索 3.1.1 狀態(tài)圖例例3.1 迷宮問(wèn)題。從入口 出發(fā)，即初始節(jié)點(diǎn)，尋找目標(biāo)節(jié)點(diǎn) (出口)，也就是尋找路徑的問(wèn)題。0SgS第 3 章 圖搜索與問(wèn)題求解 圖 3-2 迷宮的有向圖表示 第 3 章 圖搜索與問(wèn)題求解 圖 3-3 八數(shù)碼問(wèn)題示例 例例 3.2 3.2 八數(shù)碼問(wèn)題。規(guī)則：與空格相鄰的數(shù)碼方可移入空格。問(wèn)題：給出初始棋局到目標(biāo)棋局的移動(dòng)序列。這個(gè)問(wèn)題就是經(jīng)典的八數(shù)碼難題或重排九宮問(wèn)題。第 3 章 圖搜索與問(wèn)題求解 上面兩個(gè)問(wèn)

4、題雖然內(nèi)容不同，但抽象地來(lái)看，他們都是在某特有向圖中尋找目標(biāo)或路徑的問(wèn)題。在人工智能技術(shù)中，把這種描述問(wèn)題的有向圖稱(chēng)為狀態(tài)空間圖，簡(jiǎn)稱(chēng)狀態(tài)圖。 狀態(tài)圖中的節(jié)點(diǎn)代表問(wèn)題中的一種格局，一般稱(chēng)為問(wèn)題的一個(gè)狀態(tài)；邊表示兩節(jié)點(diǎn)之間的某種聯(lián)系，如，它可以是某種操作、規(guī)則、變換、算子、通道或關(guān)系等等。 從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條路徑就是問(wèn)題的一個(gè)解，根據(jù)需要，路徑解可以分為： 節(jié)點(diǎn)序列：如例3.1 邊的序列：如例3.2，也可認(rèn)為是棋步序列 還有許多智力問(wèn)題，如梵塔問(wèn)題、旅行商問(wèn)題、八皇后問(wèn)題、農(nóng)夫過(guò)河問(wèn)題等等，以及實(shí)際問(wèn)題，如路徑規(guī)劃、定理證明、演繹推理、機(jī)器人行動(dòng)規(guī)劃等，都可以歸結(jié)為在某一狀態(tài)圖中尋找目標(biāo)

5、或路徑的問(wèn)題。第 3 章 圖搜索與問(wèn)題求解 3.1.2 3.1.2 狀態(tài)圖搜索狀態(tài)圖搜索 搜索是狀態(tài)圖中尋找目標(biāo)或路徑的基本方法。 搜索的定義：從初始狀態(tài)出發(fā)，沿著與之相連得邊試探地前進(jìn)，尋找目標(biāo)節(jié)點(diǎn)的過(guò)程。尋找目標(biāo)和尋找路徑是一致的。 搜索的過(guò)程中，要經(jīng)過(guò)許多的節(jié)點(diǎn)和邊，這些節(jié)點(diǎn)和邊按照一定的關(guān)系構(gòu)成一個(gè)樹(shù)型的有向圖，稱(chēng)為搜索樹(shù)。 為了方便的找出搜索路徑或節(jié)點(diǎn)，搜索過(guò)程中應(yīng)當(dāng)隨時(shí)記錄搜索軌跡。第 3 章 圖搜索與問(wèn)題求解 第 3 章 圖搜索與問(wèn)題求解 如何用計(jì)算機(jī)來(lái)實(shí)現(xiàn)上述搜索？主要考慮三個(gè)方面：搜索方式、搜索策略和搜索算法。1. 1. 搜索方式搜索方式樹(shù)式搜索：形象的講就是以“畫(huà)樹(shù)”的方式

6、進(jìn)行搜索。即從樹(shù)根（初始節(jié)點(diǎn)）出發(fā)，一筆一筆的描繪出一顆樹(shù)來(lái)。準(zhǔn)確來(lái)說(shuō)，就是在搜索過(guò)程中記錄所經(jīng)過(guò)的所有節(jié)點(diǎn)和邊。這棵樹(shù)就是搜索過(guò)程中產(chǎn)生的搜索樹(shù)。樹(shù)式搜索又可采用多種搜索策略，如深度優(yōu)先、廣度優(yōu)先等。 線式搜索：形象的講就是以“畫(huà)線”的方式進(jìn)行搜索。準(zhǔn)確來(lái)說(shuō)，就是搜索過(guò)程中只記錄那些認(rèn)為是處在所找路徑上的節(jié)點(diǎn)和邊。這樣搜索的軌跡就是一條“線”。采用深度優(yōu)先策略。 第 3 章 圖搜索與問(wèn)題求解 線式搜索的基本方式又可分為不回溯的和可回溯的兩種。 不回溯：遇到“叉路口”僅沿一條路前進(jìn)，即對(duì)每一個(gè)節(jié)點(diǎn)始終都僅生成一個(gè)子節(jié)點(diǎn)（如果有子節(jié)點(diǎn)的話），也可稱(chēng)為對(duì)該節(jié)點(diǎn)進(jìn)行擴(kuò)展，且僅擴(kuò)展一個(gè)子節(jié)點(diǎn)。 如果遇

7、到目標(biāo)節(jié)點(diǎn)，則搜索成功； 如果不能再擴(kuò)展還沒(méi)找到目標(biāo)節(jié)點(diǎn)，則搜索失敗。 可回溯：當(dāng)遇到某節(jié)點(diǎn)不能擴(kuò)展的話，則返回上一節(jié)點(diǎn)，擴(kuò)展另一條邊（如果有的話）。 如果遇到目標(biāo)節(jié)點(diǎn)，則搜索成功； 如果回溯到初始節(jié)點(diǎn)也未找到，則搜索失敗。第 3 章 圖搜索與問(wèn)題求解 總結(jié)：樹(shù)式搜索成功后，還需要從搜索樹(shù)中找出所求路徑。而線式搜索只要成功，所經(jīng)過(guò)的那一條線就是路徑。 樹(shù)式搜索中尋找路徑的方法：對(duì)節(jié)點(diǎn)間的父子關(guān)系做一記錄，當(dāng)搜索成功時(shí)，逆向按父子關(guān)系追溯回去，到達(dá)初始節(jié)點(diǎn)，這條路徑就是所求路徑。第 3 章 圖搜索與問(wèn)題求解 2. 搜索策略搜索策略 盲目搜索：通俗的講，就是無(wú)“向?qū)А钡乃阉?，?shù)式盲目搜索就是窮舉式

8、搜索，即從初始節(jié)點(diǎn)出發(fā)，沿連接邊逐一考察各個(gè)節(jié)點(diǎn)（看是否為目標(biāo)節(jié)點(diǎn)）；線式盲目搜索，對(duì)于不回溯的就是隨機(jī)碰撞式搜索，對(duì)于回溯的則也是窮舉式的搜索。 啟發(fā)式(heuristic)搜索：利用“啟發(fā)性信息”引導(dǎo)的搜索。所謂“啟發(fā)性信息”就是與問(wèn)題有關(guān)的有利于盡快找到問(wèn)題解的信息或知識(shí)。通俗的講，可以認(rèn)為是按照某種規(guī)則進(jìn)行搜索，這樣就會(huì)少走彎路，提高搜索效率，而且可能找到問(wèn)題的最優(yōu)解。 根據(jù)啟發(fā)性信息內(nèi)容和使用方式的不同，可分為不同的策略，如全局擇優(yōu)、局部擇優(yōu)、最佳圖搜索等。 根據(jù)搜索范圍的擴(kuò)展順序不同，可分為廣度優(yōu)先和深度優(yōu)先兩種。第 3 章 圖搜索與問(wèn)題求解 圖 3-4 OPEN表與CLOSED表

9、示例 3. 3. 搜索算法搜索算法OPEN表：登記當(dāng)前待考察的節(jié)點(diǎn)。CLOSED表：記錄考察過(guò)的節(jié)點(diǎn)。第 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)(如果有的話)。 (2)對(duì)已存在于OPEN表的節(jié)點(diǎn)(如果有的話)也刪除之；但刪除

10、之前要比較其返回初始節(jié)點(diǎn)的新路徑與原路徑,如果新路徑“短”, 則修改這些節(jié)點(diǎn)在OPEN表中的原返回指針,使其沿新路返回(如圖3-5所示 )。 (3)對(duì)已存在于CLOSED表的節(jié)點(diǎn)(如果有的話), 做與(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) 步6中修改返回指針的原因是,

11、因?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)題求解 OPEN表 CLOSED表節(jié)點(diǎn)父節(jié)點(diǎn)S0DADCCBBS0AS0編號(hào)節(jié)點(diǎn)父節(jié)點(diǎn)nS0n+1BS0n+2CBn+3DCn+4AS0n+5DA第 3 章 圖搜索與問(wèn)題求解 線式搜索算法

12、： 不回溯的線式搜索不回溯的線式搜索 步1 把初始節(jié)點(diǎn)So放入CLOSED表中。步2 令NSo。步3 若N是目標(biāo)節(jié)點(diǎn),則搜索成功,結(jié)束。 步4 若N不可擴(kuò)展,則搜索失敗,退出。 步5 擴(kuò)展N,選取其一個(gè)未在CLOSED表中出現(xiàn)過(guò)的子節(jié)點(diǎn)N1放入CLOSED表中, 令NN1, 轉(zhuǎn)步3。 第 3 章 圖搜索與問(wè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,

13、 轉(zhuǎn)步4。步5擴(kuò)展N, 選取其一個(gè)未在CLOSED表用出現(xiàn)過(guò)的子節(jié)點(diǎn)N1放入CLOSED表中, 令NN1,轉(zhuǎn)步3。 第 3 章 圖搜索與問(wèn)題求解 需要說(shuō)明的是，上述算法僅是搜索目標(biāo)節(jié)點(diǎn)的算法，當(dāng)搜索成功后，如果需要路徑，則還須有CLOSED表再找出路徑。找路徑的方法是： 對(duì)于樹(shù)式搜索，從CLOSED表中序號(hào)最大的節(jié)點(diǎn)起，根據(jù)返回指針追溯至初始節(jié)點(diǎn)S0，即可得到。 對(duì)于線式搜索，CLOSED表即是所找路徑。第 3 章 圖搜索與問(wèn)題求解 3.1.3 窮舉式搜索 我們來(lái)討論樹(shù)式搜索的窮舉式，可分廣度優(yōu)先和深度優(yōu)先兩種方式，這兩種是最基本的樹(shù)式搜索策略，其他搜索策略都是建立在它們之上的。 1.1.廣度

14、優(yōu)先搜索廣度優(yōu)先搜索 先考察同一級(jí)節(jié)點(diǎn)，考察完后，繼續(xù)考察下一級(jí)節(jié)點(diǎn)。換句話說(shuō)，初始節(jié)點(diǎn)為根節(jié)點(diǎn)，向下逐級(jí)擴(kuò)展搜索樹(shù)。所以，廣度優(yōu)先策略的搜索樹(shù)式自頂向下一層一層逐漸生成的。第 3 章 圖搜索與問(wèn)題求解 例3.3 用廣度優(yōu)先搜索策略解八數(shù)碼難題。 規(guī)則:空格可向上、下、左、右四個(gè)方向移動(dòng)。圖 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é)束

15、。 步5 若N不可擴(kuò)展, 則轉(zhuǎn)步2。步6 擴(kuò)展N, 將其所有子節(jié)點(diǎn)配上指向N的指針依次放入OPEN表尾部, 轉(zhuǎn)步2。 第 3 章 圖搜索與問(wèn)題求解 這里OPEN表是一個(gè)隊(duì)列，CLOSED表是一個(gè)順序表，表中各點(diǎn)按順序編號(hào)，正被考察的節(jié)點(diǎn)在表中編號(hào)最大。如果問(wèn)題有解，OPEN表中必出現(xiàn)目標(biāo)節(jié)點(diǎn)Sg，當(dāng)搜索到該節(jié)點(diǎn)時(shí)，算法結(jié)束。然后反向追溯得路徑。 廣度優(yōu)先搜索亦稱(chēng)為寬度優(yōu)先或橫向搜索。 優(yōu)點(diǎn)：這種策略是完備的，即問(wèn)題的解存在，則一定能找到，且是最優(yōu)解（路徑最短）。 缺點(diǎn)：搜索效率低。第 3 章 圖搜索與問(wèn)題求解 2.2.深度優(yōu)先搜索深度優(yōu)先搜索 在搜索樹(shù)的每一層始終先擴(kuò)展一個(gè)子節(jié)點(diǎn)，不斷地向縱深

16、前進(jìn)，直到不能再前進(jìn)（到達(dá)葉子節(jié)點(diǎn)或受到深度限制）時(shí)，才從當(dāng)前節(jié)點(diǎn)返回到上一級(jí)節(jié)點(diǎn)，沿另一方向又繼續(xù)前進(jìn)。這種方法的搜索樹(shù)式從樹(shù)根開(kāi)始一枝一枝逐漸形成的。第 3 章 圖搜索與問(wèn)題求解 例3.4 對(duì)于八數(shù)碼問(wèn)題，應(yīng)用深度優(yōu)先策略，可得如圖3-7所示的搜索樹(shù)。圖3-7 八數(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。

17、步6擴(kuò)展N, 將其所有子節(jié)點(diǎn)配上指向N的返回指針依次放入OPEN表的首部, 轉(zhuǎn)步2。 第 3 章 圖搜索與問(wèn)題求解 這里的OPEN表為一個(gè)堆棧。這是與橫向優(yōu)先算法的唯一區(qū)別。 深度優(yōu)先搜索亦稱(chēng)為縱向搜索。由于一個(gè)有解的問(wèn)題樹(shù)可能含有無(wú)窮分枝，深度優(yōu)先如果誤入無(wú)窮分枝（即深度無(wú)限）則不可能找到目標(biāo)節(jié)點(diǎn)。所以，深度優(yōu)先搜索策略是不完備的。另外，應(yīng)用此策略得到的解不一定是最佳解（最短路徑）。第 3 章 圖搜索與問(wèn)題求解 3. 有界深度優(yōu)先搜索有界深度優(yōu)先搜索 前面兩種是基本的窮舉搜索方法，如果加上一定的限制條件，則可派生出許多特殊的搜索方法，例如有界深度優(yōu)先搜索。 如果給出搜索樹(shù)深度限制，則產(chǎn)生有界

18、深度優(yōu)先搜索。當(dāng)從初始節(jié)點(diǎn)出發(fā)沿某一分枝擴(kuò)展到一限定深度是，就不能再繼續(xù)向下擴(kuò)展，而只能改變方向繼續(xù)搜索。節(jié)點(diǎn)x的深度（即位于搜索樹(shù)的層數(shù)）通常用d(x)表示。第 3 章 圖搜索與問(wèn)題求解 有界深度優(yōu)先算法：有界深度優(yōu)先算法： 步1 把So放入OPEN表中,置So的深度d(So)=0。 步2 若OPEN表為空, 則失敗, 退出。 步3 取OPEN表中前面第一個(gè)節(jié)點(diǎn)N,放入CLOSED表中, 并冠以順序編號(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的返回指針后依次放入

19、OPEN表中前部, 置d(Ni)=d(N)+1,轉(zhuǎn)步2。 第 3 章 圖搜索與問(wèn)題求解 3.1.4 啟發(fā)式搜索 1. 1. 問(wèn)題的提出問(wèn)題的提出 窮舉式算法，從理論上講可以解決任何狀態(tài)空間的搜索問(wèn)題，但只能解決狀態(tài)空間很小的簡(jiǎn)單問(wèn)題，大空間問(wèn)題往往會(huì)導(dǎo)致“組合爆炸”。 例如，在梵塔問(wèn)題中，如果階數(shù)較小（如小于6），則用計(jì)算機(jī)計(jì)算并不困難，如果階數(shù)為64，那么狀態(tài)空間就有 個(gè)節(jié)點(diǎn)，計(jì)算機(jī)是計(jì)算不了的。 30641094. 03第 3 章 圖搜索與問(wèn)題求解 又如博弈問(wèn)題，計(jì)算機(jī)為了取勝，它可以將所有算法都試一下，然后選擇最佳走步，尋找所需要的計(jì)算量大的驚人。如國(guó)際象棋可能有的棋局?jǐn)?shù)是 ，計(jì)算機(jī)大約

20、需要計(jì)算 年，這些都迫使人們尋找更有效的搜索方法，即提出啟發(fā)式搜索策略。120101610第 3 章 圖搜索與問(wèn)題求解 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)。 (3) 用于刪除節(jié)點(diǎn)的選擇,即用于決定應(yīng)刪除哪些無(wú)用節(jié)點(diǎn), 以免造成進(jìn)一步的時(shí)空浪費(fèi)。 例如，由八數(shù)碼問(wèn)題的部分狀態(tài)圖可以看出，從初始節(jié)點(diǎn)開(kāi)始，通向目標(biāo)節(jié)點(diǎn)的路徑上，各節(jié)點(diǎn)的數(shù)碼格局同目標(biāo)節(jié)點(diǎn)相比較，其數(shù)碼不同的位置個(gè)數(shù)在逐漸減少，最好為零，這

21、就是一個(gè)啟發(fā)性信息，屬于第一種類(lè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)。 啟發(fā)函數(shù)沒(méi)有固定模式，需要具體問(wèn)題具體分析。4.4.啟發(fā)式搜索算法啟發(fā)式搜索算法 在狀態(tài)圖一般搜索算法基礎(chǔ)上增加啟發(fā)函數(shù)，由啟發(fā)函數(shù)來(lái)確定節(jié)點(diǎn)的擴(kuò)展。1) 全局擇優(yōu)搜索：最好優(yōu)先搜索法，基本思想是在OPEN表中保留已生成而未考察的節(jié)點(diǎn)，用啟發(fā)函數(shù)進(jìn)行估價(jià)，選出最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展。 第 3 章 圖搜索與問(wèn)題求解 全局擇優(yōu)搜索算法： 步1 把初始節(jié)點(diǎn)So放入OPEN表中,計(jì)算h(So)。步2 若OPEN表為空,則搜索失敗,

22、退出。 步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, 計(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.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,

23、Sg。 第 3 章 圖搜索與問(wèn)題求解 圖 3-8 八數(shù)碼問(wèn)題的全局擇優(yōu)搜索 第 3 章 圖搜索與問(wèn)題求解 2) 2) 局部擇優(yōu)搜索局部擇優(yōu)搜索 與全局擇優(yōu)搜索的不同之處：擴(kuò)展節(jié)點(diǎn)N后僅對(duì)N的子節(jié)點(diǎn)按啟發(fā)函數(shù)值大小以升序排序，再將它們依次放入OPEN表的首部。第 3 章 圖搜索與問(wèn)題求解 3.1.5 加權(quán)狀態(tài)圖搜索1.1.加權(quán)狀態(tài)圖與代價(jià)樹(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)用的旅行路線。 第 3 章 圖搜索與問(wèn)題求解 圖 3-9 交通圖及其代價(jià)樹(shù) 與狀態(tài)圖不同：邊上附有數(shù)值，表示一種度

24、量。 通常把這種數(shù)值稱(chēng)為權(quán)值，這種狀態(tài)圖稱(chēng)為加權(quán)狀態(tài)圖或賦權(quán)狀態(tài)圖。第 3 章 圖搜索與問(wèn)題求解 代價(jià)樹(shù)（加權(quán)狀態(tài)圖）的搜索。所謂代價(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-9的加權(quán)狀態(tài)圖（a）轉(zhuǎn)換為代價(jià)樹(shù)后為（b）。第 3 章 圖搜索與問(wèn)題求解 2.2.分支界限法分支界限法( (最小代價(jià)優(yōu)先法最小代價(jià)優(yōu)先法) ) 基本思想是：每次從OPEN表中選出g(x)值最小的節(jié)點(diǎn)進(jìn)行考察, 而不管

25、這個(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ì)算的。即g(x)與父節(jié)點(diǎn)代價(jià)有關(guān)； h(x) 與父、子節(jié)點(diǎn)均無(wú)關(guān)系，僅與目標(biāo)節(jié)點(diǎn)有關(guān)。第 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)。 第 3 章

26、圖搜索與問(wèn)題求解 3.1.6 A算法和A*算法1.1.估價(jià)函數(shù)估價(jià)函數(shù) h(x)作為啟發(fā)函數(shù)制導(dǎo)的啟發(fā)式搜索，實(shí)際上是一種深度優(yōu)先的搜索策略。高效，但可能誤入歧途，為此，對(duì)啟發(fā)函數(shù)進(jìn)行擴(kuò)充，提出估價(jià)函數(shù)，一般形式： f(x)g(x)h(x) 有時(shí)估價(jià)函數(shù)還可以表示為： f(x)=d(x)+h(x)d(x)表示節(jié)點(diǎn)x的深度。 g(x)、 d(x)有利于搜索的橫向發(fā)展； h(x) 有利于縱向發(fā)展?？蓮耐陚湫院退阉餍蕘?lái)分析f(x)。第 3 章 圖搜索與問(wèn)題求解 2. A算法算法 A 算法是基于估價(jià)函數(shù)f(x)的一種加權(quán)狀態(tài)圖啟發(fā)式搜索算法。其具體步驟如下： 步1 把附有f(So)的初始節(jié)點(diǎn)So放入

27、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)做如下處理： (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(

28、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ì)算公式則需由具體問(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

29、(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)題求解 A*算法中，限制h(x)h*(x) 的原因是為了保證取得最優(yōu)解。理論分析證明，如果問(wèn)題存在最優(yōu)解，則這樣的限制就可保證能找到最優(yōu)解。雖然，這個(gè)限制可能產(chǎn)生無(wú)用搜索。實(shí)際上，不難想象，當(dāng)某一節(jié)點(diǎn)x的h(x)h*(x),則該節(jié)點(diǎn)就可能失去優(yōu)先擴(kuò)展的機(jī)會(huì)，因而導(dǎo)致得不到最優(yōu)解。 A*算法也稱(chēng)為最佳圖搜索算法。第 3 章 圖搜索與問(wèn)題求解 3.1.7 狀態(tài)圖搜索策略小結(jié) 第 3 章 圖搜索與問(wèn)題求解 3.2 狀態(tài)圖搜索問(wèn)題求解

30、 3.2.1 問(wèn)題的狀態(tài)圖表示1. 1. 狀態(tài)狀態(tài) 狀態(tài)就是問(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)圖

31、表示示一個(gè)問(wèn)題的狀態(tài)圖是一個(gè)三元組 (S, F, G) 其中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), (S

32、5, S8), (S8, S5), (S8, S9), (S9, S8), (S9, Sg)G：Sg 迷宮中的格子就是一個(gè)狀態(tài)，狀態(tài)轉(zhuǎn)換規(guī)則就是迷宮中兩個(gè)格子間的通道，也就是狀態(tài)圖中的一條邊。 羅列出全部節(jié)點(diǎn)和邊的狀態(tài)圖稱(chēng)為顯示狀態(tài)圖，或者說(shuō)是狀態(tài)圖的顯示表示。 迷宮中的格子就是一個(gè)狀態(tài)，狀態(tài)轉(zhuǎn)換規(guī)則就是迷宮中兩個(gè)格子間的通道，也就是狀態(tài)圖中的一條邊。 羅列出全部節(jié)點(diǎn)和邊的狀態(tài)圖稱(chēng)為顯示狀態(tài)圖，或者說(shuō)是狀態(tài)圖的顯示表示。第 3 章 圖搜索與問(wèn)題求解 X1X2X3XX0X4X7X6X5例例 3.83.8八數(shù)碼難題的狀態(tài)圖表示。 用向量 A(X0, X1, X2, X3, X4, X5, X6,

33、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)數(shù)碼的移動(dòng)規(guī)則就是該問(wèn)題的狀態(tài)變換規(guī)則，即操作。共有24條移碼規(guī)則，可分為9組。 第 3 章 圖搜索與問(wèn)題求解 0組規(guī)則: ; 0)()0(; 0)()0(; 0)()0(; 0)()0(80804606034040220201XnXnXXrXnXnXXrXnXnXXrXnXnXXr 1組規(guī)則: ; 0)()0(

34、; 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) 第 3 章 圖搜索與問(wèn)題求解 上述狀態(tài)圖中僅給出初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，并未給出其余節(jié)點(diǎn)。其余節(jié)點(diǎn)需用狀態(tài)轉(zhuǎn)換規(guī)則來(lái)產(chǎn)生。類(lèi)似于這樣的狀態(tài)圖稱(chēng)為隱式

35、狀態(tài)圖，或者說(shuō)狀態(tài)圖的隱式表示。第 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è)有三根寶石桿,在

36、1號(hào)桿上穿有A、B兩個(gè)金盤(pán), A小于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

37、號(hào)桿移到第j號(hào)桿上。經(jīng)分析，共有12個(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條件THEN A(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 章

38、圖搜索與問(wèn)題求解 圖 3-11 二階梵塔狀態(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ī)劃一條最短的旅行路線。 該問(wèn)題的狀態(tài)為以A打頭的已訪問(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ò)的城市名序列后端。

39、規(guī)則規(guī)則2 2 如果所有城市都去過(guò)一次, 則從當(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

40、(state) open1(state,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.

41、/* 例如 solve: -search(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

42、(M,_,_), resulting(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_). %

43、步4 若當(dāng)前節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn), 則成功 第 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),

44、%可改變搜索策略 fail.step56(_,_): -!. 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的通用程序。 DOMAIN

45、S State=symbol CLAUSES 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)題程序。我們把前面給

46、出的該問(wèn)題的狀態(tài)圖表示, 用PROLOG語(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,X

47、1,X2,X3,X4,X5,X6,X7,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

48、=0.rule1(st(X0,X1,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

49、=0. 第 3 章 圖搜索與問(wèn)題求解 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,

50、X5,X6,X7,X8): -X4=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

51、(X0,X1,X2,X3,X4,X6,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

52、(X0,X1,X2,X3,X4,X5,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),s

53、t(X0,X1,X2,X3,X4,X5,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,G

54、x)第 3 章 圖搜索與問(wèn)題求解 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,i

55、nteger) repeat sort 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 city

56、s in the map:), readint(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,_)

57、, retract(open(State,_,_,_), 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)

58、,N=StateSum. step4(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

59、(_, _, _): -sort,!. % 按估價(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),p

60、a(D),fail.mindist1: -!. 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