1、 第 5 章 搜索求解策略教材： 王萬良人工智能及其應用（第3版） 高等教育出版社，2016. 22第5章 搜索求解策略在求解一個問題時，涉及到兩個方面：一是該問題的表示，如果一個問題找不到一個合適的表示方法，就談不上對它求解。另一方面則是選擇一種相對合適的求解方法。由于絕大多數需要人工智能方法求解的問題缺乏直接求解的方法，因此，搜索為一種求解問題的一般方法。下面首先討論搜索的基本概念，然后著重介紹狀態空間知識表示和搜索策略，主要有回溯策略、寬度優先搜索、深度優先搜索等盲目的圖搜索策略，以及A及A*搜索算法等啟發式圖搜索策略。3第5章 搜索求解策略5.1 搜索的概念5.2 狀態空間的搜索策略5

2、.3 盲目的圖搜索策略5.4 啟發式圖搜索策略5.5 與/或圖搜索策略4第5章 搜索求解策略5.1 搜索的概念5.2 狀態空間知識表示方法5.3 盲目的圖搜索策略5.4 啟發式圖搜索策略5.5 與/或圖搜索策略55.1 搜索的概念 問題求解：問題的表示。 求解方法。問題求解的基本方法：搜索法、歸約法、歸結法、推理法及產生式等。65.1.1 搜索的基本問題與主要過程 搜索中需要解決的基本問題：（1）是否一定能找到一個解。（2）找到的解是否是最佳解。（3）時間與空間復雜性如何。（4）是否終止運行或是否會陷入一個死循環。75.1.1 搜索的基本問題與主要過程搜索的主要過程：(1) 從初始或目的狀態出

3、發，并將它作為當前狀態。(2) 掃描操作算子集，將適用當前狀態的一些操作算子作用于當前狀態而得到新的狀態，并建立指向其父結點的指針 。(3) 檢查所生成的新狀態是否滿足結束狀態，如果滿足，則得到問題的一個解，并可沿著有關指針從結束狀態反向到達開始狀態，給出一解答路徑；否則，將新狀態作為當前狀態，返回第(2)步再進行搜索。 85.1.2 搜索策略1. 搜索方向： (1) 數據驅動：從初始狀態出發的正向搜索。 正向搜索從問題給出的條件出發。逆向搜索：從想達到的目的入手，看哪些操作算子能產生該目的以及應用這些操作算子產生目的時需要哪些條件。 (2) 目的驅動：從目的狀態出發的逆向搜索。雙向搜索：從開

4、始狀態出發作正向搜索，同時又從目的狀態出發作逆向搜索，直到兩條路徑在中間的某處匯合為止。(3) 雙向搜索95.1.2 搜索策略2. 盲目搜索與啟發式搜索:（1）盲目搜索：在不具有對特定問題的任何有關信息的條件下，按固定的步驟（依次或隨機調用操作算子）進行的搜索。 （2）啟發式搜索：考慮特定問題領域可應用的知識，動態地確定調用操作算子的步驟，優先選擇較適合的操作算子，盡量減少不必要的搜索，以求盡快地到達結束狀態。10第5章 搜索求解策略5.1 搜索的概念5.2 狀態空間知識表示方法5.3 盲目的圖搜索策略5.4 啟發式圖搜索策略5.5 與/或圖搜索策略115.2 狀態空間知識表示方法5.2.1

5、狀態空間表示法5.2.2 狀態空間的圖描述125.2.1 狀態空間表示法狀態：表示系統狀態、事實等敘述型知識的一組變量或數組： 操作：表示引起狀態變化的過程型知識的一組關 系或函數：T135.2.1 狀態空間表示法狀態空間：利用狀態變量和操作符號，表示系統或問題的有關知識的符號體系，狀態空間是一個四元組： ：狀態集合。 ：操作算子的集合。 ：包含問題的初始狀態是 的非空子集。 ：若干具體狀態或滿足某些性質的路徑信息描述。145.2.1 狀態空間表示法求解路徑：從 結點到 結點的路徑。 ：狀態空間的一個解。 狀態空間的一個解：一個有限的操作算子序列。15例 八數碼問題的狀態空間。 5.2.1 狀

