1、延邊大學工學院計算機科學與技術系第第5 5章章 搜索求解策略搜索求解策略延邊大學工學院計算機科學與技術學科延邊大學工學院計算機科學與技術學科李永珍李永珍E_mail:E_mail:人工智能基礎人工智能基礎延邊大學工學院計算機科學與技術系第5章 搜索求解策略5.1 5.1 搜索的概念搜索的概念5.2 5.2 狀態空間的搜索策略狀態空間的搜索策略5.3 5.3 盲目的圖搜索策略盲目的圖搜索策略5.4 5.4 啟發式圖搜索策略啟發式圖搜索策略5.5 5.5 與與/ /或圖搜索策略或圖搜索策略延邊大學工學院計算機科學與技術系第第5 5章章 搜索求解策略搜索求解策略5.1 5.1 搜索的概念搜索的概念5

2、.2 5.2 狀態空間知識表示方法狀態空間知識表示方法5.3 5.3 盲目的圖搜索策略盲目的圖搜索策略5.4 5.4 啟發式圖搜索策略啟發式圖搜索策略5.5 5.5 與與/ /或圖搜索策略或圖搜索策略延邊大學工學院計算機科學與技術系5.1 5.1 搜索的概念搜索的概念 n問題求解： 問題的表示。 選擇一種相對合適的求解方法。n問題求解的基本方法：搜索法、歸約法、歸結法、推理法及產生式等。延邊大學工學院計算機科學與技術系5.1 5.1 搜索的概念搜索的概念5.1.1 5.1.1 搜索的基本問題與主要過程搜索的基本問題與主要過程5.1.2 5.1.2 搜索策略搜索策略延邊大學工學院計算機科學與技術

3、系5.1.1 5.1.1 搜索的基本問題與主要過程搜索的基本問題與主要過程 n搜索中需要解決的基本問題搜索中需要解決的基本問題：（1）是否一定能找到一個解。（2）是否終止運行或是否會陷入一個死循環。（3）找到的解是否是最佳解。（4）時間與空間復雜性如何。延邊大學工學院計算機科學與技術系5.1.1 5.1.1 搜索的基本問題與主要過程搜索的基本問題與主要過程n搜索的主要過程搜索的主要過程：(1) 從初始或目的狀態出發，并將它作為當前狀態。(2) 掃描操作算子集，將適用當前狀態的一些操作算子作用于當前狀態而得到新的狀態，并建立指向其父結點的指針 。(3) 檢查所生成的新狀態是否滿足結束狀態，如果滿

4、足，則得到問題的一個解，并可沿著有關指針從結束狀態反向到達開始狀態，給出一解答路徑；否則，將新狀態作為當前狀態，返回第(2)步再進行搜索。 延邊大學工學院計算機科學與技術系5.1.2 5.1.2 搜索策略搜索策略1. 搜索方向搜索方向：(1) 數據驅動數據驅動：從初始狀態出發的正向搜索。正向搜索正向搜索從問題給出的條件（一個用于狀態轉換的操作算子集合）出發。 (2) 目的驅動目的驅動：從目的狀態出發的逆向搜索。逆向搜索逆向搜索：先從想達到的目的入手，看哪些操作算子能產生該目的以及應用這些操作算子產生目的時需要哪些條件。(3) 雙向搜索：從開始狀態出發作正向搜索，同時又從目的狀態出發作逆向搜索，

5、直到兩條路徑在中間的某處匯合為止。延邊大學工學院計算機科學與技術系5.1.2 5.1.2 搜索策略搜索策略2. 2. 盲目搜索與啟發式搜索盲目搜索與啟發式搜索: :（1 1）盲目搜索）盲目搜索：在不具有對特定問題的任何有關信息的條件下，按固定的步驟（依次或隨機調用操作算子）進行的搜索。 （2 2）啟發式搜索）啟發式搜索：考慮特定問題領域可應用的知識，動態地確定調用操作算子的步驟，優先選擇較適合的操作算子，盡量減少不必要的搜索，以求盡快地到達結束狀態。延邊大學工學院計算機科學與技術系第第5 5章章 搜索求解策略搜索求解策略5.1 5.1 搜索的概念搜索的概念5.2 5.2 狀態空間知識表示方法狀

