1、第第3章章 搜索的基本策略搜索的基本策略 3.1 盲目的搜索方法盲目的搜索方法l 盲目搜索方法又叫非啟發式搜索，是一種無信息搜索，一般只適用于求解比較簡單的問題。下面我們要討論的幾個搜索方法，它們均屬于盲目搜索方法。3.1.1 寬度優先搜索寬度優先搜索l 如果搜索是以同層鄰近節點依次擴展節點的, 那么這種搜索就叫寬度優先搜索,這種搜索是逐層進行的, 在對下一層的任一節點進行搜索之前,必須搜索完本層的所有節點。 3.1.1 寬度優先搜索寬度優先搜索寬度優先搜索寬度優先搜索算法如下: 1. 令N為一個由初始狀態構成的表； 2. 若N為空退出，標志失敗； 3. 令n為N中第一個點，將n從N中刪除；

2、4. 若n是目標，則退出，標態成功； 5. 若n不是目標，將n的后繼點加入到N表的尾部，轉2。 3.1.1 寬度優先搜索寬度優先搜索l寬度優先搜索的優點是：若問題有解，則可找出最優解;l寬度優先搜索的缺點是:效率低，組合爆炸問題難以解決。 3.1.2 深度優先搜索深度優先搜索在深度優先搜索中，我們首先擴展最新產生的（即最深的）節點。深度相等的節點可以任意排列。 3.1.2 深度優先搜索深度優先搜索深度優先搜索算法如下:1. 令N為一個由初始狀態構成的表；2. 若N為空退出，標態失敗；3. 令n為N中第一個點，將n從N中刪除；4. 若n是目標，則退出，標態成功；5. 若n不是目標，將n的后繼加入

3、到N表的首部轉2。 3.1.2 深度優先搜索深度優先搜索l 深度優先搜索的優點：節省大量時間和空間；l 深度優先搜索的缺點：不一定能找到解。因為在無限搜索樹的情況下，最壞的情況可能是不停機。3.1.3 分枝有界搜索分枝有界搜索（Branch-and-Bound）l 分枝有界搜索也是一種深度優先搜索，但每個分支都規定了一個統一的搜索深度，搜索到這個深度后，如果沒有找到目標便自動退回到上一層，繼續搜索。3.1.3 分枝有界搜索分枝有界搜索1. 令N為一由初始狀態構成的表；2. 若N為空退出，標志失敗；3. 令n為N中第一個點，將n從N中刪除；4. 若n是目標，則退出，標態成功；5. 若n深度=預先

4、定好的一個界dmax，則轉2；6. 若n不是目標，將n的后繼加入到N表的首部轉2；3.1.4 迭代加深搜索迭代加深搜索（Iterative deepening）l 迭代加深搜索是在分枝有界搜索的基礎上，對dmax進行迭代，即逐步加深。這是一種同時兼顧深度和廣度的搜索方法。在限定的深度內，保證了對廣度節點的搜索，如果沒有找到解，再加深深度。3.2 啟發式搜索方法啟發式搜索方法l 如果能夠找到一種方法用于排列待擴展節點的順序，即選擇最有希望的節點加以擴展，那么，搜索效率將會大大提高。啟發式搜索就是基于這種想法,它是深度優先的改進。搜索時不是任取一個分枝，而是根據一些啟發式信息，選擇最佳一個分枝或幾

5、個分枝往下搜索。3.2.1 啟發式信息的表示啟發式信息的表示1啟發式搜索的依據啟發式搜索的依據（1）人們善于利用一些線索來幫助自己選擇搜 索 方 向 ， 這 些 線 索 統 稱 為 啟 發 式(Heuristics)信息。（2）現實問題往往只需一個解，而不要求最優解或全部解。（3）啟發式信息可以避免某些領域里的組合爆炸問題。 3.2.1 啟發式信息的表示啟發式信息的表示啟發信息按其形式可分為下列2種：（1）表示為估計函數）表示為估計函數l 確定一個啟發式函數f(n), n 為被搜索的節點,它把問題狀態的描述映射成問題解決的程度，通常這種程度用數值來表示，就是啟發式函數的值。這個值的大小用來決定

6、最佳搜索路徑。3.2.1 啟發式信息的表示啟發式信息的表示（2）表示成規則）表示成規則如程序AM的一條啟發式規則為： 如果存在一個有趣的二元函數f(x,y)，那么看看兩變元相同時會發生什么？l若f表示乘法：導致發現平方；l若f表示集合并運算：導致發現恒等函數；l若f表示思考：導致發現反省；l若f表示謀殺：導致發現自殺。3.2.1 啟發式信息的表示啟發式信息的表示2啟發式函數的表示方法啟發式函數的表示方法l啟發式函數是一種映射函數，它把對問題狀態的描述映射成一種希望的程度。l啟發式函數設計得好，對有效引導搜索過程有著重要的作用。非常簡單的啟發式函數搜索路徑能夠作出非常令人滿意的估計。3.2.1

