1、第三章 一般搜索原理第三章 一般搜索原理 7/15/20221搜索技術搜索是人工智能中進行問題求解的一大類方法根據是否使用啟發式信息可分為 ：1，盲目搜索；2，啟發式搜索；根據問題的表示方式分為：1，狀態空間搜索；2，與或樹搜索。 例如：用狀態空間法來求解問題時，采用的是狀態空間搜索；用問題歸約方法來求解問題時，采用的是與或樹搜索。 第三章 一般搜索原理 3.1概述7/15/20222搜索的特點和通常的搜索空間不同，人工智能中大多數問題的狀態空間在問題求解之前不是全部知道的。所以，人工智能中的搜索可以分成兩個階段：狀態空間的生成階段和在該狀態空間中對所求解問題狀態的搜索。由于一個問題的整個空間

2、可能會非常的大，在搜索之前生成整個空間會占用太大的存儲空間。為此，狀態空間一般是逐漸擴展的“目標”狀態是在每次擴展的時候進行搜索的。第三章 一般搜索原理 3.1概述7/15/202233.2 盲目搜索第三章 一般搜索原理 3.2 盲目搜索7/15/20224盲目搜索 盲目搜索是按預定的控制策賂進行搜索，沒有任何關于問題本身的信息，在搜索過程中獲得的中間信息并不改變控制策略。由于搜索總是按預先規定的路線進行，沒有考慮到問題本身的特性，因此這種搜索具有盲目性，效率不高，不便于復雜問題的求解。第三章 一般搜索原理 3.2 盲目搜索7/15/20225盲目搜索分類搜索策略可分為三大類不可撤回方式、回朔

3、方式、圖搜索方式不可撤回方式：每一次搜索時，利用局部知識根據最優評價，選出下一狀態，選定后不能撤回，只能繼續回朔方式：在搜索過程中，有時會發現所選的路徑不適合找到目標，這時允許退回去另選一條路徑。圖搜索方式： 將所有應用過的操作和它們產生的狀態描述都以圖的形式記錄下來。由于當前可繼續往下搜索的狀態不只一個，因此可以從其中任一個狀態往下搜索。圖搜索方式與回溯方式的不同之處在于，回溯方式不記億那些試探失敗的操作和它們產生的狀態描述，只記憶當前正在搜索的路徑。圖搜索方式則保存所有試探過的路徑，因而可以在任何一條路徑上繼續搜索第三章 一般搜索原理 3.2 盲目搜索7/15/20226圖搜索方式與回溯方

4、式的不同回溯方式不記憶那些試探失敗的操作和它們產生的狀態描述，只記憶當前正在搜索的路徑。圖搜索方式則保存所有試探過的路徑，因而可以在任何一條路徑上繼續搜索第三章 一般搜索原理 3.2 盲目搜索7/15/20227不可撤回搜索策略 不可撤回方式的控制策略是，選擇一條可應用的操作作用于當前狀態，不論后果如何都接著做下去。這個方法類似于高等數學中求函數極值的爬山法。在爬山法中，我們從任一點出發，在該點的最大梯度方向前進一步，得到一個新的點，再在新點的最大梯度方向上前進一步，一直到梯度為0為止，這個點就是函數的極大值點。如果函數只有一個極大值點則這個點就是該函數的最大值點。第三章 一般搜索原理 3.2

5、 盲目搜索7/15/20228不可撤回搜索的實現不可撤回搜索的實現是將狀態描述定義成一個實數值的爬山函數。控制策略就利用這個爬山函數來選擇一個可應用的操作，施行該操作的結果應使爬山函數的值得到最大限度的增加。第三章 一般搜索原理 3.2 盲目搜索7/15/20229不可撤回搜索舉例(一)選擇八數碼問題我們選取“不在位”的數字個數的負值作為爬山函數 八數碼游戲的操作可描述為下面的4條產生式規則 (1) if空格不在最上一行then空格上移 (2) if空格不在最下一行then生格下移 (3) if空格不在最左一列then空格左移 (4) if空格不在最右一列then空格有移2 8 31 6 47

