1、第四章 搜索技術n狀態空間法n問題歸約法n博弈樹搜索n局部搜索How to find the best path in game ?迷宮問題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搜索的挑戰組合爆炸n魔方問題n博弈問題n皇后問題n行商問題n排課問題（調度問題）n背包問題 數碼問題1238456712384567（目標狀態）（初始狀態）八數碼難題（8-puzzle problem）426183574.1 狀態圖概念n狀態圖的概念 狀態圖(狀態空間圖)實際上是一類問題的抽象表示。n許多智力問題(八數碼問題、梵塔問題、旅行商問題、八皇

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

3、，（1，0，0，0）。 （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）4.2 狀態空間法n問題的狀態空間表示(狀態圖表示) 狀態空間的三元組(S, O, G)表示. S:初始狀態集合; O: 操作集合; G:目標狀態集合n狀態空間的搜索策略(狀態圖搜索)廣度優先搜索, 深度優先搜索, 啟發式搜索狀態空間表示的概念n例如下棋、迷宮及各種游戲。OriginalStateMid

4、dleStateGoalState三數碼難題123123123312312312初始棋局目標棋局1238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345八數碼難題的寬度優先搜索樹13456123845671238456712384567123845671 238456723242526271236782212384567123845671 238456712 3845671238456712384567123

5、84567141516171819202112384567狀態圖搜索n圖搜索是指在狀態圖中尋找目標或路徑的搜索。n所謂搜索，顧名思義，就是從初始節點出發，沿著與之相連的邊試探地前進，尋找目標節點的過程(也可以反向進行)。問題狀態圖搜索解解是由初始狀態到目標狀態的路徑狀態圖搜索相關問題n狀態選擇n解的性質：存在、分布、質量n搜索策略圖搜索策略 n圖搜索控制策略一種在狀態圖中尋找路徑的方法。圖中每個節點對應一個狀態，每條連線對應一個操作符。n圖搜索涉及兩個主要數據結構：open表 closed表OPEN 表n OPEN表是一種動態數據結構，專門登記當前待考查（待訪問）的節點，也叫未擴展節點表 。節

6、點節點父節點編號父節點編號OPEN表表open表中，每個節點信息還包括指向父節點的返回指針（即父節點地址）CLOSED 表表n Closed表是一種動態數據結構，記錄訪問過的節點，也叫已擴展節點表 ，其初始為空表。 編號編號節點節點父節點編號父節點編號CLOSED表表開始開始把把S放入放入OPEN表表OPEN表為空表？表為空表？把第一個節點把第一個節點(n)從從OPEN表移至表移至CLOSED表表n為目標節點嗎？為目標節點嗎？把把n的后繼節點放入的后繼節點放入OPEN表的表的末端，提供返回節點末端，提供返回節點n的指針的指針修改指針方向修改指針方向重排重排OPEN表表失敗失敗成功成功 圖搜索過

7、程框圖圖搜索過程框圖是是是是否否否否搜索策略即搜索策略即體現在這里體現在這里按搜索軌跡分類n圖式搜索圖式搜索：搜索過程中，搜索路徑允許形成回路。n樹式搜索樹式搜索：搜索過程中，搜索路徑不允許形成回路。n線式搜索線式搜索：擴展節點每次只擴展一個節點。SGSG搜索樹的概念 n一個可以搜索出某個可行解的問題，如“農夫、白菜、羊、狼”和“八數碼難題”等，雖然從表面上看上去和“樹”這種結構無關，但是整個搜索過程中的可能試探點所行成的搜索空間總可以對應到一顆搜索樹上去。n將各類形式上不同的搜索問題抽象并統一成為搜索樹的形式，為算法的設計與分析帶來巨大的方便。 22178634582736451827163

8、452282763451238276345114687634512787345126152163458782345817631645827931458276171621786345381635472108354276181654273813542761821786345481356247128456217381546273138136274521202178365452178634511119（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，

9、0，0，1）（1，1，0，1）（0，1，0，1） （1，1，1，1）n由于搜索具有探索性，所以要提高搜索效率(盡快地找到目標節點)，或要找最佳路徑(最佳解)就必須注意搜索策略。n對于狀態圖搜索，已經提出了許多策略，它們大體可分為盲目搜索（bland search)和啟發式搜索（heuristic search）兩大類。n盲目搜索是無向導搜索。n啟發式搜索是有向導搜索，即利用啟發信息（函數）引導去尋找問題解。搜索策略分類搜索策略分類盲目搜索n盲目搜索又叫做無信息搜索，一般只適用于求解比較簡單的問題。n種類：寬度優先搜索深度優先搜索等代價搜索圖搜索策略寬度優先深度優先啟發式搜索一種在圖中尋找路徑的

