1、第四章 搜索技術,狀態(tài)空間法 問題歸約法 博弈樹搜索 局部搜索,How to find the best path in game ?,迷宮問題,s-s s s s s s-s-s-s s-s-s-s s s s s s s s-s-s-s-s,S0,Sg,搜索的挑戰(zhàn)組合爆炸,魔方問題 博弈問題 皇后問題 行商問題 排課問題（調度問題） 背包問題 ,數碼問題,（初始狀態(tài)）,八數碼難題（8-puzzle problem）,4.1 狀態(tài)圖概念,狀態(tài)圖的概念 狀態(tài)圖(狀態(tài)空間圖)實際上是一類問題的抽象表示。 許多智力問題(八數碼問題、梵塔問題、旅行商問題、八皇后問題、農夫過河問題等)。 實際問題（如

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

3、,4.2 狀態(tài)空間法,問題的狀態(tài)空間表示(狀態(tài)圖表示) 狀態(tài)空間的三元組(S, O, G)表示. S:初始狀態(tài)集合; O: 操作集合; G:目標狀態(tài)集合 狀態(tài)空間的搜索策略(狀態(tài)圖搜索) 廣度優(yōu)先搜索, 深度優(yōu)先搜索, 啟發(fā)式搜索,狀態(tài)空間表示的概念,例如下棋、迷宮及各種游戲。,Middle State,Goal State,三數碼難題,初始棋局,目標棋局,1,八數碼難題的寬度優(yōu)先搜索樹,狀態(tài)圖搜索,圖搜索是指在狀態(tài)圖中尋找目標或路徑的搜索。 所謂搜索，顧名思義，就是從初始節(jié)點出發(fā)，沿著與之相連的邊試探地前進，尋找目標節(jié)點的過程(也可以反向進行)。,問題,狀態(tài)圖,搜索,解,解是由初始狀態(tài)到目標

4、狀態(tài)的路徑,狀態(tài)圖搜索相關問題,狀態(tài)選擇 解的性質：存在、分布、質量 搜索策略,圖搜索策略,圖搜索控制策略一種在狀態(tài)圖中尋找路徑的方法。圖中每個節(jié)點對應一個狀態(tài)，每條連線對應一個操作符。 圖搜索涉及兩個主要數據結構： open表 closed表,OPEN 表,OPEN表是一種動態(tài)數據結構，專門登記當前待考查（待訪問）的節(jié)點，也叫未擴展節(jié)點表 。,OPEN表,open表中，每個節(jié)點信息還包括指向父節(jié)點的返回指針（即父節(jié)點地址）,CLOSED 表,Closed表是一種動態(tài)數據結構，記錄訪問過的節(jié)點，也叫已擴展節(jié)點表 ，其初始為空表。,CLOSED表,開始,把S放入OPEN表,OPEN表為空表？,把

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

6、式上不同的搜索問題抽象并統(tǒng)一成為搜索樹的形式，為算法的設計與分析帶來巨大的方便。,（1，0，0，1）,由于搜索具有探索性，所以要提高搜索效率(盡快地找到目標節(jié)點)，或要找最佳路徑(最佳解)就必須注意搜索策略。 對于狀態(tài)圖搜索，已經提出了許多策略，它們大體可分為盲目搜索（bland search)和啟發(fā)式搜索（heuristic search）兩大類。 盲目搜索是無向導搜索。 啟發(fā)式搜索是有向導搜索，即利用啟發(fā)信息（函數）引導去尋找問題解。,搜索策略分類,盲目搜索,盲目搜索又叫做無信息搜索，一般只適用于求解比較簡單的問題。 種類： 寬度優(yōu)先搜索 深度優(yōu)先搜索 等代價搜索,圖搜索策略,寬度優(yōu)先,深

