第5章 搜索求解策略

1、第 5 章 搜索求解策略,教材： 王萬良《人工智能及其應用》（第2版） 高等教育出版社，2008. 6,2,第5章 搜索求解策略,5.1 搜索的概念5.2 狀態(tài)空間的搜索策略5.3 盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略5.5 與/或圖搜索策略,3,第5章 搜索求解策略,5.1 搜索的概念5.2 狀態(tài)空間知識表示方法5.3 盲目的圖搜索策略5.4 啟發(fā)式圖搜索

2、策略5.5 與/或圖搜索策略,4,5.1 搜索的概念,問題求解：問題的表示。 選擇一種相對合適的求解方法。問題求解的基本方法：搜索法、歸約法、歸結法、推理法及產生式等。,5,5.1 搜索的概念,5.1.1 搜索的基本問題與主要過程5.1.2 搜索策略,6,5.1.1 搜索的基本問題與主要過程,搜索中需要解決的基本問題：（1）是否一定能找到一個解。（2）是否終止運行或是否會陷入一個死循環(huán)。（3）找到的解是否是最

3、佳解。（4）時間與空間復雜性如何。,7,5.1.1 搜索的基本問題與主要過程,搜索的主要過程：(1) 從初始或目的狀態(tài)出發(fā)，并將它作為當前狀態(tài)。(2) 掃描操作算子集，將適用當前狀態(tài)的一些操作算子作用于當前狀態(tài)而得到新的狀態(tài)，并建立指向其父結點的指針 。(3) 檢查所生成的新狀態(tài)是否滿足結束狀態(tài)，如果滿足，則得到問題的一個解，并可沿著有關指針從結束狀態(tài)反向到達開始狀態(tài)，給出一解答路徑；否則，將新狀態(tài)作為當前狀態(tài)，返回第(

4、2)步再進行搜索。,8,5.1.2 搜索策略,1. 搜索方向： (1) 數(shù)據(jù)驅動：從初始狀態(tài)出發(fā)的正向搜索。,正向搜索——從問題給出的條件（一個用于狀態(tài)轉換的操作算子集合）出發(fā)。,逆向搜索：先從想達到的目的入手，看哪些操作算子能產生該目的以及應用這些操作算子產生目的時需要哪些條件。,(2) 目的驅動：從目的狀態(tài)出發(fā)的逆向搜索。,9,5.1.2 搜索策略,1. 搜索方向： (3) 雙向搜索,雙向搜索：從開始狀態(tài)出發(fā)作

5、正向搜索，同時又從目的狀態(tài)出發(fā)作逆向搜索，直到兩條路徑在中間的某處匯合為止。,10,5.1.2 搜索策略,2. 盲目搜索與啟發(fā)式搜索:（1）盲目搜索：在不具有對特定問題的任何有關信息的條件下，按固定的步驟（依次或隨機調用操作算子）進行的搜索。 （2）啟發(fā)式搜索：考慮特定問題領域可應用的知識，動態(tài)地確定調用操作算子的步驟，優(yōu)先選擇較適合的操作算子，盡量減少不必要的搜索，以求盡快地到達結束狀態(tài)。,11,第5章 搜索求解策略,5.1

6、 搜索的概念5.2 狀態(tài)空間知識表示方法5.3 盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略5.5 與/或圖搜索策略,12,5.2 狀態(tài)空間知識表示方法,5.2.1 狀態(tài)空間表示法5.2.2 狀態(tài)空間的圖描述,13,5.2.1 狀態(tài)空間表示法,狀態(tài)：表示系統(tǒng)狀態(tài)、事實等敘述型知識的一組變量或數(shù)組：,,,操作：表示引起狀態(tài)變化的過程型知識的一組關 系或函數(shù)：,T,14,5.2.1 狀態(tài)空間表示法,狀態(tài)空

