1、第四章 搜索技術狀態空間法問題歸約法博弈樹搜索局部搜索第1頁，共126頁。How to find the best path in game ?第2頁，共126頁。迷宮問題s-s s s s s s-s-s-ss-s-s-s s s s s s s s-s-s-s-s S0Sg第3頁，共126頁。搜索的挑戰組合爆炸魔方問題博弈問題皇后問題行商問題排課問題（調度問題）背包問題 第4頁，共126頁。數碼問題1238456712384567（目標狀態）（初始狀態）八數碼難題（8-puzzle problem）42618357第5頁，共126頁。4.1 狀態圖概念狀態圖的概念 狀態圖(狀態空間圖)實際

2、上是一類問題的抽象表示。許多智力問題(八數碼問題、梵塔問題、旅行商問題、八皇后問題、農夫過河問題等)。 實際問題（如路徑規劃、定理證明、演繹推理、機器人行動規劃等）都可以歸結為在某一狀態圖中尋找目標或路徑的問題。第6頁，共126頁。農夫過河問題 有一個農夫帶一條狼、一只羊和一棵白菜過河。如果沒有農夫看管，則狼要吃羊，羊要吃白菜。但是船很小，只夠農夫帶一樣東西過河。問農夫該如何解此難題？ 第7頁，共126頁。農夫過河問題狀態空間法表示以向量（人，狼，羊，菜）表示狀態，其中每個變元可取0或1，取0表示在左岸（出發點），取1表示在右岸初態是：（0，0，0，0）終態是：（1，1，1，1）非法中間狀態有

3、： （0，0，1，1），（0，1，1，0），（0，1，1，1）， （1，1，0，0），（1，0，0，1），（1，0，0，0）。 第8頁，共126頁。（1，0，0，1）（0，0，0，0）（1，0，1，0）（1，1，0，0）（0，0，1，0）（1，1，1，0）（1，0，1，1）（0，1，1，0）（0，0，1，1）（人，狼，羊，菜）（0，0，0，1）（1，1，0，1）（0，1，0，1） （1，1，1，1）第9頁，共126頁。4.2 狀態空間法問題的狀態空間表示(狀態圖表示) 狀態空間的三元組(S, O, G)表示. S:初始狀態集合; O: 操作集合; G:目標狀態集合狀態空間的搜索策略(狀態圖搜索

4、)廣度優先搜索, 深度優先搜索, 啟發式搜索第10頁，共126頁。狀態空間表示的概念例如下棋、迷宮及各種游戲。OriginalStateMiddleStateGoalState第11頁，共126頁。三數碼難題123123123312312312初始棋局目標棋局第12頁，共126頁。1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345八數碼難題的寬度優先搜索樹1345612384567123845671238

5、4567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567第13頁，共126頁。狀態圖搜索圖搜索是指在狀態圖中尋找目標或路徑的搜索。所謂搜索，顧名思義，就是從初始節點出發，沿著與之相連的邊試探地前進，尋找目標節點的過程(也可以反向進行)。問題狀態圖搜索解解是由初始狀態到目標狀態的路徑第14頁，共126頁。狀態圖搜索相關問題狀態選擇解的性質：存在、分布、質量搜索策略第15頁，共126頁。圖搜索策略 圖搜索控制策略一種在狀

6、態圖中尋找路徑的方法。圖中每個節點對應一個狀態，每條連線對應一個操作符。圖搜索涉及兩個主要數據結構：open表 closed表第16頁，共126頁。OPEN 表 OPEN表是一種動態數據結構，專門登記當前待考查（待訪問）的節點，也叫未擴展節點表 。節點父節點編號OPEN表open表中，每個節點信息還包括指向父節點的返回指針（即父節點地址）第17頁，共126頁。CLOSED 表 Closed表是一種動態數據結構，記錄訪問過的節點，也叫已擴展節點表 ，其初始為空表。 編號節點父節點編號CLOSED表第18頁，共126頁。開始把S放入OPEN表OPEN表為空表？把第一個節點(n)從OPEN表移至CL