7、度優(yōu)先,啟發(fā)式搜索,一種在圖中尋找路徑的方法。,寬度優(yōu)先搜索策略,優(yōu)先搜索狀態(tài)空間中離初始狀態(tài)近的節(jié)點(狀態(tài) 特點:具有完備性, 占用空間 搜索算法 數據結構: OPEN表 : 先進先出隊列,存放待擴展的節(jié)點. 節(jié)點(狀態(tài)) 父節(jié)點編號(返回指針) CLOSED表 : 存放已被擴展過的節(jié)點. 編號 節(jié)點 父節(jié)點編號,開始,把S放入OPEN表,OPEN表為空表？,把第一個節(jié)點(n)從OPEN表移至CLOSED表,是否有后繼節(jié)點 為目標節(jié)點？,擴展n，把n的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針,失敗,成功,寬度優(yōu)先算法框圖,是,否,是,否,算法,否,寬度優(yōu)先搜索算法,Step1: 把

8、初始節(jié)點S0放入OPEN表中; Step2: 若OPEN表為空,則搜索失敗,退出. Step3: 移出OPEN表中第一個節(jié)點N放入CLOSED表 中, 并標以順序號n; Step4: 若目標節(jié)點Sg=N, 則搜索成功,結束. Step5: 若N不可擴展, 則轉Step2; Step6: 擴展N, 將生成的一組子節(jié)點配上指向N的指針后, 放入OPEN表尾部, 轉 Step2;,例子八數碼難題（8-puzzle problem）,（初始狀態(tài)）,規(guī)定：將牌移入空格的順序為：從空格左邊開始順時針旋轉。不許斜向移動，也不返回先輩節(jié)點。 從圖可見，要擴展26個節(jié)點，共生成26個節(jié)點之后才求得解（目標節(jié)點）

9、。,1,圖 八數碼難題的寬度優(yōu)先搜索樹,寬度優(yōu)先搜索(Breadth-First Strategy),新的節(jié)點被插入到棧OPEN的后部,1,OPEN= (1),CLOSED=( ),6,7,8,9,10,11,12,13,14,15,寬度優(yōu)先搜索(Breadth-First Strategy),新的節(jié)點被插入到棧OPEN的后部,1,OPEN= (2,3),CLOSED=(1 ),6,7,8,9,10,11,12,13,14,15,寬度優(yōu)先搜索(Breadth-First Strategy),新的節(jié)點被插入到棧OPEN的后部,1,OPEN= (3,4,5),CLOSED=(1,2 ),6,7,8

10、,9,10,11,12,13,14,15,寬度優(yōu)先搜索(Breadth-First Strategy),新的節(jié)點被插入到棧OPEN的后部,1,OPEN= (4,5,10,11),CLOSED=(1,2,3 ),6,7,8,9,10,11,12,13,14,15,寬度優(yōu)先搜索(Breadth-First Strategy),新的節(jié)點被插入到棧OPEN的后部,1,OPEN= (5,10,11,6,7),CLOSED=(1,2,3,4 ),6,7,8,9,10,11,12,13,14,15,寬度優(yōu)先搜索(Breadth-First Strategy),新的節(jié)點被插入到棧OPEN的后部,1,OPEN=

11、 (10,11,6,7,8,9),CLOSED=(1,2,3,4,5 ),6,7,8,9,10,11,12,13,14,15,寬度優(yōu)先搜索(Breadth-First Strategy),新的節(jié)點被插入到棧OPEN的后部,1,OPEN= (11,6,7,8,9, 12,13),CLOSED=(1,2,3,4,5,10 ),6,7,8,9,10,11,12,13,14,15,深度優(yōu)先搜索策略,新節(jié)點優(yōu)先擴展, 直到達到一定的深度限制.若找不到目標或無法在擴展時,回溯到另一節(jié)點繼續(xù)擴展. 特點: 需要深度限制, 需要回溯控制, 省空間 探索算法: 數據結構: OPEN表 : 后進先出隊列,存放待擴

12、展的節(jié)點. CLOSED表 : 存放已被擴展過的節(jié)點. 除擴展后的子節(jié)點應放入到OPEN表的首部以外,與寬度優(yōu)先算法一樣.,深度優(yōu)先算法框圖,算法,開始,把S放入OPEN表,OPEN表為空表？,把第一個節(jié)點(n)從OPEN表移至CLOSED表,是否有后繼節(jié)點 為目標節(jié)點？,擴展n，把n的后繼節(jié)點放入OPEN表的前端，提供返回節(jié)點n的指針,失敗,成功,是,否,是,否,深度優(yōu)先搜索算法,Step1: 把初始節(jié)點S0放入OPEN表中; Step2: 若OPEN表為空,則搜索失敗,退出. Step3: 移出OPEN中第一個節(jié)點N放入CLOSED表 中, 并標以順序號n; Step4: 若目標節(jié)點Sg=

13、N, 則搜索成功,結束. Step5: 若N不可擴展, 則轉Step2; Step6: 擴展N, 將生成的一組子節(jié)點配上指向N的指針后, 放入OPEN表首部, 轉 Step2;,深度優(yōu)先搜索(Depth-First Strategy),新的節(jié)點被插入到棧OPEN的前部,1,CLOSED=( ),6,7,8,9,10,11,12,13,14,15,Depth-First Strategy,新的節(jié)點被插入到棧OPEN的前部,1,CLOSED=( 1 ),6,7,8,9,10,11,12,13,14,15,Depth-First Strategy,新的節(jié)點被插入到棧OPEN的前部,1,CLOSED=

14、( 1,2 ),6,7,8,9,10,11,12,13,14,15,Depth-First Strategy,新的節(jié)點被插入到棧OPEN的前部,1,CLOSED=( 1,2,4 ),6,7,OPEN = (6,7, 5, 3),8,9,10,11,12,13,14,15,Depth-First Strategy,新的節(jié)點被插入到棧OPEN的前部,1,6,7,8,9,10,11,CLOSED=( 1,2,4,6 ),OPEN = (7, 5, 3),12,13,14,15,Depth-First Strategy,新的節(jié)點被插入到棧OPEN的前部,1,6,7,8,9,10,11,CLOSED=(

15、 1,2,4,6,7 ),OPEN = (5, 3),12,13,14,15,Depth-First Strategy,新的節(jié)點被插入到棧OPEN的前部,1,2,3,4,5,6,7,8,9,10,11,CLOSED=( 1,2,4, 5,6,7 ),OPEN = (8,9,3),12,13,14,15,Depth-First Strategy,新的節(jié)點被插入到棧OPEN的前部,1,6,7,8,9,10,11,CLOSED=( 1,2,4,5, 6,7 ,8),OPEN = (9, 3),12,13,14,15,Depth-First Strategy,新的節(jié)點被插入到棧OPEN的前部,1,6,

16、7,8,9,12,10,11,13,14,15,CLOSED=( 1,2,4, 5,6,7, 8,9),OPEN = (3),Depth-First Strategy,新的節(jié)點被插入到棧OPEN的前部,1,6,7,8,9,12,10,11,13,14,15,CLOSED=( 1,2,4, 5,6,7,8,9,3),OPEN = (10,11),Depth-First Strategy,新的節(jié)點被插入到棧OPEN的前部,1,6,7,8,9,10,11,CLOSED=( 1,2,4, 5,6,7,8,9,3,10),12,13,14,15,OPEN = (12,13,11),代價樹搜索,代價樹：搜

17、索樹中每條連接弧線上的有關代價,表示時間、距離等花費。 代價樹搜索（等代價搜索） ：是寬度優(yōu)先搜索的一種推廣，不是沿著等長度路徑斷層進行擴展，而是沿著等代價路徑斷層進行擴展。,*若所有連接弧線具有相等代價，則簡化為寬度優(yōu)先搜索算法。,算法使用符號,c(i,j)：把從節(jié)點i到其后繼節(jié)點j的連接弧線代價記為c(i,j) g(i)：把從起始節(jié)點S到任一節(jié)點i的路徑代價記為g(i). 在搜索樹（非循環(huán)路徑）上，假設g(i)是從起始節(jié)點S到節(jié)點i的最少路徑上的代價。 等代價搜索方法以g(i)的遞增順序擴展其節(jié)點。,開始,把S放入OPEN表,OPEN表為空表？,把具有最小g(i)值的節(jié)點i從OPEN表移至

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

19、入OPEN表,開始,把S放入OPEN表,OPEN表為空表？,把具有最小g(i)值的節(jié)點i從OPEN表移至CLOSED表,是否有后繼節(jié)點 為目標節(jié)點？,失敗,成功,是,是,否,令g(s)=0,S是否目標節(jié)點？,是,成功,等代價搜索算法,（1） 把起始節(jié)點放到未擴展節(jié)點表OPEN中。如果此起始節(jié)點為一目標節(jié)點，則求得一個解；否則令g（S）=0。 （2） 如果OPEN是個空表，則沒有解而失敗退出。 （3） 從OPEN 表中選擇一個節(jié)點i，使其g（i）為最小。如果有幾個節(jié)點都合格，那么就要選擇一個目標節(jié)點作為節(jié)點 i（要是有目標節(jié)點的話）；否則，就從中選一個作為節(jié)點i。把節(jié)點i從OPEN表移至擴展節(jié)點

20、表CLOSED中。 （4） 如果節(jié)點i為目標節(jié)點，則求得一個解。 （5） 擴展節(jié)點i。如果沒有后繼節(jié)點，則轉向第（2）步。 （6） 對于節(jié)點i的每個后繼節(jié)點j，計算g（j）=g（i）+c（i,j），并把所有后繼節(jié)點j放進OPEN表。提供回到節(jié)點i的指針。 （7） 轉向第（2）步。,g1,g2,g3,g4,等代價搜索,等代價搜索：沿等代價路徑 斷層進行擴展,比較寬度優(yōu)先搜索與等代價搜索,等代價搜索算法,在每一步, 選擇具有最低累計權值的點進行擴展,啟發(fā)式搜索,盲目搜索的問題： “組合爆炸” 利用問題的某些控制信息(如解的特征)來引導搜索.這種控制信息稱為搜索的啟發(fā)信息. 利用啟發(fā)式信息定義節(jié)點的

21、啟發(fā)函數 h(n) 特點: 深度優(yōu)先, 效率高, 無回溯, 但不能保證得到最佳解 。 探索算法: 全局擇優(yōu)搜索(最好優(yōu)先搜索), 局部擇優(yōu)搜索 數據結構：OPEN表 、 CLOSED表,啟發(fā)信息 啟發(fā)式搜索就是利用啟發(fā)性信息進行制導的搜索。 啟發(fā)性信息就是有利于盡快找到問題之解的信息。 按其用途劃分，啟發(fā)性信息一般可分為以下三類： (1)用于擴展節(jié)點的選擇，即用于決定應先擴展哪一個節(jié)點，以免盲目擴展。 (2)用于生成節(jié)點的選擇，即用于決定應生成哪些后續(xù)節(jié)點，以免盲目地生成過多無用節(jié)點。 (3)用于刪除節(jié)點的選擇，即用于決定應刪除哪些無用節(jié)點，以免造成進一步的時空浪費。,重排OPEN表，使搜索沿

22、某個被認為最有希望的路徑擴展。 應用這種排序過程，需要某些估算節(jié)點“希望”的量度。 用來估算節(jié)點希望程度的量度，叫做估價函數（evaluation function），有時也叫作啟發(fā)函數。 一個節(jié)點的“希望”（promise）有幾種不同 的定義方法。 在狀態(tài)空間問題中，一種方法是估算目標節(jié)點到此節(jié)點的距離； 估算全路徑的長度或難度（包括此節(jié)點）。 我們用符號f來標記估價函數，用f（n）表示節(jié)點n的估價函數值。,啟發(fā)函數,如何定義一個估價（啟發(fā)）函數呢？估價（啟發(fā)）函數并無固定的模式，需要具體問題具體分析。通?？梢詤⒖嫉乃悸酚校?（1） 一個節(jié)點到目標節(jié)點的距離或差異的度量； （2）一個節(jié)點處在

23、最佳路徑上的概率； （3）或者根據經驗的主觀打分。,啟發(fā)函數,八數碼難題（8-puzzle）,f1(T) = 恰好正確地處在目標狀態(tài)的字碼數目:,從實用角度，計算與目標的距離更有實際意義！,目標：,f3(T) = 不在目標位置的字碼距離目標位置水平距離和垂直距離之和。 該函數給出了一個更好的距離評估,= 1 + 1 + 2 + 2 = 6,目標：,啟發(fā)式搜索算法 啟發(fā)式搜索要用啟發(fā)函數來導航，其搜索算法就要在狀態(tài)圖一般搜索算法基礎上再增加啟發(fā)函數值的計算與傳播過程，并且由啟發(fā)函數值來確定節(jié)點的擴展順序。兩種策略: 局部擇優(yōu)搜索 擴展節(jié)點N后僅對N的子節(jié)點按啟發(fā)函數值大小以升序排序，再將它們依次

24、放入OPEN表的首部。 全局擇優(yōu)搜索 在OPEN表中保留所有已生成而未考察的節(jié)點，并用啟發(fā)函數h(x)對它們全部進行估價，從中選出最優(yōu)節(jié)點進行擴展，而不管這個節(jié)點出現(xiàn)在搜索樹的什么地方。,全局擇優(yōu)搜索算法,Step1: 把初始節(jié)點S0放入OPEN表中,計算h(S0); Step2: 若OPEN表為空,則搜索失敗,退出. Step3: 移出OPEN中第一個節(jié)點N放入CLOSED表 中, 并標以順序編號n; Step4: 若目標節(jié)點Sg=N, 則搜索成功,結束. Step5: 若N不可擴展, 則轉Step2; Step6: 擴展N,計算每個子節(jié)點的函數值h(x),將所有子節(jié)點配上指向N的返回指針后

25、放入OPEN表中, 再按函數值的升序重新排序OPEN表中的節(jié)點, 轉 Step2;,全局擇優(yōu)搜索例子,九宮重排問題, 定義評價函數; h(n):目標格局與現(xiàn)格局(Sn)相比,位置不同的牌數 . 初始格局S0 目標格局Sg 2 8 3 1 2 3 1 4 = 8 4 7 6 5 7 6 5 h(S0) = 3,局部擇優(yōu)搜索算法,Step1: 把初始節(jié)點S0放入OPEN表中,計算h(S0); Step2: 若OPEN表為空,則搜索失敗,退出. Step3: 移出OPEN中第一個節(jié)點N放入CLOSED表 中, 并標以順序編號n; Step4: 若目標節(jié)點Sg=N, 則搜索成功,結束. Step5:

26、若N不可擴展, 則轉Step2; Step6: 擴展N,計算每個子節(jié)點的函數值h(x),并將所有子節(jié)點按函數值的升序排序后, 配上指向N的返回指針放入OPEN表的首部, 轉 Step2;,局部搜索算法,特點： 從單獨的一個當前狀態(tài)出發(fā)，通常只移動到與之相鄰的狀態(tài)，并且不保留解的路徑。 優(yōu)點： 需要很少的內存 經常能在很大或無限的狀態(tài)空間中找到合理的解,爬山法（Hill climbing）,一種基本的局部啟發(fā)式搜索方法 基本算法：擴展節(jié)點N后僅對N的子節(jié)點按啟發(fā)函數值大小以升序排序，再將選擇啟發(fā)函數值最小的節(jié)點放入OPEN表的首部。（啟發(fā)函數值越小離目標越近） 相當于深度優(yōu)先算法+啟發(fā)式搜索 線

27、式搜索，不能回溯 向目標值增加的方向持續(xù)移動,啟發(fā)式搜索:A算法,評價函數 f(x) = g(x) + h(x)，表示通過節(jié)點x的估計代價值。,n,m,S,G,g(n),g(m),h(n),h(m),比較f(n)和f(m) 大小，決定節(jié)點搜索順序，即在OPEN表中的順序,啟發(fā)式搜索:A算法,評價函數 f(x) = g(x) + h(x) 當f(x) = g(x) 時，為寬度優(yōu)先搜索 當f(x) = 1/g(x)時，為深度優(yōu)先搜索 當f(x) = h(x) 時，為全局優(yōu)先搜索,n,m,S,G,g(n),g(m),h(n),h(m),啟發(fā)式搜索:A算法,評價函數的一般形式 : f(n) = g(n

28、) + h(n) g(n):從S0到Sn的實際代價(搜索的橫向因子) h(n):從N到目標節(jié)點的估計代價,稱為啟發(fā)函數 (搜索的縱向因子); 特點: 效率高, 無回溯, 搜索算法 OPEN表 : 存放待擴展的節(jié)點. CLOSED表 : 存放已被擴展過的節(jié)點.,啟發(fā)式搜索:A算法,Step1: 把附有計算f(S0)初始節(jié)點S0放入OPEN表中; Step2: 若OPEN表為空,則搜索失敗,退出. Step3: 移出OPEN中第一個節(jié)點N放入CLOSED表中, 并標以順序編號n; Step4: 若目標節(jié)點Sg=N, 則搜索成功,結束. Step5: 若N不可擴展, 則轉Step2; Step6:

29、擴展N, 生成一組附有f(x)的子節(jié)點,作完以下處理后,將余下子節(jié)點配上指向N的返回指針后放入OPEN表中, 再按函數值的升序重新排序OPEN表中的節(jié)點, 轉 Step2; 刪除重復節(jié)點和修改返回指針.,八數碼難題（8-puzzle problem）,A算法的應用,八數碼難題:評價函數,簡單的評價函數 h(n)=d(n)+W(n) 其中：d(n)是搜索樹中節(jié)點n的深度；W(n)用來計算對應于節(jié)點n的數據庫中錯放的棋子個數。,初始棋局f值等于0+4=4,5,7,2,3,4,5,1,八數碼難題的搜索樹,5,啟發(fā)式搜索:A*算法,評價函數的一般形式: f(n) = g(n) + h(n) 且 h(n

30、) = h*(n) g(n),h(n):定義同A算法; h*(n):從N到目標節(jié)點的最短路徑; 稱此時的A算法為A*算法. A*算法的特征: A*是可采納的:只要最短路徑存在,就一定能找出. 如果有 h1(n) = h2(n) = h*(n), 那么h2比h1展開更少的節(jié)點. 廣度優(yōu)先搜索是當h(n)=0時的A*算法的特例.,啟發(fā)式搜索:A*算法,評價函數 f(x) = g(x) + h(x) ( 當h(n) = h*(n) ),n,S,G,g(n)=g*(n),h(n) = h*(n),A*算法要求保守估計： f(n) = f*(n),A*算法的定義,定義1 在圖搜索過程中，如果重排OPEN

31、表是依據f(x)=g(x)+h(x)進行的，則稱該過程為A算法。 定義2 在A算法中，如果對所有的x存在h(x)h*(x)（低估）,則稱h(x)為h*(x)的下界，它表示某種偏于保守的估計。 定義3 采用h*(x)的下界h(x)為啟發(fā)函數的A算法，稱為A*算法。,具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法的充分條件,1) 搜索樹上存在著從起始點到終了點的最優(yōu)路徑。 2) 問題域是有限的。 3）所有結點的子結點的搜索代價值0。 4)： h(n)=h*(n),為什么A*算法低估h值,在A*算法中，對所有的x存在h(x)h*(x)（低估) 在A*算法中,只有對h值低估才能獲得優(yōu)化