6、 51 2 38 47 6 5目標狀態初始狀態第三章 一般搜索原理 3.2 盲目搜索7/15/202210不可撤回搜索舉例(二)從初始狀態出發，應用第一條規則，空格上移可獲得爬山函數的最大增加、因此控 制策略選擇第一條規則作為當前的操作。在沒有操作能夠增加爬山函數的值時可任選一個不減小函數值的操作，如果不存在這樣的操作，則過程停止。2 8 31 6 47 52 31 8 47 6 52 8 31 47 6 51 2 38 47 6 5 2 31 8 47 6 5-3-3-4-2-101 2 3 8 47 6 5目標狀態爬山函數值第三章 一般搜索原理 3.2 盲目搜索7/15/202211不可撤

7、回搜索舉例(三)對于上例，采用不可撤回策略可以很快得到問題的解。但一般來講，如果爬山函數有多個局部極大值存在，該策略可能會引導到局部極大值點，而達不到目標狀態。例如當八數碼問題的初始狀態和目標狀態分別如下時，任意一個可應用的操作都會降低爬山函數的值，因此，得不到目標：1 2 3 7 48 6 51 2 57 48 6 3目標初始狀態第三章 一般搜索原理 3.2 盲目搜索7/15/202212回溯搜索策略回溯策略是一種試探性方式。在選擇一個操作時要建立一個回溯點。在搜索過程中，如果遇到了困難，則要返回到最近的一個回溯點，換一個操作繼續進行搜索。第三章 一般搜索原理 3.2 盲目搜索7/15/20

8、2213回溯搜索策略舉例例：皇后問題第三章 一般搜索原理 3.2 盲目搜索7/15/202214( )皇后問題搜索過程（一）第三章 一般搜索原理 3.2 盲目搜索7/15/202215Q( )(1,1)皇后問題搜索過程（二）第三章 一般搜索原理 3.2 盲目搜索7/15/202216QQ( )(1,1)(1,1) (2,3)皇后問題搜索過程（三）第三章 一般搜索原理 3.2 盲目搜索7/15/202217Q( )(1,1)(1,1) (2,3)皇后問題搜索過程（四）第三章 一般搜索原理 3.2 盲目搜索7/15/202218QQ( )(1,1)(1,1) (2,3)(1,1) (2,4)皇后問

9、題搜索過程（五）第三章 一般搜索原理 3.2 盲目搜索7/15/202219QQQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后問題搜索過程（六）第三章 一般搜索原理 3.2 盲目搜索7/15/202220QQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后問題搜索過程（七）第三章 一般搜索原理 3.2 盲目搜索7/15/202221Q( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后問題搜索過程（八）第三章 一般搜索原理 3.2 盲目搜索7/1

10、5/202222( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后問題搜索過程（九）第三章 一般搜索原理 3.2 盲目搜索7/15/202223Q( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)皇后問題搜索過程（十）第三章 一般搜索原理 3.2 盲目搜索7/15/202224QQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)皇后問題搜索過程（十一）第三章 一般搜索原理 3.2 盲目搜索7/15/202225QQQ

11、( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)(1,2) (2,4) (3,1)皇后問題搜索過程（十二）第三章 一般搜索原理 3.2 盲目搜索7/15/202226QQQQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)(1,2) (2,4) (3,1)(1,2) (2,4) (3,1) (4,3)皇后問題搜索過程（十三）第三章 一般搜索原理 3.2 盲目搜索7/15/202227回溯搜索算法回溯搜索可以用遞歸的方法來實現下面的算法是一個

12、用遞歸實現的算法：BACKTRACK（DATA）DATA：當前狀態。返回值：從當前狀態到目標狀態的路徑（以規則表的形式表示）或FAIL。第三章 一般搜索原理 3.2 盲目搜索7/15/202228回溯搜索算法（一）BACKTRACK(DATA)1, IF TERM(DATA) RETURN NIL;2, IF DEADEND(DATA) RETURN FAIL;3, RULES:=APPRULES(DATA);TERM: 找目標DEADEND: 狀態不合法,無法繼續搜索APPRULES: 取可應用規則集第三章 一般搜索原理 3.2 盲目搜索7/15/202229回溯搜索算法（二）4, LOOP

13、: IF NULL(RULES) RETURN FAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R, DATA);8, PATH:=BACKTRACK(RDATA);9, IF PATH=FAIL GO LOOP;10, RETURN CONS(R, PATH);TAIL: 刪除頭條規則GEN: 調用規則作用于當前狀態CONS: 獲取解路徑規則表第三章 一般搜索原理 3.2 盲目搜索7/15/202230存在問題及解決辦法問題：深度問題:如果深度太深死循環問題: 如果狀態出現重復解決辦法：對搜索深度加以限制記錄從初始狀態到

