1、第六章 搜索策略基本概念狀態空間的搜索策略 與/或樹的搜索策略搜索的完備性和效率8/21/20221福州大學陽光學院計算機系第六章 搜索策略基本概念狀態空間的搜索策略與/或樹的搜索策略搜索的完備性和效率8/21/20222福州大學陽光學院計算機系基本概念推理什么是推理：依據一定的規則（策略）從已知的事實推出新事實（結論）的過程稱為推理。8/21/20223福州大學陽光學院計算機系基本概念推理推理方式及其分類 p.112 演繹推理、歸納推理、默認推理 確定推理、不確定推理 單調推理、非單調推理 啟發式推理、非啟發式推理 8/21/20224福州大學陽光學院計算機系基本概念 - 搜索什么叫搜索：根

2、據問題的實際情況不斷尋找可用的知識，從而構造一條代價較小的推理線路，使問題得到解的過程稱為搜索。盲目搜索：按預定的控制策略進行搜索，在搜索過程中獲得的中間信息不用來改進控制策略。啟發式搜索：在搜索過程中加入了與問題有關的啟發性信息，用以指導搜索朝最有利的方向前進，加速求解過程并得到最優解。8/21/20225福州大學陽光學院計算機系基本概念 - 狀態空間表示法狀態：描述某一類事物中各不同事物之間的差異而引入的一組變量或多維數組。 Sk=(Sk0,Sk1,Skn)算符(算子) ：引起狀態中某些分量發生變化，從而使問題從一個狀態改變到另一個狀態的操作，以F指示。狀態空間：以SP指示，表示問題的全部

3、可能的狀態及其相互關系，狀態和算符的集合。一般用三元式表示： SP = ( S0 , F , Sg )8/21/20226福州大學陽光學院計算機系基本概念 - 狀態空間表示法狀態空間以SP指示，也可表示為一個二元組： SP = （S, F）S-在問題求解（即搜索）過程中所有可達的合法狀態構成的集合；F-操作算子的集合，操作算子的執行導致狀態的變遷。 所以，狀態空間又可描述為一個有向圖，其節點指示狀態，節點間的有向弧表示狀態變遷，弧上的標簽則指示導致狀態變遷的操作算子。狀態可通過定義某種數據結構來描述，用于記載問題求解（即搜索）過程中某一時刻問題現狀的快照。 8/21/20227福州大學陽光學院

4、計算機系狀態空間表示法舉例：八數碼游戲 問題：一個33棋盤，有八張牌1，2， 8及一個空格，空格周圍的牌可以向空格移動。 求解：給定一個初始狀態S0 、一個目標狀態Sg ，求從S0到Sg的走步序列。S0狀態 Sg狀態8/21/20228福州大學陽光學院計算機系狀態空間表示法舉例：八數碼游戲解： 綜合數據庫（狀態及狀態空間描述） 定義：矩陣（Sij）表示任何狀態，其中： Sij0,1, 8 1i,j3 Sij 互不相同 狀態空間：9！=362,880 種狀態8/21/20229福州大學陽光學院計算機系狀態空間表示法舉例：八數碼游戲 規則集（算符F）設：空格移動代替數碼移動。至多有四種移動的可能：

5、上、下、左、右。定義： Sij為矩陣第i行j列的數碼; 其中：i0,j0表示空格所在的位置，則Si0j0=0 （0代表空格）空格左移規則： if j0-11 then j0j0-1; Si0j00解釋：如果當前空格不在第一列，則空格左移一位，新的空格位置賦值為0。同理：右移規則：if j0+13 then j0j0+1; Si0j00 上移規則：if i0-11 then i0i0-1; Si0j00 下移規則：if i0+13 then i0i0+1; Si0j008/21/202210福州大學陽光學院計算機系狀態空間表示法舉例：八數碼游戲 控制策略需要解決的問題： 在當前可用的規則中如何選