7、OSED表n為目標節點嗎？把n的后繼節點放入OPEN表的末端，提供返回節點n的指針修改指針方向重排OPEN表失敗成功 圖搜索過程框圖是是否否搜索策略即體現在這里第19頁，共126頁。按搜索軌跡分類圖式搜索：搜索過程中，搜索路徑允許形成回路。樹式搜索：搜索過程中，搜索路徑不允許形成回路。線式搜索：擴展節點每次只擴展一個節點。SGSG第20頁，共126頁。搜索樹的概念 一個可以搜索出某個可行解的問題，如“農夫、白菜、羊、狼”和“八數碼難題”等，雖然從表面上看上去和“樹”這種結構無關，但是整個搜索過程中的可能試探點所行成的搜索空間總可以對應到一顆搜索樹上去。將各類形式上不同的搜索問題抽象并統一成為搜

8、索樹的形式，為算法的設計與分析帶來巨大的方便。 第21頁，共126頁。（1，0，0，1）（0，0，0，0）（1，0，1，0）（1，1，0，0）（0，0，1，0）（1，1，1，0）（1，0，1，1）（0，1，1，0）（0，0，1，1）（人，狼，羊，菜）（0，0，0，1）（1，1，0，1）（0，1，0，1） （1，1，1，1）第22頁，共126頁。由于搜索具有探索性，所以要提高搜索效率(盡快地找到目標節點)，或要找最佳路徑(最佳解)就必須注意搜索策略。對于狀態圖搜索，已經提出了許多策略，它們大體可分為盲目搜索（bland search)和啟發式搜索（heuristic search）兩大類。盲目搜

