人工智能原理第4章知識表示

1、 12.1 搜索與問題求解2.2 無信息搜索策略2.3 啟發(fā)式搜索策略2.4 局部搜索算法2.5 約束滿足問題2.6 博弈搜索參考書目附錄 A*算法可采納性的證明第2章 搜索技術(shù)22.4 局部搜索算法2.4.1 局部搜索與最優(yōu)化2.4.2 爬山法搜索2.4.3 模擬退火搜索2.4.4 局部剪枝搜索2.4.5 遺傳算法第2章 搜索技術(shù)3 前面的搜索算法都是保留搜索路徑的，到達(dá)目標(biāo)的路徑就是問題的解然而許多問題中到達(dá)目標(biāo)的路徑是無關(guān)緊要的 與系統(tǒng)地搜索狀態(tài)空間(保留各種路徑)相對，不關(guān)心路徑的搜索算法就是局部搜索算法 局部搜索從一個單獨的當(dāng)前狀態(tài)出發(fā)，通常只移動到相鄰狀態(tài) 典型情況下搜索的路徑不保

2、留第2章 搜索技術(shù)4 集成電路設(shè)計 工廠場地布局 車間作業(yè)調(diào)度 自動程序設(shè)計 電信網(wǎng)絡(luò)優(yōu)化 車輛尋徑 文件夾管理第2章 搜索技術(shù)5 局部搜索算法的優(yōu)點： 只使用很少的內(nèi)存(通常是一個常數(shù)) 經(jīng)常能在不適合系統(tǒng)化算法的很大或無限的狀態(tài)空間中找到合理的解 最優(yōu)化問題根據(jù)一個目標(biāo)函數(shù)找到最佳狀態(tài) / 只有目標(biāo)函數(shù)，而不考慮(沒有)“目標(biāo)測試”和“路徑耗散” 局部搜索算法適用于最優(yōu)化問題第2章 搜索技術(shù)6第2章 搜索技術(shù)山肩目 標(biāo) 函數(shù)全 局 最 大值局 部 最 大值“平坦”局部最大值狀 態(tài) 空間當(dāng) 前 狀態(tài)7 在狀態(tài)圖中，既有“位置”(用狀態(tài)表示)又有“高度”(用耗散值或目標(biāo)函數(shù)值表示) 如果高度對

3、應(yīng)于耗散值，則目標(biāo)是找到全局最小值，即圖中最低點 如果高度對應(yīng)于目標(biāo)函數(shù)，則目標(biāo)是找到全局最大值，即圖中最高峰 如果存在解，則完備的局部搜索算法能夠找到解 而最優(yōu)的局部搜索算法能夠找到全局最大或最小值第2章 搜索技術(shù)8 本節(jié)簡要介紹以下4種局部搜索算法 / 介紹其算法思想 爬山法搜索 模擬退火搜索 局部剪枝搜索 遺傳算法 從搜索的角度看遺傳算法也是搜索假設(shè)空間的一種方法(學(xué)習(xí)問題歸結(jié)為搜索問題)生成后繼假設(shè)的方式第2章 搜索技術(shù)9 爬山法(hill-climbing)就是向值增加的方向持續(xù)移動登高過程 / 如果相鄰狀態(tài)中沒有比它更高的值，則算法結(jié)束于頂峰 爬山法搜索算法思想：(1)令初始狀態(tài)S

4、0為當(dāng)前狀態(tài)(2)若當(dāng)前狀態(tài)已經(jīng)達(dá)標(biāo)，則算法運行結(jié)束，搜索成功(3)若存在一個動作可以作用于當(dāng)前狀態(tài)以產(chǎn)生一個新狀態(tài)，使新狀態(tài)的估計值優(yōu)于當(dāng)前狀態(tài)的估計值，則放棄當(dāng)前狀態(tài)，并令剛產(chǎn)生的新狀態(tài)為當(dāng)前狀態(tài)，轉(zhuǎn)(2)(4)取當(dāng)前狀態(tài)為相對最優(yōu)解，停止執(zhí)行算法第2章 搜索技術(shù)10 爬山法是一種局部貪婪搜索，不是最優(yōu)解算法(或是不完備的) / 其問題是： 局部極大值比其鄰居狀態(tài)都高的頂峰，但是小于全局最大值(參照狀態(tài)空間地形圖) 山脊一系列的局部極大值 高原評價函數(shù)平坦的一塊區(qū)域(或者山肩)第2章 搜索技術(shù)11 爬山法的變形 隨機(jī)爬山法隨機(jī)選擇下一步 首選爬山法隨機(jī)選擇直到有優(yōu)于當(dāng)前節(jié)點的下一步 隨機(jī)重