6、態空間表示法狀態集 ：所有擺法操作算子：將空格向上移Up將空格向左移Left將空格向下移Down將空格向右移Right165.2.2 狀態空間的圖描述八數碼狀態空間圖 175.2.2 狀態空間的圖描述（狀態）（操作算子）狀態空間的有向圖描述18 例 旅行商問題（traveling salesman problem, TSP）或郵遞員路徑問題。 5.2.2 狀態空間的圖描述（家）（單位：km）可能路徑：費用為375的路徑（A，B，C，D，E，A） 195.2.2 狀態空間的圖描述 旅行推銷員狀態空間圖（部分） ABCDEA 375 A A A A B B C C C C D D D D A E

7、E E E E E E D 路徑: 路徑: 路徑: 路徑: ABCEDA ABDCE ABDECA 費用: 費用: 費用: 費用: 425 525 475 525 475 375 325 400 400 300 275 275 250 225 150 100 75 125 175 225 250 100 175 225 425 . . . . . . . 20第5章 搜索求解策略5.1 搜索的概念5.2 狀態空間知識表示方法5.3 盲目的圖搜索策略5.4 啟發式圖搜索策略5.5 與/或圖搜索策略215.3 盲目的圖搜索策略5.3.1 回溯策略5.3.2 寬度優先搜索策略5.3.3 深度優先搜索

8、策略225.3.1 回溯策略 帶回溯策略的搜索： 從初始狀態出發，不停地、試探性地尋找路徑，直到它到達目的或“不可解結點”，即“死胡同”為止。若它遇到不可解結點就回溯到路徑中最近的父結點上，查看該結點是否還有其他的子結點未被擴展。若有，則沿這些子結點繼續搜索；如果找到目標，就成功退出搜索，返回解題路徑。235.3.1 回溯策略回溯搜索示意圖245.3.1 回溯策略回溯搜索的算法(1) PS（path states）表：保存當前搜索路徑上的狀態。如果找到了目的，PS就是解路徑上的狀態有序集。 (2) NPS（new path states）表：新的路徑狀態表。它包含了等待搜索的狀態，其后裔狀態還

9、未被搜索到，即未被生成擴展 。(3) NSS（no solvable states）表：不可解狀態集，列出了找不到解題路徑的狀態。如果在搜索中擴展出的狀態是它的元素，則可立即將之排除，不必沿該狀態繼續搜索。 255.3.1 回溯策略圖搜索算法（深度優先、寬度優先、最好優先搜索等）的回溯思想：（1）用未處理狀態表（NPS）使算法能返回（回溯）到其 中任一狀態。 （2）用一張“死胡同”狀態表（NSS）來避免算法重新搜索 無解的路徑。 （3）在PS 表中記錄當前搜索路徑的狀態，當滿足目的時可 以將它作為結果返回。 （4）為避免陷入死循環必須對新生成的子狀態進行檢查， 看它是否在該三張表中 。265.

10、3.2 寬度優先搜索策略open表（NPS表）：已經生成出來但其子狀態未被搜索的狀態。closed表（ PS表和NSS表的合并）：記錄了已被生成擴展過的狀態。 0S12345678910寬度優先搜索法中狀態的搜索次序27例3 通過搬動積木塊，希望從初始狀態達到一個目的狀態，即三塊積木堆疊在一起。 5.3.2 寬度優先搜索策略BCAABC(a) 初始狀態(b) 目的狀態 積木問題28操作算子為MOVE（X，Y）：把積木X搬到Y（積木或桌面）上面。5.3.2 寬度優先搜索策略MOVE（A，Table）：“搬動積木A到桌面上”。 操作算子可運用的先決條件：（1）被搬動積木的頂部必須為空。（2）如果