9、索是無向導搜索。啟發式搜索是有向導搜索，即利用啟發信息（函數）引導去尋找問題解。搜索策略分類第23頁，共126頁。盲目搜索盲目搜索又叫做無信息搜索，一般只適用于求解比較簡單的問題。種類：寬度優先搜索深度優先搜索等代價搜索第24頁，共126頁。圖搜索策略寬度優先深度優先啟發式搜索一種在圖中尋找路徑的方法。第25頁，共126頁。寬度優先搜索策略優先搜索狀態空間中離初始狀態近的節點(狀態特點:具有完備性, 占用空間搜索算法 數據結構:OPEN表 : 先進先出隊列,存放待擴展的節點. 節點(狀態) 父節點編號(返回指針)CLOSED表 : 存放已被擴展過的節點.編號 節點 父節點編號第26頁，共126

10、頁。開始把S放入OPEN表OPEN表為空表？把第一個節點(n)從OPEN表移至CLOSED表是否有后繼節點為目標節點？擴展n，把n的后繼節點放入OPEN表的末端，提供返回節點n的指針失敗成功 寬度優先算法框圖是否是否 算法否第27頁，共126頁。寬度優先搜索算法Step1: 把初始節點S0放入OPEN表中;Step2: 若OPEN表為空,則搜索失敗,退出.Step3: 移出OPEN表中第一個節點N放入CLOSED表 中, 并標以順序號n;Step4: 若目標節點Sg=N, 則搜索成功,結束.Step5: 若N不可擴展, 則轉Step2;Step6: 擴展N, 將生成的一組子節點配上指向N的指針

11、后, 放入OPEN表尾部, 轉 Step2;第28頁，共126頁。 例子八數碼難題（8-puzzle problem） 1238456712384567（目標狀態）（初始狀態）規定：將牌移入空格的順序為：從空格左邊開始順時針旋轉。不許斜向移動，也不返回先輩節點。從圖可見，要擴展26個節點，共生成26個節點之后才求得解（目標節點）。第29頁，共126頁。1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345圖

12、八數碼難題的寬度優先搜索樹13456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567第30頁，共126頁。寬度優先搜索(Breadth-First Strategy)新的節點被插入到棧OPEN的后部12345OPEN= (1)CLOSED=( )6789101112131415第31頁，共126頁。寬度優先搜索(Breadth-First Strategy)新的節點被插

13、入到棧OPEN的后部12345OPEN= (2,3)CLOSED=(1 )6789101112131415第32頁，共126頁。寬度優先搜索(Breadth-First Strategy)新的節點被插入到棧OPEN的后部12345OPEN= (3,4,5)CLOSED=(1,2 )6789101112131415第33頁，共126頁。寬度優先搜索(Breadth-First Strategy)新的節點被插入到棧OPEN的后部12345OPEN= (4,5,10,11)CLOSED=(1,2,3 )6789101112131415第34頁，共126頁。寬度優先搜索(Breadth-First S

14、trategy)新的節點被插入到棧OPEN的后部12345OPEN= (5,10,11,6,7)CLOSED=(1,2,3,4 )6789101112131415第35頁，共126頁。寬度優先搜索(Breadth-First Strategy)新的節點被插入到棧OPEN的后部12345OPEN= (10,11,6,7,8,9)CLOSED=(1,2,3,4,5 )6789101112131415第36頁，共126頁。寬度優先搜索(Breadth-First Strategy)新的節點被插入到棧OPEN的后部12345OPEN= (11,6,7,8,9,12,13)CLOSED=(1,2,3,4

15、,5,10 )6789101112131415第37頁，共126頁。深度優先搜索策略新節點優先擴展, 直到達到一定的深度限制.若找不到目標或無法在擴展時,回溯到另一節點繼續擴展.特點: 需要深度限制, 需要回溯控制, 省空間探索算法: 數據結構: OPEN表 : 后進先出隊列,存放待擴展的節點. CLOSED表 : 存放已被擴展過的節點.除擴展后的子節點應放入到OPEN表的首部以外,與寬度優先算法一樣.第38頁，共126頁。深度優先算法框圖 算法開始把S放入OPEN表OPEN表為空表？把第一個節點(n)從OPEN表移至CLOSED表是否有后繼節點為目標節點？擴展n，把n的后繼節點放入OPEN表

16、的前端，提供返回節點n的指針失敗成功是否是否第39頁，共126頁。深度優先搜索算法Step1: 把初始節點S0放入OPEN表中;Step2: 若OPEN表為空,則搜索失敗,退出.Step3: 移出OPEN中第一個節點N放入CLOSED表 中, 并標以順序號n;Step4: 若目標節點Sg=N, 則搜索成功,結束.Step5: 若N不可擴展, 則轉Step2;Step6: 擴展N, 將生成的一組子節點配上指向N的指針后, 放入OPEN表首部, 轉 Step2;第40頁，共126頁。深度優先搜索(Depth-First Strategy)新的節點被插入到棧OPEN的前部12345OPEN= (1)

17、CLOSED=( )6789101112131415第41頁，共126頁。Depth-First Strategy新的節點被插入到棧OPEN的前部12345OPEN = (2, 3)CLOSED=( 1 )6789101112131415第42頁，共126頁。Depth-First Strategy 新的節點被插入到棧OPEN的前部12345OPEN = (4, 5, 3)CLOSED=( 1,2 )6789101112131415第43頁，共126頁。Depth-First Strategy新的節點被插入到棧OPEN的前部12345CLOSED=( 1,2,4 )67OPEN = (6,7,

18、 5, 3)89101112131415第44頁，共126頁。Depth-First Strategy新的節點被插入到棧OPEN的前部1234567891011CLOSED=( 1,2,4,6 )OPEN = (7, 5, 3)12131415第45頁，共126頁。Depth-First Strategy新的節點被插入到棧OPEN的前部1234567891011CLOSED=( 1,2,4,6,7 )OPEN = (5, 3)12131415第46頁，共126頁。Depth-First Strategy新的節點被插入到棧OPEN的前部1234567891011CLOSED=( 1,2,4, 5

19、,6,7 )OPEN = (8,9,3)12131415第47頁，共126頁。Depth-First Strategy新的節點被插入到棧OPEN的前部1234567891011CLOSED=( 1,2,4,5, 6,7 ,8)OPEN = (9, 3)12131415第48頁，共126頁。Depth-First Strategy新的節點被插入到棧OPEN的前部123456789121011131415CLOSED=( 1,2,4, 5,6,7, 8,9)OPEN = (3)第49頁，共126頁。Depth-First Strategy新的節點被插入到棧OPEN的前部12345678912101

20、1131415CLOSED=( 1,2,4, 5,6,7,8,9,3)OPEN = (10,11)第50頁，共126頁。Depth-First Strategy新的節點被插入到棧OPEN的前部1234567891011CLOSED=( 1,2,4, 5,6,7,8,9,3,10)12131415OPEN = (12,13,11)第51頁，共126頁。代價樹搜索代價樹：搜索樹中每條連接弧線上的有關代價,表示時間、距離等花費。代價樹搜索（等代價搜索） ：是寬度優先搜索的一種推廣，不是沿著等長度路徑斷層進行擴展，而是沿著等代價路徑斷層進行擴展。 *若所有連接弧線具有相等代價，則簡化為寬度優先搜索算法

21、。第52頁，共126頁。算法使用符號 c(i,j)：把從節點i到其后繼節點j的連接弧線代價記為c(i,j) g(i)：把從起始節點S到任一節點i的路徑代價記為g(i). 在搜索樹（非循環路徑）上，假設g(i)是從起始節點S到節點i的最少路徑上的代價。 等代價搜索方法以g(i)的遞增順序擴展其節點。第53頁，共126頁。開始把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節點i從OPEN表移至CLOSED表是否有后繼節點為目標節點？失敗成功等代價搜索算法框圖是否是否令g(s)=0S是否目標節點？是成功否開始把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節點i從OPEN表移至

22、CLOSED表是否有后繼節點為目標節點？失敗成功是是否令g(s)=0S是否目標節點？是成功開始把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節點i從OPEN表移至CLOSED表是否有后繼節點為目標節點？失敗成功是是否令g(s)=0S是否目標節點？是成功擴展i，計算其后繼節點j的g(j)，并把后繼節點放入OPEN表開始把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節點i從OPEN表移至CLOSED表是否有后繼節點為目標節點？失敗成功是是否令g(s)=0S是否目標節點？是成功第54頁，共126頁。等代價搜索算法（1） 把起始節點放到未擴展節點表OPEN中。如果此起始節點為一

23、目標節點，則求得一個解；否則令g（S）=0。（2） 如果OPEN是個空表，則沒有解而失敗退出。（3） 從OPEN 表中選擇一個節點i，使其g（i）為最小。如果有幾個節點都合格，那么就要選擇一個目標節點作為節點 i（要是有目標節點的話）；否則，就從中選一個作為節點i。把節點i從OPEN表移至擴展節點表CLOSED中。（4） 如果節點i為目標節點，則求得一個解。（5） 擴展節點i。如果沒有后繼節點，則轉向第（2）步。（6） 對于節點i的每個后繼節點j，計算g（j）=g（i）+c（i,j），并把所有后繼節點j放進OPEN表。提供回到節點i的指針。（7） 轉向第（2）步。第55頁，共126頁。寬度優先

24、d = 1d = 2d = 3d = 4寬度優先搜索：沿著等長度路徑斷層進行擴展g1g2g3g4等代價搜索等代價搜索：沿等代價路徑斷層進行擴展比較寬度優先搜索與等代價搜索第56頁，共126頁。ADBECFGS34445543搜索樹（非循環路徑）2SADBDEACEEBBFDFBFCEACGGCGFG33333222444444444444555555第57頁，共126頁。等代價搜索算法SADBDAEEBBFBFCEACGGGFC34455525433478961011CEDFG4511121313134 在每一步, 選擇具有最低累計權值的點進行擴展第58頁，共126頁。啟發式搜索盲目搜索的問題

25、： “組合爆炸”利用問題的某些控制信息(如解的特征)來引導搜索.這種控制信息稱為搜索的啟發信息.利用啟發式信息定義節點的啟發函數 h(n)特點: 深度優先, 效率高, 無回溯, 但不能保證得到最佳解 。探索算法:全局擇優搜索(最好優先搜索), 局部擇優搜索數據結構：OPEN表 、 CLOSED表第59頁，共126頁。 啟發信息啟發式搜索就是利用啟發性信息進行制導的搜索。啟發性信息就是有利于盡快找到問題之解的信息。按其用途劃分，啟發性信息一般可分為以下三類： (1)用于擴展節點的選擇，即用于決定應先擴展哪一個節點，以免盲目擴展。 (2)用于生成節點的選擇，即用于決定應生成哪些后續節點，以免盲目地

26、生成過多無用節點。 (3)用于刪除節點的選擇，即用于決定應刪除哪些無用節點，以免造成進一步的時空浪費。第60頁，共126頁。重排OPEN表，使搜索沿某個被認為最有希望的路徑擴展。應用這種排序過程，需要某些估算節點“希望”的量度。用來估算節點希望程度的量度，叫做估價函數（evaluation function），有時也叫作啟發函數。一個節點的“希望”（promise）有幾種不同 的定義方法。 在狀態空間問題中，一種方法是估算目標節點到此節點的距離；估算全路徑的長度或難度（包括此節點）。我們用符號f來標記估價函數，用f（n）表示節點n的估價函數值。啟發函數第61頁，共126頁。如何定義一個估價（啟

27、發）函數呢？估價（啟發）函數并無固定的模式，需要具體問題具體分析。通?？梢詤⒖嫉乃悸酚校?（1） 一個節點到目標節點的距離或差異的度量； （2）一個節點處在最佳路徑上的概率； （3）或者根據經驗的主觀打分。啟發函數第62頁，共126頁。八數碼難題（8-puzzle）f1(T) = 恰好正確地處在目標狀態的字碼數目:13247658f1= 4從實用角度，計算與目標的距離更有實際意義！f2= 413247658f2(T) =沒有處在目標狀態的字碼數目（相當于粗略地給出了當前狀態與目標的距離）12384765目標：第63頁，共126頁。f3(T) = 不在目標位置的字碼距離目標位置水平距離和垂直距離

28、之和。該函數給出了一個更好的距離評估f2= 1 + 1 + 2 + 2 = 61324765812384765目標：第64頁，共126頁。 啟發式搜索算法 啟發式搜索要用啟發函數來導航，其搜索算法就要在狀態圖一般搜索算法基礎上再增加啟發函數值的計算與傳播過程，并且由啟發函數值來確定節點的擴展順序。兩種策略: 局部擇優搜索 擴展節點N后僅對N的子節點按啟發函數值大小以升序排序，再將它們依次放入OPEN表的首部。全局擇優搜索 在OPEN表中保留所有已生成而未考察的節點，并用啟發函數h(x)對它們全部進行估價，從中選出最優節點進行擴展，而不管這個節點出現在搜索樹的什么地方。第65頁，共126頁。全局

29、擇優搜索算法Step1: 把初始節點S0放入OPEN表中,計算h(S0);Step2: 若OPEN表為空,則搜索失敗,退出.Step3: 移出OPEN中第一個節點N放入CLOSED表 中, 并標以順序編號n;Step4: 若目標節點Sg=N, 則搜索成功,結束.Step5: 若N不可擴展, 則轉Step2;Step6: 擴展N,計算每個子節點的函數值h(x),將所有子節點配上指向N的返回指針后放入OPEN表中, 再按函數值的升序重新排序OPEN表中的節點, 轉 Step2;第66頁，共126頁。全局擇優搜索例子九宮重排問題, 定義評價函數; h(n):目標格局與現格局(Sn)相比,位置不同的牌

30、數. 初始格局S0 目標格局Sg 2 8 3 1 2 3 1 4 = 8 4 7 6 5 7 6 5h(S0) = 3第67頁，共126頁。局部擇優搜索算法Step1: 把初始節點S0放入OPEN表中,計算h(S0);Step2: 若OPEN表為空,則搜索失敗,退出.Step3: 移出OPEN中第一個節點N放入CLOSED表 中, 并標以順序編號n;Step4: 若目標節點Sg=N, 則搜索成功,結束.Step5: 若N不可擴展, 則轉Step2;Step6: 擴展N,計算每個子節點的函數值h(x),并將所有子節點按函數值的升序排序后, 配上指向N的返回指針放入OPEN表的首部, 轉 Step

31、2;第68頁，共126頁。局部搜索算法 特點： 從單獨的一個當前狀態出發，通常只移動到與之相鄰的狀態，并且不保留解的路徑。優點：需要很少的內存經常能在很大或無限的狀態空間中找到合理的解第69頁，共126頁。爬山法（Hill climbing）一種基本的局部啟發式搜索方法基本算法：擴展節點N后僅對N的子節點按啟發函數值大小以升序排序，再將選擇啟發函數值最小的節點放入OPEN表的首部。（啟發函數值越小離目標越近）相當于深度優先算法+啟發式搜索線式搜索，不能回溯向目標值增加的方向持續移動第70頁，共126頁。啟發式搜索:A算法評價函數 f(x) = g(x) + h(x)，表示通過節點x的估計代價值

32、。nmSGg(n)g(m)h(n)h(m)比較f(n)和f(m) 大小，決定節點搜索順序，即在OPEN表中的順序第71頁，共126頁。啟發式搜索:A算法評價函數 f(x) = g(x) + h(x) 當f(x) = g(x) 時，為寬度優先搜索當f(x) = 1/g(x)時，為深度優先搜索當f(x) = h(x) 時，為全局優先搜索nmSGg(n)g(m)h(n)h(m)第72頁，共126頁。啟發式搜索:A算法評價函數的一般形式 : f(n) = g(n) + h(n)g(n):從S0到Sn的實際代價(搜索的橫向因子)h(n):從N到目標節點的估計代價,稱為啟發函數 (搜索的縱向因子);特點:

33、 效率高, 無回溯, 搜索算法OPEN表 : 存放待擴展的節點. CLOSED表 : 存放已被擴展過的節點.第73頁，共126頁。啟發式搜索:A算法Step1: 把附有計算f(S0)初始節點S0放入OPEN表中;Step2: 若OPEN表為空,則搜索失敗,退出.Step3: 移出OPEN中第一個節點N放入CLOSED表中, 并標以順序編號n;Step4: 若目標節點Sg=N, 則搜索成功,結束.Step5: 若N不可擴展, 則轉Step2;Step6: 擴展N, 生成一組附有f(x)的子節點,作完以下處理后,將余下子節點配上指向N的返回指針后放入OPEN表中, 再按函數值的升序重新排序OPEN

34、表中的節點, 轉 Step2;刪除重復節點和修改返回指針.第74頁，共126頁。八數碼難題（8-puzzle problem）12384567（目標狀態）12384567（初始狀態）A算法的應用第75頁，共126頁。八數碼難題:評價函數 簡單的評價函數 h(n)=d(n)+W(n)其中：d(n)是搜索樹中節點n的深度；W(n)用來計算對應于節點n的數據庫中錯放的棋子個數。 初始棋局f值等于0+4=4 12384567（初始狀態）第76頁，共126頁。5723451238456712384567123845671+31+51+511238456712384567123845672+42+32+3

35、12384567123845673+2 3+412384567123845673+3 3+4123845674+181324567123845675+05+2八數碼難題的搜索樹1238460+475第77頁，共126頁。啟發式搜索:A*算法評價函數的一般形式:f(n) = g(n) + h(n) 且 h(n) = h*(n)g(n),h(n):定義同A算法;h*(n):從N到目標節點的最短路徑; 稱此時的A算法為A*算法.A*算法的特征:A*是可采納的:只要最短路徑存在,就一定能找出.如果有 h1(n) = h2(n) = h*(n), 那么h2比h1展開更少的節點.廣度優先搜索是當h(n)=

36、0時的A*算法的特例.第78頁，共126頁。啟發式搜索:A*算法評價函數 f(x) = g(x) + h(x) ( 當h(n) = h*(n) )nSGg(n)=g*(n)h(n) = h*(n) A*算法要求保守估計： f(n) 0。4)： h(n)=h*(n)第81頁，共126頁。為什么A*算法低估h值在A*算法中，對所有的x存在h(x)h*(x)（低估)在A*算法中,只有對h值低估才能獲得優化的搜索性能第82頁，共126頁。為什么A*算法低估h值舉例：SADFBEHCGI11111111111紅色值表示真實的剩余代價3212132132154432多估在多估情況下：SADF1+31+51

