湖南大學(xué)人工智能課件32

第三章

PartII

有信息的搜索策略

第三章

PartII

有信息的搜索策略

2015年1月湖南大學(xué)信息科學(xué)與工程學(xué)院內(nèi)容提要最佳優(yōu)先搜索貪婪最佳優(yōu)先搜索A*搜索啟發(fā)式函數(shù)松弛問題內(nèi)容提要最佳優(yōu)先搜索2回顧：樹搜索一種搜索策略實際上就是根據(jù)樹結(jié)點擴(kuò)張的順序來決定的回顧：樹搜索一種搜索策略實際上就是根據(jù)樹結(jié)點擴(kuò)張的順序來決定3最佳優(yōu)先搜索基本思路：通過對每一個結(jié)點設(shè)置一個評價函數(shù)f(n),找到一個代價最低的未擴(kuò)散的結(jié)點實現(xiàn)：根據(jù)結(jié)點的評價函數(shù)值從低到高在隊列中對結(jié)點進(jìn)行排序

大多數(shù)評價函數(shù)由啟發(fā)函數(shù)h構(gòu)成h(n):結(jié)點到目標(biāo)結(jié)點的最小代價路徑的代價估計值最佳優(yōu)先搜索基本思路：4最佳優(yōu)先搜索最佳優(yōu)先搜索vs.一致代價搜索？代價函數(shù)的定義不同算法實例貪婪最佳優(yōu)先搜索A*樹最佳優(yōu)先搜索最佳優(yōu)先搜索vs.一致代價搜索？5Romania問題Romania問題6貪婪最佳優(yōu)先搜索評價函數(shù)f(n)=h(n)從結(jié)點n到目標(biāo)結(jié)點的代價估測值羅馬尼亞問題：貪婪最佳優(yōu)先搜索首先擴(kuò)展與目標(biāo)結(jié)點估測距離最近的結(jié)點羅馬尼亞問題中使用直線距離為估測距離貪婪最佳優(yōu)先搜索評價函數(shù)f(n)=h(n)7貪婪最佳優(yōu)先搜索貪婪最佳優(yōu)先搜索8貪婪最佳優(yōu)先搜索完備性？最優(yōu)性？時間復(fù)雜度：O(bm)空間復(fù)雜度:O(bm)貪婪最佳優(yōu)先搜索完備性？9A*搜索評價函數(shù)f(n)=g(n)+h(n)g(n)=到達(dá)結(jié)點n已經(jīng)花費的代價h(n)=結(jié)點n到目標(biāo)節(jié)點的評估代價f(n)=通過結(jié)點n到達(dá)目標(biāo)結(jié)點的總評估代價A*搜索評價函數(shù)10A*搜索A*搜索11A*搜索A*搜索12可采納的啟發(fā)函數(shù)啟發(fā)函數(shù)h(n)是可采納的條件：如果對于每個結(jié)點n,h(n)<h*(n)，其中h*(n)是到達(dá)目標(biāo)結(jié)點的真實代價可采納啟發(fā)函數(shù)絕不會高估到達(dá)目標(biāo)結(jié)點的代價，因此它是最優(yōu)的可采納的啟發(fā)函數(shù)啟發(fā)函數(shù)h(n)是可采納的條件：13A*算法的最優(yōu)化證明定理：如果啟發(fā)函數(shù)h(n)是可采納的，那么A*使用樹搜索是最優(yōu)的證明：假定存在一個局部最優(yōu)目標(biāo)G2和一個全局最優(yōu)目標(biāo)G,設(shè)n是一個未擴(kuò)散的結(jié)點且n在到達(dá)G的最短路徑上，n,G2都位于算法的fringe隊列之中如下圖所示A*算法的最優(yōu)化證明定理：如果啟發(fā)函數(shù)h(n)是可采納的，那14A*算法的最優(yōu)化證明A*算法的最優(yōu)化證明15一致性啟發(fā)一個啟發(fā)函數(shù)是一致的條件：對于任意一個結(jié)點n，以及n的行為a產(chǎn)生的后繼結(jié)點n’,滿足如下公式：h(n)≤c(n,a,n')+h(n')如果h(n)是一致的，我們得到一致性啟發(fā)一個啟發(fā)函數(shù)是一致的條件：16A*算法的最優(yōu)化證明定理：如果h(n)是一致的，A*使用圖搜索是最優(yōu)的證明：A*根據(jù)f值從小到大擴(kuò)展結(jié)點;A*選擇擴(kuò)散結(jié)點n時，就已經(jīng)找到了達(dá)到結(jié)點n的最優(yōu)路徑A*算法的最優(yōu)化證明定理：如果h(n)是一致的，A*使用圖搜17A*算法的屬性Environment:Patient,hospital,staffActuators:Screendisplay(questions,tests,diagnoses,treatments,referrals)Sensors:Keyboard(entryofsymptoms,findings,patient'sanswers)完備性每步的代價都大于某個常數(shù)e，并且分支數(shù)b是有限的最優(yōu)性時間復(fù)雜度O(bΔ)空間復(fù)雜度O(bΔ)A*算法的屬性Environment:Patient,18啟發(fā)式函數(shù)19例子：八數(shù)碼問題平均解的深度？22平均分支因數(shù)？3啟發(fā)式函數(shù)19例子：八數(shù)碼問題啟發(fā)式函數(shù)20例子：八數(shù)碼問題h1(n):不在位的棋子數(shù)h2(n):所有棋子到其目標(biāo)位置的距離和h1(n)=8,h2(n):=3+1+2+2+2+3+3+2=18啟發(fā)式函數(shù)20例子：八數(shù)碼問題啟發(fā)式搜索性能分析21有效分支因子：對于某一問題，如果A*算法生成的總結(jié)點數(shù)為N,解的深度為d,那么b*就是深度為d的標(biāo)準(zhǔn)搜索樹為了能夠包括N+1個結(jié)點所必需的分支因子 N+1=1+b*+(b*)2+…+(b*)d有效分支因子越小，算法性能越好啟發(fā)式搜索性能分析21有效分支因子：對于某一問題，如果A*算啟發(fā)式搜索性能分析22SearchCost(nodesgenerated)EffectiveBranchingFactordIDSA*(h1)A*(h2)IDSA*(h1)A*(h2)210662.451.791.79411213122.871.481.45668020182.731.341.308638439252.801.331.24104712793392.781.381.22啟發(fā)式搜索性能分析22SearchCost(nodesg優(yōu)勢23對于所有的結(jié)點n,h1(n)>=h2(n)(兩個函數(shù)都是可采納的)，我們說h2(n)比h1(n)有優(yōu)勢。典型的搜索代價(平均結(jié)點擴(kuò)展數(shù))：d=12IDS=3,644,035nodesA*(h1)=227nodesA*(h2)=73nodesd=24IDS=toomanynodesA*(h1)=39,135nodesA*(h2)=1,641nodes優(yōu)勢23對于所有的結(jié)點n,h1(n)>=h2(n)(兩個松弛問題減少了行動限制的問題稱為松弛問題。松弛問題增加了狀態(tài)空間的邊原有問題的任一最優(yōu)解同樣也是松弛問題的最優(yōu)解，但松弛問題可能存在更好的解。松弛問題減少了行動限制的問題稱為松弛問題。24松弛問題八數(shù)碼問題行動描述棋子可以從方格A移動到方格B如果A與B水平或者垂直相鄰并且B是空的三個松弛問題：去掉條件B的空的：h2將給出最短解的確切步數(shù)去掉條件AB相鄰上述兩者都去掉：h1將給出最短解的確切步數(shù)松弛問題八數(shù)碼問題25總結(jié)最佳優(yōu)先搜索貪婪最佳優(yōu)先搜索A*搜索啟發(fā)式函數(shù)松弛問題總結(jié)最佳優(yōu)先搜索26Qa？

Qa？

第三章

PartII

有信息的搜索策略

第三章

PartII

有信息的搜索策略

2015年1月湖南大學(xué)信息科學(xué)與工程學(xué)院內(nèi)容提要最佳優(yōu)先搜索貪婪最佳優(yōu)先搜索A*搜索啟發(fā)式函數(shù)松弛問題內(nèi)容提要最佳優(yōu)先搜索29回顧：樹搜索一種搜索策略實際上就是根據(jù)樹結(jié)點擴(kuò)張的順序來決定的回顧：樹搜索一種搜索策略實際上就是根據(jù)樹結(jié)點擴(kuò)張的順序來決定30最佳優(yōu)先搜索基本思路：通過對每一個結(jié)點設(shè)置一個評價函數(shù)f(n),找到一個代價最低的未擴(kuò)散的結(jié)點實現(xiàn)：根據(jù)結(jié)點的評價函數(shù)值從低到高在隊列中對結(jié)點進(jìn)行排序

大多數(shù)評價函數(shù)由啟發(fā)函數(shù)h構(gòu)成h(n):結(jié)點到目標(biāo)結(jié)點的最小代價路徑的代價估計值最佳優(yōu)先搜索基本思路：31最佳優(yōu)先搜索最佳優(yōu)先搜索vs.一致代價搜索？代價函數(shù)的定義不同算法實例貪婪最佳優(yōu)先搜索A*樹最佳優(yōu)先搜索最佳優(yōu)先搜索vs.一致代價搜索？32Romania問題Romania問題33貪婪最佳優(yōu)先搜索評價函數(shù)f(n)=h(n)從結(jié)點n到目標(biāo)結(jié)點的代價估測值羅馬尼亞問題：貪婪最佳優(yōu)先搜索首先擴(kuò)展與目標(biāo)結(jié)點估測距離最近的結(jié)點羅馬尼亞問題中使用直線距離為估測距離貪婪最佳優(yōu)先搜索評價函數(shù)f(n)=h(n)34貪婪最佳優(yōu)先搜索貪婪最佳優(yōu)先搜索35貪婪最佳優(yōu)先搜索完備性？最優(yōu)性？時間復(fù)雜度：O(bm)空間復(fù)雜度:O(bm)貪婪最佳優(yōu)先搜索完備性？36A*搜索評價函數(shù)f(n)=g(n)+h(n)g(n)=到達(dá)結(jié)點n已經(jīng)花費的代價h(n)=結(jié)點n到目標(biāo)節(jié)點的評估代價f(n)=通過結(jié)點n到達(dá)目標(biāo)結(jié)點的總評估代價A*搜索評價函數(shù)37A*搜索A*搜索38A*搜索A*搜索39可采納的啟發(fā)函數(shù)啟發(fā)函數(shù)h(n)是可采納的條件：如果對于每個結(jié)點n,h(n)<h*(n)，其中h*(n)是到達(dá)目標(biāo)結(jié)點的真實代價可采納啟發(fā)函數(shù)絕不會高估到達(dá)目標(biāo)結(jié)點的代價，因此它是最優(yōu)的可采納的啟發(fā)函數(shù)啟發(fā)函數(shù)h(n)是可采納的條件：40A*算法的最優(yōu)化證明定理：如果啟發(fā)函數(shù)h(n)是可采納的，那么A*使用樹搜索是最優(yōu)的證明：假定存在一個局部最優(yōu)目標(biāo)G2和一個全局最優(yōu)目標(biāo)G,設(shè)n是一個未擴(kuò)散的結(jié)點且n在到達(dá)G的最短路徑上，n,G2都位于算法的fringe隊列之中如下圖所示A*算法的最優(yōu)化證明定理：如果啟發(fā)函數(shù)h(n)是可采納的，那41A*算法的最優(yōu)化證明A*算法的最優(yōu)化證明42一致性啟發(fā)一個啟發(fā)函數(shù)是一致的條件：對于任意一個結(jié)點n，以及n的行為a產(chǎn)生的后繼結(jié)點n’,滿足如下公式：h(n)≤c(n,a,n')+h(n')如果h(n)是一致的，我們得到一致性啟發(fā)一個啟發(fā)函數(shù)是一致的條件：43A*算法的最優(yōu)化證明定理：如果h(n)是一致的，A*使用圖搜索是最優(yōu)的證明：A*根據(jù)f值從小到大擴(kuò)展結(jié)點;A*選擇擴(kuò)散結(jié)點n時，就已經(jīng)找到了達(dá)到結(jié)點n的最優(yōu)路徑A*算法的最優(yōu)化證明定理：如果h(n)是一致的，A*使用圖搜44A*算法的屬性Environment:Patient,hospital,staffActuators:Screendisplay(questions,tests,diagnoses,treatments,referrals)Sensors:Keyboard(entryofsymptoms,findings,patient'sanswers)完備性每步的代價都大于某個常數(shù)e，并且分支數(shù)b是有限的最優(yōu)性時間復(fù)雜度O(bΔ)空間復(fù)雜度O(bΔ)A*算法的屬性Environment:Patient,45啟發(fā)式函數(shù)46例子：八數(shù)碼問題平均解的深度？22平均分支因數(shù)？3啟發(fā)式函數(shù)19例子：八數(shù)碼問題啟發(fā)式函數(shù)47例子：八數(shù)碼問題h1(n):不在位的棋子數(shù)h2(n):所有棋子到其目標(biāo)位置的距離和h1(n)=8,h2(n):=3+1+2+2+2+3+3+2=18啟發(fā)式函數(shù)20例子：八數(shù)碼問題啟發(fā)式搜索性能分析48有效分支因子：對于某一問題，如果A*算法生成的總結(jié)點數(shù)為N,解的深度為d,那么b*就是深度為d的標(biāo)準(zhǔn)搜索樹為了能夠包括N+1個結(jié)點所必需的分支因子 N+1=1+b*+(b*)2+…+(b*)d有效分支因子越小，算法性能越好啟發(fā)式搜索性能分析21有效分支因子：對于某一問題，如果A*算啟發(fā)式搜索性能分析49SearchCost(nodesgenerated)EffectiveBranchingFactordIDSA*(h1)A*(h2)IDSA*(h1)A*(h2)210662.451.791.79411213122.871.481.45668020182.731.341.308638439252.801.331.24104712793392.781.381.22啟發(fā)式搜索性能分析22Se