6、擇其中之一來實現狀態的轉換 實時判斷是否到達目標狀態8/21/202211福州大學陽光學院計算機系狀態空間表示法舉例：傳教士和野人問題傳教士和野人問題 設N個傳教士帶領N個野人劃船渡河，且為安全起見，渡河需遵從二個約束： 1）船上人數不得超過載重限量，設為K個人； 2）為預防野人攻擊，任何時刻（包括兩岸、船上）野人數目不得超過傳教士。 8/21/202212福州大學陽光學院計算機系狀態空間表示法舉例：傳教士和野人問題 為便于理解狀態空間表示方法，我們簡化該問題到一個特例：N=3，K=2；并以變量m和c分別指示傳教士和野人在左岸或船上的實際人數，變量b指示船是否在左岸（值1指示船在左岸，否則為0

7、）。從而上述約束條件轉變為m + c = c。 考慮到在這個渡河問題中，左岸的狀態描述（m、c和b）可以決定右岸的狀態，所以整個問題狀態就可以左岸的狀態來描述，以簡化問題的表示。 8/21/202213福州大學陽光學院計算機系狀態空間表示法舉例：傳教士和野人問題 設初始狀態下傳教士、野人和船都在左岸，目標狀態下這三者均在右岸，問題狀態以三元組（m,c,b）表示，則問題求解任務可描述為： (3，3，1） （0，0，0） 在這個簡單問題中，狀態空間可能的狀態總數為442 = 32 ，但由于要遵守安全約束，只有20個狀態是合法的。下面是幾個不合法狀態的例子： (1，0，1）， （1，2，1）， （2

8、，3，1） 鑒于存在不合法狀態，還會導致某些合法狀態不可達，例如狀態（0，0，1），（0，3，0）。結果，這個問題總共只有16個可達的合法狀態。8/21/202214福州大學陽光學院計算機系狀態空間表示法舉例：傳教士和野人問題 渡河問題中的操作算子可以定義2類：L(m,c)、R(m,c)，分別指示從左岸到右岸的劃船操作和從右岸回到左岸的劃船操作。由于m和c取值的可能組合只有5個：10，20，11，01，02，故而總共有10個操作算子。 渡河問題狀態空間的有向圖8/21/202215福州大學陽光學院計算機系狀態空間表示法舉例：傳教士和野人問題8/21/202216福州大學陽光學院計算機系基本概念

9、 - 與/或樹表示法與/或樹又稱問題歸約。問題歸約是人們求解問題常用的策略，就是把復雜的問題變換為若干需要同時處理的較為簡單的子問題后再加以分別求解。只有當這些子問題全部解決時，問題才算解決，問題的解答就由子問題的解答聯合構成。8/21/202217福州大學陽光學院計算機系基本概念 - 與/或樹表示法與/或圖：應用問題歸約策略得到的狀態空間圖。與節點：用圓弧將幾條節點間關聯弧連接在一起去指示問題分解為若干子問題，只有這些子問題全部解決才會導致問題的解決。 或節點：問題（子問題）也可能激活多條重寫規則（等價變換）；顯然，只要有一條激活的重寫規則能導致最終的解答成功即可。 8/21/202218福

10、州大學陽光學院計算機系基本概念 - 與/或樹表示法本原問題：不可或不需再通過變換，可以直接得到問題的解的子問題。 端節點與終止節點：沒有子節點的節點稱為端節點（葉節點）。本原問題對應的節點稱為終止節點。8/21/202219福州大學陽光學院計算機系基本概念 - 與/或樹表示法可解節點： 終止節點是可解節點。 如果非終止節點有“或”子節點，當且僅當其子節點至少有一個能解，則該非終止節點是可解節點。 如果非終止節點有“與”子節點，當且僅當其子節點都能解，則該非終止節點是可解節點。8/21/202220福州大學陽光學院計算機系基本概念 - 與/或樹表示法不可解節點： 沒有后裔的非終止節點是不可解節點

11、（該節點是葉節點但不是本原問題）。 如果非終止節點有“或”子節點，當且僅當所有子節點都不能解，則該非終止節是不可解節點。 如果非終止節點有“與”子節點，至少有一個子節點不能解，則該非終止節點是不可解節點。解樹：由可解節點構成，并且由這些可解節點可推出初始節點為可解節點的子樹。8/21/202221福州大學陽光學院計算機系與/或樹表示法舉例：梵塔問題（1 1 1） （3 3 3） （1 2 2） （3 2 2） （3 2 2） （3 3 3） （1 1 1） （1 2 2） （1 1 1） （1 1 3） （3 2 2） （3 2 1） （3 2 1） （3 3 1） （3 3 1） （3 3

12、3） （1 2 3） （1 2 2） （1 1 3） （1 2 3） ( c b a )P.261 圖6-78/21/202222福州大學陽光學院計算機系與/或樹表示法舉例：符號積分問題符號積分是求不定積分原函數的問題，通過應用各種代數和三角變換以及不定積分性質（如函數和積分、分部積分等）可以把復雜的積分問題逐步歸約為若干個本原積分問題（可利用積分表直接求出原函數）。六十年代開發的SAINT系統。就是一個應用問題歸約的符號積分系統。 8/21/202223福州大學陽光學院計算機系第六章 搜索策略基本概念狀態空間的搜索策略與/或樹的搜索策略搜索的完備性和效率8/21/202224福州大學陽光學院

13、計算機系第六章 搜索策略基本概念狀態空間的搜索策略與/或樹的搜索策略搜索的完備性和效率8/21/202225福州大學陽光學院計算機系狀態空間的搜索策略狀態空間的搜索以SE指示，可表示為一個五元組：SE = (S,F,E,S0,Sg)E -搜索引擎；S0 -問題的初始狀態， S0 S;Sg -問題的目標狀態集， Sg S。 狀態空間搜索的基本思想就是通過搜索引擎尋找一個操作算子的調用序列，使問題從初始狀態變遷到目標狀態之一，而變遷過程中的狀態序列或相應的操作算子調用序列稱為從初始狀態到目標狀態的 解答路徑。搜索引擎可以設計為任意實現搜索算法的控制系統。 8/21/202226福州大學陽光學院計算

14、機系狀態空間的搜索策略通常，狀態空間的解答路徑有多條，但最短的只有1條或少數幾條。上述渡河問題就有無數條解答路徑（因為劃船操作可逆），但只有4條是最短的，都包含11個操作算子的調用。由于一個狀態可以有多個可供選擇的操作算子，導致了多個待搜索的解答路徑。除了少數像渡河這樣的簡單問題外，描述狀態空間的一般圖都很大，無法直觀地畫出，只能將其視為隱含圖，在搜索解答路徑的過程中只畫出搜索時直接涉及到的節點和弧線，構成所謂的 搜索圖。 8/21/202227福州大學陽光學院計算機系狀態空間的搜索策略八數碼問題的搜索圖。對于八數碼游戲，可能的棋盤布局（問題狀態）總共9!=362880個，由于棋盤的對稱性，實

15、際只有這個總數的一半。顯然，我們無法直觀地畫出整個狀態空間的一般圖，但搜索圖則小得多，可以圖示。狀態空間、搜索圖和解答路徑之間的關系 8/21/202228福州大學陽光學院計算機系狀態空間的搜索策略盡管狀態空間可以很大（例如國際象棋），但只要確保搜索空間足夠小，就能在合理的時間范圍內搜索到問題解答。搜索空間的壓縮程度主要取決于搜索引擎采用的搜索算法。換言之，當問題有解時，使用不同的搜索策略，找到解答路徑時，搜索圖的大小是有區別的。 8/21/202229福州大學陽光學院計算機系狀態空間的一般搜索過程一般圖搜索算法為建立該算法，令： s -指示初始狀態節點；G -指示搜索圖；OPEN -作為存放

16、待擴展節點的表；CLOSE -作為存放已被擴展節點的表；MOVE-FIRST(OPEN) -指示取OPEN表首的節點作為當前要被擴展的節點n，同時將節點n移至CLOSE表；SNS -子節點集合； 8/21/202230福州大學陽光學院計算機系狀態空間的一般搜索過程該算法的一般過程如下：1） G := s； / 即算法開始時搜索圖只包括初始狀態節點； OPEN := (s), CLOSE := ()； / 即此時僅有作為待擴展節點，而CLOSE表為空； 2）若OPEN是空表，則算法以失敗結束； / 因為此時未搜索到解答（目標狀態），又無法繼續搜索； 3） n := MOVE-FIRST(OPEN

17、)； 4）若n是目標狀態節點，則搜索成功結束，并給出解答路徑； 5）擴展節點n，將非節點n祖先的子節點置于子節點集合SNS中，并插入搜索圖G中； 8/21/202231福州大學陽光學院計算機系狀態空間的一般搜索過程 6） 標記和修改指針： 把SNS中的子節點分為三類：（1）全新節點，（2）已出現于OPEN表的節點，（3）已出現于CLOSE表的節點； / 后二類子節點實際上意味著具有新老二個父節點； 加第1類子節點于OPEN表，并建立從子節點到父節點n的指針； 比較第2類子節點經由新、老父節點到達初始狀態節點s的路徑代價，若經由新父節點的代價較小， 則移動子節點指向老父節點的指針，改為指向新父節

18、點n； 對于第3類子節點作與第2類同樣的處理，并把這些子節點從CLOSE表中移出，重新加入OPEN表；7） 按某種原則重新排序OPEN表中的節點；8） 返回語句2）； 8/21/202232福州大學陽光學院計算機系狀態空間的一般搜索過程8/21/202233福州大學陽光學院計算機系狀態空間的一般搜索過程討論：1 OPEN中的節點是尚未擴充的節點2 CLOSED的節點是已經擴充過的節點 3 G中的每個節點都唯一地指向一個父節點4 mi mj mk ml其中： mi是當前被擴充的全部節點 mj是新擴充的節點 mk是已經在OPEN中的節點 ml是已經在CLOSED中的節點5 n是當前被選中的節點，它

19、是OPEN表中排列在最前面的一個節點。6 該算法對于連通圖及樹都適用。8/21/202234福州大學陽光學院計算機系狀態空間的一般搜索過程例：n=1S23456當前節點ml節點表示圖本身的連接關系搜索路徑8/21/202235福州大學陽光學院計算機系狀態空間的一般搜索過程討論： 空心節點是已經在OPEN中的節點，如：1，4，5 實心節點是已經在CLOSED中的節點，如：S，2，3 擴充節點2后，對其原來搜索路徑進行修改，由原來指向節點3改為指向節點1 對后繼節點4的搜索路徑進行修改，由原來指向節點6改為指向節點28/21/202236福州大學陽光學院計算機系狀態空間的一般搜索過程修改后的搜索圖

20、如下：n=1S234568/21/202237福州大學陽光學院計算機系狀態空間的一般搜索過程下面給出兩種對OPEN表中節點按照某種規則排列的算法： 深度優先算法 寬度優先算法8/21/202238福州大學陽光學院計算機系狀態空間的一般搜索過程一般圖搜索算法中，提高搜索效率的關鍵在于優化OPEN表中節點的排序方式，若每次排在表首的節點都在最終搜索到的解答路徑上，則算法不會擴展任何多余的節點就可快速結束搜索。所以排序方式成為研究搜索算法的焦點，并由此形成了多種搜索策略。一種簡單的排序策略就是按預先確定的順序或隨機地排序新加入到OPEN表中的節點，常用的方式是深度優先和寬度優先。 8/21/2022

21、39福州大學陽光學院計算機系狀態空間的一般搜索過程8/21/202240福州大學陽光學院計算機系廣（寬）度優先搜索 寬度優先-擴展當前節點后生成的子節點總是置于OPEN表的后端（未部），即OPEN表作為排隊表使用，先進先出，使搜索優先向橫廣方向發展。 先進先出排序策略使寬度優先法能確保搜索到最短的解答路徑。8/21/202241福州大學陽光學院計算機系深度優先搜索 深度優先-擴展當前節點后生成的子節點總是置于OPEN表的前端（首部），即OPEN表作為棧表使用，后進先出，使搜索優先向縱深方向發展。 當一個問題有多個解答或多條解答路徑，且只須找到其中一個時，深度優先法十分適用。例如8數碼游戲，若不

22、限定從初始布局轉變到目標布局所需移動的棋牌個數（即移動步數），則存在多條解答路徑，應用深度優先法可隨機地找到其中一條。8/21/202242福州大學陽光學院計算機系深度優先搜索 不過有些問題的狀態空間搜索或許會無限延伸，而又存在較短的解答路徑，則可以對搜索深度加以限制，以求提高搜索效率并確保尋找到較短的解答路徑。 有界深度優先如果當前節點的深度不超過限定的界限，則擴展當前節點后生成的子節點總是置于OPEN表的前端（首部） ，后進先出，使搜索優先向縱深方向發展。 8/21/202243福州大學陽光學院計算機系狀態空間搜索上述二種搜索方法可直接應用一般圖搜索算法實現，且只要問題有解就一定能搜索到解

23、答。由于不需要設計特別的節點排序方法，從而簡單易行，適合于許多復雜度不高的問題求解任務。 這兩種搜索方法的共同缺點是節點排序的盲目性，由于不采用領域專門知識去指導排序，往往會在白白搜索了大量無關的狀態節點后才碰到解答，所以也稱為盲目搜索。8/21/202244福州大學陽光學院計算機系狀態空間搜索 只要引入與應用領域相關的啟發式知識來指導OPEN表中節點的排序，使最有希望出現在較短解答路徑上的節點優先考察，就能顯著提高搜索的有效性。用啟發式知識指導排序可劃分為二種方式: 局部排序-這是對上述深度優先法的改進，僅對新擴展出來的子節點排序，使這些節點中最有希望者能優先取出考察和擴展。如：代價樹深度優

24、先。 全局排序-對OPEN表中的所有節點排序，使最有希望的節點排在表首。如：代價樹廣度優先。 8/21/202245福州大學陽光學院計算機系代價樹的廣度優先搜索代價樹廣度優先-對OPEN表中的所有節點按代價大小排序，使最有希望的節點排在表首。是一種全局排序方法。代價樹：邊上標有代價（費用）的樹。代價：若用g(x)表示從初始節點S0到節點x的代價，用 c(x1,x2)表示從父節點x1到子節點x2的代價，則有： g(x2) = g(x1) + c(x1,x2)最有希望的節點：代價最小的節點。8/21/202246福州大學陽光學院計算機系代價樹的廣度優先搜索例：巡回推銷員問題，從A出發并返回。 A

25、(75 )E (100)B (100)D (125)C(125 ) B (125 ) C (75 ) D (75 ) B (100 ) C (5 0) C (125 ) AABCDE75100125125757510050125100A-E-D-B-C-A : 3758/21/202247福州大學陽光學院計算機系代價樹的深度優先搜索代價樹深度優先-這是對上述深度優先法的改進，僅對新擴展出來的子節點按代價大小排序，使這些節點中最有希望者能優先取出考察和擴展。是一種局部排序方法。8/21/202248福州大學陽光學院計算機系啟發式搜索搜索是一種試探性的查尋過程，引入啟發式知識可以減少搜索的盲目性，

26、增加試探的準確性，為此就稱應用啟發式知識的搜索是啟發式搜索。 啟發式知識對于搜索的指導作用可歸納為三方面： 選擇下一個要被擴展的節點，排序OPEN表中的待擴展節點是一種常用的方法。在擴展一個節點時，僅僅有選擇性地生成部分有用的節點，而非所有可能的子節點。修剪掉某些估計不可能導致成功的子節點。 本節只討論如何應用第一方面的啟發式知識于一般圖搜索。8/21/202249福州大學陽光學院計算機系啟發式搜索啟發式信息用于解決OPEN表中節點的排列次序問題，方法是利用一個評(估)價函數計算OPEN表中節點的評價函數值，按照函數值從大到小（或從小到大）排列所有節點。 一種有效的方法就是設計體現啟發式知識的

27、所謂評價函數來計算每個節點的得分，以便用于排列它們在OPEN表中的位置。 應用這種評價函數來實現啟發式搜索的典型是算法A，其將評價函數f設計為：8/21/202250福州大學陽光學院計算機系啟發式搜索 -算法A算法A，其將評價函數f設計為： f(n) = g(n) + h(n) n-搜索圖中的某個當前被擴展的節點； f(n)-從初始狀態節點s0, 經由節點n到達目標狀節點sg，估計的最小路徑代價； g(n)-從s0到n ,估計的最小路徑代價； h(n)-從n到sg,估計的最小路徑代價； 通常我們可以用至今已發現的自s0到n的最短路徑作為g(n)值，但h(n)則要依賴于啟發式知識來加以估算，故h

28、(n)稱為啟發式函數。8/21/202251福州大學陽光學院計算機系啟發式搜索 -算法A算法A的設計與前述一般圖算法類同，主要的不同是在算法第（5）步中增加了子節點函數f的計算，在第（6）步中依賴于f值確定子節點指向父節點指針的修改，并在第（7）步中按f值從小到大排序OPEN表中的節點。算法A第（5）和第（6）步的修改如下：8/21/202252福州大學陽光學院計算機系啟發式搜索 -算法A(5) 擴展節點n,將非節點n祖先的子節點置于子節點集合SNS中， 并插入搜索圖G中，對于SNS中每個子節點ni,計算f(n,ni) = g(n,ni) + h(ni);(6) 標記和修改指針把SNS中的子節

29、點分為三類（同一般圖搜索算法）；加第1類子節點于OPEN表（同一般圖搜索算法）；比較第2類子節點ni經由新、老父節點的評價函數值f(n,ni)、f(ni);若f(n,ni) 8/21/202263福州大學陽光學院計算機系啟發式搜索 - A*算法性質1.算法可采納性： 給定任意圖，設存在從初始節點s到目標節點t的路徑。如果算法能夠結束在從s到t的最佳解路徑上，則稱該算法是可采納的。 A*算法是可納的，即它能在有限步內終止并找到最優解。（證明略）8/21/202264福州大學陽光學院計算機系啟發式搜索 - A*算法性質 對于八數碼游戲，從當前被擴展節點n到目標狀態節點的最短路徑-棋牌移動的最少次數

30、必定不少于錯位棋牌的個數w(n) （因為有些棋牌可能需移動多于一次才能到達目標狀態的相應位置）， 即w(n) h*(n) 也必定不會少于錯位棋牌不受阻擋情況下移動到目標狀態相應位置的移動次數總和p(n) （因為有些棋牌的移動可能受阻擋），即p(n) h*(n) 從而采用w(n)和p(n)作為評價函數時，算法A都是可納的。 8/21/202265福州大學陽光學院計算機系啟發式搜索 - A*算法性質思考1: 傳教士和野人問題(m,c,b) 1) h(n)=0； 2) h(n)=m+c 3) h(n)=m+c-2b哪個是A*算法？思考2: 只有A*算法才能找到最優解？ 對于八數碼游戲，令h(n)=

