第二章2 啟發(fā)式搜索

1、問題求解的基本方法啟發(fā)式搜索 2盲目搜索 3盲目搜索算法的缺點：盲目應對之道：應對之道：引入與應用領域相關(guān)的啟發(fā)式知識來指導引入與應用領域相關(guān)的啟發(fā)式知識來指導OPEN表中節(jié)點的排序表中節(jié)點的排序 4 局部排序局部排序-這是對深度優(yōu)先法的改進，僅這是對深度優(yōu)先法的改進，僅對新擴展出來的子節(jié)點排序，使這些節(jié)點中對新擴展出來的子節(jié)點排序，使這些節(jié)點中最有希望者能優(yōu)先取出考察和擴展最有希望者能優(yōu)先取出考察和擴展 全局排序全局排序-對對OPEN表中的所有節(jié)點排表中的所有節(jié)點排序，使最有希望的節(jié)點排在表首序，使最有希望的節(jié)點排在表首 5啟發(fā)式搜索啟發(fā)式搜索 概念：在搜索過程中，引入啟發(fā)式知識減少搜索的盲

2、概念：在搜索過程中，引入啟發(fā)式知識減少搜索的盲目性，提高搜索的效率，稱之為啟發(fā)式搜索目性，提高搜索的效率，稱之為啟發(fā)式搜索啟發(fā)式知識對搜索的作用：啟發(fā)式知識對搜索的作用： 選擇下一個要被擴展的節(jié)點，對選擇下一個要被擴展的節(jié)點，對OPEN表進行排序表進行排序 在擴展一個節(jié)點時，僅僅有選擇性的生成部分有用的節(jié)在擴展一個節(jié)點時，僅僅有選擇性的生成部分有用的節(jié)點點 修剪掉某些估計不可能導致成功的子節(jié)點修剪掉某些估計不可能導致成功的子節(jié)點 6啟發(fā)式搜索啟發(fā)式搜索-算法算法A應用評價函數(shù)來實現(xiàn)啟發(fā)式搜索的典型是算法應用評價函數(shù)來實現(xiàn)啟發(fā)式搜索的典型是算法A ，評，評價函數(shù)價函數(shù)f(n)： f(n)= g(

3、n) + h(n)n-搜索圖中的某個當前被擴展的節(jié)點；搜索圖中的某個當前被擴展的節(jié)點；f(n)-從初始狀態(tài)節(jié)點從初始狀態(tài)節(jié)點s, 經(jīng)由節(jié)點經(jīng)由節(jié)點n到達目標狀態(tài)節(jié)點到達目標狀態(tài)節(jié)點n ng，估計的最小路徑代價，估計的最小路徑代價g(n)-從從s到到n ,估計的最小路徑代價；估計的最小路徑代價；h(n)-從從n到到ng,估計的最小路徑代價；估計的最小路徑代價； 7g(n)是已知的h(n)是未知的，需要采用啟發(fā)式函數(shù)來估算，稱為啟發(fā)式函數(shù) 8算法算法A搜索算法搜索算法A的一般過程：的一般過程：1） G := s； 2） OPEN := (s), CLOSE := ()； 3） 若若OPEN是空表，

4、則算法以失敗結(jié)束；是空表，則算法以失敗結(jié)束； 4） n := MOVE-FIRST(OPEN)；5） 若若n是目標狀態(tài)節(jié)點，則搜索成功結(jié)束，并給出解答路是目標狀態(tài)節(jié)點，則搜索成功結(jié)束，并給出解答路徑；徑；6） 擴展節(jié)點擴展節(jié)點n,將非節(jié)點將非節(jié)點n祖先的子節(jié)點置于子節(jié)點集合祖先的子節(jié)點置于子節(jié)點集合SNS中，中， 并插入搜索圖并插入搜索圖G中，對于中，對于SNS中每個子節(jié)點中每個子節(jié)點n ni,計算計算 f(n,n ni) = g(n,ni) + h(ni); 97） 標記和修改指針標記和修改指針 把把SNS中的子節(jié)點分為三類（同一般圖搜索算法）中的子節(jié)點分為三類（同一般圖搜索算法） 加第加第

