人工智能課件

人工智能徐長明第五章主要內(nèi)容閱讀教材5.1、5.2、5.3、5.4、5.5。爬山法和動態(tài)規(guī)劃法最佳優(yōu)先搜索算法可納性、單調(diào)性以及信息性博弈樹搜索計算復雜度最佳優(yōu)先搜索g搜索就是尋找問題的解的過程，即，尋找從初始狀態(tài)s到目標狀態(tài)g的路徑。假設(shè)單步的路徑耗散值非負，即，cost(x,y)≥0。xys基本要素：初始狀態(tài)后繼函數(shù)目標測試路徑耗散一般的圖搜索數(shù)據(jù)結(jié)構(gòu)OPEN表：保存待擴展的節(jié)點（也稱前端節(jié)點或邊緣節(jié)點）。CLOSED表：保存已擴展了的節(jié)點。評價函數(shù)量化從任意狀態(tài)n到某個目標狀態(tài)代價的評價函數(shù)f(n)。算法的三個關(guān)鍵步驟：選擇、目標檢測、擴展。一般的圖搜索算法描述圖搜索算法的執(zhí)行過程描述：1.初始化：OPEN={初始狀態(tài)s}，CLOSED=

。2.選擇：(1)若OPEN=

，搜索算法失敗；(2)OPEN

，從OPEN表中按照某種策略選擇一個狀態(tài)node。3.目標檢測：(1)若IsGoal(node)=True,則得一解,算法結(jié)束;(2)若IsGoal(node)=False,則執(zhí)行”4.擴展”.4.擴展：(1)生成直接后繼的集合T

GenAllSuccessors(node)

;(2)計算f(suc)，更新OPEN表和CLOSED表。將node移至CLOSE表，對

suc

T：若suc不OPEN表或CLOSED表中，則計算f(suc)，并將suc加入OPEN表中；若suc已經(jīng)在OPEN表中，且新路徑更短，則更新f(suc)的值為新代價；若suc已經(jīng)在closed表中，且新路徑更短，則將closed表從CLOSED表移至OPEN表，并更新f(suc)；(3)跳轉(zhuǎn)到”

2.選擇”.一般的啟發(fā)式搜索算法搜索算法的不同，歸根結(jié)底在于，對OPEN表節(jié)點擴展順序的策略不同。OPEN表節(jié)點擴展策略一般受制于一下因素：稱為評價函數(shù)的f(n)。其中，n可以是任意節(jié)點。一般地，f(n)有實際意義，如表示代價或耗散時，值越小越好。選擇下一個節(jié)點時考慮OPEN表哪些節(jié)點。一般地，評價函數(shù)定義為

f(n)=g(n)+h(n)搜索算法或許已發(fā)現(xiàn)多條從初始節(jié)點s到節(jié)點n的路徑，它們的最小代價為g(n)

。雖然從節(jié)點n到任一目標節(jié)點g的所有路徑的最小代價尚不知道，但是可由領(lǐng)域知識對其作出估計，通過啟發(fā)函數(shù)h(n)實現(xiàn)。于是，f(n)表示從初始節(jié)點s經(jīng)由節(jié)點n到達目標節(jié)點g的最優(yōu)路徑的代價估計值。啟發(fā)式搜索是OPEN表是優(yōu)先隊列的搜索。啟發(fā)式搜索算法舉例八數(shù)碼f(n)=g(n)+h(n)的選取g(n)=“x所在的搜索深度”；h(n)=“x與sg相比，錯位數(shù)字的數(shù)目”。錯位數(shù)h(n)=5。顯然，5≤“實際需要的最少步數(shù)”，滿足h(n)≤h*(n)。112831576412384765目標狀態(tài)sg當前狀態(tài)x貪婪搜索啟發(fā)式搜索也稱最佳優(yōu)先搜索。貪婪搜索或貪婪最佳優(yōu)先搜索：f(n)=h(n)若n是目標節(jié)點，則h(n)=0。啟發(fā)函數(shù)h(n)基于領(lǐng)域知識，前瞻（或猜測）從當前節(jié)點抵達任意目標節(jié)點的最小代價。