31、p(n) + 3 s(n) ,其中s(n)為所有棋子得分總和，計算方法：中心方格棋子得1分，非中心方格棋子后繼棋子與目標順序不同得2分，否則0分。8/21/202266福州大學陽光學院計算機系啟發式搜索 - A*算法性質2.算法最優性： （啟發式函數的強弱及其影響 ） 用h(n)接近h* (n)的程度去衡量啟發式函數的強弱。當h(n) h* (n)且兩者差距較大時，h(n)過弱，從而導致OPEN表中節點排序的誤差較大，易于產生較大的搜索圖；反之，當h(n) h* (n),則h(n)過強，使算法A失去可采納性，從而不能確保找到最短解答路徑。 設計接近、又總是 h* (n)的h(n)成為應用A*算

32、法搜索問題解答的關鍵，以壓縮搜索圖，提高搜索效率。 8/21/202267福州大學陽光學院計算機系啟發式搜索 - A*算法性質算法最優性： （啟發式函數的強弱及其影響 ）定理： 給定兩個A*算法A1、A2，如果A2的啟發信息比A1多，則在任何存在從節點s到目標節點t 路徑的圖上，搜索結束時由A2擴充的每一個節點必定被A1擴充。（ A1擴充的節點數至少與A2 擴充的節點數一樣多)。 （證明略）8/21/202268福州大學陽光學院計算機系啟發式搜索 - A*算法性質算法最優性： （啟發式函數的強弱及其影響 ） 可以證明，對于解決同一問題的兩個算法A1和A2，若有h1(n) h2(n) h* (n

33、)，則t(A1) t(A2) 其中，h1、h2分別是算法A1、A2 的啟發式函數，t指示相應算法達到目標狀態時搜索圖含的節點總數。 8/21/202269福州大學陽光學院計算機系啟發式搜索 - A*算法性質算法最優性： （啟發式函數的強弱及其影響 ）再以八數碼游戲為例，正因為w(n) p(n) h* (n),所以采用p(n)擴展出的節點總數不會比采用w(n)時多。更明顯的例子是采用寬度優先法解決八數碼問題，其相當于h(n)0，則搜索樹會變得比采用w(n)時龐大得多。 8/21/202270福州大學陽光學院計算機系啟發式搜索 - A*算法性質算法最優性： （啟發式函數的強弱及其影響 ） 三種算法