6、態空間知識表示方法5.3 5.3 盲目的圖搜索策略盲目的圖搜索策略5.4 5.4 啟發式圖搜索策略啟發式圖搜索策略5.5 5.5 與與/ /或圖搜索策略或圖搜索策略延邊大學工學院計算機科學與技術系5.2 5.2 狀態空間知識表示方法狀態空間知識表示方法5.2.1 5.2.1 狀態空間表示法狀態空間表示法5.2.2 5.2.2 狀態空間的圖描述狀態空間的圖描述延邊大學工學院計算機科學與技術系5.2.1 5.2.1 狀態空間表示法狀態空間表示法n 狀態狀態：表示系統狀態、事實等敘述型知識的一組變量或數組：n 操作操作：表示引起狀態變化的過程型知識的一組關 系或函數：,21nqqqQ,21mfffF

7、T延邊大學工學院計算機科學與技術系5.2.1 5.2.1 狀態空間表示法狀態空間表示法n 狀態空間狀態空間：利用狀態變量和操作符號，表示系統或問題的有關知識的符號體系，狀態空間是一個四元組： ),(0GSOS ：狀態集合。 ：操作算子的集合。 ：包含問題的初始狀態是 的非空子集。 ：若干具體狀態或滿足某些性質的路徑信息描述。O0SGSS延邊大學工學院計算機科學與技術系5.2.1 5.2.1 狀態空間表示法狀態空間表示法n 求解路徑求解路徑：從 結點到 結點的路徑。 n 狀態空間的一個解狀態空間的一個解：一個有限的操作算子序列。 0SGGSSSkOOOO321210kOO,1：狀態空間的一個解。

8、延邊大學工學院計算機科學與技術系n 例例1 八數碼問題的狀態空間八數碼問題的狀態空間。 狀態集 ：所有擺法S操作算子：將空格向上移Up將空格向左移Left將空格向下移Down將空格向右移Right5.2.1 5.2.1 狀態空間表示法狀態空間表示法延邊大學工學院計算機科學與技術系5.2.2 5.2.2 狀態空間的圖描述狀態空間的圖描述（狀態）（操作算子）狀態空間的有向圖描述狀態空間的有向圖描述延邊大學工學院計算機科學與技術系5.2.2 5.2.2 狀態空間的圖描述狀態空間的圖描述八數碼狀態空間圖八數碼狀態空間圖 延邊大學工學院計算機科學與技術系5.2.2 5.2.2 狀態空間的圖描述狀態空間的

9、圖描述 例例2 旅行商問題旅行商問題（traveling salesman problem, TSP）或郵遞員路徑問題。）或郵遞員路徑問題。 （家）（單位：km）可能路徑：費用為375的路徑（A，B，C，D，E，A） 延邊大學工學院計算機科學與技術系5.2.2 5.2.2 狀態空間的圖描述狀態空間的圖描述 旅行推銷員狀態空間圖（部分） ABCDEA 375 A A A A B B C C C C D D D D A E E E E E E E D 路徑: 路徑: 路徑 : 路徑: ABCEDA ABDCE ABDECA 費用 : 費用 : 費用 : 費用: 425 525 475 525 47

10、5 375 325 400 400 300 275 275 250 225 150 100 75 125 175 225 250 100 175 225 425 . . . . . . . 延邊大學工學院計算機科學與技術系第第5 5章章 搜索求解策略搜索求解策略5.1 5.1 搜索的概念搜索的概念5.2 5.2 狀態空間知識表示方法狀態空間知識表示方法5.3 5.3 盲目的圖搜索策略盲目的圖搜索策略5.4 5.4 啟發式圖搜索策略啟發式圖搜索策略5.5 5.5 與與/ /或圖搜索策略或圖搜索策略延邊大學工學院計算機科學與技術系5.3 5.3 盲目的圖搜索策略盲目的圖搜索策略5.3.1 5.3.

11、1 回溯策略回溯策略5.3.2 5.3.2 寬度優先搜索策略寬度優先搜索策略5.3.3 5.3.3 深度優先搜索策略深度優先搜索策略延邊大學工學院計算機科學與技術系5.3.1 5.3.1 回溯策略回溯策略n 帶回溯策略的搜索帶回溯策略的搜索：從初始狀態出發，不停地、試探性地尋找路徑，直到它到達目的或“不可解結點”，即“死胡同”為止。若它遇到不可解結點就回溯到路徑中最近的父結點上，查看該結點是否還有其他的子結點未被擴展。若有，則沿這些子結點繼續搜索；如果找到目標，就成功退出搜索，返回解題路徑。延邊大學工學院計算機科學與技術系n 遞歸過程遞歸過程：Step Track (DataList)：Dat

12、a：= First(DataList);if Member(Data, Tail(DataList) then return FAIL; *回老路退回if Goal(Data) then return NIL; *達到目的地成功返回if DeadEnd(Data) then return FAIL; *達到不合理狀態，退出if Length(DataList) Bound then return FAIL; *已到深度限制，退回Rules：= AppRules(Data); *得出可應用的規則集Loop：if Null(Rules) then return FAIL; *進入死胡同，退回R：=

13、 First(Rules); *取出第一條可用規則Rules：= Tail(Rules); Newdata：= Gen(R,Data); *運用規則，生成新狀態NewDataList：= Cons(Newdata, DataList);Path：= Back Track(NewDataList); *遞歸If Path：= FAIL then go loop else return Cons(R, Path);5.3.1 5.3.1 回溯策略回溯策略延邊大學工學院計算機科學與技術系5.3.1 5.3.1 回溯策略回溯策略1 AB 2E 3J 57 K9 G6 F10 H11 D8 C回溯搜索示

14、意圖回溯搜索示意圖延邊大學工學院計算機科學與技術系5.3.1 5.3.1 回溯策略回溯策略n 回溯搜索的算法回溯搜索的算法(1) PS（path states）表）表：保存當前搜索路徑上的狀態。如果找到了目的，PS就是解路徑上的狀態有序集。 (2) NPS（new path states）表）表：新的路徑狀態表。它包含了等待搜索的狀態，其后裔狀態還未被搜索到，即未被生成擴展 。(3) NSS（no solvable states）表）表：不可解狀態集，列出了找不到解題路徑的狀態。如果在搜索中擴展出的狀態是它的元素，則可立即將之排除，不必沿該狀態繼續搜索。 延邊大學工學院計算機科學與技術系Fun

15、ction backtrack：begin PS：= Start; NPS：= Start; NSS：= ; CS：= Start; *初始化 while NPS do begin if CS=目的狀態 then return(PS); *成功，返回解題路徑 if CS沒有子狀態（不包括PS，NPS和NSS中已有的狀態） then begin while（(PS非空) and (CS=PS中的第一個元素)）do begin 將CS加入NSS *標明此狀態不可解 從PS中刪除第一個元素CS *回溯 從NPS中刪除第一個元素CS； CS：= NPS中的第一個元素； 5.3.1 5.3.1 回溯策略

16、回溯策略延邊大學工學院計算機科學與技術系 end; 將CS加入PS； endelse begin 將CS子狀態（不包括PS、NPS和NSS中已有的）加入NPS； CS：= NPS中第一個元素； 將CS加入到PS； end end； return FAIL; end.5.3.1 5.3.1 回溯策略回溯策略延邊大學工學院計算機科學與技術系n 回溯搜索示意圖的回溯軌跡： 初值：PS=A； NPS=A； NSS= ； CS=A。 5.3.1 5.3.1 回溯策略回溯策略延邊大學工學院計算機科學與技術系5.3.1 5.3.1 回溯策略回溯策略n 圖搜索算法（深度優先、寬度優先、最好優先搜索等）的回溯思

17、想：（1）用未處理狀態表（NPS）使算法能返回（回溯）到其中任一狀態。 （2）用一張“死胡同”狀態表（NSS）來避免算法重新搜索無解的路徑。 （3）在PS 表中記錄當前搜索路徑的狀態，當滿足目的時可以將它作為結果返回。 （4）為避免陷入死循環必須對新生成的子狀態進行檢查，看它是否在該三張表中 。延邊大學工學院計算機科學與技術系5.3.2 5.3.2 寬度優先搜索策略寬度優先搜索策略n open表（NPS表）：已經生成出來但其子狀態未被搜索的狀態。n closed表（ PS表和NSS表的合并）：記錄了已被生成擴展過的狀態。 0S12345678910寬度優先搜索法中狀態的搜索次序寬度優先搜索法中

18、狀態的搜索次序延邊大學工學院計算機科學與技術系5.3.2 5.3.2 寬度優先搜索策略寬度優先搜索策略Procedure breadth_first_searchbeginopen：= start; closed：= *初始化while open do begin 從open表中刪除第一個狀態，稱之為n； 將n放入closed表中； if n = 目的狀態 then return (success); 生成n的所有子狀態； 從n的子狀態中刪除已在open或closed表中出現的狀態； 將n的其余子狀態，按生成的次序加入到open表的后段。 end; end;open表：隊列結構，即先進先出（F

19、IFO）的數據結構 延邊大學工學院計算機科學與技術系n 例例3 通過搬動積木塊，希望從初始狀態達到一個目的狀態，即三塊積木堆疊在一起。 5.3.2 5.3.2 寬度優先搜索策略寬度優先搜索策略BCAABC(a) 初始狀態(b) 目的狀態 積木問題積木問題延邊大學工學院計算機科學與技術系n 操作算子為MOVE（X，Y）：把積木X搬到Y（積木或桌面）上面。n 操作算子可運用的先決條件：（1）被搬動積木的頂部必須為空。（2）如果 Y 是積木，則積木 Y 的頂部也必須為空。（3）同一狀態下，運用操作算子的次數不得多于一次。5.3.2 5.3.2 寬度優先搜索策略寬度優先搜索策略MOVE（A，Table

20、）：“搬動積木A到桌面上”。延邊大學工學院計算機科學與技術系A AB BA AB BA AC CC CB BA AC CC CC CB BA AB BC CA AB BA AC CB BA AA AB BC CB BC CB BC CC CA AB BA AMOVE(A,TABLE)MOVE(A,TABLE)MOVE(C,A)MOVE(C,A)MOVE(A,C)MOVE(A,C)MOVE(B,A)MOVE(B,A)MOVE(B,C)MOVE(B,C) MOVE(C,A) MOVE(C,A)MOVE(C,B)MOVE(C,B) MOVE(C,B) MOVE(C,B)MOVE(A,B)MOVE(A

21、,B)0S1S2S3S4S5S6S7S8S9S10S沒有后裔，沒有后裔，失敗退出失敗退出 積木問題的寬度優先搜索樹積木問題的寬度優先搜索樹5.3.2 5.3.2 寬度優先搜索策略寬度優先搜索策略延邊大學工學院計算機科學與技術系5.3.3 5.3.3 深度優先搜索策略深度優先搜索策略0S12345678910111213KK 深度優先搜索法中狀態的搜索次序0S12345678910111213KK深度優先搜索法中狀態的搜索次序延邊大學工學院計算機科學與技術系5.3.3 5.3.3 深度優先搜索策略深度優先搜索策略n 在深度優先搜索中，當搜索到某一個狀態時，它所有的子狀態以及子狀態的后裔狀態都必須

22、先于該狀態的兄弟狀態被搜索。 n 為了保證找到解，應選擇合適的深度限制值，或采取不斷加大深度限制值的辦法，反復搜索，直到找到解。 延邊大學工學院計算機科學與技術系5.3.3 5.3.3 深度優先搜索策略深度優先搜索策略n 深度優先搜索過程： Procedure depth_first_searchbeginopen:=start;closed:= ;d:=深度限制值while open dobegin從open表表中刪除第一個狀態，稱之為n;將n放入closed表表中；if n=目的狀態 then return (success);if n的深度d then continue;生成n的所有子狀

23、態；從n的子狀態中刪除已在open或closed表中出現的狀態；將n的其余子狀態，按生成的次序加入到open 表的前端。endend。 open表：堆棧結構，即先進后出（FILO）的數據結構。open表：所有已生成但未作擴展的狀態 closed表記錄了已擴展過的狀態 延邊大學工學院計算機科學與技術系5.3.3 5.3.3 深度優先搜索策略深度優先搜索策略n 深度優先搜索并不能保證第一次搜索到的某個狀態時的路徑是到這個狀態的最短路徑。 n 對任何狀態而言，以后的搜索有可能找到另一條通向它的路徑。如果路徑的長度對解題很關鍵的話，當算法多次搜索到同一個狀態時，它應該保留最短路徑。 延邊大學工學院計算

24、機科學與技術系n 例例4 卒子穿陣問題卒子穿陣問題，要求一卒子從頂部通過下圖所示的陣列到達底部。卒子行進中不可進入到代表敵兵駐守的區域（標注1），并不準后退。假定深度限制值為5。 5.3.3 5.3.3 深度優先搜索策略深度優先搜索策略000100100100000121342134行列圖5.10陣列 圖000100100100000121342134行列圖5.10陣列 圖 陣列圖陣列圖 延邊大學工學院計算機科學與技術系5.3.3 5.3.3 深度優先搜索策略深度優先搜索策略0S1S)1 ,1(2S)2,1(3S)2,2(4S)1 ,2(5S)1 ,3(6S)2,3(7S)3,2(8S)3,1

25、(9S)2,1(14S)4,1(10S)2,2(11S)1 ,2(12S)1 ,3(13S)3,2(15S)4,2(16S)4,3(17S)4,4(18S)4,1(死死死死深度限制解 0S1S)1 ,1(2S)2,1(3S)2,2(4S)1 ,2(5S)1 ,3(6S)2,3(7S)3,2(8S)3,1(9S)2,1(14S)4,1(10S)2,2(11S)1 ,2(12S)1 ,3(13S)3,2(15S)4,2(16S)4,3(17S)4,4(18S)4,1(死死死死深度限制解卒子穿陣的深度優先搜索樹卒子穿陣的深度優先搜索樹延邊大學工學院計算機科學與技術系第第5 5章章 搜索求解策略搜索求

26、解策略5.1 5.1 搜索的概念搜索的概念5.2 5.2 狀態空間知識表示方法狀態空間知識表示方法5.3 5.3 盲目的圖搜索策略盲目的圖搜索策略5.4 5.4 啟發式圖搜索策略啟發式圖搜索策略5.5 5.5 與與/ /或圖搜索策略或圖搜索策略延邊大學工學院計算機科學與技術系5.4 5.4 啟發式圖搜索策略啟發式圖搜索策略5.4.1 5.4.1 啟發式策略啟發式策略5.4.2 5.4.2 啟發信息和估價函數啟發信息和估價函數5.4.3 5.4.3 A A搜索算法搜索算法5.4.4 5.4.4 A A* *搜索算法及其特性搜索算法及其特性分析分析延邊大學工學院計算機科學與技術系5.4.1 5.4

27、.1 啟發式策略啟發式策略n “啟發啟發”（heuristic）：關于發現和發明操作算子及搜索方法的研究。n 在狀態空間搜索中，啟發式啟發式被定義成一系列操作算子，并能從狀態空間中選擇最有希望到達問題解的路徑。n 啟發式策略啟發式策略：利用與問題有關的啟發信息進行搜索。延邊大學工學院計算機科學與技術系5.4.1 5.4.1 啟發式策略啟發式策略n 運用啟發式策略的兩種基本情況運用啟發式策略的兩種基本情況： （1）一個問題由于在問題陳述和數據獲取方面固有 的模糊性，可能會使它沒有一個確定的解。 （2）雖然一個問題可能有確定解，但是其狀態空間 特別大，搜索中生成擴展的狀態數會隨著搜索 的深度呈指數

28、級增長。延邊大學工學院計算機科學與技術系n 例例5 一字棋一字棋。在九宮棋盤上，從空棋盤開始，雙方輪流在棋盤上擺各自的棋子 或 （每次一枚），誰先取得三子一線（一行、一列或一條對角線）的結果就取勝。 5.4.1 5.4.1 啟發式策略啟發式策略 和 能夠在棋盤中擺成的各種不同的棋局就是問題空間中的不同狀態。 9個位置上擺放空， ， 有 39 種棋局。 可能的走法 ： 。1789延邊大學工學院計算機科學與技術系5.4.1 5.4.1 啟發式策略啟發式策略贏的幾率贏的幾率贏的幾率圖5.12 啟發式策略的運用贏的幾率贏的幾率贏的幾率圖5.12 啟發式策略的運用 啟發式策略的運用啟發式策略的運用延邊大

29、學工學院計算機科學與技術系5.4.1 5.4.1 啟發式策略啟發式策略圖5.13啟發式搜索下縮減的狀態空間啟發式搜索下縮減的狀態空間啟發式搜索下縮減的狀態空間延邊大學工學院計算機科學與技術系5.4.2 5.4.2 啟發信息和估價函數啟發信息和估價函數n 在具體求解中，能夠利用與該問題有關的信息來簡化搜索過程，稱此類信息為啟發信息啟發信息。n 啟發式搜索啟發式搜索：利用啟發信息的搜索過程。延邊大學工學院計算機科學與技術系5.4.2 5.4.2 啟發信息和估價函數啟發信息和估價函數n 求解問題中能利用的大多是非完備的啟發信息：（1）求解問題系統不可能知道與實際問題有關的全部信息，因而無法知道該問題

30、的全部狀態空間，也不可能用一套算法來求解所有的問題。（2）有些問題在理論上雖然存在著求解算法，但是在工程實踐中，這些算法不是效率太低，就是根本無法實現。一字棋：9！，西洋跳棋：1078，國際象棋：10120，圍棋：10761。假設每步可以搜索一個棋局，用極限并行速度（10-104年/步）來處理，搜索一遍國際象棋的全部棋局也得1016年即1億億年才可以算完！ 延邊大學工學院計算機科學與技術系5.4.2 5.4.2 啟發信息和估價函數啟發信息和估價函數n啟發信息的分類： （1）陳述性啟發信息 （2）過程性啟發信息 （3）控制性啟發信息n利用控制性的啟發信息的情況： （1）沒有任何控制性知識作為搜索

31、的依據，因而搜索的每一步完全是隨意的。 （2）有充分的控制知識作為依據，因而搜索的每一步選擇都是正確的，但這是不現實的。延邊大學工學院計算機科學與技術系5.4.2 5.4.2 啟發信息和估價函數啟發信息和估價函數n 估價函數的任務就是估計待搜索結點的“有希望”程度，并依次給它們排定次序（在open表中）。n 估價函數 ：從初始結點經過 結點到達目的 結點的路徑的最小代價估計值，其一般形式是)(nfn)()()(nhngnfn 一般地，在 中， 的比重越大，越傾向于寬度優先搜索方式，而 的比重越大，表示啟發性能越強。( )f n( )g n( )h n延邊大學工學院計算機科學與技術系5.4.2

32、5.4.2 啟發信息和估價函數啟發信息和估價函數n 例例6 八數碼的估價函數八數碼的估價函數設計方法有多種，并且不同的估價函數對求解八數碼問題有不同的影響。 最簡單的估價函數：取一格局與目的格局相比，其位置不符的將牌數目。 較好的估價函數：各將牌移到目的位置所需移動的距離的總和。 第三種估價函數：對每一對逆轉將牌乘以一個倍數。 第四種估價函數：克服了僅計算將牌逆轉數目策略的局限，將位置不符將牌數目的總和與3倍將牌逆轉數目相加。延邊大學工學院計算機科學與技術系5.4.3 A5.4.3 A搜索算法搜索算法n 啟發式圖搜索法的基本特點啟發式圖搜索法的基本特點：如何尋找并設計一個與問題有關的 及構出

33、，然后以 的大小來排列待擴展狀態的次序，每次選擇 值最小者進行擴展。n open表：保留所有已生成而未擴展的狀態。n closed表：記錄已擴展過的狀態。n 進入open表的狀態是根據其估值的大小插入到表中合適的位置，每次從表中優先取出啟發估價函數值最小的狀態加以擴展。)(nh)()()(nhngnf)(nf)(nf延邊大學工學院計算機科學與技術系5.4.3 A5.4.3 A搜索算法搜索算法n 一般啟發式圖搜索算法（一般啟發式圖搜索算法（簡記為簡記為A）procedure heuristic_searchopen：=start；closed：= ；f(s)：=g(s)+h(s)；*初始化whi

34、le open dobegin從open表中刪除第一個狀態，稱之為n；if n=目的狀態then return(success)；生成n的所有子狀態；if n沒有任何子狀態then continue；for n的每個子狀態docase子狀態is not already on open表or closed表；begin計算該子狀態的估價函數值；將該子狀態加到open表中； end； 延邊大學工學院計算機科學與技術系5.4.3 A5.4.3 A搜索算法搜索算法case子狀態is already on open表：if該子狀態是沿著一條比在open表已有的更短路徑而到達then 記錄更短路徑走向及其

35、估價函數值；case子狀態is already on closed表：if該子狀態是沿著一條比在closed表已有的更短路徑而到達thenbegin將該子狀態從closed表移到open表中；記錄更短路徑走向及其估價函數值；end；case end；將n放入closed表中；根據估價函數值，從小到大重新排列open表；end；*open表中結點已耗盡return(failure)；end.延邊大學工學院計算機科學與技術系5.4.3 A5.4.3 A搜索算法搜索算法n 每次重復時，A搜索算法從open表中取出第一個狀態，如果該狀態滿足目的條件，則算法返回到該狀態的搜索路徑。n 如果open表的第

36、一個狀態不是目的狀態，則算法利用與之相匹配的一系列操作算子進行相應的操作來產生它的子狀態。如果某個子狀態已在open表（或closed表）中出現過，即該狀態再一次被發現時，則通過刷新它的祖先狀態的歷史記錄，使算法極有可能找到到達目的狀態的更短的路徑n 接著，A搜索算法open表中每個狀態的估價函數值，按照值的大小重新排序，將值最小的狀態放在表頭，使其第一個被擴展。 延邊大學工學院計算機科學與技術系A(-5)B(-3)C(-4)D(-6)E(-5)F(-3)G(-4)H(-3)IJKL(-5)M(-5) NO(-2)P(-3)QRSTU(-3)5.4.3 A5.4.3 A搜索算法搜索算法延邊大學

37、工學院計算機科學與技術系5.4.3 A5.4.3 A搜索算法搜索算法n 例例7 利用A搜索算法求解八數碼問題的搜索樹，其估價函數定義為 ：狀態的深度，每步為單位代價。 ：以“不在位”的將牌數作為啟發信息的度量。)(nd)()()(nwndnf)(nw ：為狀態 到目的狀態的最優路徑的代價。 ：A搜索算法 A*搜索算法。 ( )( )*( )w nh nhnn)(*nh延邊大學工學院計算機科學與技術系5.4.3 A5.4.3 A搜索算法搜索算法初始s ( 4)2 8 31 6 47 5B( 4)2 8 31 47 6 5C( 4)2 8 31 6 47 5A( 4)2 8 31 6 47 5D( 5)2 8 31 47 6 5E( 5)2 31 8 47 6 5F( 6)2 8 31 47 6 5J ( 7)2 31 8 47 6 5I ( 5)2 31 8 47 6 5H( 7)2 8 37 1 46 5G( 6)8 32 1 47 6 5K( 5)1 2 38 47 6 5M( 7)1 2 37 8 46 5L( 5)1 2 38 47 6 5目的延邊大學工學院計算機科學與技術系5.4.3 A5.4.3 A搜索算法搜索算法n open表和closed表內狀態排列的變化情況 延邊大學工學院計算機科學與技術系5.4.4