人工智能原理第2部分搜索技術(shù)下

1、人工智能原理第2章 搜索技術(shù)（下） 1本章內(nèi)容2.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)空間(保留各種路徑)相對(duì)，不關(guān)心路徑的搜索算法就是局部搜索算法局部搜索從一個(gè)單獨(dú)的當(dāng)前狀態(tài)出發(fā)

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

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

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

5、索技術(shù)11爬山法搜索的變形爬山法的變形隨機(jī)爬山法隨機(jī)選擇下一步首選爬山法隨機(jī)選擇直到有優(yōu)于當(dāng)前節(jié)點(diǎn)的下一步隨機(jī)重新開始爬山法隨機(jī)生成初始狀態(tài)，進(jìn)行一系列爬山法搜索這時(shí)算法是完備的概率接近1第2章 搜索技術(shù)122.4.3 模擬退火搜索將爬山法(停留在局部山峰)和隨機(jī)行走以某種方式結(jié)合，以同時(shí)獲得完備性和效率模擬退火的思想想象在不平的表面上如何使一個(gè)乒乓球掉到最深的裂縫中如果只讓其在表面滾動(dòng)，則它只會(huì)停留在局部極小點(diǎn) / 如果晃動(dòng)平面，可以使乒乓球彈出局部極小點(diǎn) / 技巧是晃動(dòng)足夠大使乒乓球彈出局部極小點(diǎn)，但又不能太大把它從全局極小點(diǎn)中趕出第2章 搜索技術(shù)13模擬退火的解決思路(1)思路開始使勁晃

6、動(dòng)(先高溫加熱)然后慢慢降低搖晃的強(qiáng)度(逐漸降溫)退火過程算法的核心移動(dòng)選擇選擇隨機(jī)移動(dòng)，如果評(píng)價(jià)值改善，則移動(dòng)被接受，否則以某個(gè)小于1的概率接受概率按照移動(dòng)評(píng)價(jià)值變壞的梯度E而呈指數(shù)級(jí)下降 / 同時(shí)也會(huì)隨著作為控制的參數(shù)“溫度”T的降低(數(shù)值減小)而降低接受概率=eE/T(注意此時(shí)E 0)第5章 搜索技術(shù)14模擬退火的解決思路(2)溫度T是時(shí)間的函數(shù)，按照模擬退火的思想，數(shù)值應(yīng)該逐漸減小(降溫)因?yàn)榻邮芨怕?eE/T且E n則此約束不能被滿足相應(yīng)算法刪除約束中只有單值值域的變量，將其取值從其余變量值域中刪去；對(duì)單值變量重復(fù)此過程；如果得到空值域或剩下的變量數(shù)大于取值數(shù)，則產(chǎn)生矛盾其他約束資源

7、約束/邊界約束第2章 搜索技術(shù)442.5.5 關(guān)于失敗變量的啟發(fā)式在回溯算法中，當(dāng)發(fā)現(xiàn)不滿足約束即搜索失敗時(shí)，則回到上一個(gè)變量并嘗試下一個(gè)取值稱為歷時(shí)回溯 / 在很多情況下這樣做是效率很低的因?yàn)閱栴}并不決定于上一個(gè)(甚至幾個(gè))變量的取值所以，回溯應(yīng)該倒退到導(dǎo)致失敗的變量集合中的一個(gè)變量該集合稱為沖突集變量X的沖突集是通過約束與X相連接的先前已賦值變量的集合第2章 搜索技術(shù)45沖突集對(duì)于地圖染色問題，設(shè)有不完全賦值Q=red, NSW=green, V=blue, T=red / 此時(shí)，SA賦值將發(fā)現(xiàn)不滿足任何約束SA的沖突集=Q, NSW, V對(duì)于前向檢驗(yàn)算法，可以很容易得到?jīng)_突集基于X賦值的

8、前向檢驗(yàn)從變量Y的值域中刪除一個(gè)值時(shí)，說明X和Y存在沖突，則顯然X是Y的沖突集中的一個(gè)變量當(dāng)?shù)竭_(dá)Y時(shí)，可知回溯到哪個(gè)變量第2章 搜索技術(shù)46后向跳轉(zhuǎn)回溯檢驗(yàn)導(dǎo)致失敗的變量的賦值后向跳轉(zhuǎn)：回溯到?jīng)_突集中時(shí)間最近(最后賦值)的變量每個(gè)被后向跳轉(zhuǎn)剪枝的分支在前向檢驗(yàn)算法中也被剪枝簡單的后向跳轉(zhuǎn)在前向檢驗(yàn)(弧相容性檢驗(yàn))搜索中是多余的因?yàn)槎际亲鋈≈迪嗳莸臋z測(cè)，只要在弧相容檢驗(yàn)時(shí)增加一個(gè)變量集合記錄即可第2章 搜索技術(shù)47沖突指導(dǎo)的后向跳轉(zhuǎn)變量的沖突集更一般的情況前面的變量集合中全部變量(不是其中一個(gè)變量)使得當(dāng)前變量與之沖突沖突指導(dǎo)的后向跳轉(zhuǎn)處理令Xj是當(dāng)前變量，conf(Xj)是其沖突集，如果Xj每