34、的搜索代價,其中IDS為寬度搜索,h1采用的啟發式函數為w(n), h2采用的啟發式函數為p(n),d為解的長度.隨機產生1200個八數碼問題統計: d=12 IDS = 3,644,035 nodes A*(h1) = 227 nodes A*(h2) = 73 nodes d=24 IDS = too many nodes A*(h1) = 39,135 nodes A*(h2) = 1,641 nodes8/21/202271福州大學陽光學院計算機系啟發式搜索 - A*算法性質3.h(x)的單調性限制：單調性定義：給定一個啟發函數h，如果對于所有節點ni 、 nj （ nj是ni的子節點

35、）滿足 h(ni) h(nj) c(ni, nj) 且 h(t) 0 ，則稱h 滿足單調性限制。上式可以寫成 h(ni) c(ni, nj) h(nj) 可以理解為三角形邊長和不等式。 單調性限制的作用是：避免重復計算某些節點的f值（主要針對連通圖而言）以便減少搜索代價。tninjh(ni)h(nj)c(ni, nj)8/21/202272福州大學陽光學院計算機系啟發式搜索 - A*算法性質h(x)的單調性限制：結論1 如果h(n)滿足單調性限制條件，則A*算法擴充了節點n之后，就已經找到了到達節點n的最佳路徑，即：如果A*選中節點n，在單調性限制條件下，有 g(n) g*(n) 結論2 如果

