1、第 3 章 圖搜索與問題求解 第 3 章 圖搜索與問題求解 3.1 狀態圖搜索狀態圖搜索 3.2 狀態圖搜索問題求解狀態圖搜索問題求解 3.3 與或圖搜索與或圖搜索 3.4 與或圖搜索問題求解與或圖搜索問題求解 3.5 博弈樹搜索博弈樹搜索 習題三習題三 第 3 章 圖搜索與問題求解 3.1 狀狀 態態 圖圖 搜搜 索索 3.1.1 3.1.1 狀態圖狀態圖例例3.13.1 走迷宮是人們熟悉的一種游戲, 如圖31就是一個迷宮。如果我們把該迷宮的每一個格子以及入口和出口都作為節點, 把通道作為邊, 則該迷宮可以由一個有向圖表示(如圖3-2所示)。 那么, 走迷宮其實就是從該有向圖的初始節點(入口

2、)出發, 尋找目標節點(出口)的問題, 或者是尋找通向目標節點(出口)的路徑的問題。 第 3 章 圖搜索與問題求解 圖 3-1 迷宮圖 第 3 章 圖搜索與問題求解 圖 3-2 迷宮的有向圖表示 第 3 章 圖搜索與問題求解 例例 3.23.2 在一個33的方格棋盤上放置著1, 2, 3, 4, 5, 6, 7, 8八個數碼, 每個數碼占一格, 且有一個空格。 這些數碼可在棋盤上移動, 其移動規則是：與空格相鄰的數碼方可移入空格。現在的問題是：對于指定的初始棋局和目標棋局(如圖3-3所示), 給出數碼的移動序列。該問題稱為八數碼難題或重排九宮問題。 可以看出,圖中的一條邊(即相鄰兩個節點的連線

3、)就對應一次數碼移動,反之, 一次數碼移動也就對應著圖中的一條邊。而數碼移動是按數碼的移動規則進行的。所以, 圖中的一條邊也就代表一個移動規則或者移動規則的一次執行。于是,這個八數碼問題也就是要在該有向圖中尋找目標節點, 或找一條從初始節點到目標節點的路徑問題。 第 3 章 圖搜索與問題求解 圖 3-3 八數碼問題示例 第 3 章 圖搜索與問題求解 3.1.2 3.1.2 狀態圖搜索狀態圖搜索1. 1. 搜索方式搜索方式用計算機來實現狀態圖的搜索, 有兩種最基本的方式： 樹式搜索和線式搜索。 所謂樹式搜索, 形象地講就是以“畫樹”的方式進行搜索。 即從樹根(初始節點)出發, 一筆一筆地描出一棵

4、樹來。準確地講, 樹式搜索就是在搜索過程中記錄所經過的所有節點和邊。 所以, 樹式搜索所記錄的軌跡始終是一棵“樹”, 這棵樹也就是搜索過程中所產生的搜索樹。 第 3 章 圖搜索與問題求解 所謂線式搜索, 形象地講就是以“畫線”的方式進行搜索。 準確地講, 線式搜索在搜索過程中只記錄那些當前認為是處在所找路徑上的節點和邊。所以,線式搜索所記錄的軌跡始終是一條“線”(折線)。 第 3 章 圖搜索與問題求解 線式搜索的基本方式又可分為不回溯的和可回溯的兩種。 不回溯的線式搜索就是每到一個“叉路口”僅沿一條路繼續前進, 即對每一個節點始終都僅生成一個子節點(如果有子節點的話)。 生成一個節點的子節點也

5、稱對該節點進行擴展。這樣,如果擴展到某一個節點, 該節點恰好就是目標節點,則搜索成功；如果直到不能再擴展時, 還未找到目標節點,則搜索失敗。可回溯的線式搜索也是對每一個節點都僅擴展一條邊,但當不能再擴展時, 則退回一個節點, 然后再擴展另一條邊(如果有的話)。 這樣, 要么最終找到了目標節點, 搜索成功；要么一直回溯到初始節點也未找到目標節點, 則搜索失敗。 第 3 章 圖搜索與問題求解 由上所述可以看出, 樹式搜索成功后, 還需再從搜索樹中找出所求路徑, 而線式搜索只要搜索成功, 則“搜索線”就是所找的路徑, 即問題的解。 那么, 又怎樣從搜索樹中找出所求路徑呢？ 這只需在擴展節點時記住節點