14、當前狀態的路徑第三章 一般搜索原理 3.2 盲目搜索7/15/202231增加約束后的回溯搜索算法BACKTRACK1（DATALIST）DATALIST：從初始到當前的狀態表（逆向）返回值：從當前狀態到目標狀態的路徑（以規則表的形式表示）或FAIL。第三章 一般搜索原理 3.2 盲目搜索7/15/202232增加約束后的回溯搜索算法(一)1, DATA:=FIRST(DATALIST)2, IF MENBER(DATA, TAIL(DATALIST) RETURN FAIL;3, IF TERM(DATA) RETURN NIL;4, IF DEADEND(DATA) RETURN FAIL

15、;5, IF LENGTH(DATALIST)BOUND RETURN FAIL;第三章 一般搜索原理 3.2 盲目搜索7/15/202233增加約束后的回溯搜索算法(二)6, RULES:=APPRULES(DATA);7, LOOP: IF NULL(RULES) RETURN FAIL;8,R:=FIRST(RULES);9,RULES:=TAIL(RULES);第三章 一般搜索原理 3.2 盲目搜索7/15/202234增加約束后的回溯搜索算法(三)10,RDATA:=GEN(R, DATA);11,RDATALIST:=CONS(RDATA, DATALIST);12,PATH:=B

16、ACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R, PATH);第三章 一般搜索原理 3.2 盲目搜索7/15/202235圖搜索策略圖搜索策略就是在圖中尋找從起始點到目標點的路徑的方法圖搜索的一般過程是構造搜索圖的過程。令搜索圖開始時只有起始點S0，然后逐步擴展節點，直到將目標點擴展到搜索圖里為止。擴展的過程就是搜索的過程擴展節點的方法不同，就意味著搜索的方法不同，也就是搜索的路徑不同。第三章 一般搜索原理 3.2 盲目搜索7/15/202236圖搜索包括寬度優先搜索：搜索以接近起始節點的程度依次擴展節點，在對下一層搜索前

17、，必須搜索完本層的所有節點。深度優先搜索：搜索首先擴展最新產生的節點。等代價搜索：搜索沿最小代價節點進行擴展。第三章 一般搜索原理 3.2 盲目搜索7/15/202237圖搜索的一般過程成功是把第一個節點(n)從OPEN表移至CLOSED表把n的后繼節點放入OPEN表的末端，提供返回節點n的指針修改指針方向把S放入OPEN表重排OPEN表是否否OPEN為空？n為目標節點？失敗開始第三章 一般搜索原理 3.2 盲目搜索7/15/202238圖搜索過程說明我們在搜索過程中用到了OPEN表和CLOSED表兩個數據結構OPEN表中的節點都是搜索樹的端節點，即至今尚未被選作為擴展的節點CLOSED表中的

18、節點或者是已被擴展而不能生成后繼節點的那些端節點，或者是搜索樹的非端節點重排OPEN表，實際上就是在選擇搜索順序，也就是擴展的節點的順序。第三章 一般搜索原理 3.2 盲目搜索7/15/202239節點類型說明.mj.mk.ml擴展的節點OPEN表沒有的部分擴展的節點在已在close表中的部分擴展的節點已在OPEN表中的部分選定的擴展節點第三章 一般搜索原理 3.2 盲目搜索7/15/202240圖搜索過程的圖示（一）現要擴展它第三章 一般搜索原理 3.2 盲目搜索7/15/202241圖搜索過程的圖示（二）修改父子關系現要擴展它第三章 一般搜索原理 3.2 盲目搜索7/15/202242圖搜

19、索過程的圖示（三）修改父子關系修改父子關系第三章 一般搜索原理 3.2 盲目搜索7/15/202243寬度優先搜索成功是把第一個節點(n)從OPEN表移至CLOSED表把n的后繼節點放入OPEN表的末端，提供返回節點n的指針把S放入OPEN表是否否OPEN為空？是否有任何后繼節點為目標節點？失敗開始第三章 一般搜索原理 3.2 盲目搜索7/15/202244目標2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7

20、 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 582 3 41 8 7 6 54八數碼難題的寬度優先搜索樹按上下左右序走步第三章 一般搜索原理 3.2 盲目搜索7/15/202245寬度優先搜索的性質當問題有解時，一定能找到解當問題為單位代價值，且問題有解時，一定能找到最優解方法與問題無關，具有通用性效率較低第三章 一般搜索原理 3.2 盲目搜索7/15/202246深度優先搜索成功是把第一個節點(n)從OPEN表移至CLOSED表把n