36、h 滿足單調性限制，則由A*擴充的節點序列的f 值是非遞減的。8/21/202273福州大學陽光學院計算機系第六章 搜索策略基本概念狀態空間的搜索策略與/或樹的搜索策略搜索的完備性和效率8/21/202274福州大學陽光學院計算機系第六章 搜索策略基本概念狀態空間的搜索策略與/或樹的搜索策略搜索的完備性和效率8/21/202275福州大學陽光學院計算機系與/或樹的一般搜索過程 可以把 與/或圖（樹）視為對一般圖的擴展；或反之，把一般圖視為與/或圖的特例，即一般圖不允許節點間具有“與”關系，所以又可把一般圖稱為或圖。與一般圖類似，與/或圖也有根節點，用于指示初始狀態。由于同父子節點間可以存在“與

37、”關系，父、子節點間不能簡單地以弧線關聯，需要引入超連接概念。同樣原因，在典型的與/或圖中，解答路徑往往不復存在，代之以廣義的解路徑-解圖。 8/21/202276福州大學陽光學院計算機系與/或樹的一般搜索過程8/21/202277福州大學陽光學院計算機系與/或樹的一般搜索過程 解圖的生成-自根節點開始選一外向連接，并從該連接指向的每個子節點出發，再選一外向連接，如此反復進行，直到所有外向連接都指向終節點為止。 解圖是遵從問題歸約策略而搜索到的，解圖中不存在節點或節點組之間的“或”關系；換言之，解圖純粹是一種“與”圖。另外，正因為與或圖中存在“或”關系，所以往往會搜索到多個解圖，本例中就有4個