32、的搜索性能,為什么A*算法低估h值,舉例：,在多估情況下：,為什么A*算法低估h值,舉例：,如果h被低估:,2+1,啟發(fā)式搜索算法A*,Step1: 把初始節(jié)點S0放入OPEN表中; Step2: 若OPEN表為空,則搜索失敗,退出. Step3: 移出OPEN中第一個節(jié)點N放入CLOSED表 中, 并標以順序號n; Step4: 若目標節(jié)點Sg=N, 則搜索成功,結束. Step5: 若N不可擴展, 則轉Step2; Step6: 擴展N, 生成一組子節(jié)點, 對這組子節(jié)點作如下處 理后, 放入OPEN表, 按評價函數的升序重新排序 OPEN表, 轉 Step2; 刪除重復節(jié)點和修改返回指針處

33、理.,八數碼難題:,h1(T) 0 啟發(fā)函數為0,注意: h3(T) h2(T) h1(T),目標：,曼哈頓距離,八數碼難題舉例,Robot navigation,Cost of one horizontal/vertical step = 1 Cost of one diagonal step = 2,f(N) = g(N) + h(N), with h(N) =距離目標位置水平距離和垂直距離之和,Robot Navigation,Robot Navigation,f(N) = h(N), with h(N) =距離目標位置水平距離和垂直距離之,Robot Navigation,0,2,1,