5、新開始爬山法隨機(jī)生成初始狀態(tài)，進(jìn)行一系列爬山法搜索這時算法是完備的概率接近1第2章 搜索技術(shù)12 將爬山法(停留在局部山峰)和隨機(jī)行走以某種方式結(jié)合，以同時獲得完備性和效率 模擬退火的思想 想象在不平的表面上如何使一個乒乓球掉到最深的裂縫中如果只讓其在表面滾動，則它只會停留在局部極小點 / 如果晃動平面，可以使乒乓球彈出局部極小點 / 技巧是晃動足夠大使乒乓球彈出局部極小點，但又不能太大把它從全局極小點中趕出第2章 搜索技術(shù)13 思路開始使勁晃動(先高溫加熱)然后慢慢降低搖晃的強(qiáng)度(逐漸降溫)退火過程 算法的核心移動選擇 選擇隨機(jī)移動，如果評價值改善，則移動被接受，否則以某個小于1的概率接受

6、概率按照移動評價值變壞的梯度E而呈指數(shù)級下降 / 同時也會隨著作為控制的參數(shù)“溫度”T的降低(數(shù)值減小)而降低 接受概率=eE/T(注意此時E 0)第5章 搜索技術(shù)14 溫度T是時間的函數(shù)，按照模擬退火的思想，數(shù)值應(yīng)該逐漸減小(降溫) 因為接受概率=eE/T且E n則此約束不能被滿足 相應(yīng)算法刪除約束中只有單值值域的變量，將其取值從其余變量值域中刪去；對單值變量重復(fù)此過程；如果得到空值域或剩下的變量數(shù)大于取值數(shù)，則產(chǎn)生矛盾 其他約束資源約束/邊界約束第2章 搜索技術(shù)44 在回溯算法中，當(dāng)發(fā)現(xiàn)不滿足約束即搜索失敗時，則回到上一個變量并嘗試下一個取值稱為歷時回溯 / 在很多情況下這樣做是效率很低的

7、因為問題并不決定于上一個(甚至幾個)變量的取值 所以，回溯應(yīng)該倒退到導(dǎo)致失敗的變量集合中的一個變量該集合稱為沖突集 變量X的沖突集是通過約束與X相連接的先前已賦值變量的集合第2章 搜索技術(shù)45 對于地圖染色問題，設(shè)有不完全賦值Q=red, NSW=green, V=blue, T=red / 此時，SA賦值將發(fā)現(xiàn)不滿足任何約束SA的沖突集=Q, NSW, V 對于前向檢驗算法，可以很容易得到?jīng)_突集 基于X賦值的前向檢驗從變量Y的值域中刪除一個值時，說明X和Y存在沖突，則顯然X是Y的沖突集中的一個變量 當(dāng)?shù)竭_(dá)Y時，可知回溯到哪個變量第2章 搜索技術(shù)46 回溯檢驗導(dǎo)致失敗的變量的賦值后向跳轉(zhuǎn)：回溯

8、到?jīng)_突集中時間最近(最后賦值)的變量 每個被后向跳轉(zhuǎn)剪枝的分支在前向檢驗算法中也被剪枝簡單的后向跳轉(zhuǎn)在前向檢驗(弧相容性檢驗)搜索中是多余的 因為都是做取值相容的檢測，只要在弧相容檢驗時增加一個變量集合記錄即可第2章 搜索技術(shù)47 變量的沖突集更一般的情況前面的變量集合中全部變量(不是其中一個變量)使得當(dāng)前變量與之沖突 沖突指導(dǎo)的后向跳轉(zhuǎn)處理 令Xj是當(dāng)前變量，conf(Xj)是其沖突集，如果Xj每個可能取值都失敗了，則后向跳轉(zhuǎn)到conf(Xj)中最近的一個變量Xi 令conf(Xi)=conf(Xi)conf(Xj)-Xi 從Xi向前是無解的 / 從Xi回到某個以前的變量賦值(參考p116例

9、子)第2章 搜索技術(shù)482.6 博弈搜索2.6.1 極大極小決策2.6.2 -剪枝第2章 搜索技術(shù)49 從智能體角度看，博弈是多智能體之間的競爭和對抗 / 在競爭的環(huán)境中，每個智能體的目的是沖突的，由此引出對抗搜索問題稱為博弈 本節(jié)探討兩個問題如何搜索到取勝的路徑 / 如何提高搜索效率 相應(yīng)的方法最優(yōu)策略(極大極小決策)/-剪枝第2章 搜索技術(shù)50 兩個游戲者的博弈可以定義為一類搜索問題，其中包括： 初始狀態(tài)棋盤局面和哪個游戲者出招 后繼函數(shù)返回(招數(shù),狀態(tài))對的一個列表，其中每對表示一個合法招數(shù)和相應(yīng)的結(jié)果狀態(tài) 終止測試判斷游戲是否結(jié)束 效用函數(shù)或稱目標(biāo)函數(shù)，對終止?fàn)顟B(tài)給出一個數(shù)值如輸贏和平

