《人工智能》搜索技術(shù).ppt

1、第四章 搜索技術(shù),狀態(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)組合爆炸,魔方問題 博弈問題 皇后問題 行商問題 排課問題（調(diào)度問題） 背包問題 ,數(shù)碼問題,（初始狀態(tài)）,八數(shù)碼難題（8-puzzle problem）,4.1 狀態(tài)圖概念,狀態(tài)圖的概念 狀態(tài)圖(狀態(tài)空間圖)實(shí)際上是一類問題的抽象表示。 許多智力問題(八數(shù)碼問題、梵塔問題、旅行商問題、八皇后問題、農(nóng)夫過河問題等)。 實(shí)際問題（如

2、路徑規(guī)劃、定理證明、演繹推理、機(jī)器人行動(dòng)規(guī)劃等）都可以歸結(jié)為在某一狀態(tài)圖中尋找目標(biāo)或路徑的問題。,農(nóng)夫過河問題,有一個(gè)農(nóng)夫帶一條狼、一只羊和一棵白菜過河。如果沒有農(nóng)夫看管，則狼要吃羊，羊要吃白菜。但是船很小，只夠農(nóng)夫帶一樣?xùn)|西過河。問農(nóng)夫該如何解此難題？,農(nóng)夫過河問題狀態(tài)空間法表示,以向量（人，狼，羊，菜）表示狀態(tài)，其中每個(gè)變元可取0或1，取0表示在左岸（出發(fā)點(diǎn)），取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:目標(biāo)狀態(tài)集合 狀態(tài)空間的搜索策略(狀態(tài)圖搜索) 廣度優(yōu)先搜索, 深度優(yōu)先搜索, 啟發(fā)式搜索,狀態(tài)空間表示的概念,例如下棋、迷宮及各種游戲。,Middle State,Goal State,三數(shù)碼難題,初始棋局,目標(biāo)棋局,1,八數(shù)碼難題的寬度優(yōu)先搜索樹,狀態(tài)圖搜索,圖搜索是指在狀態(tài)圖中尋找目標(biāo)或路徑的搜索。 所謂搜索，顧名思義，就是從初始節(jié)點(diǎn)出發(fā)，沿著與之相連的邊試探地前進(jìn)，尋找目標(biāo)節(jié)點(diǎn)的過程(也可以反向進(jìn)行)。,問題,狀態(tài)圖,搜索,解,解是由初始狀態(tài)到目標(biāo)

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

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

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

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

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

9、。,1,圖 八數(shù)碼難題的寬度優(yōu)先搜索樹,寬度優(yōu)先搜索(Breadth-First Strategy),新的節(jié)點(diǎn)被插入到棧OPEN的后部,1,OPEN= (1),CLOSED=( ),6,7,8,9,10,11,12,13,14,15,寬度優(yōu)先搜索(Breadth-First Strategy),新的節(jié)點(diǎn)被插入到棧OPEN的后部,1,OPEN= (2,3),CLOSED=(1 ),6,7,8,9,10,11,12,13,14,15,寬度優(yōu)先搜索(Breadth-First Strategy),新的節(jié)點(diǎn)被插入到棧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é)點(diǎn)被插入到棧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é)點(diǎn)被插入到棧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é)點(diǎn)被插入到棧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é)點(diǎn)被插入到棧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é)點(diǎn)優(yōu)先擴(kuò)展, 直到達(dá)到一定的深度限制.若找不到目標(biāo)或無法在擴(kuò)展時(shí),回溯到另一節(jié)點(diǎn)繼續(xù)擴(kuò)展. 特點(diǎn): 需要深度限制, 需要回溯控制, 省空間 探索算法: 數(shù)據(jù)結(jié)構(gòu): OPEN表 : 后進(jìn)先出隊(duì)列,存放待擴(kuò)

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

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

14、( 1,2 ),6,7,8,9,10,11,12,13,14,15,Depth-First Strategy,新的節(jié)點(diǎn)被插入到棧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é)點(diǎn)被插入到棧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é)點(diǎn)被插入到棧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é)點(diǎn)被插入到棧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é)點(diǎn)被插入到棧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é)點(diǎn)被插入到棧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é)點(diǎn)被插入到棧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é)點(diǎn)被插入到棧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),代價(jià)樹搜索,代價(jià)樹：搜

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

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

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

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

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

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

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

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

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

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

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

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

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

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