38、。 8/21/202278福州大學陽光學院計算機系與/或樹的一般搜索過程8/21/202279福州大學陽光學院計算機系與/或樹的一般搜索過程初始節點S0對應原始問題的描述。用可適用的分解或等價變換算符求得S0的后繼節點集合。從每個后裔設置指向父輩節點的指針（用于標示可解或不可解，并指出一個到終葉節點的解圖），刪去沒有意義的節點。繼續擴展節點和設置指針的過程，直至S0被標示為可解或不可解為止。 8/21/202280福州大學陽光學院計算機系與/或樹的廣度優先搜索基本思想：把新生成的子節點放入OPEN表的尾部。算法：1）把初始節點S0放入OPEN表。2）把OPEN表中首節點（記為n）取出放入CLO

39、SE表。3）如果節點n可擴展，則 i)擴展n，將其子節點配置指針，放入OPEN表尾部。 ii)這些子節點是否有終止節點，若是，應用可解標示過程。若S0被標示可解，則得到解樹搜索成功；否則從OPEN表中刪除具有可解先輩的節點。 iii)轉2）8/21/202281福州大學陽光學院計算機系與/或樹的廣度優先搜索算法： （續）4）如果節點n不可擴展，則 i)應用不可解標示過程。若S0被標示為不可解，則搜索失敗；否則從OPEN表中刪除具有不可解先輩的節點。 ii)轉2）流程圖： P.281舉例：8/21/202282福州大學陽光學院計算機系與/或樹的深度優先搜索基本思想：把新生成的子節點放入OPEN表