7、啟發式信息的表示啟發式信息的表示l如何構造啟發式函數？（1）啟發式函數能夠根據問題的當前狀態，確定用于繼續求解問題的信息。 這樣的啟發式函數能夠有效地幫助決定那些后繼節點應被產生。3.2.1 啟發式信息的表示啟發式信息的表示 2 8 3 1 6 47 5 例2.7 八數碼問題。 1 2 3 8 47 6 5 a11 a12 a13 a21 a22 a23a31 a32 a33 問題空間為： S0 Sg 3.2.1 啟發式信息的表示啟發式信息的表示各狀態間的轉換規則為：Pr1: 空格上移 If i，j and i1 then ai-1,j i，j Pr2: 空格下移 If i，j and i3

8、then aI+1,j i，j 3.2.1 啟發式信息的表示啟發式信息的表示Pr3: 空格左移 If i，j and j1 then ai,j-1 i，j Pr4: 空格右移 If i，j and j3 then ai,j+1 i，j 啟發式函數f1= 數字錯放位置的個數，f1=0，則達到目標。 2 8 3 1 6 47 52 8 31 6 4 7 52 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 3 1 6 47 52 8 31 47 6 52 8 31 6 47 53.2.1 啟發式信息的表示啟發式信息的表示 當f1值相同時如何決定走步? 現在定義：