31、表是依據(jù)f(x)=g(x)+h(x)進(jìn)行的，則稱該過程為A算法。 定義2 在A算法中，如果對所有的x存在h(x)h*(x)（低估）,則稱h(x)為h*(x)的下界，它表示某種偏于保守的估計(jì)。 定義3 采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。,具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法的充分條件,1) 搜索樹上存在著從起始點(diǎn)到終了點(diǎn)的最優(yōu)路徑。 2) 問題域是有限的。 3）所有結(jié)點(diǎn)的子結(jié)點(diǎn)的搜索代價(jià)值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é)點(diǎn)S0放入OPEN表中; Step2: 若OPEN表為空,則搜索失敗,退出. Step3: 移出OPEN中第一個(gè)節(jié)點(diǎn)N放入CLOSED表 中, 并標(biāo)以順序號n; Step4: 若目標(biāo)節(jié)點(diǎn)Sg=N, 則搜索成功,結(jié)束. Step5: 若N不可擴(kuò)展, 則轉(zhuǎn)Step2; Step6: 擴(kuò)展N, 生成一組子節(jié)點(diǎn), 對這組子節(jié)點(diǎn)作如下處 理后, 放入OPEN表, 按評價(jià)函數(shù)的升序重新排序 OPEN表, 轉(zhuǎn) Step2; 刪除重復(fù)節(jié)點(diǎn)和修改返回指針處

33、理.,八數(shù)碼難題:,h1(T) 0 啟發(fā)函數(shù)為0,注意: h3(T) h2(T) h1(T),目標(biāo)：,曼哈頓距離,八數(shù)碼難題舉例,Robot navigation,Cost of one horizontal/vertical step = 1 Cost of one diagonal step = 2,f(N) = g(N) + h(N), with h(N) =距離目標(biāo)位置水平距離和垂直距離之和,Robot Navigation,Robot Navigation,f(N) = h(N), with h(N) =距離目標(biāo)位置水平距離和垂直距離之,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) =距離目標(biāo)位置水平距離和垂直距離之,7,0,Robot Navigation,f(N) = g(N)+h(N), with h(N) = 距離目標(biāo)位置水平距離和垂直距離之和,7+0,8+1,搜索算法小結(jié),樹搜索-盲目搜索-廣度優(yōu)先搜索 -深度優(yōu)先搜索-有界深度優(yōu)先 -代價(jià)樹搜索 -啟發(fā)式搜索-全局擇優(yōu)搜索(最好優(yōu)先) -局部擇優(yōu)搜索(爬山法) -A算法( 基于: f(n)=g(n)+h(n) ) A*算法(最佳

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

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

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

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

39、的節(jié)點(diǎn). To Step2.,5,4,A,t2,t3,t4,2,t1,B,3,問題歸約的例子,積分問題的與或樹 三階梵塔問題的與或樹 幾何定理證明的與或樹,4.4 博弈樹搜索,博弈樹的概念 博弈:下棋, 打牌等一類競爭性智力活動(dòng).最簡單的是“二人零和,全信息,非偶然”博弈. 博弈樹:描述博弈過程的與或樹. 特點(diǎn): 或與節(jié)點(diǎn)分層交替出現(xiàn); 搜索空間指數(shù)增長,只能前推幾步 極大極小過程 剪枝技術(shù),(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失敗 分幣原則:每次要將一堆分為幣數(shù)不等的兩堆 . 勝負(fù)標(biāo)準(zhǔn):交替分錢幣,誰不能再分誰輸.,分錢幣游戲的博弈樹,結(jié)論: ?,(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é)點(diǎn) min可解節(jié)點(diǎn),分錢幣游戲的博弈樹,結(jié)論: max必勝,錢幣為8，9時(shí)，結(jié)論如何？ 錢幣為10 時(shí)，結(jié)論如何？ 錢幣為 x 時(shí)，結(jié)論如何？,分錢幣游戲思考題,極大極小過程,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,倒推過程,-剪枝技術(shù),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é)點(diǎn)的下界

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

43、最終搜索到滿足要求的最優(yōu)解或次優(yōu)解. 一般過程 Step1: 初始化. 求初始解x0=當(dāng)前解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),局部搜索法的特征,局部搜索的要素 評價(jià)函數(shù)的確定 初始解的確定 N(x)的確定 解更新的方法 終止條件 特點(diǎn)：簡單,高效,但不完備-局部最優(yōu)解 改進(jìn)方法:多起點(diǎn)、加入非確定性、 加入從局部最優(yōu)解脫出的方法,Nqueen問題的求解,Q,Q,Q,Q,Q,Q,Q,Q,Nqueen問題的求解,(皇后 N,方案