37、+4B2+2ABC3+1CG4并不是優化路徑!第83頁，共126頁。為什么A*算法低估h值舉例：32SADFBEHCGI11111111111322111紅色值表示真實的剩余代價如果h被低估:SADF1+11+21+310023121低估AB2+0C3+0BG4GCDEE3 !2+1第84頁，共126頁。f1f2f3f4A*A*算法沿f函數進行擴展第85頁，共126頁。啟發式搜索算法A*Step1: 把初始節點S0放入OPEN表中;Step2: 若OPEN表為空,則搜索失敗,退出.Step3: 移出OPEN中第一個節點N放入CLOSED表 中, 并標以順序號n;Step4: 若目標節點Sg=N

38、, 則搜索成功,結束.Step5: 若N不可擴展, 則轉Step2;Step6: 擴展N, 生成一組子節點, 對這組子節點作如下處 理后, 放入OPEN表, 按評價函數的升序重新排序 OPEN表, 轉 Step2;刪除重復節點和修改返回指針處理.第86頁，共126頁。八數碼難題:h1(T) 0 啟發函數為0注意: h3(T) h2(T) h1(T) h2= 413247658h2(T) =沒有處在目標狀態的字碼數目h3= 1 + 1 + 2 + 2 = 613247658h3(T) =不在目標位置的字碼距離目標位置水平距離和垂直距離之和。12384765目標：曼哈頓距離第87頁，共126頁。八