6、間的父子關系即可。 這樣, 當搜索成功時, 從目標節點反向沿搜索樹按所作標記追溯回去一直到初始節點, 便得到一條從初始節點到目標節點的路徑, 即問題的一個解。 第 3 章 圖搜索與問題求解 2. 2. 搜索策略搜索策略由于搜索具有探索性, 所以要提高搜索效率(盡快地找到目標節點), 或要找最佳路徑(最佳解)就必須注意搜索策略。 對于狀態圖搜索, 已經提出了許多策略, 它們大體可分為盲目搜索和啟發式(heuristic)搜索兩大類。 通俗地講, 盲目搜索就是無“向導”的搜索, 啟發式搜索就是有“向導”的搜索。那么, 樹式盲目搜索就是窮舉式搜索, 即從初始節點出發, 沿連接邊逐一考察各個節點(看是

7、否為目標節點), 或者反向進行；而線式盲目搜索, 對于不回溯的就是隨機碰撞式搜索, 對于回溯的則也是窮舉式的搜索。 第 3 章 圖搜索與問題求解 啟發式搜索則是利用“啟發性信息”引導的搜索。 所謂“啟發性信息”就是與問題有關的有利于盡快找到問題解的信息或知識。例如：“欲速則不達”、“知已知彼, 百戰不殆”、 “學如逆水行舟不進則退”等格言, 就是指導人們行為的啟發性信息。常識告訴我們,如果有向導引路, 則就會少走彎路而事半功倍。 所以, 啟發式搜索往往會提高搜索效率, 而且可能找到問題的最優解。根據啟發性信息的內容和使用方式的不同, 啟發式搜索又可分為許多不同的策略, 如全局擇優、局部擇優、

8、最佳圖搜索等等。 按搜索范圍的擴展順序的不同, 搜索又可分為廣度優先和深度優先兩種類型。對于樹式搜索, 既可深度優先進行, 也可廣度優先進行。對于線式搜索則總是深度優先進行。 第 3 章 圖搜索與問題求解 3. 3. 搜索算法搜索算法由于搜索的目的是為了尋找初始節點到目標節點的路徑, 所以在搜索過程中就得隨時記錄搜索軌跡。為此, 我們用一個稱為CLOSED表的動態數據結構來專門記錄考查過的節點。顯然, 對于樹式搜索來說, CLOSED表中存儲的正是一棵不斷成長的搜索樹； 而對于線式搜索來說, CLOSED表中存儲的是一條不斷伸長的折線, 它可能本身就是所求的路徑(如果能找到目標節點的話)。 另

9、一方面, 對于樹式搜索來說, 還得不斷地把待考查的節點組織在一起, 并做某種排列, 以便控制搜索的方向和順序。 為此, 我們采用一個稱為OPEN表的動態數據結構,來專門登記當前待考查的節點。 第 3 章 圖搜索與問題求解 圖 3-4 OPEN表與CLOSED表示例 第 3 章 圖搜索與問題求解 樹式搜索算法：樹式搜索算法： 步1 把初始節點So放入OPEN表中。步2 若OPEN表為空, 則搜索失敗, 退出。 步3 移出OPEN表中第一個節點N放入CLOSED表中, 并冠以順序編號n。步4 若目標節點Sg=N, 則搜索成功, 結束。 步5 若N不可擴展, 則轉步2。 第 3 章 圖搜索與問題求解

10、 步6擴展N, 生成一組子節點, 對這組子節點做如下處理： (1) 刪除N的先輩節點(如果有的話)。 (2)對已存在于OPEN表的節點(如果有的話)也刪除之；但刪除之前要比較其返回初始節點的新路徑與原路徑,如果新路徑“短”, 則修改這些節點在OPEN表中的原返回指針,使其沿新路返回(如圖3-5所示 )。 (3)對已存在于CLOSED表的節點(如果有的話), 做與(2)同樣的處理, 并且再將其移出CLOSED表, 放入OPEN表重新擴展(為了重新計算代價)。 (4)對其余子節點配上指向N的返回指針后放入OPEN表中某處, 或對OPEN表進行重新排序, 轉步2。 第 3 章 圖搜索與問題求解 圖

11、3-5 修改返回指針示例 第 3 章 圖搜索與問題求解 說明： (1) 這里的返回指針也就是父節點在CLOSED表中的編號。 (2) 步6中修改返回指針的原因是, 因為這些節點又被第二次生成, 所以它們返回初始節點的路徑已有兩條, 但這兩條路徑的“長度”可能不同。 那么, 當新路短時自然要走新路。(3) 這里對路徑的長短是按路徑上的節點數來衡量的, 后面我們將會看到路徑的長短也可以其“代價”(如距離、 費用、 時間等)衡量。若按其代價衡量, 則在需修改返回指針的同時還要修改相應的代價值, 或者不修改返回指針也要修改代價值(為了實現代價小者優先擴展)。 第 3 章 圖搜索與問題求解 線式搜索算法

12、： 不回溯的線式搜索不回溯的線式搜索 步1 把初始節點So放入CLOSED表中。步2 令NSo。步3 若N是目標節點,則搜索成功,結束。 步4 若N不可擴展,則搜索失敗,退出。 步5 擴展N,選取其一個未在CLOSED表中出現過的子節點N1放入CLOSED表中, 令NN1, 轉步3。 第 3 章 圖搜索與問題求解 可回溯的線式搜索步1 把初始節點So放入CLOSED表中。步2令NSo。步3若N是目標節點, 則搜索成功, 結束。 步4 若N不可擴展, 則移出CLOSED表的末端節點Ne,若NeSo,則搜索失敗, 退出。否則, 以CLOSED表新的末端節點Ne作為N,即令NNe, 轉步4。步5擴展

