湖南大學人工智能課件32

第三章

PartII

有信息的搜索策略

第三章

PartII

有信息的搜索策略

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

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

Qa？

第三章

PartII

有信息的搜索策略

第三章

PartII

有信息的搜索策略

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

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