7、間：利用狀態(tài)變量和操作符號，表示系統(tǒng)或問題的有關知識的符號體系，狀態(tài)空間是一個四元組：,,,,,,,,：狀態(tài)集合。 ：操作算子的集合。 ：包含問題的初始狀態(tài)是 的非空子集。 ：若干具體狀態(tài)或滿足某些性質的路徑信息描述。,15,5.2.1 狀態(tài)空間表示法,求解路徑：從 結點到 結點的路徑。,,,,,：狀態(tài)空間的一個解。,狀態(tài)空間的一個解：一個有限的操作算子序列。,

8、16,,例1 八數(shù)碼問題的狀態(tài)空間。,5.2.1 狀態(tài)空間表示法,狀態(tài)集 ：所有擺法,操作算子：,將空格向上移Up將空格向左移Left將空格向下移Down將空格向右移Right,17,5.2.2 狀態(tài)空間的圖描述,,,,,,,,,,,,,,,狀態(tài)空間的有向圖描述,18,5.2.2 狀態(tài)空間的圖描述,八數(shù)碼狀態(tài)空間圖,19,例2 旅行商問題（traveling salesman problem, TSP

9、）或郵遞員路徑問題。,5.2.2 狀態(tài)空間的圖描述,可能路徑：費用為375的路徑（A，B，C，D，E，A）,,,,,,20,5.2.2 狀態(tài)空間的圖描述,,,21,第5章 搜索求解策略,5.1 搜索的概念5.2 狀態(tài)空間知識表示方法5.3 盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略5.5 與/或圖搜索策略,22,5.3 盲目的圖搜索策略,5.3.1 回溯策略5.3.2 寬度優(yōu)先搜索策略5.3.3 深度優(yōu)

10、先搜索策略,23,5.3.1 回溯策略,帶回溯策略的搜索： 從初始狀態(tài)出發(fā)，不停地、試探性地尋找路徑，直到它到達目的或“不可解結點”，即“死胡同”為止。若它遇到不可解結點就回溯到路徑中最近的父結點上，查看該結點是否還有其他的子結點未被擴展。若有，則沿這些子結點繼續(xù)搜索；如果找到目標，就成功退出搜索，返回解題路徑。,24,,遞歸過程：,5.3.1 回溯策略,Step Track (DataList)：Data：=

11、First(DataList);if Member(Data, Tail(DataList)) then return FAIL; *回老路退回if Goal(Data) then return NIL; *達到目的地成功返回if DeadEnd(Data) then return FAIL; *達到不合理狀態(tài)，退出

12、if Length(DataList) > Bound then return FAIL; *已到深度限制，退回Rules：= AppRules(Data); *得出可應用的規(guī)則集Loop：if Null(Rules) then return FAIL; *進入死胡同，退回R：= First(Rules);

13、 *取出第一條可用規(guī)則Rules：= Tail(Rules); Newdata：= Gen(R,Data); *運用規(guī)則，生成新狀態(tài)NewDataList：= Cons(Newdata, DataList);Path：= Back Track(NewDataList); *遞歸If Path：= FAI

14、L then go loop else return Cons(R, Path);,25,5.3.1 回溯策略,,回溯搜索示意圖,,,,,,,,,,,,,,,,,,,,,,26,5.3.1 回溯策略,回溯搜索的算法(1) PS（path states）表：保存當前搜索路徑上的狀態(tài)。如果找到了目的，PS就是解路徑上的狀態(tài)有序集。 (2) NPS（new path states）表：新的路徑狀態(tài)表。它包含了等待搜索的狀

15、態(tài)，其后裔狀態(tài)還未被搜索到，即未被生成擴展 。(3) NSS（no solvable states）表：不可解狀態(tài)集，列出了找不到解題路徑的狀態(tài)。如果在搜索中擴展出的狀態(tài)是它的元素，則可立即將之排除，不必沿該狀態(tài)繼續(xù)搜索。,27,,5.3.1 回溯策略,Function backtrack：begin PS：= [Start]; NPS：= [Start]; NSS：= [ ]; CS：= Start; *初始化