13、N, 選取其一個未在CLOSED表用出現過的子節點N1放入CLOSED表中, 令NN1,轉步3。 第 3 章 圖搜索與問題求解 需說明的是,上述算法僅是搜索目標節點的算法, 當搜索成功后, 如果需要路徑, 則還須由CLOSED表再找出路徑。找路徑的方法是： 對于樹式搜索, 從CLOSED表中序號最大的節點起,根據返回指針追溯至初始節點So,所得的節點序列或邊序列即為所找路徑；對于線式搜索, CLOSED表即是所找路徑。第 3 章 圖搜索與問題求解 3.1.3 3.1.3 窮舉式搜索窮舉式搜索1. 1. 廣度優先搜索廣度優先搜索廣度優先搜索就是始終先在同一級節點中考查, 只有當同一級節點考查完之

14、后, 才考查下一級節點。或者說,是以初始節點為根節點, 向下逐級擴展搜索樹。所以,廣度優先策略的搜索樹是自頂向下一層一層逐漸生成的。 第 3 章 圖搜索與問題求解 例例 3.3 用廣度優先搜索策略解八數碼難題。 由于把一個與空格相鄰的數碼移入空格, 等價于把空格向數碼方向移動一位。所以,該題中給出的數碼走步規則也可以簡化為： 對空格可施行左移、移、上移和下移等四種操作。 設初始節點So和目標節點Sg分別如圖3-3的初始棋局和目標棋局所示, 我們用廣度優先搜索策略, 則可得到如圖3-6所示的搜索樹。 第 3 章 圖搜索與問題求解 圖 3-6 八數碼問題的廣度優先搜索第 3 章 圖搜索與問題求解

15、廣度優先搜索算法：步1 把初始節點So放入OPEN表中。步2 若OPEN表為空, 則搜索失敗,退出。 步3 取OPEN表中前面第一個節點N放在CLOSED表中, 并冠以順序編號n。步4 若目標節點Sg=N,則搜索成功, 結束。 步5 若N不可擴展, 則轉步2。步6 擴展N, 將其所有子節點配上指向N的指針依次放入OPEN表尾部, 轉步2。 第 3 章 圖搜索與問題求解 其中OPEN表是一個隊列,CLOSED表是一個順序表,表中各節點按順序編號, 正被考察的節點在表中編號最大。如果問題有解, OPEN表中必出現目標節點Sg,那么,當搜索到目標節點Sg時,算法結束,然后根據返回指針在CLOSED表

16、中往回追溯,直至初始節點,所得的路徑即為問題的解。 廣度優先搜索亦稱為寬度優先或橫向搜索。這種策略是完備的,即如果問題的解存在, 用它則一定能找到解,且找到的解還是最優解(即最短的路徑)。這是廣度優先搜索的優點。但它的缺點是搜索效率低。 第 3 章 圖搜索與問題求解 2. 2. 深度優先搜索深度優先搜索深度優先搜索就是在搜索樹的每一層始終先只擴展一個子節點,不斷地向縱深前進, 直到不能再前進(到達葉子節點或受到深度限制)時, 才從當前節點返回到上一級節點, 沿另一方向又繼續前進。這種方法的搜索樹是從樹根開始一枝一枝逐漸形成的。 第 3 章 圖搜索與問題求解 深度優先搜索算法：步1 把初始節點S

17、o放入OPEN表中。步2 若OPEN表為空, 則搜索失敗, 退出。 步3 取OPEN表中前面第一個節點N放入CLOSED表中,并冠以順序編號n。步4 若目標節點Sg=N, 則搜索成功,結束。 步5 若N不可擴展, 則轉步2。步6擴展N, 將其所有子節點配上指向N的返回指針依次放入OPEN表的首部, 轉步2。 第 3 章 圖搜索與問題求解 圖 3-7 八數碼問題的深度優先搜索 例例3.43.4對于八數碼問題, 應用深度優先搜索策略, 可得如圖3-7所示的搜索樹。 第 3 章 圖搜索與問題求解 深度優先搜索亦稱為縱向搜索。由于一個有解的問題樹可能含有無窮分枝, 深度優先搜索如果誤入無窮分枝(即深度

18、無限), 則不可能找到目標節點。所以, 深度優先搜索策略是不完備的。另外, 應用此策略得到的解不一定是最佳解(最短路徑)。 第 3 章 圖搜索與問題求解 3. 有界深度優先搜索有界深度優先搜索廣度優先和深度優先是兩種最基本的窮舉搜索方法, 在此基礎上, 根據需要再加上一定的限制條件, 便可派生出許多特殊的搜索方法。例如有界深度優先搜索。 有界深度優先搜索就是給出了搜索樹深度限制, 當從初始節點出發沿某一分枝擴展到一限定深度時, 就不能再繼續向下擴展, 而只能改變方向繼續搜索。節點x的深度(即其位于搜索樹的層數)通常用d(x)表示, 則有界深度優先搜索算法如下： 第 3 章 圖搜索與問題求解 步