10、方法。寬度優先搜索策略n優先搜索狀態空間中離初始狀態近的節點(狀態n特點:具有完備性, 占用空間n搜索算法n 數據結構:OPEN表 : 先進先出隊列先進先出隊列,存放待擴展的節點. 節點(狀態) 父節點編號(返回指針)CLOSED表 : 存放已被擴展過的節點.編號 節點 父節點編號開始開始把把S放入放入OPEN表表OPEN表為空表？表為空表？把第一個節點把第一個節點(n)從從OPEN表移至表移至CLOSED表表是否有后繼節點是否有后繼節點為目標節點？為目標節點？擴展擴展n，把，把n的后繼節點放入的后繼節點放入OPEN表的表的末端末端，提供返回節點，提供返回節點n的指針的指針失敗失敗成功成功 寬

11、度優先算法框圖寬度優先算法框圖是是否否是是否否v 算法否否寬度優先搜索算法nStep1: 把初始節點S0放入OPEN表中;nStep2: 若OPEN表為空,則搜索失敗,退出.nStep3: 移出OPEN表中第一個節點N放入CLOSED表 中, 并標以順序號n;nStep4: 若目標節點Sg=N, 則搜索成功,結束.nStep5: 若N不可擴展, 則轉Step2;nStep6: 擴展N, 將生成的一組子節點配上指向N的指針后, 放入放入OPEN表尾部表尾部, 轉 Step2;n 例子例子八數碼難題（八數碼難題（8-puzzle problem） 1238456712384567（目標狀態）（初始

12、狀態）規定：將牌移入空格的順序為：從空格左邊開始順時針旋轉。不許斜向移動，也不返回先輩節點。從圖可見，要擴展26個節點，共生成26個節點之后才求得解（目標節點）。1238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345圖 八數碼難題的寬度優先搜索樹13456123845671238456712384567123845671 238456723242526271236782212384567123845671

13、238456712 384567123845671238456712384567141516171819202112384567寬度優先搜索寬度優先搜索(新的節點被插入到棧OPEN的后部12345OPEN= (1)CLOSED=( )6789101112131415寬度優先搜索寬度優先搜索(新的節點被插入到棧OPEN的后部12345OPEN= (2,3)CLOSED=(1 )6789101112131415寬度優先搜索寬度優先搜索(新的節點被插入到棧OPEN的后部12345OPEN= (3,4,5)CLOSED=(1,2 )6789101112131415寬度優先搜索寬度優先搜索(新的節點被插

14、入到棧OPEN的后部12345OPEN= (4,5,10,11)CLOSED=(1,2,3 )6789101112131415寬度優先搜索寬度優先搜索(新的節點被插入到棧OPEN的后部12345OPEN= (5,10,11,6,7)CLOSED=(1,2,3,4 )6789101112131415寬度優先搜索寬度優先搜索(新的節點被插入到棧OPEN的后部12345OPEN= (10,11,6,7,8,9)CLOSED=(1,2,3,4,5 )6789101112131415寬度優先搜索寬度優先搜索(新的節點被插入到棧OPEN的后部12345OPEN= (11,6,7,8,9,12,13)CLO

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

16、表是否有后繼節點是否有后繼節點為目標節點？為目標節點？擴展擴展n，把，把n的后繼節點放入的后繼節點放入OPEN表的表的前端前端，提供返回節點，提供返回節點n的指針的指針失敗失敗成功成功是是否否是是否否深度優先搜索算法nStep1: 把初始節點S0放入OPEN表中;nStep2: 若OPEN表為空,則搜索失敗,退出.nStep3: 移出OPEN中第一個節點N放入CLOSED表 中, 并標以順序號n;nStep4: 若目標節點Sg=N, 則搜索成功,結束.nStep5: 若N不可擴展, 則轉Step2;nStep6: 擴展N, 將生成的一組子節點配上指向N的指針后, 放入放入OPEN表首部表首部,

17、 轉 Step2;深度優先搜索深度優先搜索(新的節點被插入到棧OPEN的前部12345OPEN= (1)CLOSED=( )6789101112131415新的節點被插入到棧OPEN的前部12345OPEN = (2, 3)CLOSED=( 1 )6789101112131415 新的節點被插入到棧OPEN的前部12345OPEN = (4, 5, 3)CLOSED=( 1,2 )6789101112131415新的節點被插入到棧OPEN的前部12345CLOSED=( 1,2,4 )67OPEN = (6,7, 5, 3)89101112131415新的節點被插入到棧OPEN的前部12345

18、67891011CLOSED=( 1,2,4,6 )OPEN = (7, 5, 3)12131415新的節點被插入到棧OPEN的前部1234567891011CLOSED=( 1,2,4,6,7 )OPEN = (5, 3)12131415新的節點被插入到棧OPEN的前部1234567891011CLOSED=( 1,2,4, 5,6,7 )OPEN = (8,9,3)12131415新的節點被插入到棧OPEN的前部1234567891011CLOSED=( 1,2,4,5, 6,7 ,8)OPEN = (9, 3)12131415新的節點被插入到棧OPEN的前部123456789121011

19、131415CLOSED=( 1,2,4, 5,6,7, 8,9)OPEN = (3)新的節點被插入到棧OPEN的前部123456789121011131415CLOSED=( 1,2,4, 5,6,7,8,9,3)OPEN = (10,11)新的節點被插入到棧OPEN的前部1234567891011CLOSED=( 1,2,4, 5,6,7,8,9,3,10)12131415OPEN = (12,13,11)代價樹搜索代價樹：搜索樹中每條連接弧線上的有關代價,表示時間、距離等花費。代價樹搜索（等代價搜索） ：是寬度優先搜索的一種推廣，不是沿著等長度路徑斷層進行擴展，而是沿著等代價路徑斷層進行

20、擴展。 *若所有連接弧線具有相等代價，則簡化為寬度優先搜索算法。算法使用符號n c(i,j)：把從節點把從節點i i到其后繼節點到其后繼節點j j的連接弧線代價記為的連接弧線代價記為c(i,jc(i,j) )n g(i)：把從起始節點把從起始節點S S到任一節點到任一節點i i的路徑代價記為的路徑代價記為g(ig(i).).n 在搜索樹在搜索樹（非循環路徑）（非循環路徑）上，假設上，假設g(ig(i) )是從起始節點是從起始節點S S到節點到節點i i的最少路徑上的代價。的最少路徑上的代價。n 等代價搜索方法以等代價搜索方法以g(ig(i) )的遞增順序擴展其節點。的遞增順序擴展其節點。開始把

21、S放入OPEN表OPEN表為空表？把具有最小g(i)值的節點i從OPEN表移至CLOSED表是否有后繼節點為目標節點？失敗成功等代價搜索算法框圖等代價搜索算法框圖是是否否是是否否令令g(s)=0S S是否目標節點是否目標節點？是是成功否否開始把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節點i從OPEN表移至CLOSED表是否有后繼節點為目標節點？失敗成功是是是是否否令令g(s)=0S S是否目標節點是否目標節點？是是成功開始把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節點i從OPEN表移至CLOSED表是否有后繼節點為目標節點？失敗成功是是是是否否令令g(s)=0S

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

23、令g（S）=0。n（2） 如果如果OPEN是個空表，則沒有解而失敗退出。是個空表，則沒有解而失敗退出。n（3） 從從OPEN 表中選擇一個節點表中選擇一個節點i，使其，使其g（i）為最小。如果有幾個節）為最小。如果有幾個節點都合格，那么就要選擇一個目標節點作為節點點都合格，那么就要選擇一個目標節點作為節點 i（要是有目標節點的（要是有目標節點的話）；否則，就從中選一個作為節點話）；否則，就從中選一個作為節點i。把節點。把節點i從從OPEN表移至擴展節點表移至擴展節點表表CLOSED中。中。n（4） 如果節點如果節點i為目標節點，則求得一個解。為目標節點，則求得一個解。n（5） 擴展節點擴展節點

24、i。如果沒有后繼節點，則轉向第（。如果沒有后繼節點，則轉向第（2）步。）步。n（6） 對于節點對于節點i的每個后繼節點的每個后繼節點j，計算，計算g（j）=g（i）+c（i,j），），并并把所有后繼節點把所有后繼節點j放進放進OPEN表。提供回到節點表。提供回到節點i的指針。的指針。n（7） 轉向第（轉向第（2）步。）步。沿著等長度沿著等長度路徑斷層進行擴展路徑斷層進行擴展等代價路徑等代價路徑斷層進行擴展斷層進行擴展比較寬度優先搜索與等代價搜索比較寬度優先搜索與等代價搜索搜索樹（非循環路徑）等代價搜索算法等代價搜索算法 在每一步, 選擇具有最低累計權值的點進行擴展啟發式搜索n盲目搜索的問題：

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

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

27、呢？估價（啟發）函數并無固定的模式，需要具體問題具體分析。通常可以參考的思路有： （1） 一個節點到目標節點的距離或差異的度量； （2）一個節點處在最佳路徑上的概率； （3）或者根據經驗的主觀打分。啟發函數啟發函數八數碼難題（八數碼難題（8-puzzle）f1(T) = 恰好正確地處在目標狀態的字碼數目恰好正確地處在目標狀態的字碼數目:f2(T) =沒有處在目標狀態的字碼數目（相當于粗略地給出了當前狀態沒有處在目標狀態的字碼數目（相當于粗略地給出了當前狀態與目標的距離）與目標的距離）1 2 3847 6 5目標：目標：f3(T) = 不在目標位置的字碼距離目標位置水平距離和垂直不在目標位置的字

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

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

30、現格局(Sn)相比,位置不同的牌數. 初始格局S0 目標格局Sg 2 8 3 1 2 3 1 4 = 8 4 7 6 5 7 6 5h(S0) = 3局部擇優搜索算法nStep1: 把初始節點S0放入OPEN表中,計算h(S0);nStep2: 若OPEN表為空,則搜索失敗,退出.nStep3: 移出OPEN中第一個節點N放入CLOSED表 中, 并標以順序編號n;nStep4: 若目標節點Sg=N, 則搜索成功,結束.nStep5: 若N不可擴展, 則轉Step2;nStep6: 擴展N,計算每個子節點的函數值h(x),并將所有子節點按函數值的升序排序后函數值的升序排序后, 配上指向N的返回

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

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

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

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

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

36、 = g(x) + h(x) ( 當h(n) = h*(n) )nSGg(n)=g*(n)h(n) = h*(n) A*算法要求保守估計： f(n) 0。n4)： h(n)=h*(n)為什么A*算法低估h值n在A*算法中，對所有的x存在h(x)h*(x)（低估)n在A*算法中,只有對h值低估才能獲得優化的搜索性能為什么A*算法低估h值n舉例：n在多估情況下：為什么A*算法低估h值n舉例：n如果h被低估:啟發式搜索算法A*nStep1: 把初始節點S0放入OPEN表中;nStep2: 若OPEN表為空,則搜索失敗,退出.nStep3: 移出OPEN中第一個節點N放入CLOSED表 中, 并標以順

37、序號n;nStep4: 若目標節點Sg=N, 則搜索成功,結束.nStep5: 若N不可擴展, 則轉Step2;nStep6: 擴展N, 生成一組子節點, 對這組子節點作如下處 理后, 放入OPEN表, 按評價函數的升序重新排序按評價函數的升序重新排序 OPEN表表, 轉 Step2;n刪除重復節點和修改返回指針處理.八數碼難題:nh1(T) 0 啟發函數為0nh2(T) =沒有處在目標狀態的字碼數目沒有處在目標狀態的字碼數目nh3(T) =不在目標位置的字碼距離目標位置水平距離和垂不在目標位置的字碼距離目標位置水平距離和垂直距離之和。直距離之和。1 2 3847 6 5目標：目標：曼哈頓距離

38、曼哈頓距離八數碼難題舉例曼哈頓距離曼哈頓距離Cost of one horizontal/vertical step = 1Cost of one diagonal step = 2 f(N) = g(N) + h(N), with h(N) =距離目標位置水平距離和垂直距離之和距離目標位置水平距離和垂直距離之和02115877347676328645233365244355465645f(N) = h(N), with h(N) =距離目標位置水平距離和垂直距離之距離目標位置水平距離和垂直距離之02115877347676328645233365244355465645f(N) = h(N)

39、, with h(N) =距離目標位置水平距離和垂直距離之距離目標位置水平距離和垂直距離之70f(N) = g(N)+h(N), with h(N) =距離目標位置水平距離和垂直距離之和距離目標位置水平距離和垂直距離之和021158773476763286452333652443554656457+06+16+18+17+07+26+17+26+18+17+28+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+10 0+11搜索算法小結

40、樹搜索-盲目搜索-廣度優先搜索 -深度優先搜索-有界深度優先 -代價樹搜索 -啟發式搜索-全局擇優搜索(最好優先) -局部擇優搜索(爬山法) -A算法( 基于: f(n)=g(n)+h(n) ) A*算法(最佳搜索: h(n) 8 4 7 5 3 7 6 5n請針對TSP問題，提出啟發式搜索策略，并對搜索效率進行分析？4.3 問題歸約法n問題歸約的概念n問題歸約的描述: 三元組(S0, O, P)表示. S0:初始問題; P:本原問題本原問題集合O:操作算子集;將問題化成若干子問題.n問題歸約的最終目標: 原問題 = 本原問題n狀態空間法是問題歸約法的特例.n問題歸約的與或圖表示與或圖表示AA

41、C6C5C4C3C2C1C6C5C4C3C2C1m1m2或節點與節點葉節點(或稱:端節點)3連接弧節點的可解性判別AC6C5C4C3C2C1m1m2或節點與節點可解節點的判別條件 葉節點可解或節點可解當且僅當至少有一個子節點可解.與節點可解當且僅當所有子節點都可解.不可解節點的判別條件沒有子節點的非終止節點或節點不可解當且僅當所有子節點不可解.與節點不可解當且僅當至少有一個子節點不可解.與或圖的搜索AC6C5C4C3C2C1m1m2或節點與節點解圖求解與或圖問題就是在與或圖中搜索解圖(或解樹)的問題.解圖是原與或圖的一個子圖(與圖)搜索策略:無信息搜索與啟發式搜索搜索過程: 標記初始節點為可解

42、節點(成功)或不可解節點(失敗)的過程.搜索算法: 與或樹的搜索算法1Step1: S0 = OPEN表Step2: OPEN -N- CLOSED (n)Step3: 如N可擴展:擴展N=OPEN標記可解節點=CLOSED 如初始節點可解,搜索成功,結束.刪去OPEN中有可解先輩的節點.Step4: N不可擴展:標記不可解節點.如初始節點不可解, 搜索失敗,退出.刪去OPEN中有不可解先輩的節點. To Step2.54At2t3t42t1B3問題歸約的例子n積分問題的與或樹n三階梵塔問題的與或樹n幾何定理證明的與或樹4.4 博弈樹搜索n博弈樹的概念n博弈:下棋, 打牌等一類競爭性智力活動.

43、最簡單的是“二人零和,全信息,非偶然”博弈.n博弈樹:描述博弈過程的與或樹. 特點: 或與節點分層交替出現;n搜索空間指數增長,只能前推幾步 n極大極小過程n剪枝技術 (7,min) (6,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失敗分幣原則:每次要將一堆分為幣數不等的兩堆 . 勝負標準

44、:交替分錢幣,誰不能再分誰輸.分錢幣游戲的博弈樹結論: ? (7,min) (6,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,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必勝 n錢幣為8，9時，結論如何？n錢幣為10 時，結論如何？n錢幣為 x 時，結論如何？分錢

45、幣游戲思考題極大極小過程BAIHGFCQPONMLKIEDMAXMIN 2 8 1 3 -2 5 7 -1 1 R25-222-15倒推過程-剪枝技術BAIHGFCQPONMLKIEDMAXMIN 2 8 1 3 -2 5 7 R25 1MAX節點的下界 2MIN節點的上界25剪枝剪枝-剪枝技術nMAX節點的倒退值 : 取后繼節點估值的最大值. MAX節點的倒推下界值.nMIN節點的倒退值 : 取后繼節估值點的最小值. MIN節點的倒推上界值.n剪枝: 當MIN節點的值 祖先MAX節點的值時,不必展開MIN的其余子節點. n剪枝: 當MAX節點的值 祖先MIN節點的值時,不必展開MAX的其余子

46、節點. 討論n局部優先搜索與全局優先搜索的區別是什么?n什么是啟發式搜索？A算法？A*算法？n博弈樹有什么特點?n利用博弈樹分析九枚分錢幣游戲的可能結論?-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等問題的求解.局部搜索法初始解x0 x3x4x1x2x5N(x0)N(x1)N(x5)局部搜索法的特征1. 局部搜索的要素評價函數的確定初始解的確定N(x)的確定解更新的方法終止條件2. 特點：簡單,高效,但不完備-局部最優解3. 改進方法:多起點、加入非確定性、 加入從局部最優解脫出