16、 while NPS[ ] do begin if CS=目的狀態(tài) then return(PS); *成功，返回解題路徑 if CS沒有子狀態(tài)（不包括PS，NPS和NSS中已有的狀態(tài)） then begin while（(PS非空) and (CS=PS中的第一個元素)）do

17、 begin 將CS加入NSS *標明此狀態(tài)不可解 從PS中刪除第一個元素CS *回溯 從NPS中刪除第一個元素CS； CS：= NPS中的第一個元素；,28,,5.3.1 回溯策略,end;

18、 將CS加入PS； endelse begin 將CS子狀態(tài)（不包括PS、NPS和NSS中已有的）加入NPS； CS：= NPS中第一個元素； 將CS加入到PS； end end； return FAIL; end.,29,,回溯

19、搜索示意圖的回溯軌跡： 初值：PS=[A]； NPS=[A]； NSS=[ ]； CS=A。,5.3.1 回溯策略,30,5.3.1 回溯策略,圖搜索算法（深度優(yōu)先、寬度優(yōu)先、最好優(yōu)先搜索等）的回溯思想：,（1）用未處理狀態(tài)表（NPS）使算法能返回（回溯）到其 中任一狀態(tài)。 （2）用一張“死胡同”狀態(tài)表（NSS）來避免算法重新搜索 無解的路徑。 （3）在PS 表中記錄當前搜索路

20、徑的狀態(tài)，當滿足目的時可 以將它作為結果返回。 （4）為避免陷入死循環(huán)必須對新生成的子狀態(tài)進行檢查， 看它是否在該三張表中 。,31,5.3.2 寬度優(yōu)先搜索策略,,,open表（NPS表）：已經生成出來但其子狀態(tài)未被搜索的狀態(tài)。closed表（ PS表和NSS表的合并）：記錄了已被生成擴展過的狀態(tài)。,寬度優(yōu)先搜索法中狀態(tài)的搜索次序,32,5.3.2 寬度優(yōu)先搜索策略,Procedure

21、breadth_first_searchbeginopen：= [start]; closed：= [ ] *初始化while open [ ] do begin 從open表中刪除第一個狀態(tài)，稱之為n； 將n放入closed表中； if n = 目的狀態(tài) then return (success); 生成n的所有子狀態(tài)； 從n的

22、子狀態(tài)中刪除已在open或closed表中出現(xiàn)的狀態(tài)； 將n的其余子狀態(tài)，按生成的次序加入到open表的后段。 end; end;,open表：隊列結構，即先進先出（FIFO）的數(shù)據(jù)結構,33,例3 通過搬動積木塊，希望從初始狀態(tài)達到一個目的狀態(tài)，即三塊積木堆疊在一起。,5.3.2 寬度優(yōu)先搜索策略,,34,操作算子為MOVE（X，Y）：把積木X搬到Y（積木或桌面）上面。,5.3.2 寬度優(yōu)先搜索策

23、略,MOVE（A，Table）：“搬動積木A到桌面上”。,操作算子可運用的先決條件：（1）被搬動積木的頂部必須為空。（2）如果 Y 是積木，則積木 Y 的頂部也必須為空。（3）同一狀態(tài)下，運用操作算子的次數(shù)不得多于一次。,35,,,5.3.2 寬度優(yōu)先搜索策略,,,,,,,,,,,,36,5.3.3 深度優(yōu)先搜索策略,,37,在深度優(yōu)先搜索中，當搜索到某一個狀態(tài)時，它所有的子狀態(tài)以及子狀態(tài)的后裔狀態(tài)都必須先于該狀態(tài)的兄弟狀態(tài)被