21、的后繼節點放入OPEN表的前端，提供返回節點n的指針把S放入OPEN表是否否OPEN為空？節點n的深度是否等于深度界限？失敗開始是否有任何后繼節點為目標節點？是否S是否為目標節點？否成功第三章 一般搜索原理 3.2 盲目搜索7/15/2022472 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1

22、2 37 8 4 6 51 2 38 47 6 5123456789abcd1 2 3 8 47 6 5目標。八數碼難題的深度優先搜索樹第三章 一般搜索原理 3.2 盲目搜索7/15/202248深度優先搜索的性質一般不能保證找到最優解當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉是一個通用的與問題無關的方法第三章 一般搜索原理 3.2 盲目搜索7/15/202249等代價搜索搜索樹的每條弧線上可能有代價值有些問題要求搜索代價最小的解當搜索樹的每條弧線上的代價值都為1時，寬度優先搜索可以看成是最小代價搜索推廣寬度優先搜索，以獲得最小代價的搜索方法稱為

23、等代價搜索第三章 一般搜索原理 3.2 盲目搜索7/15/202250等代價搜索成功是把具有最小g(i)值的節點i從OPEN表移至CLOSED表計算其后繼節點j的g(j)值。把其后繼節點放入OPEN表把S放入OPEN表否否OPEN為空？失敗開始 i是否為目標節點？是S是否為目標節點？否成功是令g(s)=0第三章 一般搜索原理 3.2 盲目搜索7/15/2022513.3 啟發式搜索第三章 一般搜索原理 3.3 啟發式搜索7/15/202252為何引入啟發式信息盲目搜索的效率低，耗費過多的計算時間和空間，容易產生組合爆炸。利用知識來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。對搜索產生幫助

24、的信息稱為啟發信息第三章 一般搜索原理 3.3 啟發式搜索7/15/202253啟發式信息對搜索方法的影響啟發信息的多少用啟發信息強度來表示不同的啟發信息對搜索方法帶來不同的影響：強：降低搜索工作量，但可能導致找不到最優解弱：一般導致工作量加大，極限情況下變為盲目搜索，但可能可以找到最優解第三章 一般搜索原理 3.3 啟發式搜索7/15/202254啟發式搜索類型啟發信息按用途可分為3類：用于決定要擴展哪一個節點（這個節點稱為最有希望節點），以免像在寬度優先或深度優先搜索中那樣盲目地擴展在擴展一個節點的過程中，用于決定要生成哪些其后繼節點，以免盲目地生成所有節點。用于決定哪些節點應從搜索樹中拋

25、棄或修剪。用來估算節點希望程度的方法為估價函數體現問題自身的啟發性信息的函數稱為啟發函數第三章 一般搜索原理 3.3 啟發式搜索7/15/202255對啟發式搜索的認識有些啟發信息能夠大大減少搜索工作量，但不能保證能夠得到最小代價路徑我們往往希望獲得路徑代價和求該路徑所需的搜索代價的綜合為最小由于計算綜合代價很困難，因此，比較兩種方法的優劣，依賴使用的經驗第三章 一般搜索原理 3.3 啟發式搜索7/15/202256有序搜索若按估價函數的增序對OPEN表進行排序，這種搜索方法叫做有序搜索或最佳優先搜索有序搜索的有效性取決于估價函數的選擇，否則有可能失去一個最好的解甚至全部的解如果沒有合適的選擇

26、，可考慮兩個方面的內容：一個是時間和空間的折中保證有一個解第三章 一般搜索原理 3.3 啟發式搜索7/15/202257有序搜索框圖成功是選取f值最小的節點i，從OPEN表移至CLOSED表擴展i，計算后繼節點j的f(j)，對OPEN表重排序，調整親子關系把S放入OPEN表，計算f(s)是否否OPEN為空？i是目標節點？失敗開始第三章 一般搜索原理 3.3 啟發式搜索7/15/202258估價函數：f(n)=d(n)+w(n) 其中， d(n):節點的深度 w(n):節點放錯棋子數目八數碼難題的有序搜索樹2 8 31 6 47 52 31 8 47 6 52 8 31 47 6 52 31 8