11、Y 是積木，則積木 Y 的頂部也必須為空。（3）同一狀態下，運用操作算子的次數不得多于一次。29ABABACCBACCCBABCABACBAABCBCBCCABAMOVE(A,TABLE)MOVE(C,A)MOVE(A,C)MOVE(B,A)MOVE(B,C) MOVE(C,A)MOVE(C,B) MOVE(C,B)MOVE(A,B)0S1S2S3S4S5S6S7S8S9S10S沒有后裔，失敗退出 積木問題的寬度優先搜索樹5.3.2 寬度優先搜索策略305.3.3 深度優先搜索策略0S12345678910111213KK 深度優先搜索法中狀態的搜索次序0S12345678910111213K

12、K深度優先搜索法中狀態的搜索次序31在深度優先搜索中，當搜索到某一個狀態時，它所有的子狀態以及子狀態的后裔狀態都必須先于該狀態的兄弟狀態被搜索。 為了保證找到解，應選擇合適的深度限制值，或采取不斷加大深度限制值的辦法，反復搜索，直到找到解。 5.3.3 深度優先搜索策略32深度優先搜索并不能保證第一次搜索到的某個狀態時的路徑是到這個狀態的最短路徑。 對任何狀態而言，以后的搜索有可能找到另一條通向它的路徑。如果路徑的長度對解題很關鍵的話，當算法多次搜索到同一個狀態時，它應該保留最短路徑。 5.3.3 深度優先搜索策略33例 卒子穿陣問題，要求一卒子從頂部通過下圖所示的陣列到達底部。卒子行進中不可

13、進入到代表敵兵駐守的區域（標注1），并不準后退。假定深度限制值為5。 5.3.3 深度優先搜索策略 陣列圖 345.3.3 深度優先搜索策略open表：S17、S18closed表：S0S16 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(死死死死深度限制解 0S1S)1,1(2S)2,1(3S)2,2(4S)1,2(5S)1,3(6S)2,3(7S)3,2(8S)3,