9、個(gè)可能取值都失敗了，則后向跳轉(zhuǎn)到conf(Xj)中最近的一個(gè)變量Xi令conf(Xi)=conf(Xi)conf(Xj)-Xi從Xi向前是無解的 / 從Xi回到某個(gè)以前的變量賦值(參考p116例子)第2章 搜索技術(shù)482.6 博弈搜索2.6.1 極大極小決策2.6.2 -剪枝第2章 搜索技術(shù)49博弈搜索問題與方法從智能體角度看，博弈是多智能體之間的競(jìng)爭和對(duì)抗 / 在競(jìng)爭的環(huán)境中，每個(gè)智能體的目的是沖突的，由此引出對(duì)抗搜索問題稱為博弈本節(jié)探討兩個(gè)問題如何搜索到取勝的路徑 / 如何提高搜索效率相應(yīng)的方法最優(yōu)策略(極大極小決策)/-剪枝第2章 搜索技術(shù)50博弈游戲的描述兩個(gè)游戲者的博弈可以定義為一類

10、搜索問題，其中包括：初始狀態(tài)棋盤局面和哪個(gè)游戲者出招后繼函數(shù)返回(招數(shù),狀態(tài))對(duì)的一個(gè)列表，其中每對(duì)表示一個(gè)合法招數(shù)和相應(yīng)的結(jié)果狀態(tài)終止測(cè)試判斷游戲是否結(jié)束效用函數(shù)或稱目標(biāo)函數(shù)，對(duì)終止?fàn)顟B(tài)給出一個(gè)數(shù)值如輸贏和平局(以-1/+1/0表示)雙方的初始狀態(tài)和合法招數(shù)定義了游戲的博弈樹此為博弈搜索第2章 搜索技術(shù)51井字棋的博弈樹第2章 搜索技術(shù)XXXXXXXXXXOOXXOXOXXOXXOXXOXXOOXOOXXXXOOXXOXOOXMAX(X)MIN(O)MAX(X)MIN(O)TERMINAL效用-10+1522.6.1 極大極小決策博弈搜索中，最優(yōu)解是導(dǎo)致取勝的終止?fàn)顟B(tài)的一系列招數(shù)在井字棋搜索

11、樹中，因?yàn)镸AX先行，所以MAX的任務(wù)是利用搜索樹確定最佳招數(shù) / 但是另一方MIN也有發(fā)言權(quán)因此MAX制定取勝策略時(shí)必須不斷地考慮MIN應(yīng)對(duì)條件下如何取勝即MAX初始狀態(tài)下應(yīng)該采取什么招數(shù)，然后是MIN應(yīng)對(duì)造成的狀態(tài)下MAX采取的招數(shù)，接著繼續(xù)考慮下一步應(yīng)對(duì)后的招數(shù).第2章 搜索技術(shù)53極大極小值(1)假設(shè)一個(gè)兩層的博弈樹(因?yàn)榧词故蔷制宓牟┺臉湟蔡珡?fù)雜了)，其中有MAX節(jié)點(diǎn)和MIN節(jié)點(diǎn)博弈樹中，每個(gè)單方的招數(shù)(或稱走步)是一層 / 雙方各走一招稱為一步(博弈樹的深度是一步的)給定一棵博弈樹，最優(yōu)策略可以通過檢查每個(gè)節(jié)點(diǎn)的極大極小值來決定記為MAX-MIN(n)，所以也稱為極大極小決策第2