34、1,5,8,7,7,3,4,7,6,7,6,3,2,8,6,4,5,2,3,3,3,6,5,2,4,4,3,5,5,4,6,5,6,4,5,f(N) = h(N), with h(N) =距離目標位置水平距離和垂直距離之,7,0,Robot Navigation,f(N) = g(N)+h(N), with h(N) = 距離目標位置水平距離和垂直距離之和,7+0,8+1,搜索算法小結,樹搜索-盲目搜索-廣度優(yōu)先搜索 -深度優(yōu)先搜索-有界深度優(yōu)先 -代價樹搜索 -啟發(fā)式搜索-全局擇優(yōu)搜索(最好優(yōu)先) -局部擇優(yōu)搜索(爬山法) -A算法( 基于: f(n)=g(n)+h(n) ) A*算法(最佳

35、搜索: h(n) =h*(n),復習,什么是寬度優(yōu)先、深度優(yōu)先、代價樹搜索？ 什么是啟發(fā)信息、啟發(fā)函數？ 什么是盲目搜索和啟發(fā)式搜索？ 什么是A算法和A*算法？ A*算法有什么特點？,討論,判斷：A*算法中 1 比目標節(jié)點遠的節(jié)點都不會被展開； 2 比目標節(jié)點近的節(jié)點都會被展開； 3 解是唯一的； 4 搜索的時間復雜度是指數的。 設評價函數為 f(N) =g(N) + h(N), 怎樣才能保證搜索到最優(yōu)解？設 f12(N) =K1 g(N) + K2 h(N)，討論K1 ,K2對搜索結果的影響？ 如何進一步提高搜索效率？（雙向、多起點、非確定),八數碼難題（8-puzzle problem）