19、1 把So放入OPEN表中,置So的深度d(So)=0。步2 若OPEN表為空, 則失敗, 退出。 步3 取OPEN表中前面第一個節點N,放入CLOSED表中, 并冠以順序編號n。步4 若目標節點Sg=N, 則成功, 結束。 步5 若N的深度d(N)=dm(深度限制值), 或者若N無子節點, 則轉步2。步6 擴展N, 將其所有子節點Ni配上指向N的返回指針后依次放入OPEN表中前部, 置d(Ni)=d(N)+1,轉步2。 第 3 章 圖搜索與問題求解 3.1.4 3.1.4 啟發式搜索啟發式搜索1. 1. 問題的提出問題的提出從理論上講, 似乎可以解決任何狀態空間的搜索問題,但實踐表明,窮舉搜

20、索只能解決一些狀態空間很小的簡單問題, 而對于那些大狀態空間問題, 窮舉搜索就不能勝任了。因為大空間問題往往會導致“組合爆炸”。 例如梵塔問題, 當階數較小(如小于6)時, 在計算機上求解并不難, 但當階數再增加時, 其時空要求將會急劇地增加。第 3 章 圖搜索與問題求解 例如當取64時, 則其狀態空間中就有364=0.94*10個節點,最短的路徑長度(節點數)=264-121019,這是現有的任何計算機都存放不下,也計算不了的。又如博弈問題, 計算機為了取勝, 它可以將所有算法都試一下,然后選擇最佳走步。找到這樣算法并不難, 但計算時的時空消耗卻大得驚人。例如：就可能有的棋局數講,一字棋是9

21、!3.6105, 西洋棋是1078,國際象棋是10120,圍棋是10761。假設每步可以選擇一種棋局,用極限并行速度(10-104秒/步)計算, 國際象棋的算法也得1016年,即1億億年才可以算完。 第 3 章 圖搜索與問題求解 2. 2. 啟發性信息啟發性信息啟發式搜索就是利用啟發性信息進行制導的搜索。啟發性信息就是有利于盡快找到問題之解的信息。按其用途劃分, 啟發性信息一般可分為以下三類： (1) 用于擴展節點的選擇, 即用于決定應先擴展哪一個節點, 以免盲目擴展。 (2) 用于生成節點的選擇,即用于決定應生成哪些后續節點,以免盲目地生成過多無用節點。 (3) 用于刪除節點的選擇,即用于決

22、定應刪除哪些無用節點, 以免造成進一步的時空浪費。 第 3 章 圖搜索與問題求解 例如, 由八數碼問題的部分狀態圖可以看出, 從初始節點開始, 在通向目標節點的路徑上, 各節點的數碼格局同目標節點相比較, 其數碼不同的位置個數在逐漸減少, 最后為零。 所以, 這個數碼不同的位置個數便是標志一個節點到目標節點距離遠近的一個啟發性信息, 利用這個信息就可以指導搜索。 可以看出, 這種啟發性信息屬于上面的第一種類型。 需指出的是,不存在能適合所有問題的萬能啟發性信息, 或者說, 不同的問題有不同的啟發性信息。 第 3 章 圖搜索與問題求解 3. 啟發函數啟發函數在啟發式搜索中,通常用所謂啟發函數來表

23、示啟發性信息。 啟發函數是用來估計搜索樹上節點x與目標節點Sg接近程度的一種函數, 通常記為h(x)。 如何定義一個啟發函數呢？啟發函數并無固定的模式, 需要具體問題具體分析。通常可以參考的思路有：一個節點到目標節點的某種距離或差異的度量；一個節點處在最佳路徑上的概率；或者根據經驗的主觀打分，等等。例如,對于八數碼難題,用h(x)就可表示節點x的數碼格局同目標節點相比數碼不同的位置個數。 第 3 章 圖搜索與問題求解 4. 啟發式搜索算法啟發式搜索算法1) 全局擇優搜索全局擇優搜索就是利用啟發函數制導的一種啟發式搜索方法。該方法亦稱為最好優先搜索法, 它的基本思想是：在OPEN表中保留所有已生

24、成而未考察的節點, 并用啟發函數h(x)對它們全部進行估價,從中選出最優節點進行擴展,而不管這個節點出現在搜索樹的什么地方。 第 3 章 圖搜索與問題求解 全局擇優搜索算法如下： 步1 把初始節點So放入OPEN表中,計算h(So)。步2 若OPEN表為空,則搜索失敗, 退出。 步3 移出OPEN表中第一個節點N放入CLOSED表中, 并冠以序號n。步4 若目標節點Sg=N, 則搜索成功, 結束。 步5 若N不可擴展, 則轉步2。步6 擴展N, 計算每個子節點x的函數值h(x), 并將所有子節點配以指向N的返回指針后放入OPEN表中, 再對OPEN表中的所有子節點按其函數值大小以升序排序,轉步