12、章 搜索技術(shù)54極大極小值(2)如果博弈雙方都按照最優(yōu)策略進(jìn)行，那么一個(gè)節(jié)點(diǎn)的極大極小值就是對(duì)應(yīng)狀態(tài)的效用值(對(duì)應(yīng)MAX)對(duì)于某個(gè)節(jié)點(diǎn)，極大極小函數(shù)如下定義MAX優(yōu)先選擇有極大值的狀態(tài) / MIN則選擇有極小值的狀態(tài)第5章 搜索技術(shù)55極大極小值(3)第2章 搜索技術(shù) 3 12 8 2 4 6 14 5 2ABDC3223MAXMINMAX56極大極小值(4)圖中MAX先行，有3個(gè)后繼MIN節(jié)點(diǎn)，此時(shí)MAX的取值必須看MIN如何取值每個(gè)MIN節(jié)點(diǎn)亦有3個(gè)后繼MAX節(jié)點(diǎn)，假設(shè)其取值已知因?yàn)镸IN節(jié)點(diǎn)只取其后繼節(jié)點(diǎn)中之最小者(讓MAX效用最小)，故B=3/C=2/D=2MAX節(jié)點(diǎn)取A/B/C中最大

13、者，故A=3最后根節(jié)點(diǎn)A的極大極小函數(shù)值=3引向具有最高極大極小值的后繼第2章 搜索技術(shù)57極大極小值算法說明簡單的遞歸算法按照定義計(jì)算每個(gè)后繼節(jié)點(diǎn)的極大極小值 / 搜索是從目標(biāo)到初始節(jié)點(diǎn)的反向推導(dǎo)算法對(duì)博弈樹實(shí)行了深度優(yōu)先搜索如果博弈樹的最大深度為m，每個(gè)節(jié)點(diǎn)的合法招數(shù)為b，則算法的時(shí)間復(fù)雜度是O(bm)每次生成全部后繼節(jié)點(diǎn)的空間復(fù)雜度是O(bm)每次只生成一個(gè)后繼節(jié)點(diǎn)的空間復(fù)雜度是O(m)第2章 搜索技術(shù)58極大極小值算法Function MAX-MIN-DECISION(state) returns an actioninputs: state (current state in gam

14、e)v MAX-VALUE(state)return the action in SUCCESSORS(state) with 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 T

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

16、)=max(3,min(2,x,y),2)=max(3,z,2)=3第2章 搜索技術(shù)60博弈樹的剪枝(1)第2章 搜索技術(shù)3-, +AB-,3(a)-, +12AB3-,3(b)61博弈樹的剪枝(2)第2章 搜索技術(shù)12AB3, +383,3(c)12ABC3, +-,23823,3(d)62博弈樹的剪枝(3)第2章 搜索技術(shù)-,1412ABDC3,14-,2382143,3(e)12ABDC3,3-,22,238214523,3(f )63-剪枝算法(1)在極大極小值算法基礎(chǔ)上增加了剪枝功能，即在返回值基礎(chǔ)上增加了判斷Function ALPHA-BETA-SEARCH(state) ret

17、urns an actioninputs: state (current state in game)v MAX-VALUE(state, -, +)return the action in SUCCESSORS(state) with value v第2章 搜索技術(shù)64-剪枝算法(2)Function 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

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