27、 47 6 52 8 31 47 6 51 2 38 47 6 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 51 2 37 8 4 6 5 2 31 8 47 6 554646677567551 2 3 8 47 6 5目標5估價函數值第三章 一般搜索原理 3.3 啟發式搜索7/15/202259A算法A算法是一種有序搜索的啟發式搜索算法。估價函數的形式： f(n) = g(n) + h(n)g(n)是從初始節點S0到節點n的實際代價h(n)是從節點n到目標節點Sg的最小路徑代價h*(n)的啟發式估計

28、h(n)稱為啟發函數：第三章 一般搜索原理 3.3 啟發式搜索7/15/202260A算法流程1, OPEN:=(s), f(s):=g(s)+h(s);2, LOOP: IF OPEN=( ) THEN EXIT(FAIL);3, n:=FIRST(OPEN);4, IF GOAL(n) THEN EXIT(SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) mi, 計算f(n, mi):=g(n, mi)+h(mi);第三章 一般搜索原理 3.3 啟發式搜索7/15/202261A算法流程（續）ADD(mj, OPEN), 標記

29、mj到n的指針；IF f(n, mk)f(mk) THEN f(mk):=f(n, mk), 標記mk到n的指針；IF f(n, ml)f(ml,) THEN f(ml):=f(n, ml),標記ml到n的指針, ADD(ml, OPEN);7, OPEN中的節點按f值從小到大排序；8, GO LOOP；第三章 一般搜索原理 3.3 啟發式搜索7/15/202262最佳圖搜索算法A*（A*算法）在A算法中，如果對于任意點n滿足條件：h(n)h*(n)則A算法稱為A*算法。如果存在從初始節點S0目標節點Sg的最小路徑， A*算法就一定能搜索到第三章 一般搜索原理 3.3 啟發式搜索7/15/20

30、2263A*算法估價函數舉例在問題求解過程中，不可能明確知道h*(n) ，可根據經驗估計下界范圍條件例如，8數碼問題如取h(n) = “不在位”的牌數，可估計出至少要移動h(n) 步，才能達到目標，因此，有h(n) h*(n) 如取h (n) = 每個牌與目標位置的距離和，同樣可估計出至少要移動h(n) 步，才能達到目標，因此，有h(n) h*(n) 2 8 31 6 47 51 2 38 47 6 5第三章 一般搜索原理 3.3 啟發式搜索7/15/2022643.4 與或樹搜索第三章 一般搜索原理 3.4 與或樹搜索7/15/202265與或樹搜索 與或樹的搜索是實現用與或樹表示的問題的求

31、解。與或樹的搜索過程將形成一棵與或樹，這種由搜索過程形成的與或樹稱為搜索樹。與或樹的搜索過程實際上是一個不斷尋找解樹的過程。第三章 一般搜索原理 3.4 與或樹搜索7/15/202266幾個概念由可解節點構成，并且由這些可解節點可以推出初始節點為可解節點的子樹稱為解樹，解樹中一定包含初始節點。沒有子節點的節點稱為端節點。本原問題所對應的節點稱為終止節點。可解問題所對應的節點稱為可解節點。反之為不可解節點。終止節點是可解節點。子節點都是可解節點的與節點是可解節點至少一個子節點是可解節點的或節點是可解節點。第三章 一般搜索原理 3.4 與或樹搜索7/15/202267與或樹搜索的一般過程(1)把原

32、始問題作為初始節點S0，并把它作為當前節點；(2)應用分解或等價變換操作對當前節點進行擴展(3)為每個子節點設置指向父節點的指針(4)選擇合適的子節點作為當前節點，反復執行第(2)步和第(3)步，多次調用標記過程，直到初始節點被標記。如果某個節點被標記為可解節點，則其不可解的后繼節點就可從搜索樹中刪去；如果被標記為不可解節點則其后繼節點也可從搜索樹中刪去。第三章 一般搜索原理 3.4 與或樹搜索7/15/202268寬度優先搜索成功是把第一個節點(n)從OPEN表移至CLOSED表可擴展處理把S放入OPEN表是否否OPEN為空？節點(n)是否有可擴展？失敗開始不可擴展處理S標為可解節點？是否S

