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

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

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

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

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

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

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

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

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

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

11、（該節(jié)點是葉節(jié)點但不是本原問題）。 如果非終止節(jié)點有“或”子節(jié)點，當(dāng)且僅當(dāng)所有子節(jié)點都不能解，則該非終止節(jié)是不可解節(jié)點。 如果非終止節(jié)點有“與”子節(jié)點，至少有一個子節(jié)點不能解，則該非終止節(jié)點是不可解節(jié)點。解樹：由可解節(jié)點構(gòu)成，并且由這些可解節(jié)點可推出初始節(jié)點為可解節(jié)點的子樹。8/21/202221福州大學(xué)陽光學(xué)院計算機系與/或樹表示法舉例：梵塔問題（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福州大學(xué)陽光學(xué)院計算機系與/或樹表示法舉例：符號積分問題符號積分是求不定積分原函數(shù)的問題，通過應(yīng)用各種代數(shù)和三角變換以及不定積分性質(zhì)（如函數(shù)和積分、分部積分等）可以把復(fù)雜的積分問題逐步歸約為若干個本原積分問題（可利用積分表直接求出原函數(shù)）。六十年代開發(fā)的SAINT系統(tǒng)。就是一個應(yīng)用問題歸約的符號積分系統(tǒng)。 8/21/202223福州大學(xué)陽光學(xué)院計算機系第六章 搜索策略基本概念狀態(tài)空間的搜索策略與/或樹的搜索策略搜索的完備性和效率8/21/202224福州大學(xué)陽光學(xué)院

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

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

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

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

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

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

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

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

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

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

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

24、先。 全局排序-對OPEN表中的所有節(jié)點排序，使最有希望的節(jié)點排在表首。如：代價樹廣度優(yōu)先。 8/21/202245福州大學(xué)陽光學(xué)院計算機系代價樹的廣度優(yōu)先搜索代價樹廣度優(yōu)先-對OPEN表中的所有節(jié)點按代價大小排序，使最有希望的節(jié)點排在表首。是一種全局排序方法。代價樹：邊上標(biāo)有代價（費用）的樹。代價：若用g(x)表示從初始節(jié)點S0到節(jié)點x的代價，用 c(x1,x2)表示從父節(jié)點x1到子節(jié)點x2的代價，則有： g(x2) = g(x1) + c(x1,x2)最有希望的節(jié)點：代價最小的節(jié)點。8/21/202246福州大學(xué)陽光學(xué)院計算機系代價樹的廣度優(yōu)先搜索例：巡回推銷員問題，從A出發(fā)并返回。 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福州大學(xué)陽光學(xué)院計算機系代價樹的深度優(yōu)先搜索代價樹深度優(yōu)先-這是對上述深度優(yōu)先法的改進，僅對新擴展出來的子節(jié)點按代價大小排序，使這些節(jié)點中最有希望者能優(yōu)先取出考察和擴展。是一種局部排序方法。8/21/202248福州大學(xué)陽光學(xué)院計算機系啟發(fā)式搜索搜索是一種試探性的查尋過程，引入啟發(fā)式知識可以減少搜索的盲目性，

26、增加試探的準(zhǔn)確性，為此就稱應(yīng)用啟發(fā)式知識的搜索是啟發(fā)式搜索。 啟發(fā)式知識對于搜索的指導(dǎo)作用可歸納為三方面： 選擇下一個要被擴展的節(jié)點，排序OPEN表中的待擴展節(jié)點是一種常用的方法。在擴展一個節(jié)點時，僅僅有選擇性地生成部分有用的節(jié)點，而非所有可能的子節(jié)點。修剪掉某些估計不可能導(dǎo)致成功的子節(jié)點。 本節(jié)只討論如何應(yīng)用第一方面的啟發(fā)式知識于一般圖搜索。8/21/202249福州大學(xué)陽光學(xué)院計算機系啟發(fā)式搜索啟發(fā)式信息用于解決OPEN表中節(jié)點的排列次序問題，方法是利用一個評(估)價函數(shù)計算OPEN表中節(jié)點的評價函數(shù)值，按照函數(shù)值從大到?。ɑ驈男〉酱螅┡帕兴泄?jié)點。 一種有效的方法就是設(shè)計體現(xiàn)啟發(fā)式知識的

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

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

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

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

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

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

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

34、的搜索代價,其中IDS為寬度搜索,h1采用的啟發(fā)式函數(shù)為w(n), h2采用的啟發(fā)式函數(shù)為p(n),d為解的長度.隨機產(chǎn)生1200個八數(shù)碼問題統(tǒng)計: 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福州大學(xué)陽光學(xué)院計算機系啟發(fā)式搜索 - A*算法性質(zhì)3.h(x)的單調(diào)性限制：單調(diào)性定義：給定一個啟發(fā)函數(shù)h，如果對于所有節(jié)點ni 、 nj （ nj是ni的子節(jié)點

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

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

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

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

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

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

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

42、PEN表中刪除具有可解先輩的所有節(jié)點。 8/21/202287福州大學(xué)陽光學(xué)院計算機系與/或樹的有序搜索_希望樹算法： （續(xù)）5）如果節(jié)點n為不可解節(jié)點，則應(yīng)用不可解標(biāo)示過程。若S0被標(biāo)示為不可解，則搜索失敗退出；否則從OPEN表中刪除具有不可解先輩的所有節(jié)點。6）如果節(jié)點n可擴展，則 i)擴展n，將其子節(jié)點配置指針，放入OPEN表。 ii)計算這些子節(jié)點的h值及其先輩節(jié)點的h值。7） 轉(zhuǎn)第2）步。流程圖：P.2868/21/202288福州大學(xué)陽光學(xué)院計算機系與/或樹的有序搜索舉例： 假定在搜索過程中擴展出來的某些節(jié)點的啟發(fā)式函數(shù)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福州大學(xué)陽光學(xué)院計算機系與/或樹的有序搜索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福州大學(xué)陽光學(xué)院計算機系博弈樹的啟發(fā)式搜索概念：MINMINMAXMAXMAX8/21/202291福州大學(xué)陽光學(xué)院計算機系博弈樹的啟發(fā)式搜索概念：MINMINMINMAXMAXMAX8/21/202292福州大學(xué)陽光學(xué)院計算機系博弈樹的啟發(fā)式搜索概念（博奕樹特點）：1）初始格局為初始節(jié)點S0。2）或節(jié)點和與節(jié)點逐層交替出現(xiàn)。3）己方獲勝格局為可解節(jié)點，對方獲勝為不可解節(jié)點。 可以用類似于求解與/或樹搜索技術(shù)來處理許多簡單博弈以及若干復(fù)雜的博弈殘局。8/21/202293福州大學(xué)陽光學(xué)院計算機系博弈樹的啟發(fā)式搜索極大極小分析法 基本思想：