19、native 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 SUCCESSORS(state) dov MIN(v, MAX-VALUE(s, , )if v then return v MIN(, v)return v第2章 搜索技術(shù)66-剪枝算法的說明-剪枝可以應(yīng)用樹的任何深度，許多情況下可以剪掉整個(gè)子樹 / 其原則

20、是如果在節(jié)點(diǎn)n的父節(jié)點(diǎn)或者更上層的節(jié)點(diǎn)有一個(gè)更好的選擇m，則在實(shí)際游戲(搜索)中永遠(yuǎn)不會(huì)到達(dá)n=到目前為止在路徑上任意點(diǎn)發(fā)現(xiàn)的MAX最佳選擇=到目前為止在路徑上任意點(diǎn)發(fā)現(xiàn)的MIN最佳選擇-搜索不斷更新/值，當(dāng)某個(gè)節(jié)點(diǎn)的值分別比/值更差時(shí)剪掉該節(jié)點(diǎn)的剩余分支第2章 搜索技術(shù)67-剪枝的效率-剪枝的效率很大程度上取決于檢查后繼節(jié)點(diǎn)的次序應(yīng)該先檢查那些可能最好的后繼如果能夠先檢查那些最好的后繼，則-剪枝算法只需檢查O(bd/2)個(gè)節(jié)點(diǎn)以決定最佳招數(shù) / 極大極小值算法為O(bd)有效分支因子b到b的平方根效率大大提高第2章 搜索技術(shù)68本章復(fù)習(xí)提示嘗試使用搜索方式求解問題 / 注意本章的搜索算法都是

21、通用算法，即沒有考慮具體任務(wù)的相關(guān)知識(shí)具體搜索問題的形式化表示(初始狀態(tài)/后繼函數(shù)/搜索代價(jià)等)了解各種搜索算法(包括局部搜索和博弈搜索)的思想、相關(guān)性質(zhì)和性能嘗試用啟發(fā)式搜索算法(A*算法)解決一些游戲問題約束滿足問題的相關(guān)概念第2章 搜索技術(shù)69參考書目Stuart Russell / Peter Norvig: AIMA 第3章 / 第4章 / 第5章 / 第6章陸汝鈐 編著: 人工智能(上冊(cè)) 第5章 / 第6章 / 第8章 / 第9章田盛豐、黃厚寬，人工智能與知識(shí)工程，中國鐵道出版社，1999年8月第1版，第4章 / 第9章第2章 搜索技術(shù)70附錄 A*算法可采納性的證明第2章 搜索

22、技術(shù)71A*算法可采納性定理：A*算法是可采納的，即若存在從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)點(diǎn)Sg的路徑，則A*算法必能結(jié)束在最佳路徑上證明的過程：首先證明A*算法必定成功結(jié)束其次證明A*算法結(jié)束時(shí)中止于最佳路徑第2章 搜索技術(shù)72證明的步驟證明分為三步：(1)對(duì)于有限圖，A*算法一定成功結(jié)束(2)對(duì)于無限圖，A*算法一定成功結(jié)束(3)A*算法必定終止于最佳路徑上對(duì)于無限圖情況的證明，引入2個(gè)引理(1)如果A*算法不終止，則存在f值任意大的節(jié)點(diǎn)(2)A*算法結(jié)束前，仍有耗散值更小的節(jié)點(diǎn)待擴(kuò)展第2章 搜索技術(shù)73定理1的證明(1)定理1對(duì)于有限圖，如果從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)點(diǎn)Sg有路徑存在，則A*算法一定成

23、功結(jié)束證明：首先證明算法必定會(huì)結(jié)束由于搜索圖為有限圖，如果算法能找到解，則會(huì)成功結(jié)束；如果算法找不到解，則必然會(huì)由于Open表變空而結(jié)束。因此，A*算法必然會(huì)結(jié)束第2章 搜索技術(shù)74定理1的證明(2)然后證明算法一定會(huì)成功結(jié)束由于至少存在一條由初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑，設(shè)此路徑為S0= n0，n1 ，nk =Sg算法開始時(shí)，節(jié)點(diǎn)n0在Open表中，而且路徑中任一節(jié)點(diǎn)ni離開Open表后，其后繼節(jié)點(diǎn)ni+1必然進(jìn)入Open表，這樣，在Open表變?yōu)榭罩?，目?biāo)節(jié)點(diǎn)必然出現(xiàn)在Open表中 / 因此，算法必定會(huì)成功結(jié)束第2章 搜索技術(shù)75引理1的證明(1)引理1對(duì)無限圖，如果從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)點(diǎn)

24、Sg有路徑存在，且A*算法不終止的話，則從Open表中選出的節(jié)點(diǎn)必將具有任意大的f值證明：設(shè)d*(n)是A*算法生成的從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的最短路徑長度，由于搜索圖中每條邊的代價(jià)都是一個(gè)正數(shù)，令這些正數(shù)中最小的一個(gè)數(shù)是e, 則有第2章 搜索技術(shù)76引理1的證明(2)因?yàn)槭亲罴崖窂降拇鷥r(jià)，故有又因?yàn)閔(n)0，故有如果A*算法不終止的話，從Open表中選出的節(jié)點(diǎn)必將具有任意大的d*(n)值，因此，也將具有任意大的f值第2章 搜索技術(shù)77引理2的證明(1)引理2在A*算法終止前的任何時(shí)刻，Open表中總存在節(jié)點(diǎn)n，它是從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)點(diǎn)的最佳路徑上的一個(gè)節(jié)點(diǎn)，且滿足證明：設(shè)從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)點(diǎn)t的最佳路徑序列為 S0 = n0，n1，nk =Sg算法開始時(shí)，節(jié)點(diǎn)S0在Open表中，當(dāng)節(jié)點(diǎn)S0離開Open進(jìn)入Closed表時(shí)，節(jié)點(diǎn)n1進(jìn)入Open表第2章 搜索技術(shù)78引理2的證明(2)因此，A*沒有結(jié)束以前，在Open表中必存在最佳路徑上的節(jié)點(diǎn)設(shè)這些節(jié)點(diǎn)排在最前面的節(jié)點(diǎn)為n,則有f(n)=g(n)+h(n)由于n在最佳路徑上，故有g(shù)(n)=g*