10、局(以-1/+1/0表示) 雙方的初始狀態(tài)和合法招數(shù)定義了游戲的博弈樹此為博弈搜索第2章 搜索技術(shù)51第2章 搜索技術(shù)XXXXXXXXXX OOXXOX O XX OXX OXX O XXOOX OOX XXXOOXX OXOOXMAX(X)MIN(O)MAX(X)MIN(O)TERMINAL效用-10+152 博弈搜索中，最優(yōu)解是導(dǎo)致取勝的終止?fàn)顟B(tài)的一系列招數(shù) 在井字棋搜索樹中，因為MAX先行，所以MAX的任務(wù)是利用搜索樹確定最佳招數(shù) / 但是另一方MIN也有發(fā)言權(quán) 因此MAX制定取勝策略時必須不斷地考慮MIN應(yīng)對條件下如何取勝即MAX初始狀態(tài)下應(yīng)該采取什么招數(shù)，然后是MIN應(yīng)對造成的狀態(tài)下

11、MAX采取的招數(shù)，接著繼續(xù)考慮下一步應(yīng)對后的招數(shù).第2章 搜索技術(shù)53 假設(shè)一個兩層的博弈樹(因為即使是井字棋的博弈樹也太復(fù)雜了)，其中有MAX節(jié)點和MIN節(jié)點 博弈樹中，每個單方的招數(shù)(或稱走步)是一層 / 雙方各走一招稱為一步(博弈樹的深度是一步的) 給定一棵博弈樹，最優(yōu)策略可以通過檢查每個節(jié)點的極大極小值來決定記為MAX-MIN(n)，所以也稱為極大極小決策第2章 搜索技術(shù)54 如果博弈雙方都按照最優(yōu)策略進(jìn)行，那么一個節(jié)點的極大極小值就是對應(yīng)狀態(tài)的效用值(對應(yīng)MAX) 對于某個節(jié)點，極大極小函數(shù)如下定義 MAX優(yōu)先選擇有極大值的狀態(tài) / MIN則選擇有極小值的狀態(tài)第5章 搜索技術(shù)節(jié)點為當(dāng)