9、f2 = 所有數字當前位置以最短路徑走到正確位置的步數之和。 在這個定義之下，各狀態的啟發式函數值為： 數碼 1 2 3 4 5 6 7 8 F2(S0）= 1 + 1 +0 +0 + 0 + 1 +0 + 2 =5 F2(S1）= 1 + 1 +0 +0 + 0 + 0 +0 + 2 =43.2.1 啟發式信息的表示啟發式信息的表示數碼 1 2 3 4 5 6 7 8 F2(S2）= 1 + 1 +0 +0 + 0 + 1 +1 + 2 =6 F2(S3）= 1 + 1 +0 +0 + 1 + 1 +0 + 2 =6F2(S4）= 1 + 1 +0 +0 + 0 + 0 +0 + 1 =3F

10、2(S5）= 1 + 1 +0 +0 + 0 + 1 +0 + 2 =5 F2(S6）= 1 + 2 +0 +0 + 0 + 0 +0 + 2 =53.2.1 啟發式信息的表示啟發式信息的表示 (2) 啟發式函數應能夠估計出可能加速達到目標的程度 這可以幫助確定當擴展一個節點時，那些節點應從搜索樹中刪除。 啟發式函數對搜索樹(圖)的每一節點的真正優點估計得愈精確,解題過程就愈少走彎路。3.2.1 啟發式信息的表示啟發式信息的表示l例 2 . 8 八 皇 后 問 題 ( 8 - Q u e e n s problem） 在8*8棋盤要求放下8個皇后，要求沒有一個皇后能夠攻擊其它皇后，即要使得在任

11、何一行、一列或對角線上都不存在兩個或兩個以上的皇后。3.2.1 啟發式信息的表示啟發式信息的表示求解這個問題的過程為： （a）定義狀態空間。 設狀態空間的一點為：8*8矩陣。 （b）定義操作規則。 按如下規則放置皇后：3.2.1 啟發式信息的表示啟發式信息的表示 第一個皇后放第一行。 第二個皇后放在第二行且不與第一個皇后在同一列或對角線的空格上。 第i個皇后放在第i行且不與前面i 1個皇后在同一列或對角線的空格上。 3.2.1 啟發式信息的表示啟發式信息的表示可使用如下啟發式函數：l設x為當前要放置Queen的空格lf（x）= 剩下未放行中能夠用來放Queen的空格數l不難看出，f（x）愈大愈

12、好，應選擇f（x）最大的空格來放置皇后。例如，在放置了三個Q后，第4個Q可放在第4行的A，B，C三個位置。 Q Q Q A BC abc bc ab bc c ac abc b acb ac acabbc 3.2.1 啟發式信息的表示啟發式信息的表示a為第4行A處放了皇后剩下可放Q的位置； b為第4行B處放了皇后剩下可放Q的位置； c為第4行C處放了皇后剩下可放Q的位置。 按照以上定義，可求得： f（A）=8， f（B）=9， f（C）=10。所以搜索可以從C對應的空格放置一個皇后開始，其余的空格對應的搜索樹可以刪除。3.2.1 啟發式信息的表示啟發式信息的表示（c）定義搜索策略。第i個皇后放

13、到第i行中的那個與前面i-l個皇后不在同一列或對角線上且f（x）值最大的空格中。啟發式信息是某些領域里的知識信息，它能使計算機系統在這些知識信息提示以后可能采取的某些可能的動作或避免某些不可能的動作。 搜索方向的選擇搜索方向的選擇 搜索過程：在問題空間中找出從開始狀態到目標狀態的一條最好的或較好的路徑。這種搜索可按兩個方向進行： 正向搜索：從初始狀態朝著目標狀態方向搜索； 逆向搜索：從目標狀態朝著初始狀態方向搜索。 將以上兩種搜索方法結合起來，就產生了雙向搜索 搜索方向的選擇搜索方向的選擇l正向搜索 和 逆向搜索 S0 S0 Sg Sg 搜索方向的選擇搜索方向的選擇(1) 朝分枝因子低的方向更

14、有效。l 分子因子指從一點出發可以直接到達的平均結點數。朝著分枝因子低的方向搜索意味著朝著“收斂”的方向搜索，例如定理證明, 一般是從公理或定理出發，推出新的定理。公理是有限的，而定理是大量的。 搜索方向的選擇搜索方向的選擇(2) 由狀態少的一方出發，朝著大量的可識別的狀態的方向搜索l 例如符號積分問題, 正向搜索意味著從被積函數出發，按照積分規則，尋找原函數。而逆向搜索，則要從大量的原函數的任意組合出發，通過積分規則，找出被積函數，這顯然要困難得多，我們在人工演算積分問題時決不會這么去做。搜索方向的選擇搜索方向的選擇 (3) 依據用戶可接受的方向l 特別是需要向用戶解釋推理過程時，順應用戶的

15、心理，選擇搜索方向會使系統顯得更自然一些。在建造專家系統時，向用戶解釋為什么系統會得出某個結論, 這一步驟是必不可少的，所以尤其要考慮這個問題。3.2.2 幾種最基本的搜索策略幾種最基本的搜索策略 l下面主要介紹采用Best-first策略的幾個基本方法，這些方法構成了許多數AI系統的構架，其效率取決于問題所在領域知識的利用與開發。由于這些方法的通用性，并且難于克服搜索過程的組合爆炸問題，所以又稱為弱法(Weak method）。3.2.2 幾種最基本的搜索策略幾種最基本的搜索策略l 弱法主要包括：最佳優先法 生成測試法爬山法廣度優先法問題歸約法約束滿足法手段目的分析法。1生成測試法生成測試法

16、(Generate-and-test） 生成測試法的基本步驟為： 1. 生成一個可能的解，此解是狀態空間一個點，或一條始于S0的路徑。 2. 用生成的“解”與目標比較。 3. 達到目標則停止，否則轉第一步。1生成測試法生成測試法(Generate-and-test）l 此方法屬于深度優先搜索(depth-first-search）, 因為要產生一個完全的解后再判斷，若不是目標又要生成下一個“解”。這種方法幾乎接近耗盡式搜索，因而效率低。 于是人們考慮能否利用反饋信息以幫助決定生成什么樣的解，這種改進就是下面要講的爬山法。 2爬山法爬山法(Hill-climbing） 1 生成第一個可能的解。若

17、是目標，則停止；否則轉下一步。2 從當前可能的解出發，生成新的可能解集。 3 以當前最佳元素為起點，轉(）。 2爬山法爬山法(Hill-climbing） 爬山法在生成的元素中尋找最優解，這種最優是局部最優。爬山法會產生下述問題： (1）找到的是局部最大值。(如左圖) (2）碰到平頂時無法處理。(如右圖)2爬山法爬山法(Hill-climbing） (3）碰到山脊時無法處理。碰到山脊的克服辦法是： (1) 退回較大一步，即允許回朔。(2) 向前跨一大步。(3) 多設幾個初始點，從幾個初始點同時或先后進行搜索。3最佳優先搜索最佳優先搜索(Best-first search)1 生成第一個可能的解

18、。若是目標，則停止；否則轉下一步。 2 從該可能的解出發，生成新的可能解集。3 從解集中挑選最好的元素作為起點，再轉 4. 模擬退火法模擬退火法(simulated Annealing) 退火是冶金專家為了達到某些特種晶體結構重復將金屬加熱或冷卻的過程, 該過程的控制參數為溫度T。這種思想應用于許多優化問題就產生了模擬退火算法, 模擬退火法的基本思想是, 在系統朝著能量減小的趨勢這樣一個變化過程中, 偶爾允許系統跳到能量較高的狀態，以避開局部極小點, 最終穩定到全局最小點。 4. 模擬退火法模擬退火法(simulated Annealing)l如圖所示，若使能量在C點突然增加h，就能跳過局部極小點B, 而找到全局最小點A 。l現在的問題是何時增加能量？應該增加多少能量？為此，柯克帕特里克(S.Kirkpatri