40、的首部。算法： P.282 （與廣度優先類似）流程圖：舉例：8/21/202283福州大學陽光學院計算機系與/或樹的有序搜索基本思想：考慮付出的代價，選擇擴展節點時，先走幾步，選擇代價最小的節點進行擴展。解樹的代價：從起始節點為根的最優解樹的代價，記為h*(s)。任一節點x為根的解樹的最小代價h(x)定義：1）若x為終止節點，則h(x)=0；2）若x為或節點，則h(x)=minc(x,yi)+h(yi)3）若x為與節點，則h(x)= maxc(x,yi)+h(yi)或h(x)= c(x,yi)+h(yi)8/21/202284福州大學陽光學院計算機系8/21/202285福州大學陽光學院計算機

41、系與/或樹的有序搜索-希望樹希望樹：可能構成最優解樹的一部分的樹。希望樹T的定義：1）初始節點S0在T中。2）如果節點x在T中，則一定有 i）x是一個或節點，則具有minc(x,yi)+h(yi)值的那個子節點yl也應該在T中。 ii）x是一個與節點，則它的所有子節點都應該在T中。8/21/202286福州大學陽光學院計算機系與/或樹的有序搜索_希望樹算法：1）把初始節點S0放入OPEN表。2）根據當前搜索樹中節點的代價h，求希望樹T。3）把OPEN表中T的端節點（記為n）取出放入CLOSE表。4）如果節點n為可解節點，則應用可解標示過程。若S0被標示可解，則得到最優解樹T，搜索成功；否則從O