36、用A*算法搜索， 給出搜索樹。,課堂練習,1 試用A*算法（ h(N) =距離目標位置水平距離和垂直距離之和）f(N) = g(N)+h(N) 對下圖進行搜索,作業(yè),規(guī)定允許動作：左、上、右、下,作業(yè),利用啟發(fā)式搜索，找出以下問題的解，并說明是否是最優(yōu)解？（可選） 2 1 6 1 2 3 4 8 = 8 4 7 5 3 7 6 5 請針對TSP問題，提出啟發(fā)式搜索策略，并對搜索效率進行分析？,4.3 問題歸約法,問題歸約的概念 問題歸約的描述: 三元組(S0, O, P)表示. S0:初始問題; P:本原問題集合 O:操作算子集;將問題化成若干子問題. 問題歸約的最終目標: 原問題 = 本原問

37、題 狀態(tài)空間法是問題歸約法的特例. 問題歸約的與或圖表示,與或圖表示,A,A,C6,C5,C4,C3,C2,C1,C6,C5,C4,C3,C2,C1,m1,m2,或節(jié)點,與節(jié)點,葉節(jié)點(或稱:端節(jié)點),3連接弧,節(jié)點的可解性判別,A,C6,C5,C4,C3,C2,C1,m1,m2,或節(jié)點,與節(jié)點,可解節(jié)點的判別條件 葉節(jié)點可解 或節(jié)點可解當且僅當至少有一個子節(jié)點可解. 與節(jié)點可解當且僅當所有子節(jié)點都可解. 不可解節(jié)點的判別條件 沒有子節(jié)點的非終止節(jié)點 或節(jié)點不可解當且僅當所有子節(jié)點不可解. 與節(jié)點不可解當且僅當至少有一個子節(jié)點不可解.,與或圖的搜索,A,C6,C5,C4,C3,C2,C1,m1