25、2。 第 3 章 圖搜索與問題求解 圖 3-8 八數碼問題的全局擇優搜索 第 3 章 圖搜索與問題求解 例例 3.5 用全局擇優搜索法解八數碼難題。 初始棋局和目標棋局同例3。 解解設啟發函數h(x)為節點x的格局與目標格局相比數碼不同的位置個數。以這個函數制導的搜索樹如圖3-8所示。圖中節點旁的數字就是該節點的估價值。由圖可見此八數問題的解為： So, S1, S2, S3, Sg。 第 3 章 圖搜索與問題求解 2) 局部擇優搜索局部擇優搜索與全局擇優搜索的區別是, 擴展節點N后僅對N的子節點按啟發函數值大小以升序排序, 再將它們依次放入OPEN表的首部。 故算法從略。 第 3 章 圖搜索

26、與問題求解 3.1.5 加權狀態圖搜索加權狀態圖搜索1. 加權狀態圖與代價樹加權狀態圖與代價樹例例 3.6 圖3-9(a)是一個交通圖,設A城是出發地,E城是目的地, 邊上的數字代表兩城之間的交通費。試求從A到E最小費用的旅行路線。 第 3 章 圖搜索與問題求解 圖 3-9 交通圖及其代價樹 第 3 章 圖搜索與問題求解 可以看出, 這個圖與前面的狀態圖不同的地方是邊上附有數值。它表示邊的一種度量(此例中是交通費, 當然也可以是距離)。一般地, 稱這種數值為權值, 而把邊上附有數值的狀態圖稱之為加權狀態圖圖或賦權狀態圖賦權狀態圖。 顯然,加權狀態圖的搜索與權值有關, 并且要用權值來導航。 具體

27、來講,加權狀態圖的搜索算法, 要在一般狀態圖搜索算法基礎上再增加權值的計算與傳播過程, 并且要由權值來確定節點的擴展順序。 第 3 章 圖搜索與問題求解 同樣, 為簡單起見,我們先考慮樹型的加權狀態圖代價樹的搜索。所謂代價,可以是兩點之間的距離、交通費用或所需時間等等。通常用g(x)表示從初始節點So到節點x的代價, 用c(xi,xj)表示父節點xi到子節點xj的代價,即邊(xi,xj)的代價。從而有 g(xj)g(xi)c(xi, xj) 而 g(So)0 第 3 章 圖搜索與問題求解 2. 分支界限法分支界限法(最小代價優先法最小代價優先法) 其基本思想是：每次從OPEN表中選出g(x)值

28、最小的節點進行考察, 而不管這個節點在搜索樹的什么位置上。 可以看出,這種搜索法與前面的最好優先法(即全局擇優法)的區別僅是選取擴展節點的標準不同,一個是代價值g(x)(最小),一個是啟發函數值h(x)(最小)。這就是說, 把最好優先法算法中的h(x)換成g(x)即得分支界限法的算法。所以,從算法角度考慮, 這兩種搜索法實際是一樣的。但二者在計算節點的代價值與啟發函數值的方法是有差別的。 第 3 章 圖搜索與問題求解 事實上, 一個節點x的代價值g(x)是從初始節點So方向計算而來的, 其計算方法為 g(So)0g(xj)g(xi)c(xi, xj) (xj是xi的子節點) 而啟發函數值h(x

29、)則是朝目標節點方向計算的；g(x)與x的父節點代價有關,與子節點代價無關, 而h(x)與x的父、子節點的啟發值均無關。 第 3 章 圖搜索與問題求解 3. 最近擇優法最近擇優法(瞎子爬山法瞎子爬山法) 同上面的情形一樣,這種方法實際同局部擇優法類似, 區別也僅是選取擴展節點的標準不同,一個是代價值g(x)(最小), 一個是啟發函數值h(x)(最小)。這就是說,把局部擇優法算法中的h(x)換成g(x)就可得最近擇優法的算法。 現在我們用代價樹搜索求解例3.6中給出的問題。 我們用分支界限法得到的路徑為ACDE這是一條最小費用路徑(費用為8)。 第 3 章 圖搜索與問題求解 3.1.6 A算法和

30、算法和A*算法算法1. 估價函數估價函數利用啟發函數h(x)制導的啟發式搜索, 實際是一種深度優先的搜索策略。雖然它是很高效的, 但也可能誤入歧途。所以, 為了更穩妥一些,人們把啟發函數擴充為估價函數。估價函數的一般形式為 f(x)g(x)h(x) 其中g(x)為從初始節點So到節點x已經付出的代價, h(x)是啟發函數。即估價函數f(x)是從初始節點So到達節點x處已付出的代價與節點x到達目標節點Sg的接近程度估計值之總和。 第 3 章 圖搜索與問題求解 有時估價函數還可以表示為 f(x)d(x)h(x) 其中d(x)表示節點x的深度。 可以看出,(x)中的g(x)或d(x)有利于搜索的橫向