14、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(死死死死深度限制解卒子穿陣的深度優先搜索樹35第5章 搜索求解策略5.1 搜索的概念5.2 狀態空間知識表示方法5.3 盲目的圖搜索策略5.4 啟發式圖搜索策略5.5 與/或圖搜索策略365.4 啟發式圖搜索策略5.4.1 啟發式策略5.4.2 啟發信息和估價函數5.4.3 A搜索算法5.4.4 A*搜索算法及其特性分析375.4.1 啟發式策略“啟發”（heuristic）：關于發現和發明操作算子及搜索方法的研究。在狀態空間搜索中，

15、啟發式被定義成一系列操作算子，并能從狀態空間中選擇最有希望到達問題解的路徑。啟發式策略：利用與問題有關的啟發信息進行搜索。385.4.1 啟發式策略運用啟發式策略的兩種基本情況： （1）一個問題由于在問題陳述和數據獲取方面固有 的模糊性，可能會使它沒有一個確定的解。 （2）雖然一個問題可能有確定解，但是其狀態空間 特別大，搜索中生成擴展的狀態數會隨著搜索 的深度呈指數級增長。39 例 一字棋。在九宮棋盤上，從空棋盤開始，雙方輪流在棋盤上擺各自的棋子 或 （每次一枚），誰先取得三子一線（一行、一列或一條對角線）的結果就取勝。 5.4.1 啟發式策略 和 能夠在棋盤中擺成的各種不同的棋局就是問題空

16、間中的不同狀態。 9個位置上擺放空， ， 有 39 種棋局。 可能的走法 ： 。405.4.1 啟發式策略 啟發式策略的運用415.4.1 啟發式策略啟發式搜索下縮減的狀態空間425.4.2 啟發信息和估價函數在具體求解中，能夠利用與該問題有關的信息來簡化搜索過程，稱此類信息為啟發信息。啟發式搜索：利用啟發信息的搜索過程。435.4.2 啟發信息和估價函數 求解問題中能利用的大多是非完備的啟發信息：（1）求解問題系統不可能知道與實際問題有關的全部信息，因而無法知道該問題的全部狀態空間，也不可能用一套算法來求解所有的問題。（2）有些問題在理論上雖然存在著求解算法，但是在工程實踐中，這些算法不是效

17、率太低，就是根本無法實現。一字棋：9！，西洋跳棋：1078，國際象棋：10120，圍棋：10761。假設每步可以搜索一個棋局，用極限并行速度（10-104年/步）來處理，搜索一遍國際象棋的全部棋局也得1016年即1億億年才可以算完！ 445.4.2 啟發信息和估價函數啟發信息的分類： （1）陳述性啟發信息 （2）過程性啟發信息 （3）控制性啟發信息利用控制性的啟發信息的情況： （1）沒有任何控制性知識作為搜索的依據，因而搜索的每一步完全是隨意的。 （2）有充分的控制知識作為依據，因而搜索的每一步選擇都是正確的，但這是不現實的。455.4.2 啟發信息和估價函數 估價函數的任務就是估計待搜索結點

18、的“有希望”程度，并依次給它們排定次序（在open表中）。 估價函數 ：從初始結點經過 結點到達目的 結點的路徑的最小代價估計值，其一般形式是 一般地，在 中， 的比重越大，越傾向于寬度優先搜索方式，而 的比重越大，表示啟發性能越強。46 例 八數碼的估價函數設計方法有多種，并且不同的估價函數對求解八數碼問題有不同的影響。 最簡單的估價函數：取一格局與目的格局相比，其位置不符的將牌數目。 較好的估價函數：各將牌移到目的位置所需移動的距離的總和。 第三種估價函數：對每一對逆轉將牌乘以一個倍數。 第四種估價函數：克服了僅計算將牌逆轉數目策略的局限，將位置不符將牌數目的總和與3倍將牌逆轉數目相加。

19、5.4.2 啟發信息和估價函數475.4.3 A搜索算法啟發式圖搜索法的基本特點：如何尋找并設計一個與問題有關的 及構出 ， 然后以 的大小來排列待擴展狀態的次序，每次選擇 值最小者進行擴展。 open表：保留所有已生成而未擴展的狀態。 closed表：記錄已擴展過的狀態。 進入open表的狀態是根據其估值的大小插入到表中合適的位置，每次從表中優先取出啟發估價函數值最小的狀態加以擴展。 48一般啟發式圖搜索算法（簡記為A）5.4.3 A搜索算法procedure heuristic_searchopen：=start；closed：= ；f(s)：=g(s)+h(s)；*初始化while op

20、en 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； 495.4.3 A搜索算法case子狀態is already on open表：if該子狀態是沿著一條比在open表已有的更短路徑而到達then 記錄更短路徑走向及其估價函數值；case子狀態is already on clo

21、sed表：if該子狀態是沿著一條比在closed表已有的更短路徑而到達thenbegin將該子狀態從closed表移到open表中；記錄更短路徑走向及其估價函數值；end；case end；將n放入closed表中；根據估價函數值，從小到大重新排列open表；end；*open表中結點已耗盡return(failure)；end.505.4.3 A搜索算法每次重復時，A搜索算法從open表中取出第一個狀態，如果該狀態滿足目的條件，則算法返回到該狀態的搜索路徑。如果open表的第一個狀態不是目的狀態，則算法利用與之相匹配的一系列操作算子進行相應的操作來產生它的子狀態。如果某個子狀態已在open表

22、（或closed表）中出現過，即該狀態再一次被發現時，則通過刷新它的祖先狀態的歷史記錄，使算法極有可能找到到達目的狀態的更短的路徑接著，A搜索算法open表中每個狀態的估價函數值，按照值的大小重新排序，將值最小的狀態放在表頭，使其第一個被擴展。 515.4.3 A搜索算法525.4.3 A搜索算法例 利用A搜索算法求解八數碼問題的搜索樹，其估價函數定義為 ：狀態的深度，每步為單位代價。 ：以“不在位”的將牌數作為啟發信息的度量。 ：為狀態 到目的狀態的最優路徑的代價。 ：A搜索算法 A*搜索算法。 535.4.3 A搜索算法54open表和closed表內狀態排列的變化情況 5.4.3 A搜索算法55如果某一問題有解，那么利用A*搜索算法對