39、數碼難題舉例2 8 31 6 47 52 8 31 6 4 7 52 8 31 47 6 52 8 31 6 47 5 2 8 3 6 41 7 52 8 3 1 47 6 52 31 8 47 6 52 8 31 4 7 6 52 8 31 6 7 5 4 8 32 6 41 7 52 8 36 41 7 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 8 31 4 57 6 2 8 31 67 5 42 3 1 8 47 6 52 8 1 4 37 6 52 8 1 6 37 5 4h1 = 00111222223333333333h2 = 錯誤數

40、目0+41+51+31+52+32+32+43+33+43+2Notselectedh3 =曼哈頓距離0+51+61+41+62+52+32+5第88頁，共126頁。Robot navigationCost of one horizontal/vertical step = 1Cost of one diagonal step = 2 f(N) = g(N) + h(N), with h(N) =距離目標位置水平距離和垂直距離之和第89頁，共126頁。Robot Navigation第90頁，共126頁。Robot Navigation02115877347676328645233365244

41、355465645f(N) = h(N), with h(N) =距離目標位置水平距離和垂直距離之第91頁，共126頁。Robot Navigation02115877347676328645233365244355465645f(N) = h(N), with h(N) =距離目標位置水平距離和垂直距離之70第92頁，共126頁。Robot Navigationf(N) = g(N)+h(N), with h(N) =距離目標位置水平距離和垂直距離之和021158773476763286452333652443554656457+06+16+18+17+07+26+17+26+18+17+2