33、標為不可解節點？是否失敗第三章 一般搜索原理 3.4 與或樹搜索7/15/202269寬度優先搜索（續）可擴展處理把節點(n)標記為不可解節點把n的后繼節點放入OPEN表的末端，提供返回節點n的指針不可擴展處理若n的后繼節點中有終節點，則標記其為可解節點從OPEN表中刪去具有可解先輩的節點調用可解標記過程，標記其先輩節點從OPEN表中刪去具有不可解先輩的節點調用不可解標記過程，標記其先輩節點返回返回第三章 一般搜索原理 3.4 與或樹搜索7/15/202270寬度優先搜索舉例（一） t1,t2,t3為終節點ABC為端節點搜索過程：擴展1號生成2、3號節點，都是非終節點擴展2號生成A、4號節點，

34、都是非終節點 擴展3號生成t1、5號節點，t1是終節點，標記為可解節點，調用可解標記過程，由于t1的父節點是與節點，不能確定其父節點是可解t2A13542BCt1t3第三章 一般搜索原理 3.4 與或樹搜索7/15/202271寬度優先搜索舉例（二）A是端節點，不可擴展，調用不可解標記過程，由于A的父節點是或節點，不能確定其父節點是不可解擴展4號生成t2、B節點，t2是終節點，標記為可解節點，調用可解標記過程，由于t2的父節點是或節點，標節點4為可解，繼續向上，標節點2為可解，但無法確定標節點1擴展5號生成t3、C節點，t3是終節點，標記為可解節點，調用可解標記過程，由于t3的父節點是或節點，

35、標節點5為可解，繼續向上，標節點3為可解，最后可確定節點1為可解t2A13542BCt1t3第三章 一般搜索原理 3.4 與或樹搜索7/15/202272深度優先搜索成功是把第一個節點(n)從OPEN表移至CLOSED表可擴展處理把S放入OPEN表是否否OPEN為空？節點(n)是否有可擴展？失敗開始不可擴展處理S標為可解節點？是否S標為不可解節點？是否失敗節點(n)深度=d？是否第三章 一般搜索原理 3.4 與或樹搜索7/15/202273深度優先搜索（續）可擴展處理把節點(n)標記為不可解節點把n的后繼節點放入OPEN表的前端，提供返回節點n的指針不可擴展處理若n的后繼節點中有終節點，則標記

36、其為可解節點從OPEN表中刪去具有可解先輩的節點調用可解標記過程，標記其先輩節點從OPEN表中刪去具有不可解先輩的節點調用不可解標記過程，標記其先輩節點返回返回第三章 一般搜索原理 3.4 與或樹搜索7/15/2022743.5 與或樹的啟發式搜索第三章 一般搜索原理 3.5 與或樹的啟發式搜索7/15/202275與或樹的啟發式搜索 與或樹的啟發式搜索過程是一種利用搜索過程所得到的啟發性信息尋找最優解樹的過程。對搜索的每一步，算法都試圖找到一個最有希望成為最優解樹的子樹。最優解樹是指代價最小的那棵解樹。第三章 一般搜索原理 3.5 與或樹的啟發式搜索7/15/202276解樹的代價設n為節點