31、發展(因為g(x)或d(x)越小,則說明節點x越靠近初始節點So), 因而可提高搜索的完備性, 但影響搜索效率；h(x)則有利于搜索的縱向發展(因為h(x)越小,則說明節點x越接近目標節點Sg),因而可提高搜索的效率, 但影響完備性。所以,f(x)恰好是二者的一個折中。但在確定f(x)時,要權衡利弊, 使g(x)(或d(x)與h(x)的比重適當。 這樣,才能取得理想的效果。例如,我們只關心到達目標節點的路徑, 并希望有較高的搜索效率,則g(x)可以忽略。當然, 這樣會影響搜索的完備性。 第 3 章 圖搜索與問題求解 2.2.A A算法算法 A算法是基于估價函數f(x)的一種加權狀態圖啟發式搜索

32、算法。其具體步驟如下： 步1 把附有f(So)的初始節點So放入OPEN表。步2 若OPEN表為空, 則搜索失敗, 退出。 步3 移出OPEN表中第一個節點N放入CLOSED表中, 并冠以順序編號n。步4 若目標節點Sg=N, 則搜索成功, 結束。 步5 若N不可擴展, 則轉步2。 第 3 章 圖搜索與問題求解 步6 擴展N,生成一組附有f(x)的子節點,對這組子節點做如下處理： (1)考察是否有已在OPEN表或CLOSED表中存在的節點；若有則再考察其中有無N的先輩節點,若有則刪除之；對于其余節點, 也刪除之,但由于它們又被第二次生成, 因而需考慮是否修改已經存在于OPEN表或CLOSED表

33、中的這些節點及其后裔的返回指針和f(x)值, 修改原則是“抄f(x)值小的路走”。 (2)對其余子節點配上指向N的返回指針后放入OPEN表中, 并對OPEN表按f(x)值以升序排序, 轉步2。 第 3 章 圖搜索與問題求解 算法中節點x的估價函數f(x)的計算方法是 f(xj)g(xj)h(xj) g(xi)c(xi, xj)h(xj) (xj是xi的子節點) 至于h(x)的計算公式則需由具體問題而定。 可以看出,A算法其實就是對于本節開始給出的圖搜索一般算法中的樹式搜索算法, 再增加了估價函數f(x)的一種啟發式搜索算法。 第 3 章 圖搜索與問題求解 3.3.A A* *算法算法 如果對上

34、述A算法再限制其估價函數中的啟發函數h(x)滿足： 對所有的節點x均有 h(x)h*(x) 其中h*(x)是從節點x到目標節點的最小代價, 即最佳路徑上的實際代價(若有多個目標節點則為其中最小的一個),則它就稱為A*算法。 第 3 章 圖搜索與問題求解 A*算法中,限制h(x)h*(x)的原因是為了保證取得最優解。 理論分析證明,如果問題存在最優解, 則這樣的限制就可保證能找到最優解。雖然,這個限制可能產生無用搜索。 實際上, 不難想像,當某一節點x的h(x)h*(x),則該節點就可能失去優先擴展的機會, 因而導致得不到最優解。 A*算法也稱為最佳圖搜索算法。它是著名的人工智能學者Nilsso

35、n提出的。 第 3 章 圖搜索與問題求解 3.1.7 狀態圖搜索策略小結狀態圖搜索策略小結 第 3 章 圖搜索與問題求解 3.2 狀態圖搜索問題求解狀態圖搜索問題求解 3.2.1 3.2.1 問題的狀態圖表示問題的狀態圖表示1. 1. 狀態狀態狀態就是問題在任一確定時刻的狀況,它表征了問題特征和結構等。狀態在狀態圖中表示為節點。狀態一般用一組數據表示。在程序中用字符、數字、記錄、數組、結構、對象等表示。 第 3 章 圖搜索與問題求解 2. 2. 狀態轉換規則狀態轉換規則狀態轉換規則就是能使問題狀態改變的某種操作、規則、 行為、變換、關系、函數、算子、過程等等。狀態轉換規則也稱為操作,問題的狀態

36、也只能經定義在其上的這種操作而改變。狀態轉換規則在狀態圖中表示為邊。在程序中狀態轉換規則可用數據對、條件語句、規則、函數、過程等表示。 第 3 章 圖搜索與問題求解 3. 3. 狀態圖表示狀態圖表示一個問題的狀態圖是一個三元組 (S, F, G) 其中S是問題的初始狀態集合, F是問題的狀態轉換規則集合, G是問題的目標狀態集合。 一個問題的全體狀態及其關系就構成一個空間, 稱為狀態空間。所以,狀態圖也稱為狀態空間圖。 第 3 章 圖搜索與問題求解 例例 3.73.7 迷宮問題的狀態圖表示。 我們仍以例3.1中的迷宮為例。我們以每個格子作為一個狀態,并用其標識符作為其表示。那么,兩個標識符組成

37、的序對就是一個狀態轉換規則。于是, 該迷宮的狀態圖表示為 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), (S9, S8), (S9, Sg)G：Sg 第 3 章 圖搜索與問題求解 X1X2X3XX0X4X7X6X5例例 3.83.8八數碼難題的狀態圖表示。 我們將棋局 用向量 A(X0, X1,

38、 X2, X3, X4, X5, X6, X7, X8)表示,Xi為變量,Xi的值就是方格Xi內的數字。于是,向量A就是該問題的狀態表達式。 第 3 章 圖搜索與問題求解 設初始狀態和目標狀態分別為 So(0, 2, 8, 3, 4, 5, 6, 7, 1) Sg(0, 1, 2, 3, 4, 5, 6, 7, 8) 易見,數碼的移動規則就是該問題的狀態變換規則,即操作。經分析, 該問題共有24條移碼規則, 可分為9組。 第 3 章 圖搜索與問題求解 0組規則: ; 0)()0(; 0)()0(; 0)()0(; 0)()0(80804606034040220201XnXnXXrXnXnXXr

39、XnXnXXrXnXnXXr 1組規則: ; 0)()0(; 0)()0(8181621215XnXnXXrXnXnXXr第 3 章 圖搜索與問題求解 2組規則組規則: ; 0)()0(; 0)()0(; 0)()0(020293232812127XnXnXXrXnXnXXrXnXnXXr8組規則: ; 0)()0(; 0)()0(; 0)()0(787824080823181822XnXnXXrXnXnXXrXnXnXXr 于是, 八數碼問題的狀態圖可表示為 (So, r1, r2, , r24, Sg) 第 3 章 圖搜索與問題求解 當然,上述24條規則也可以簡化為4條: 即空格上移、 下

40、移、左移、右移。不過,這時狀態(即棋局)就需要用矩陣來表示。 可以看出,這個狀態圖中僅給出了初始節點和目標節點, 并未給出其余節點。而其余節點需用狀態轉換規則來產生。 類似于這樣表示的狀態圖稱為隱式狀態圖, 或者說狀態圖的隱式表示。 第 3 章 圖搜索與問題求解 例例 3.93.9 梵塔問題。傳說在印度的貝那勒斯的圣廟中,主神梵天做了一個由64個大小不同的金盤組成的“梵塔”, 并把它穿在一個寶石桿上。另外, 旁邊再插上兩個寶石桿。 然后, 他要求僧侶們把穿在第一個寶石桿上的64個金盤全部搬到第三個寶石桿上。 搬動金盤的規則是：一次只能搬一個；不允許將較大的盤子放在較小的盤子上。于是,梵天預言：

41、一旦64個盤子都搬到了3號桿上, 世界將在一聲霹靂中毀滅。這就是梵塔問題。 經計算, 把64個盤子全部搬到3號桿上, 需要穿插搬動盤子 264-118 446 744 073 709 511 615 次。所以直接考慮原問題, 將過于復雜。 第 3 章 圖搜索與問題求解 設有三根寶石桿,在1號桿上穿有A、B兩個金盤, A小于B, A位于B的上面。要求把這兩個金盤全部移到另一根桿上,而且規定每次只能移動一個盤子,任何時刻都不能使B位于A的上面。 設用二元組(SA,SB)表示問題的狀態, SA表示金盤A所在的桿號, SB表示金盤B所在的桿號, 這樣, 全部可能的狀態有9種, 可表示如下： (1, 1

42、), (1, 2), (1, 3)(2, 1), (2, 2), (2, 3) (3, 1), (3, 2), (3, 3) 如圖3-10所示。 第 3 章 圖搜索與問題求解 圖 3-10 二階梵塔的全部狀態 第 3 章 圖搜索與問題求解 這里的狀態轉換規則就是金盤的搬動規則，分別用A(i,j)及B(i,j)表示：A(i,j)表示把A盤從第i號桿移到第j號桿上;B(i,j)表示把B盤從第i號桿移到第j號桿上。經分析，共有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),