24、搜索。 為了保證找到解，應選擇合適的深度限制值，或采取不斷加大深度限制值的辦法，反復搜索，直到找到解。,5.3.3 深度優(yōu)先搜索策略,38,深度優(yōu)先搜索過程：,5.3.3 深度優(yōu)先搜索策略,Procedure depth_first_searchbeginopen:=[start];closed:=[ ];d:=深度限制值while open[ ] dobegin從open表中刪除第一個狀態(tài)，稱之為n;將n放入clos

25、ed表中；if n=目的狀態(tài) then return (success);if n的深度>d then continue;生成n的所有子狀態(tài)；從n的子狀態(tài)中刪除已在open或closed表中出現(xiàn)的狀態(tài)；將n的其余子狀態(tài)，按生成的次序加入到open 表的前端。endend。,open表：堆棧結構，即先進后出（FILO）的數(shù)據(jù)結構。open表：所有已生成但未作擴展的狀態(tài),closed表記錄了已擴展過的狀態(tài),39,深

26、度優(yōu)先搜索并不能保證第一次搜索到的某個狀態(tài)時的路徑是到這個狀態(tài)的最短路徑。 對任何狀態(tài)而言，以后的搜索有可能找到另一條通向它的路徑。如果路徑的長度對解題很關鍵的話，當算法多次搜索到同一個狀態(tài)時，它應該保留最短路徑。,5.3.3 深度優(yōu)先搜索策略,40,例4 卒子穿陣問題，要求一卒子從頂部通過下圖所示的陣列到達底部。卒子行進中不可進入到代表敵兵駐守的區(qū)域（標注1），并不準后退。假定深度限制值為5。,5.3.3 深度優(yōu)先搜索策略,

27、,陣列圖,41,,5.3.3 深度優(yōu)先搜索策略,,,,,,,open表：S17、S18closed表：S0～S16,,卒子穿陣的深度優(yōu)先搜索樹,42,第5章 搜索求解策略,5.1 搜索的概念5.2 狀態(tài)空間知識表示方法5.3 盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略5.5 與/或圖搜索策略,43,5.4 啟發(fā)式圖搜索策略,5.4.1 啟發(fā)式策略5.4.2 啟發(fā)信息和估價函數(shù)5.4.3 A搜索算法5.

28、4.4 A*搜索算法及其特性分析,44,5.4.1 啟發(fā)式策略,“啟發(fā)”（heuristic）：關于發(fā)現(xiàn)和發(fā)明操作算子及搜索方法的研究。在狀態(tài)空間搜索中，啟發(fā)式被定義成一系列操作算子，并能從狀態(tài)空間中選擇最有希望到達問題解的路徑。啟發(fā)式策略：利用與問題有關的啟發(fā)信息進行搜索。,45,5.4.1 啟發(fā)式策略,運用啟發(fā)式策略的兩種基本情況： （1）一個問題由于在問題陳述和數(shù)據(jù)獲取方面固有 的模糊性，可能會使它沒

29、有一個確定的解。 （2）雖然一個問題可能有確定解，但是其狀態(tài)空間 特別大，搜索中生成擴展的狀態(tài)數(shù)會隨著搜索 的深度呈指數(shù)級增長。,46,例5 一字棋。在九宮棋盤上，從空棋盤開始，雙方輪流在棋盤上擺各自的棋子 ? 或 ? （每次一枚），誰先取得三子一線（一行、一列或一條對角線）的結果就取勝。,5.4.1 啟發(fā)式策略,,,? 和 ? 能夠在棋盤中擺成的各種不同的棋局就是問題空間中的不同狀態(tài)。

30、 9個位置上擺放{空， ? ， ?}有 39 種棋局。 可能的走法 ： 。,47,5.4.1 啟發(fā)式策略,啟發(fā)式策略的運用,?,?,?,48,,5.4.1 啟發(fā)式策略,,,,,,啟發(fā)式搜索下縮減的狀態(tài)空間,49,5.4.2 啟發(fā)信息和估價函數(shù),在具體求解中，能夠利用與該問題有關的信息來簡化搜索過程，稱此類信息為啟發(fā)信息。啟發(fā)式搜索：利用啟發(fā)信息的搜索過程。,50,5.4.2