42、PEN表中刪除具有可解先輩的所有節點。 8/21/202287福州大學陽光學院計算機系與/或樹的有序搜索_希望樹算法： （續）5）如果節點n為不可解節點，則應用不可解標示過程。若S0被標示為不可解，則搜索失敗退出；否則從OPEN表中刪除具有不可解先輩的所有節點。6）如果節點n可擴展，則 i)擴展n，將其子節點配置指針，放入OPEN表。 ii)計算這些子節點的h值及其先輩節點的h值。7） 轉第2）步。流程圖：P.2868/21/202288福州大學陽光學院計算機系與/或樹的有序搜索舉例： 假定在搜索過程中擴展出來的某些節點的啟發式函數h(ni)的估算如下：h(n0)=3, h(n1)=2, h(

43、n2)=1, h(n3)=1, h(n4)=4,h(n5)=2, h(n6)=2, h(n7)=1, h(n8)=1，h(n13)=3。 8/21/202289福州大學陽光學院計算機系與/或樹的有序搜索h(n0)=3, h(n1)=2, h(n2)=1, h(n3)=1, h(n4)=4,h(n5)=2, h(n6)=2, h(n7)=1, h(n8)=1,h(n13)=3。8/21/202290福州大學陽光學院計算機系博弈樹的啟發式搜索概念：MINMINMAXMAXMAX8/21/202291福州大學陽光學院計算機系博弈樹的啟發式搜索概念：MINMINMINMAXMAXMAX8/21/202292福州大學陽光學院計算機系博弈樹的啟發式搜索概念（博奕樹特點）：1）初始格局為初始節點S0。2）或節點和與節點逐層交替出現。3）己方獲勝格局為可解節點，對方獲勝為不可解節點。 可以用類似于求解與/或樹搜索技術來處理許多簡單博弈以及若干復雜的博弈殘局。8/21/202293福州大學陽光學院計算機系博弈樹的啟發式搜索極大極小分析法 基本思想：