12、節(jié)點為當(dāng)為終止?fàn)顟B(tài)MINn)(minMAXn)(maxn當(dāng))()()()(sMINMAXsMINMAXnUtilitynMINMAXnsonsnsons55第2章 搜索技術(shù) 3 12 8 2 4 6 14 5 2ABDC3223MAXMINMAX56 圖中MAX先行，有3個后繼MIN節(jié)點，此時MAX的取值必須看MIN如何取值 每個MIN節(jié)點亦有3個后繼MAX節(jié)點，假設(shè)其取值已知 因為MIN節(jié)點只取其后繼節(jié)點中之最小者(讓MAX效用最小)，故B=3/C=2/D=2 MAX節(jié)點取A/B/C中最大者，故A=3 最后根節(jié)點A的極大極小函數(shù)值=3引向具有最高極大極小值的后繼第2章 搜索技術(shù)57 簡單的遞

13、歸算法按照定義計算每個后繼節(jié)點的極大極小值 / 搜索是從目標(biāo)到初始節(jié)點的反向推導(dǎo) 算法對博弈樹實行了深度優(yōu)先搜索 如果博弈樹的最大深度為m，每個節(jié)點的合法招數(shù)為b，則 算法的時間復(fù)雜度是O(bm) 每次生成全部后繼節(jié)點的空間復(fù)雜度是O(bm) 每次只生成一個后繼節(jié)點的空間復(fù)雜度是O(m)第2章 搜索技術(shù)58Function MAX-MIN-DECISION(state) returns an actioninputs: state (current state in game)v MAX-VALUE(state)return the action in SUCCESSORS(state) wi

14、th value vFunction MAX-VALUE(state) returns a utility valueif TERMINAL-TEST(state) then return UTILITY(state)v -for a, s in SUCCESSORS(state) do v MAX(v, MIN-VALUE(s)return v(a=action招數(shù))Function MIN-VALUE(state) returns a utility valueif TERMINAL-TEST(state) then return UTILITY(state) v +for a, s in

15、 SUCCESSORS(state) do v MIN(v, MAX-VALUE(s)return v第2章 搜索技術(shù)59 極大極小值搜索的問題是狀態(tài)數(shù)隨著棋局步數(shù)的數(shù)量而指數(shù)級增長不幸的是沒有辦法消除這種指數(shù)級增長，所幸的是可以有效將其減半剪枝技術(shù) 應(yīng)用于極大極小值搜索樹中-剪枝 剪掉那些不可能影響最后決策的分支，返回和極大極小值算法同樣的結(jié)果 例子的剪枝過程中 MAX-MIN(n)=max(min(3,12,8), min(2,x,y), min(14,5,2)=max(3,min(2,x,y),2)=max(3,z,2)=3第2章 搜索技術(shù)60第2章 搜索技術(shù)3-, +AB-,3(a)-

16、, +12AB3-,3(b)61第2章 搜索技術(shù)12AB3, +383,3(c)12ABC3, +-,23823,3(d)62第2章 搜索技術(shù)-,1412ABDC3,14-,2382143,3(e)12ABDC3,3-,22,238214523,3(f )63 在極大極小值算法基礎(chǔ)上增加了剪枝功能，即在返回值基礎(chǔ)上增加了判斷Function ALPHA-BETA-SEARCH(state) returns an actioninputs: state (current state in game)v MAX-VALUE(state, -, +)return the action in SUCC

17、ESSORS(state) with value v第2章 搜索技術(shù)64Function MAX-VALUE(state, ) returns a utility valueinputs: state , the value of the best alternative for MAX along the path to state , the value of the best alternative for MIN along the path to stateif TERMINAL-TEST(state) then return UTILITY(state)v -for a, s in

18、 SUCCESSORS(state) dov MAX(v, MIN-VALUE(s, )if v then return v MAX(, v)return v第2章 搜索技術(shù)65Function MIN-VALUE(state, , ) returns a utility valueinputs: state, the value of the best alternative for MAX along the path to state the value of the best alternative for MIN along the path to stateif TERMINAL-

19、TEST(state) then return UTILITY(state)v +for a, s in SUCCESSORS(state) dov MIN(v, MAX-VALUE(s, , )if v then return v MIN(, v)return v第2章 搜索技術(shù)66 -剪枝可以應(yīng)用樹的任何深度，許多情況下可以剪掉整個子樹 / 其原則是如果在節(jié)點n的父節(jié)點或者更上層的節(jié)點有一個更好的選擇m，則在實際游戲(搜索)中永遠(yuǎn)不會到達(dá)n =到目前為止在路徑上任意點發(fā)現(xiàn)的MAX最佳選擇 =到目前為止在路徑上任意點發(fā)現(xiàn)的MIN最佳選擇 -搜索不斷更新/值，當(dāng)某個節(jié)點的值分別比/值更差時剪掉

20、該節(jié)點的剩余分支第2章 搜索技術(shù)67 -剪枝的效率很大程度上取決于檢查后繼節(jié)點的次序應(yīng)該先檢查那些可能最好的后繼 如果能夠先檢查那些最好的后繼，則-剪枝算法只需檢查O(bd/2)個節(jié)點以決定最佳招數(shù) / 極大極小值算法為O(bd)有效分支因子b到b的平方根效率大大提高第2章 搜索技術(shù)68 嘗試使用搜索方式求解問題 / 注意本章的搜索算法都是通用算法，即沒有考慮具體任務(wù)的相關(guān)知識 具體搜索問題的形式化表示(初始狀態(tài)/后繼函數(shù)/搜索代價等) 了解各種搜索算法(包括局部搜索和博弈搜索)的思想、相關(guān)性質(zhì)和性能 嘗試用啟發(fā)式搜索算法(A*算法)解決一些游戲問題 約束滿足問題的相關(guān)概念第2章 搜索技術(shù)69

21、 Stuart Russell / Peter Norvig: AIMA 第3章 / 第4章 / 第5章 / 第6章 陸汝鈐 編著: 人工智能(上冊) 第5章 / 第6章 / 第8章 / 第9章 田盛豐、黃厚寬，人工智能與知識工程，中國鐵道出版社，1999年8月第1版，第4章 / 第9章第2章 搜索技術(shù)70附錄 A*算法可采納性的證明第2章 搜索技術(shù)71 定理： A*算法是可采納的，即若存在從初始節(jié)點S0到目標(biāo)節(jié)點Sg的路徑，則A*算法必能結(jié)束在最佳路徑上 證明的過程： 首先證明A*算法必定成功結(jié)束 其次證明A*算法結(jié)束時中止于最佳路徑第2章 搜索技術(shù)72 證明分為三步：(1)對于有限圖，A*

22、算法一定成功結(jié)束(2)對于無限圖，A*算法一定成功結(jié)束(3)A*算法必定終止于最佳路徑上 對于無限圖情況的證明，引入2個引理(1)如果A*算法不終止，則存在f值任意大的節(jié)點(2)A*算法結(jié)束前，仍有耗散值更小的節(jié)點待擴(kuò)展第2章 搜索技術(shù)73 定理1對于有限圖，如果從初始節(jié)點S0到目標(biāo)節(jié)點Sg有路徑存在，則A*算法一定成功結(jié)束 證明： 首先證明算法必定會結(jié)束 由于搜索圖為有限圖，如果算法能找到解，則會成功結(jié)束；如果算法找不到解，則必然會由于Open表變空而結(jié)束。因此，A*算法必然會結(jié)束第2章 搜索技術(shù)74 然后證明算法一定會成功結(jié)束 由于至少存在一條由初始節(jié)點到目標(biāo)節(jié)點的路徑，設(shè)此路徑為 S0=

23、 n0，n1 ，nk =Sg 算法開始時，節(jié)點n0在Open表中，而且路徑中任一節(jié)點ni離開Open表后，其后繼節(jié)點ni+1必然進(jìn)入Open表，這樣，在Open表變?yōu)榭罩埃繕?biāo)節(jié)點必然出現(xiàn)在Open表中 / 因此，算法必定會成功結(jié)束第2章 搜索技術(shù)75 引理1對無限圖，如果從初始節(jié)點S0到目標(biāo)節(jié)點Sg有路徑存在，且A*算法不終止的話，則從Open表中選出的節(jié)點必將具有任意大的f值 證明： 設(shè)d*(n)是A*算法生成的從初始節(jié)點S0到節(jié)點n的最短路徑長度，由于搜索圖中每條邊的代價都是一個正數(shù)，令這些正數(shù)中最小的一個數(shù)是e, 則有第2章 搜索技術(shù)endng)()(*76 因為是最佳路徑的代價，故

24、有 又因為h(n)0，故有 如果A*算法不終止的話，從Open表中選出的節(jié)點必將具有任意大的d*(n)值，因此，也將具有任意大的f值endng)()(g(n) *第2章 搜索技術(shù)endngnhngnf)()()()()(*77 引理2在A*算法終止前的任何時刻，Open表中總存在節(jié)點n，它是從初始節(jié)點S0到目標(biāo)節(jié)點的最佳路徑上的一個節(jié)點，且滿足 證明： 設(shè)從初始節(jié)點S0到目標(biāo)節(jié)點t的最佳路徑序列為 S0 = n0，n1，nk =Sg 算法開始時，節(jié)點S0在Open表中，當(dāng)節(jié)點S0離開Open進(jìn)入Closed表時，節(jié)點n1進(jìn)入Open表第2章 搜索技術(shù))()(0*Sfnf78 因此，A*沒有結(jié)束以前，在Open表中必存在最佳路徑上的節(jié)點 設(shè)這些節(jié)點排在最前面的節(jié)點為n,則有f(n)=g(n)+h(n) 由于n在最佳路徑上，故有g(shù)(n)=g*(n), 從