31、 啟發(fā)信息和估價函數(shù),求解問題中能利用的大多是非完備的啟發(fā)信息：（1）求解問題系統(tǒng)不可能知道與實際問題有關的全部信息，因而無法知道該問題的全部狀態(tài)空間，也不可能用一套算法來求解所有的問題。（2）有些問題在理論上雖然存在著求解算法，但是在工程實踐中，這些算法不是效率太低，就是根本無法實現(xiàn)。,一字棋：9！，西洋跳棋：1078，國際象棋：10120，圍棋：10761。假設每步可以搜索一個棋局，用極限并行速度（10-104年/步）來處理，

32、搜索一遍國際象棋的全部棋局也得1016年即1億億年才可以算完！,51,5.4.2 啟發(fā)信息和估價函數(shù),啟發(fā)信息的分類： （1）陳述性啟發(fā)信息 （2）過程性啟發(fā)信息 （3）控制性啟發(fā)信息利用控制性的啟發(fā)信息的情況： （1）沒有任何控制性知識作為搜索的依據(jù)，因而搜索的每一步完全是隨意的。 （2）有充分的控制知識作為依據(jù)，因而搜索的每一步選擇都是正確的，但這是不現(xiàn)實的。,52,5.4.2 啟發(fā)信息和估價函

33、數(shù),估價函數(shù)的任務就是估計待搜索結點的“有希望”程度，并依次給它們排定次序（在open表中）。,,,,估價函數(shù) ：從初始結點經過 結點到達目的 結點的路徑的最小代價估計值，其一般形式是,,,,,一般地，在 中， 的比重越大，越傾向于寬度優(yōu)先搜索方式，而 的比重越大，表示啟發(fā)性能越強。,53,例6 八數(shù)碼的估價函數(shù)設計方法有多種，并且不同的估價函數(shù)對求解八數(shù)碼問題有不同的影響。 最簡單的估價函數(shù)：

34、取一格局與目的格局相比，其位置不符的將牌數(shù)目。 較好的估價函數(shù)：各將牌移到目的位置所需移動的距離的總和。 第三種估價函數(shù)：對每一對逆轉將牌乘以一個倍數(shù)。 第四種估價函數(shù)：克服了僅計算將牌逆轉數(shù)目策略的局限，將位置不符將牌數(shù)目的總和與3倍將牌逆轉數(shù)目相加。,5.4.2 啟發(fā)信息和估價函數(shù),54,5.4.3 A搜索算法,啟發(fā)式圖搜索法的基本特點：如何尋找并設計一個與問題有關的 及構出

35、 ， 然后以 的大小來排列待擴展狀態(tài)的次序，每次選擇 值最小者進行擴展。,,,,,open表：保留所有已生成而未擴展的狀態(tài)。 closed表：記錄已擴展過的狀態(tài)。 進入open表的狀態(tài)是根據(jù)其估值的大小插入到表中合適的位置，每次從表中優(yōu)先取出啟發(fā)估價函數(shù)值最小的狀態(tài)加以擴展。,55,一般啟發(fā)式圖搜索算法（簡記為A）,5.4.3 A搜索算法,procedure heuristic_se

36、archopen：=[start]；closed：=[ ]；f(s)：=g(s)+h(s)；*初始化while open≠[ ] dobegin從open表中刪除第一個狀態(tài)，稱之為n；if n=目的狀態(tài)then return(success)；生成n的所有子狀態(tài)；if n沒有任何子狀態(tài)then continue；for n的每個子狀態(tài)docase子狀態(tài)is not already on open表or closed表