42、8+37+26+36+35+45+44+54+53+63+62+78+37+47+46+55+66+35+62+73+84+75+64+73+84+73+83+82+92+93+102+93+82+91+101+100+11第93頁，共126頁。搜索算法小結樹搜索-盲目搜索-廣度優先搜索 -深度優先搜索-有界深度優先 -代價樹搜索 -啟發式搜索-全局擇優搜索(最好優先) -局部擇優搜索(爬山法) -A算法( 基于: f(n)=g(n)+h(n) ) A*算法(最佳搜索: h(n) 8 4 7 5 3 7 6 5請針對TSP問題，提出啟發式搜索策略，并對搜索效率進行分析？第100頁，共126頁。

43、4.3 問題歸約法問題歸約的概念問題歸約的描述: 三元組(S0, O, P)表示. S0:初始問題; P:本原問題集合O:操作算子集;將問題化成若干子問題.問題歸約的最終目標: 原問題 = 本原問題狀態空間法是問題歸約法的特例.問題歸約的與或圖表示第101頁，共126頁。與或圖表示AAC6C5C4C3C2C1C6C5C4C3C2C1m1m2或節點與節點葉節點(或稱:端節點)3連接弧第102頁，共126頁。節點的可解性判別AC6C5C4C3C2C1m1m2或節點與節點可解節點的判別條件 葉節點可解或節點可解當且僅當至少有一個子節點可解.與節點可解當且僅當所有子節點都可解.不可解節點的判別條件沒有

44、子節點的非終止節點或節點不可解當且僅當所有子節點不可解.與節點不可解當且僅當至少有一個子節點不可解.第103頁，共126頁。與或圖的搜索AC6C5C4C3C2C1m1m2或節點與節點解圖求解與或圖問題就是在與或圖中搜索解圖(或解樹)的問題.解圖是原與或圖的一個子圖(與圖)搜索策略:無信息搜索與啟發式搜索搜索過程: 標記初始節點為可解節點(成功)或不可解節點(失敗)的過程.搜索算法: 第104頁，共126頁。與或樹的搜索算法1Step1: S0 = OPEN表Step2: OPEN -N- CLOSED (n)Step3: 如N可擴展:擴展N=OPEN標記可解節點=CLOSED 如初始節點可解,

45、搜索成功,結束.刪去OPEN中有可解先輩的節點.Step4: N不可擴展:標記不可解節點.如初始節點不可解, 搜索失敗,退出.刪去OPEN中有不可解先輩的節點. To Step2.54At2t3t42t1B3第105頁，共126頁。問題歸約的例子積分問題的與或樹三階梵塔問題的與或樹幾何定理證明的與或樹第106頁，共126頁。4.4 博弈樹搜索博弈樹的概念博弈:下棋, 打牌等一類競爭性智力活動.最簡單的是“二人零和,全信息,非偶然”博弈.博弈樹:描述博弈過程的與或樹. 特點: 或與節點分層交替出現;搜索空間指數增長,只能前推幾步 極大極小過程剪枝技術第107頁，共126頁。 (7,min) (6

46、,1,max)(5,2,max) (4,3,max)(5,1,1,min)(4,2,1min)(3,2,2,min)(3,3,1,min) (4,1,1,1,max)(3,2,1,1,mix) (2,2,2,1,max) max 失敗 (3,1,1,1,1,min) (2,2,1,1,1,min) min失敗 (2,1,1,1,1,1,max) max失敗分幣原則:每次要將一堆分為幣數不等的兩堆 . 勝負標準:交替分錢幣,誰不能再分誰輸.分錢幣游戲的博弈樹結論: ?第108頁，共126頁。 (7,min) (6,1,max)(5,2,max) (4,3,max)(5,1,1,min)(4,2,

47、1min)(3,2,2,min)(3,3,1,min) (4,1,1,1,max)(3,2,1,1,max) (2,2,2,1,max) max失敗 (3,1,1,1,1,min) (2,2,1,1,1,min) min失敗 (2,1,1,1,1,1,max)max失敗 . max 可解節點 min可解節點分錢幣游戲的博弈樹結論: max必勝第109頁，共126頁。 錢幣為8，9時，結論如何？錢幣為10 時，結論如何？錢幣為 x 時，結論如何？分錢幣游戲思考題第110頁，共126頁。極大極小過程BAIHGFCQPONMLKIEDMAXMIN 2 8 1 3 -2 5 7 -1 1 R25-22

48、2-15倒推過程第111頁，共126頁。-剪枝技術BAIHGFCQPONMLKIEDMAXMIN 2 8 1 3 -2 5 7 R25 1MAX節點的下界 2MIN節點的上界25剪枝剪枝第112頁，共126頁。-剪枝技術MAX節點的倒退值 : 取后繼節點估值的最大值. MAX節點的倒推下界值.MIN節點的倒退值 : 取后繼節估值點的最小值. MIN節點的倒推上界值.剪枝: 當MIN節點的值 祖先MAX節點的值時,不必展開MIN的其余子節點. 剪枝: 當MAX節點的值 祖先MIN節點的值時,不必展開MAX的其余子節點. 第113頁，共126頁。討論局部優先搜索與全局優先搜索的區別是什么?什么是啟

49、發式搜索？A算法？A*算法？博弈樹有什么特點?利用博弈樹分析九枚分錢幣游戲的可能結論?-第114頁，共126頁。4.5 局部搜索(Local Search)*通過在當前解近旁的搜索,不斷改善當前解,最終搜索到滿足要求的最優解或次優解.一般過程Step1: 初始化. 求初始解x0=當前解x, k=1;Step2: 完善解. 在x的近旁N(x)中如果有更好解y, 則 更新解x:=y, k:=k+1; To Step2 否則,輸出x, 停止搜索.被用于大規模N-queen, SAT等問題的求解.第115頁，共126頁。局部搜索法初始解x0 x3x4x1x2x5N(x0)N(x1)N(x5)第116頁，共126頁。局部搜索法的特征局部搜索的要素評價函數的確定初始解的確定