湖南大學人工智能課件3-2

第三章

PartII

有信息的搜索策略

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

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