5、1類子節(jié)點于類子節(jié)點于OPEN表（同一般圖搜索算法）表（同一般圖搜索算法） 比較第比較第2類子節(jié)點類子節(jié)點ni經(jīng)由新、老父節(jié)點的評價函數(shù)值經(jīng)由新、老父節(jié)點的評價函數(shù)值f(n,ni)、f(ni);若若f(n,ni) f(ni)點點,則令則令f(ni) = f(n,ni),并移動子節(jié)點指并移動子節(jié)點指向老父節(jié)點的指針，改為指向新父節(jié)點向老父節(jié)點的指針，改為指向新父節(jié)點 對第對第3類子節(jié)點作與第類子節(jié)點作與第2類同樣的處理，并把這些子節(jié)點從類同樣的處理，并把這些子節(jié)點從CLOSE表中移出，重新加入表中移出，重新加入OPEN表。表。8）按）按f值從小到大排序值從小到大排序OPEN表中的節(jié)點表中的節(jié)點

6、9) 返回語句返回語句3）；）； 10啟發(fā)式搜索算法啟發(fā)式搜索算法A結(jié)論結(jié)論按按f(n)排序排序OPEN表中的節(jié)點表中的節(jié)點 f(n)值最小者排在首位，優(yōu)先加以擴展值最小者排在首位，優(yōu)先加以擴展 體現(xiàn)了最佳優(yōu)先體現(xiàn)了最佳優(yōu)先(best-first)搜索策略的思想搜索策略的思想 11算法算法A舉例：舉例：8數(shù)碼游戲數(shù)碼游戲f(n) = g(n) + h(n)g(n)=d(n)-當前被考察和擴展的節(jié)點當前被考察和擴展的節(jié)點n在搜索圖中的在搜索圖中的節(jié)點深度節(jié)點深度 h(n)=w(n) -節(jié)點節(jié)點n與目標狀態(tài)節(jié)點與目標狀態(tài)節(jié)點n ng相比較，錯位的相比較，錯位的棋牌個數(shù)棋牌個數(shù) 12初始節(jié)點：初始節(jié)

7、點： f(n) = 0 + 4 = 4 13 14 二二 實現(xiàn)啟發(fā)式搜索的關(guān)鍵因素實現(xiàn)啟發(fā)式搜索的關(guān)鍵因素（1）搜索算法的可采納性）搜索算法的可采納性(Admissibility) 在搜索圖存在從初始狀態(tài)節(jié)點到目標狀態(tài)節(jié)點在搜索圖存在從初始狀態(tài)節(jié)點到目標狀態(tài)節(jié)點解答路徑的情況下，若一個搜索法總能找到解答路徑的情況下，若一個搜索法總能找到最短最短（代價最?。┑慕獯鹇窂剑瑒t稱算法具有可采納性（代價最?。┑慕獯鹇窂?，則稱算法具有可采納性 寬度優(yōu)先的搜索算法就是可采納的寬度優(yōu)先的搜索算法就是可采納的 15引入評價函數(shù)引入評價函數(shù)f f* *: f f* *(n)=g(n)=g * *(n)+h(n)+

8、h * *(n)(n) f f*(n)(n)、g g*(n)(n)、h h*(n)(n)分別指示當經(jīng)由節(jié)點分別指示當經(jīng)由節(jié)點n的的最短最短（代價最?。┙獯鹇窂秸业綍r（代價最?。┙獯鹇窂秸业綍r實際的實際的路經(jīng)代價路經(jīng)代價（長度）、該路徑前段（自初始狀態(tài)節(jié)點到節(jié)點（長度）、該路徑前段（自初始狀態(tài)節(jié)點到節(jié)點n）代價和后段（自節(jié)點代價和后段（自節(jié)點n到目標狀態(tài)節(jié)點）代價。到目標狀態(tài)節(jié)點）代價。 將評價函數(shù)將評價函數(shù)f與與f f*相比較，實際上，相比較，實際上，f(n)f(n)、g(n)和和h(n)分別是分別是f f*(n)、g g*(n)(n)和和h h*(n)(n)的近似值。的近似值。 在理想的情況