43、B(3,2)當然,規則的具體形式應是： IF條件THENA(i,j) IF條件THEN B(i, j) 第 3 章 圖搜索與問題求解 這樣由題意,問題的初始狀態為(1, 1),目標狀態為(3, 3), 則二階梵塔問題可用狀態圖表示為 (1, 1), A(1, 2), , B(3, 2), (3, 3) 由這9種可能的狀態和12種操作, 二階梵塔問題的狀態空間圖如圖3-11所示。 第 3 章 圖搜索與問題求解 圖 3-11 二階梵塔狀態空間圖 第 3 章 圖搜索與問題求解 例例3.10 3.10 旅行商問題(Traveling-Salesman Problem,TSP)。 設有n個互相可直達的城

44、市, 某推銷商準備從其中的A城出發,周游各城市一遍, 最后又回到A城。 要求為該推銷商規劃一條最短的旅行路線。 該問題的狀態為以A打頭的已訪問過的城市序列: A So:A。 Sg: A, , A。其中“”為其余n-1個城市的一個序列。 第 3 章 圖搜索與問題求解 狀態轉換規則： 規則規則1 1 如果當前城市的下一個城市還未去過, 則去該城市,并把該城市名排在已去過的城市名序列后端。 規則規則2 2 如果所有城市都去過一次, 則從當前城市返回A城, 把A也添在去過的城市名序列后端。 第 3 章 圖搜索與問題求解 3.2.2 狀態圖問題求解程序舉例狀態圖問題求解程序舉例 例3.11 下面是一個通

