湖南大學(xué)人工智能課件3-2

第三章

PartII

有信息的搜索策略

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

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