9、下，設計評價函數(shù)在理想的情況下，設計評價函數(shù)f時可以讓時可以讓g(n)g(n) = g g*(n)(n),h(n) = h h*(n)(n) 16如何挖掘貼切的啟發(fā)式知識如何挖掘貼切的啟發(fā)式知識(h(n)是設計評價函數(shù)乃是設計評價函數(shù)乃至算法至算法A的關(guān)鍵的關(guān)鍵 在前述的八數(shù)碼游戲中，在前述的八數(shù)碼游戲中，h(n)采用了采用了w(n)現(xiàn)在采用現(xiàn)在采用p(n)-節(jié)節(jié)點點n與目標狀態(tài)節(jié)點相比較，每與目標狀態(tài)節(jié)點相比較，每個錯位棋牌在假設不受阻攔的情況下，移動到目標個錯位棋牌在假設不受阻攔的情況下，移動到目標狀態(tài)相應位置所需走步（移動次數(shù)）的總和狀態(tài)相應位置所需走步（移動次數(shù)）的總和 17 18可以

10、證明，若確保對于搜索圖中的節(jié)點可以證明，若確保對于搜索圖中的節(jié)點n n，總是，總是有有h(n) h(n) h h* * (n), (n), 則算法則算法A A具有可采納性具有可采納性即總能搜索到最短（代價最小）的解答路徑即總能搜索到最短（代價最?。┑慕獯鹇窂轿覀兎Q滿足我們稱滿足h(n) h(n) h h* * (n) (n)的算法的算法A A為為A A* *寬度優(yōu)先算法，是一種特殊的寬度優(yōu)先算法，是一種特殊的A*算法算法h(n) 0 19實例實例傳教士和野人問題傳教士和野人問題N=5,K h(n) h h* * (n), (n),則則h(n)h(n)過強，使算法過強，使算法A A失去可采納失去

11、可采納性，從而不能確保找到最短解答路徑性，從而不能確保找到最短解答路徑設計接近、又總是設計接近、又總是 h h* * (n) (n)的的h(n)h(n)成為應用成為應用A A* *算法搜索算法搜索問題解答的關(guān)鍵，以壓縮搜索圖，提高搜索效率問題解答的關(guān)鍵，以壓縮搜索圖，提高搜索效率 23(3) (3) 設計設計h(n)h(n)的實用考慮的實用考慮f(n) = g(n) + h(n)使用評價函數(shù)使用評價函數(shù)f(n) = g(n) + wh(n)f(n) = g(n) + wh(n)w w用作加權(quán)用作加權(quán) 在搜索圖的淺層（上部），可讓在搜索圖的淺層（上部），可讓w w取較大值，以使取較大值，以使g(

12、n)g(n)所占比例很小，從而突出啟發(fā)式函數(shù)的作用，加速向縱深所占比例很小，從而突出啟發(fā)式函數(shù)的作用，加速向縱深方向搜索；一旦搜索到較深的層次，又讓方向搜索；一旦搜索到較深的層次，又讓w w取較小值，以取較小值，以使使g(n)g(n)所占比例很大，并確保所占比例很大，并確保wh(n)wh(n)h h* * (n), (n),從而引導搜從而引導搜索向橫廣方向發(fā)展，尋找到較短的解答路徑。索向橫廣方向發(fā)展，尋找到較短的解答路徑。 24三三 回溯策略和回溯策略和 爬山法爬山法 在在g(n)0的情況下，若限制只用評價函數(shù)的情況下，若限制只用評價函數(shù) f(n)= h(n)去去排序新擴展出來的子節(jié)點排序新擴

13、展出來的子節(jié)點，即局部，即局部排序，就可實現(xiàn)較為簡單的搜索策略：回溯策排序，就可實現(xiàn)較為簡單的搜索策略：回溯策略和爬山法略和爬山法 爬山法適用于能逐步求精的問題爬山法適用于能逐步求精的問題 25（1）爬山法爬山法 爬山法實際上就是求函數(shù)極大值問題，不過這爬山法實際上就是求函數(shù)極大值問題，不過這里不是用數(shù)值解法，而是依賴于啟發(fā)式知識，試里不是用數(shù)值解法，而是依賴于啟發(fā)式知識，試探性地逐步向頂峰逼近（廣義地，逐步求精），探性地逐步向頂峰逼近（廣義地，逐步求精），直到登上頂峰直到登上頂峰 在爬山法中，限制只能向山頂爬去，即向目標在爬山法中，限制只能向山頂爬去，即向目標狀態(tài)逼近，不準后退，從而簡化了搜

14、索算法；即狀態(tài)逼近，不準后退，從而簡化了搜索算法；即不需設置不需設置OPEN和和CLOSE表，因為沒有必要保存表，因為沒有必要保存任何待擴展節(jié)點任何待擴展節(jié)點 26爬山法對于爬山法對于單一極值問題單一極值問題（登單一山峰）十分（登單一山峰）十分有效而又簡便，但對于具有多極值的問題就無有效而又簡便，但對于具有多極值的問題就無能為力了，因為很可能會因錯登上次高峰而失能為力了，因為很可能會因錯登上次高峰而失敗敗-不能到達最高峰不能到達最高峰 27 28（2）回溯策略）回溯策略 保存了每次擴展出的子節(jié)點，并按保存了每次擴展出的子節(jié)點，并按h(n)值從值從小到大排列小到大排列 相當于爬山的過程中記住了途

15、經(jīng)的岔路口，相當于爬山的過程中記住了途經(jīng)的岔路口，只要當前路徑搜索失敗就回溯（退回）到時序上只要當前路徑搜索失敗就回溯（退回）到時序上最近的岔路口，向另一路徑方向搜索最近的岔路口，向另一路徑方向搜索 可以確保最后到達最高峰（即目標狀態(tài)）?？梢源_保最后到達最高峰（即目標狀態(tài)）。 29令令PATH、SNL、n、n 為局部變量：為局部變量： P A T H - - 節(jié) 點 列 表 ， 指 示 解 答 路 徑 ；節(jié) 點 列 表 ， 指 示 解 答 路 徑 ； S N L - - 當 前 節(jié) 點 擴 展 出 的 子 節(jié) 點 列 表 ；當 前 節(jié) 點 擴 展 出 的 子 節(jié) 點 列 表 ； MOVE-FI

16、RST(SNL)-把把SNL表首的節(jié)點移出，作為下一次表首的節(jié)點移出，作為下一次要加以擴展的節(jié)點；要加以擴展的節(jié)點； n、 n -分別指示當前考察和下一次考察的節(jié)點。分別指示當前考察和下一次考察的節(jié)點。該遞歸過程的算法就取名為該遞歸過程的算法就取名為BACKTRACK(n),參數(shù)參數(shù)n為當前被為當前被擴展的節(jié)點，算法的初次調(diào)用式是擴展的節(jié)點，算法的初次調(diào)用式是BACKTRACK(s),s即為初即為初始狀態(tài)節(jié)點。始狀態(tài)節(jié)點。 30算法的步驟如下：算法的步驟如下：（1） 若若n是目標狀態(tài)節(jié)點，則算法的本次調(diào)用成功結(jié)束，是目標狀態(tài)節(jié)點，則算法的本次調(diào)用成功結(jié)束，返回空表；返回空表；（2） 若若n是失

17、敗狀態(tài)，則算法的本次調(diào)用失敗結(jié)束，返回是失敗狀態(tài)，則算法的本次調(diào)用失敗結(jié)束，返回FAIL；（3） 擴展節(jié)點擴展節(jié)點n，將生成的子節(jié)點置于列表，將生成的子節(jié)點置于列表SNL，并按評，并按評價函數(shù)價函數(shù)f(k) = h(k)的值從小到大排序（的值從小到大排序（k指示子節(jié)點）；指示子節(jié)點）；(4） 若若SNL為空，則算法的本次調(diào)用失敗結(jié)束，返回為空，則算法的本次調(diào)用失敗結(jié)束，返回FAIL；（5） n= MOVE-FIRST(SNL)；（6） PATH = BACKTRACK(n)；（7）若）若PATH =FAIL, 返回到語句（返回到語句（4）；）；（8） 將將n加到加到PATH表首，算法的本次調(diào)用

18、成功結(jié)束，返表首，算法的本次調(diào)用成功結(jié)束，返回回PATH。 31失敗狀態(tài)通常意指三種情況：失敗狀態(tài)通常意指三種情況：（1）不合法狀態(tài)（如傳教士和野人問題中所述的那）不合法狀態(tài)（如傳教士和野人問題中所述的那樣）樣）（2）舊狀態(tài)重現(xiàn)（如八數(shù)碼游戲中某一棋盤布局的）舊狀態(tài)重現(xiàn)（如八數(shù)碼游戲中某一棋盤布局的重現(xiàn)，會導致搜索算法死循環(huán)）重現(xiàn)，會導致搜索算法死循環(huán)）（3）狀態(tài)節(jié)點深度超過預定限度（例如八數(shù)碼游戲）狀態(tài)節(jié)點深度超過預定限度（例如八數(shù)碼游戲中，指示解答路徑不超過中，指示解答路徑不超過6步）。步）。 32 皇后問題 33 34四四 狀態(tài)空間抽象和生成狀態(tài)空間抽象和生成-測試法測試法 狀態(tài)空間抽象

19、策略適合尋找令人滿意的解答狀態(tài)空間抽象策略適合尋找令人滿意的解答 生成生成-測試法用于最優(yōu)化問題測試法用于最優(yōu)化問題 35（1）狀態(tài)空間抽象策略）狀態(tài)空間抽象策略 狀態(tài)空間抽象是減少搜索量的重要技術(shù)。常用的方式是狀態(tài)空間抽象是減少搜索量的重要技術(shù)。常用的方式是將狀態(tài)空間按子問題進行劃分，子問題構(gòu)成抽象空間。顯然，將狀態(tài)空間按子問題進行劃分，子問題構(gòu)成抽象空間。顯然，抽象空間中的一個搜索與步抽象空間中的一個搜索與步(一個子問題一個子問題)對應于實際狀態(tài)空對應于實際狀態(tài)空間中的許多步，因而抽象空間小得多，使搜索大幅度加快間中的許多步，因而抽象空間小得多，使搜索大幅度加快 36（2）生成）生成-測試

20、法測試法 搜索過程由兩個部件合作完成：可能解的生成器搜索過程由兩個部件合作完成：可能解的生成器和修剪不正確解答的測試器。和修剪不正確解答的測試器。 在搜索過程中，生成器和測試器的工作往往需交在搜索過程中，生成器和測試器的工作往往需交替進行。替進行。 使用生成使用生成-測試法應考慮的關(guān)鍵問題是如何在生成測試法應考慮的關(guān)鍵問題是如何在生成器和測試器之間分配知識器和測試器之間分配知識 經(jīng)驗證明，知識豐富的生成器會導致較高的搜索經(jīng)驗證明，知識豐富的生成器會導致較高的搜索效率效率 37 38五五 啟發(fā)式搜索的適用性討論啟發(fā)式搜索在人工智能研究的啟發(fā)式搜索在人工智能研究的早期早期是很重要的議是很重要的議題

21、，甚至有人說人工智能就是啟發(fā)式搜索。題，甚至有人說人工智能就是啟發(fā)式搜索。但隨著知識工程的興起，啟發(fā)式搜索已較少用于但隨著知識工程的興起，啟發(fā)式搜索已較少用于作為人工智能系統(tǒng)的頂層控制結(jié)構(gòu)，尤其是使用作為人工智能系統(tǒng)的頂層控制結(jié)構(gòu)，尤其是使用全局評價器的啟發(fā)式搜索方法，因為其不適合知全局評價器的啟發(fā)式搜索方法，因為其不適合知識密集型的問題求解。識密集型的問題求解。 但啟發(fā)式搜索仍不失為重要技術(shù)用于解決某些適但啟發(fā)式搜索仍不失為重要技術(shù)用于解決某些適合于它的子問題，且搜索技術(shù)的不少思想方法可合于它的子問題，且搜索技術(shù)的不少思想方法可用于用于KB系統(tǒng)的設計。系統(tǒng)的設計。 39啟發(fā)式搜索技術(shù)面臨啟發(fā)式搜索技術(shù)面臨三個關(guān)鍵三個關(guān)鍵選擇：選擇： 確定性或非確定性搜索方式；確定性或非確定性搜索方式； 搜索目標狀態(tài)本身還是達到目標狀態(tài)的解搜索目標狀態(tài)本身還是達到目標狀態(tài)的解答路徑答路徑(往往表示為狀態(tài)或操作算子序列往往表示為狀態(tài)或操作算子序列)； 搜索一個還是全部或最優(yōu)解答。搜索一個還是全部或最優(yōu)解答。 所謂確定性方式，就是利用啟發(fā)式信息選取所謂確定性方式，就是利用啟發(fā)式信息選取最好的分枝，而舍棄所有其余分枝不再予以考慮最好的分枝，而舍棄所有