37、；begin計算該子狀態(tài)的估價函數(shù)值；將該子狀態(tài)加到open表中； end；,56,,5.4.3 A搜索算法,case子狀態(tài)is already on open表：if該子狀態(tài)是沿著一條比在open表已有的更短路徑而到達then 記錄更短路徑走向及其估價函數(shù)值；case子狀態(tài)is already on closed表：if該子狀態(tài)是沿著一條比在closed表已有的更短路徑而到達thenbeg

38、in將該子狀態(tài)從closed表移到open表中；記錄更短路徑走向及其估價函數(shù)值；end；case end；將n放入closed表中；根據(jù)估價函數(shù)值，從小到大重新排列open表；end；*open表中結點已耗盡return(failure)；end.,57,5.4.3 A搜索算法,每次重復時，A搜索算法從open表中取出第一個狀態(tài)，如果該狀態(tài)滿足目的條件，則算法返回到該狀態(tài)的搜索路徑。如果open表的第一個

39、狀態(tài)不是目的狀態(tài)，則算法利用與之相匹配的一系列操作算子進行相應的操作來產生它的子狀態(tài)。如果某個子狀態(tài)已在open表（或closed表）中出現(xiàn)過，即該狀態(tài)再一次被發(fā)現(xiàn)時，則通過刷新它的祖先狀態(tài)的歷史記錄，使算法極有可能找到到達目的狀態(tài)的更短的路徑接著，A搜索算法open表中每個狀態(tài)的估價函數(shù)值，按照值的大小重新排序，將值最小的狀態(tài)放在表頭，使其第一個被擴展。,58,,5.4.3 A搜索算法,59,5.4.3 A搜索算法,例7 利

40、用A搜索算法求解八數(shù)碼問題的搜索樹，其估價函數(shù)定義為 ：狀態(tài)的深度，每步為單位代價。 ：以“不在位”的將牌數(shù)作為啟發(fā)信息的度量。,,,：為狀態(tài) 到目的狀態(tài)的最優(yōu)路徑的代價。 ：A搜索算法 → A*搜索算法。,60,,5.4.3 A搜索算法,,61,open表和closed表內狀態(tài)排列的變化情況,5.4.3 A搜索算法,62,如果某一問題有解，那么利用A*搜索算法對該問題進行搜索則

41、一定能搜索到解，并且一定能搜索到最優(yōu)的解而結束。上例中的八數(shù)碼A搜索樹也是A*搜索樹，所得的解路（s，B，E，I，K，L）為最優(yōu)解路，其步數(shù)為狀態(tài)L（5）上所標注的5 。,5.4.4 A*搜索算法及其特性分析,63,1. 可采納性 當一個搜索算法在最短路徑存在時能保證找到它，就稱它是可采納的。2. 單調性 搜索算法的單調性：在整個搜索空間都是局部可采納的。一個狀態(tài)和任一個子狀態(tài)之間的差由該狀態(tài)與其子狀態(tài)之間的實際

42、代價所限定。,5.4.4 A*搜索算法及其特性分析,64,3. 信息性 在兩個A*啟發(fā)策略的 中，如果對搜索空間中的任一狀態(tài) 都有 ，就稱策略 具有更多的信息性。,5.4.4 A*搜索算法及其特性分析,65,第5章 搜索求解策略,5.1 搜索的概念5.2 狀態(tài)空間知識表示方法5.3 盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略5.5 與/或圖搜索策略,66,5.5

43、 與/或圖搜索策略,1. 分解──與樹,,,與樹問題分解,67,5.5.1 與/或圖表表達法,2. 變換──或樹,或樹問題變換,5.5 與/或圖搜索策略,68,5.5.1 與/或圖表表達法,例8 猴子和香蕉問題。,5.5 與/或圖搜索策略,,,猴子和香蕉問題,69,5.5 與/或圖搜索策略,,,設系統(tǒng)的狀態(tài)用四元數(shù)組描述：,,,,,,：猴子所處水平位置 ：臺子所在水平位置 ：猴子是否在臺子上（ ，在；