37、，n1，n2，nk為其子節點， h(n)為節點n的代價， c(n，ni)為節點n到其子節點ni的邊代價若n為終節點，則h(n)0。若n為或節點，則h(n)min(c(n，ni)+h(ni)若n為與節點，則n的代價可用和代價法或最大代價法。和代價法：h(n)(c(n，ni)+h(ni)最大代價法：h(n)maxc(n，ni)+h(ni) 若n是端節點，但非終節點，則n不可擴展，h(n)。解樹的代價，為根節點的代價。第三章 一般搜索原理 3.5 與或樹的啟發式搜索7/15/202277解樹的代價舉例圖中與或樹包括兩棵解樹左邊的解樹由S、A、t1、C及t3組成右邊的解樹由S、B、t2、D及t4組成。

38、t1、t2、t3、t4為終節點E 、 F是端節點左邊的解樹:按和代價：h(S)2+4+6+214按最大代價：h(S)2+6+210右邊的解樹:按和代價：h(S)1+5+3+211按最大代價：h(S)1+5+28可見，右邊的解樹是最優解樹。t2SBDCAEFt1t3t464222351第三章 一般搜索原理 3.5 與或樹的啟發式搜索7/15/202278希望解樹 為了找到最優解樹，搜索過程的任何時刻都應該選擇那些最有希望成為最優解樹一部分的節點進行擴展由于這些節點及其父節點所構成的與或樹最有可能成為最優解樹的一部分，因此稱為希望解樹，簡稱為希望樹。需要注意，希望解樹是會隨搜索過程而不斷變化的。希

39、望樹定義：初始節點S在希望樹T中若n為具有子節點n1，n2，nk的或節點，其子節點ni在希望樹T中的充分必要條件： h(ni)min(c(n，nt)+h(nt)若n為與節點，其子節點都在希望樹T。第三章 一般搜索原理 3.5 與或樹的啟發式搜索7/15/202279與或樹的啟發式搜索過程成功是計算希望樹T可擴展處理把S放入OPEN表，計算h(S)是否否節點(n)是否可擴展？開始終節點處理S標為可解節點？是否S標為不可解節點？是否失敗把OPEN表中第一個屬于T的節點(n)移至CLOSED表節點(n)是終節點？不可擴展處理第三章 一般搜索原理 3.5 與或樹的啟發式搜索7/15/202280與或樹

40、的啟發式搜索過程（續1）可擴展處理把節點(n)標記為不可解節點把n的后繼節點放入OPEN表的末端，提供返回節點n的指針不可擴展處理計算這些子節點及其先輩節點的h值從OPEN表中刪去具有不可解先輩的節點在T上運用不可解標記過程，標記其先輩節點返回返回第三章 一般搜索原理 3.5 與或樹的啟發式搜索7/15/202281與或樹的啟發式搜索過程（續2）把節點(n)標記為可解節點終節點處理從OPEN表中刪去具有可解先輩的節點在T上運用可解標記過程，標記其先輩節點返回第三章 一般搜索原理 3.5 與或樹的啟發式搜索7/15/202282與或樹的啟發式搜索舉例 在該例子中，搜索過程每次擴展節點時都同時擴展

41、兩層，且按一層或節點、一層與節點的間隔方式進行擴展。后面將要討論的博弈樹就是這種結構。第三章 一般搜索原理 3.5 與或樹的啟發式搜索7/15/202283擴展初始節點S后S擴展后如圖所示B、C、E、F的h值由啟發函數估計節點S、A、D的h值按和代價法計算。此時，S的右子樹是當前的希望樹接著，對右子樹的E節點進行擴展SDFCA8338372BE第三章 一般搜索原理 3.5 與或樹的啟發式搜索7/15/202284右子樹的E節點擴展后E擴展后如圖所示各端節點h值由啟發函數估計先輩節點的h值按和代價法計算。此時，S的左子樹代價小，因此，當前左子樹又變成了希望樹接著，對左子樹的B節點進行擴展SDFC

42、A8339116BEF372272第三章 一般搜索原理 3.5 與或樹的啟發式搜索27/15/202285H左子樹的B節點擴展后S9CA833F372DF11E76220206JL22K2IGB第三章 一般搜索原理 3.5 與或樹的啟發式搜索7/15/202286H左子樹的C節點擴展后9833F372DF11E76220206JL22K2SIGBN020952PMCA第三章 一般搜索原理 3.5 與或樹的啟發式搜索7/15/2022873.6 博弈樹搜索第三章 一般搜索原理 3.6 博弈樹搜索7/15/202288博弈博弈是一類富有智能行為的競爭活動，如下棋、打牌、戰爭等博弈可分為雙人完備信息

43、博弈奔和機遇性博弈雙人完備信息博弈：兩位選手對壘，輪流走步，每一方不僅知道對方已經走過的棋步，而且還能估計出對方未來的走步。對弈的結果是一方贏，另一方輸；或者雙方和局。例如，有象棋、圍棋等。機遇性博弈：指存在不可預測性的博弈，例如擲幣等。我們只討論雙人完備信息博弈問題。第三章 一般搜索原理 3.6 博弈樹搜索7/15/202289博弈過程分析在博弈過程的每一步，可供雙方選擇的行動方案都可能有多種。雙方都希望自己能夠獲勝。任何一方走步時，都是選澤對自己最為有利，而對另一方最為不利的行動方案。雙方交替選擇行動方案，直到一方勝利或雙方和局。第三章 一般搜索原理 3.6 博弈樹搜索7/15/202290從MAX方看博弈假設博弈的一方為MAX，另一方為MIN。可供自己選擇的行動方案之間是“或”的關系主動權掌握在自己手里，選擇哪個方案完全由自己決定；可供MIN選擇的行動方案之間是“與”的關系主動權掌握在MIN的手里，任何一個方案都有可能被MIN選中，MAX必須防止那種對自己最為不利的情況的發生。第三章 一般搜索原理 3.6 博弈樹搜索