38、,m2,或節(jié)點,與節(jié)點,解圖,求解與或圖問題就是在與或圖中搜索解圖(或解樹)的問題. 解圖是原與或圖的一個子圖(與圖) 搜索策略:無信息搜索與啟發(fā)式搜索 搜索過程: 標記初始節(jié)點為可解節(jié)點(成功)或不可解節(jié)點(失敗)的過程. 搜索算法:,與或樹的搜索算法,1,Step1: S0 = OPEN表 Step2: OPEN -N- CLOSED (n) Step3: 如N可擴展: 擴展N=OPEN 標記可解節(jié)點=CLOSED 如初始節(jié)點可解,搜索成功,結束. 刪去OPEN中有可解先輩的節(jié)點. Step4: N不可擴展: 標記不可解節(jié)點.如初始節(jié)點不可解, 搜索失敗,退出. 刪去OPEN中有不可解先輩

39、的節(jié)點. To Step2.,5,4,A,t2,t3,t4,2,t1,B,3,問題歸約的例子,積分問題的與或樹 三階梵塔問題的與或樹 幾何定理證明的與或樹,4.4 博弈樹搜索,博弈樹的概念 博弈:下棋, 打牌等一類競爭性智力活動.最簡單的是“二人零和,全信息,非偶然”博弈. 博弈樹:描述博弈過程的與或樹. 特點: 或與節(jié)點分層交替出現(xià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

40、,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失敗 分幣原則:每次要將一堆分為幣數不等的兩堆 . 勝負標準:交替分錢幣,誰不能再分誰輸.,分錢幣游戲的博弈樹,結論: ?,(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

41、,1,min) min失敗 (2,1,1,1,1,1,max)max失敗 . max 可解節(jié)點 min可解節(jié)點,分錢幣游戲的博弈樹,結論: max必勝,錢幣為8，9時，結論如何？ 錢幣為10 時，結論如何？ 錢幣為 x 時，結論如何？,分錢幣游戲思考題,極大極小過程,B,A,I,H,G,F,C,Q,P,O,N,M,L,K,I,E,D,MAX,MIN,2 8 1 3 -2 5 7 -1 1,R,2,5,-2,2,2,-1,5,倒推過程,-剪枝技術,B,A,I,H,G,F,C,Q,P,O,N,M,L,K,I,E,D,MAX,MIN,2 8 1 3 -2 5 7,R,2,5, 1,MAX節(jié)點的下界

42、2,MIN節(jié)點的上界2,5,剪枝,剪枝,-剪枝技術,MAX節(jié)點的倒退值 : 取后繼節(jié)點估值的最大值. MAX節(jié)點的倒推下界值. MIN節(jié)點的倒退值 : 取后繼節(jié)估值點的最小值. MIN節(jié)點的倒推上界值. 剪枝: 當MIN節(jié)點的值 祖先MAX節(jié)點的值時,不必展開MIN的其余子節(jié)點. 剪枝: 當MAX節(jié)點的值 祖先MIN節(jié)點的值時,不必展開MAX的其余子節(jié)點.,討論,局部優(yōu)先搜索與全局優(yōu)先搜索的區(qū)別是什么? 什么是啟發(fā)式搜索？A算法？A*算法？ 博弈樹有什么特點? 利用博弈樹分析九枚分錢幣游戲的可能結論? -,4.5 局部搜索(Local Search)*,通過在當前解近旁的搜索,不斷改善當前解,

43、最終搜索到滿足要求的最優(yōu)解或次優(yōu)解. 一般過程 Step1: 初始化. 求初始解x0=當前解x, k=1; Step2: 完善解. 在x的近旁N(x)中如果有更好解y, 則 更新解x:=y, k:=k+1; To Step2 否則,輸出x, 停止搜索. 被用于大規(guī)模N-queen, SAT等問題的求解.,局部搜索法,初始解x0,x3,x4,x1,x2,x5,N(x0),N(x1),N(x5),局部搜索法的特征,局部搜索的要素 評價函數的確定 初始解的確定 N(x)的確定 解更新的方法 終止條件 特點：簡單,高效,但不完備-局部最優(yōu)解 改進方法:多起點、加入非確定性、 加入從局部最優(yōu)解脫出的方法,Nqueen問題的求解,Q,Q,Q,Q,Q,Q,Q,Q,Nqueen問題的求解,(皇后 N,方案