45、用的狀態圖搜索程序。對于求解的具體問題，只需將其狀態圖的程序表示并入該程序即可。 /*狀態圖搜索通用程序*/ DOMAINS state= %例如:state=symbol DATABASE-mydatabase open(state,integer) %用動態數據庫實現OPEN表 closed(integer,state,integer) %和CLOSED表 res(state) open1(state,integer) min(state,integer) mark(state) fail第 3 章 圖搜索與問題求解 PREDICATES solve search(state,state)

46、 result searching step4(integer,state) step56(integer,state) equal(state,state) repeat resulting(integer) rule(state,state) 第 3 章 圖搜索與問題求解 GOAL solve.CLAUSES solve: -search(,),result. /* 例如 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(_,myd

47、atabase), assert(closed(0,Begin,0), assert(open(Begin,0),%步1 將初始節點放入OPEN表 assert(mark(End), repeat, searching,!. 第 3 章 圖搜索與問題求解 result: -% 輸出解 not(fail_), retract(closed(0,_,0), closed(M,_,_), resulting(M),!.result: - beep,write(sorry dont find a road!).searching: - open(State,Pointer), %步2 若OPEN表空,

48、 則失敗,退出 retract(open(State,Pointer), %步3 取出OPEN表中第一個節點,給其 closed(No, _, _),No2=No+1, % 編號 asserta(closed(No2,State,Pointer), %放入CLOSED表 !,step4(No2,State). searching: -assert(fail_). %步4 若當前節點為目標節點, 則成功 第 3 章 圖搜索與問題求解 step4(_,State): -mark(End),equal(State,End). %轉步2step4(No,State): -step56(No,State

49、),!,fail. step56(No,StateX): -%步5 若當前節點不可擴展, 轉步2 rule(StateX,StateY), %步6 擴展當前節點X得Y not(open(StateY,_), %考察Y是否已在OPEN表中 not(closed(_,StateY,_),%考察Y是否已在CLOSED表中 assertz(open(StateY,No), %可改變搜索策略 fail.step56(_,_): -!. equal(X,X).repeat.repeat: -repeat. resulting(N): -closed(N,X,M),asserta(res(X),result

50、ing(M).resulting(_): -res(X),write(X),nl,fail.resulting(_): -!.rule(X,Y): -. % 例如: rule(X,Y): -road(X,Y). 第 3 章 圖搜索與問題求解 例例 3.123.12迷宮問題程序。下面僅給出初始狀態、目標狀態和狀態轉換規則集, 程序用例3.11的通用程序。 DOMAINS State=symbol CLAUSESsolve: - search(a,e), result./*把該問題的狀態轉換規則掛接在通用程序的規則上*/ rule(X,Y): -road(X,Y). /* 下面是該問題的狀態轉換規

51、則(其實也就是迷宮圖)集, 需并入通用程序后 */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 章 圖搜索與問題求解 例例 3.133.13 八數碼問題程序。我們把前面給出的該問題的狀態圖表示, 用PROLOG語言翻譯如下,搜索程序用例3.11的通用程序。 DOMAINS state=st(integer,integer,integer,integer,integer,integer,intege

52、r,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). /*把該問題的狀態轉換規則掛接在通用程序的規則上*/ /* 下面是該問題的狀態轉換規則(即走步規則)集,需并入通用程序后 */rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X2,X1,X0,X3,X4,X5,X6,X7,X8): -X0=0.第 3 章 圖搜索與問題求解 rule1(st(X0,X1,X2,X3,X4,X5,X6,X7

53、,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,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,X

54、7,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 章 圖搜索與問題求解 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

55、,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=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

56、,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 章 圖搜索與問題求解 rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(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=

57、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,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

58、=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,X5,X6,X8,X7): -X8=0. 第 3 章 圖搜索與問題求解 例例 3.143.14 旅行商問題程序。 /* 旅行商問題 */ DOMAINS State=st(lists,

59、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 章 圖搜索與問題求解 open1(State,integer,integer,integer) min(State,integer,integer,integer) mark(string,integer

60、) 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 sort p1 第 3 章 圖搜索與問題求解 p12(State,integer,integer,integer) p2 rule(State,State,Grule) member(s