人工智能課件

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

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

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

，從OPEN表中按照某種策略選擇一個狀態(tài)node。3.目標檢測：(1)若IsGoal(node)=True,則得一解,算法結束;(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已經在OPEN表中，且新路徑更短，則更新f(suc)的值為新代價；若suc已經在closed表中，且新路徑更短，則將closed表從CLOSED表移至OPEN表，并更新f(suc)；(3)跳轉到”

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

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

。雖然從節(jié)點n到任一目標節(jié)點g的所有路徑的最小代價尚不知道，但是可由領域知識對其作出估計，通過啟發(fā)函數h(n)實現。于是，f(n)表示從初始節(jié)點s經由節(jié)點n到達目標節(jié)點g的最優(yōu)路徑的代價估計值。啟發(fā)式搜索是OPEN表是優(yōu)先隊列的搜索。啟發(fā)式搜索算法舉例八數碼f(n)=g(n)+h(n)的選取g(n)=“x所在的搜索深度”；h(n)=“x與sg相比，錯位數字的數目”。錯位數h(n)=5。顯然，5≤“實際需要的最少步數”，滿足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ā)函數h(n)基于領域知識，前瞻（或猜測）從當前節(jié)點抵達任意目標節(jié)點的最小代價。

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

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

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

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

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

，從OPEN表中按照某種策略選擇一個狀態(tài)node。3.目標檢測：(1)若IsGoal(node)=True,則得一解,算法結束;(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)跳轉到”

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相比，錯位數字的曼哈頓距離之和”；h2(n)=“x與sg相比，錯位數字的數目”。h1(n)=6

；h2(n)=5。202831576412384765目標狀態(tài)sg當前狀態(tài)x思考題尋找從城市A到城市G的最短路徑21啟發(fā)函數h(n)城市到G的直線距離A300B210C150D165E80F120G0ABCDEFG270245265215100125150145165尋找從城市A到城市G的最短路徑22啟發(fā)函數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）生成的搜索樹中出現了目標G，算法結束了么？（2）為什么？26f(B)=480ABCD(e)擴展E之后BAEAGf(B)=605f(A)=790370+100=470f(A)=830f(G)=480CG495+150=64527思考題如何用A*求解旅行商問題？補充：如何設計A*的啟發(fā)函數松弛子問題多個啟發(fā)函數的復合迭加28啟發(fā)函數的設計原則和方法29降低了問題的行動（操作）限制，稱為松弛。以八數碼為例。八數碼的行動描述：A與B水平或垂直相鄰，且B是空的。松弛a：一個數字可以從方格A移動到方格B，如果A與B相鄰；松弛b：一個數字可以從方格A移動到方格B，如果B是空的。松弛c：一個數字可以從方格A移動到方格B。注意：將松弛問題作為啟發(fā)函數時，應保證容易求解。啟發(fā)函數的設計原則和方法如果有多個可納式啟發(fā)函數可用，h1,h2,…,hn，選擇哪個最好？可以通過定義多個函數的