h(n)越小，代表n越有希望好?？杉{性、單調(diào)性、信息度A*搜索若一個啟發(fā)式搜索：對任意節(jié)點n，h(n)

h*(n)，且對所有目標節(jié)點g有h(g)=0，則稱之為A*搜索?？杉{性。啟發(fā)函數(shù)對任意節(jié)點n滿足滿足h(n)

h*(n)，則稱該算法是可納的，稱h是可納的啟發(fā)函數(shù)。根據(jù)A*定義，所有A*搜索都是可納的?？杉{性請證明：A*算法是最優(yōu)的。證：若問題有解，令最優(yōu)解G的耗散為C*。假設(shè)一個非最優(yōu)解G‘出現(xiàn)在邊緣上。G‘是解，故h(G’)=0，f(G‘)=g(G’)+h(G‘)=g(G’)>C*。對于任意一個處于最優(yōu)解路徑上的結(jié)點n，而f(n)不會高估經(jīng)過n的最優(yōu)解的路徑耗散，總有f(n)≤f(G)=C*。f(n)≤C*<f(G’)綜上，故G’將不會得到擴展，算法最終將得到最優(yōu)解。單調(diào)性單調(diào)性（一致性）。h(n)滿足以下條件就是一致的：對于每個結(jié)點n，通過任何行動a生成的n的每個后繼結(jié)點n‘，滿足下列三角不等式：h(n)≤cost(n,a,n‘)+h(n‘)。該三角形是由n，n‘和離n最近的目標構(gòu)成。試證明：如果h(n)是一致的，那么，它一定也是可納的。如果h(n)是一致的，那么，沿著任何路徑的f(n)值是非遞減的。具有單調(diào)性的啟發(fā)函數(shù)的A*啟發(fā)函數(shù)具有單調(diào)性的A*搜索算法的執(zhí)行過程描述：1.初始化：OPEN={初始狀態(tài)s}，CLOSED=

。2.選擇：(1)若OPEN=

，搜索算法失??；(2)OPEN

，從OPEN表中按照某種策略選擇一個狀態(tài)node。3.目標檢測：(1)若IsGoal(node)=True,則得一解,算法結(jié)束;(2)若IsGoal(node)=False,則執(zhí)行”4.擴展”.4.擴展：(1)生成直接后繼的集合T

GenAllSuccessors(node)

;(2)

suc

T,

suc在OPEN表，則更新f(suc)；若suc在CLOSED表，則不做任何操作；否則，將f(suc)賦予suc并放入OPEN表；

(3)OPEN

OPEN

T,CLOSED

CLOSED

{node};(4)跳轉(zhuǎn)到”

2.選擇”.信息度信息度。何時一個啟發(fā)策略要比另一個啟發(fā)策略好？在兩個A*啟發(fā)策略的h1和h2中，如對搜索空間中的任一狀態(tài)n都有h1(n)

h2(n)

h*(n)，就稱策略h2比h1具有更多的信息度（或h2比h1更占優(yōu)）須注意的是：更多的信息性需要更多的計算時間，從而有可能抵消減少搜索空間所帶來的益處！h1(n)=“x與sg相比，錯位數(shù)字的曼哈頓距離之和”；h2(n)=“x與sg相比，錯位數(shù)字的數(shù)目”。h1(n)=6

；h2(n)=5。202831576412384765目標狀態(tài)sg當前狀態(tài)x思考題尋找從城市A到城市G的最短路徑21啟發(fā)函數(shù)h(n)城市到G的直線距離A300B210C150D165E80F120G0ABCDEFG270245265215100125150145165尋找從城市A到城市G的最短路徑22啟發(fā)函數(shù)h(n)城市到G的直線距離A300B210C150D165E80F120G0ABCDEFG270245265215100125150145165A*搜索搜索最短路徑的過程23g(A)=0h(A)=300f(A)=300270+210=480ABCDA245+150=395265+165=430(a)初始狀態(tài)(b)擴展A之后考慮將A*搜索用于樹搜索。即，下述過程沒有考慮狀態(tài)重復的問題。(a)～(e)描述了搜索的幾個階段。24f(B)=480ABCD395+210=605(c)擴展C之后f(D)=430BAE490+300=790370+80=45025f(B)=480ABCD(d)擴展D之后f(D)=430BAEAGf(B)=605f(A)=790f(E)=450530+300=830480+0=480問題：（1）生成的搜索樹中出現(xiàn)了目標G，算法結(jié)束了么？（2）為什么？26f(B)=480ABCD(e)擴展E之后BAEAGf(B)=605f(A)=790370+100=470f(A)=830f(G)=480CG495+150=64527思考題如何用A*求解旅行商問題？補充：如何設(shè)計A*的啟發(fā)函數(shù)松弛子問題多個啟發(fā)函數(shù)的復合迭加28啟發(fā)函數(shù)的設(shè)計原則和方法29降低了問題的行動（操作）限制，稱為松弛。以八數(shù)碼為例。八數(shù)碼的行動描述：A與B水平或垂直相鄰，且B是空的。松弛a：一個數(shù)字可以從方格A移動到方格B，如果A與B相鄰；松弛b：一個數(shù)字可以從方格A移動到方格B，如果B是空的。松弛c：一個數(shù)字可以從方格A移動到方格B。注意：將松弛問題作為啟發(fā)函數(shù)時，應保證容易求解。啟發(fā)函數(shù)的設(shè)計原則和方法如果有多個可納式啟發(fā)函數(shù)可用，h1,h2,…,hn，選擇哪個最好？可以通過定義多個函數(shù)的