《人工智能》搜索技術(shù).ppt_第1頁
《人工智能》搜索技術(shù).ppt_第2頁
《人工智能》搜索技術(shù).ppt_第3頁
《人工智能》搜索技術(shù).ppt_第4頁
《人工智能》搜索技術(shù).ppt_第5頁
已閱讀5頁,還剩121頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

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,方案

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論