人工智能原理第2章搜索技術(shù)下.ppt

人工智能原理 第2章 搜索技術(shù) （下）,本章內(nèi)容 2.1 搜索與問題求解 2.2 無信息搜索策略 2.3 啟發(fā)式搜索策略 2.4 局部搜索算法 2.5 約束滿足問題 2.6 博弈搜索 參考書目 附錄 A*算法可采納性的證明,第2章 搜索技術(shù),2.4 局部搜索算法 2.4.1 局部搜索與最優(yōu)化 2.4.2 爬山法搜索 2.4.3 模擬退火搜索 2.4.4 局部剪枝搜索 2.4.5 遺傳算法,第2章 搜索技術(shù),4,局部搜索算法,前面的搜索算法都是保留搜索路徑的，到達(dá)目標(biāo)的路徑就是問題的解然而許多問題中到達(dá)目標(biāo)的路徑是無關(guān)緊要的 與系統(tǒng)地搜索狀態(tài)空間(保留各種路徑)相對，不關(guān)心路徑的搜索算法就是局部搜索算法 局部搜索從一個單獨(dú)的當(dāng)前狀態(tài)出發(fā)，通常只移動到相鄰狀態(tài) 典型情況下搜索的路徑不保留,第2章 搜索技術(shù),5,局部搜索算法的應(yīng)用,集成電路設(shè)計(jì) 工廠場地布局 車間作業(yè)調(diào)度 自動程序設(shè)計(jì) 電信網(wǎng)絡(luò)優(yōu)化 車輛尋徑 文件夾管理,第2章 搜索技術(shù),6,2.4.1 局部搜索與最優(yōu)化問題,局部搜索算法的優(yōu)點(diǎn)： 只使用很少的內(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ù),7,狀態(tài)空間地形圖(1),第2章 搜索技術(shù),8,狀態(tài)空間地形圖(2),在狀態(tài)圖中，既有“位置”(用狀態(tài)表示)又有“高度”(用耗散值或目標(biāo)函數(shù)值表示) 如果高度對應(yīng)于耗散值，則目標(biāo)是找到全局最小值，即圖中最低點(diǎn) 如果高度對應(yīng)于目標(biāo)函數(shù)，則目標(biāo)是找到全局最大值，即圖中最高峰 如果存在解，則完備的局部搜索算法能夠找到解 而最優(yōu)的局部搜索算法能夠找到全局最大或最小值,第2章 搜索技術(shù),9,局部搜索算法,本節(jié)簡要介紹以下4種局部搜索算法 / 介紹其算法思想 爬山法搜索 模擬退火搜索 局部剪枝搜索 遺傳算法 從搜索的角度看遺傳算法也是搜索假設(shè)空間的一種方法(學(xué)習(xí)問題歸結(jié)為搜索問題)生成后繼假設(shè)的方式,第2章 搜索技術(shù),10,2.4.2 爬山法搜索,爬山法(hill-climbing)就是向值增加的方向持續(xù)移動登高過程 / 如果相鄰狀態(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)若存在一個動作可以作用于當(dāng)前狀態(tài)以產(chǎn)生一個新狀態(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)為相對最優(yōu)解，停止執(zhí)行算法,第2章 搜索技術(shù),11,爬山法搜索的局限,爬山法是一種局部貪婪搜索，不是最優(yōu)解算法(或是不完備的) / 其問題是： 局部極大值比其鄰居狀態(tài)都高的頂峰，但是小于全局最大值(參照狀態(tài)空間地形圖) 山脊一系列的局部極大值 高原評價函數(shù)平坦的一塊區(qū)域(或者山肩),第2章 搜索技術(shù),12,爬山法搜索的變形,爬山法的變形 隨機(jī)爬山法隨機(jī)選擇下一步 首選爬山法隨機(jī)選擇直到有優(yōu)于當(dāng)前節(jié)點(diǎn)的下一步 隨機(jī)重新開始爬山法隨機(jī)生成初始狀態(tài)，進(jìn)行一系列爬山法搜索這時算法是完備的概率接近1,第2章 搜索技術(shù),13,2.4.3 模擬退火搜索,將爬山法(停留在局部山峰)和隨機(jī)行走以某種方式結(jié)合，以同時獲得完備性和效率 模擬退火的思想 想象在不平的表面上如何使一個乒乓球掉到最深的裂縫中如果只讓其在表面滾動，則它只會停留在局部極小點(diǎn) / 如果晃動平面，可以使乒乓球彈出局部極小點(diǎn) / 技巧是晃動足夠大使乒乓球彈出局部極小點(diǎn)，但又不能太大把它從全局極小點(diǎn)中趕出,第2章 搜索技術(shù),14,模擬退火的解決思路(1),思路開始使勁晃動(先高溫加熱)然后慢慢降低搖晃的強(qiáng)度(逐漸降溫)退火過程 算法的核心移動選擇 選擇隨機(jī)移動，如果評價值改善，則移動被接受，否則以某個小于1的概率接受 概率按照移動評價值變壞的梯度E而呈指數(shù)級下降 / 同時也會隨著作為控制的參數(shù)“溫度”T的降低(數(shù)值減小)而降低 接受概率=eE/T(注意此時E 0),第5章 搜索技術(shù),15,模擬退火的解決思路(2),溫度T是時間的函數(shù)，按照模擬退火的思想，數(shù)值應(yīng)該逐漸減小(降溫) 因?yàn)榻邮芨怕?eE/T且E 0，所以當(dāng)溫度高時，接受概率較大(接近1) / 而T越來越低時，E/T變大，因而接受概率降低 可以證明，如果T下降得足夠慢，則算法找到全局最優(yōu)解的概率接近1,第5章 搜索技術(shù),16,2.4.4 局部剪枝搜索,基本思想與只從一個單獨(dú)的起始狀態(tài)出發(fā)不同，局部剪枝搜索從k個隨機(jī)生成的狀態(tài)開始，每步生成全部k個狀態(tài)的所有后繼狀態(tài) / 如果其中之一是目標(biāo)狀態(tài)，算法停止；否則從全部后繼狀態(tài)中選擇最佳的k個狀態(tài)繼續(xù)搜索 在局部剪枝搜索過程中，有用的信息在k個并行的搜索線程之間傳遞算法會很快放棄沒有成果的搜索而把資源放在取得最大進(jìn)展的搜索上,第2章 搜索技術(shù),17,隨機(jī)剪枝搜索,如果k個狀態(tài)缺乏多樣性，則局部剪枝搜索會受其影響，性能變差 算法的變種隨機(jī)剪枝搜索幫助緩解這一問題隨機(jī)剪枝搜索不是選擇最好的k個后代，而是按照一定概率隨機(jī)地選擇k個后繼狀態(tài) / 選擇給定后繼狀態(tài)的概率是狀態(tài)值的遞增函數(shù) 類似于自然選擇過程狀態(tài)對應(yīng)生物體，其值對應(yīng)于適應(yīng)性，后代就是后繼狀態(tài),第2章 搜索技術(shù),18,2.4.5 遺傳算法,遺傳算法(generic algorithm/GA)是隨機(jī)剪枝的變種不是通過修改單一狀態(tài)而是通過把兩個父狀態(tài)結(jié)合以生成后繼狀態(tài) 與剪枝搜索一樣，遺傳算法也是從k個隨機(jī)狀態(tài)開始這k個狀態(tài)稱為種群，每個狀態(tài)稱為個體 個體用有限長的字符串(通常為0/1串)表示 每個狀態(tài)用其評價函數(shù)(適應(yīng)度函數(shù))給出評價值(適應(yīng)值) 隨后的操作包括選擇/雜交/變異,第2章 搜索技術(shù),19,遺傳算法的操作,選擇(或者稱繁殖)按照一定概率隨機(jī)地選擇兩對個體進(jìn)行繁殖(即生成后繼狀態(tài)) 雜交(或者稱交叉)雜交點(diǎn)是在表示狀態(tài)的字符串中隨機(jī)選擇的一個位置，以此形成新狀態(tài)后代是父串在雜交點(diǎn)上進(jìn)行雜交(各取一部分)得來的 變異在新生成的串中各個位置都會按照一個獨(dú)立的小概率隨機(jī)變異,第2章 搜索技術(shù),20,遺傳算法簡要描述,(1)定義問題和目標(biāo)函數(shù) (2)選擇候選解作為初始種群，每個解作為個體用二進(jìn)制串表示(個體相當(dāng)于染色體，其中的元素相當(dāng)于基因) (3)根據(jù)目標(biāo)函數(shù)，對于每個個體計(jì)算適應(yīng)函數(shù)值 (4)為每個個體指定一個與其適應(yīng)值成正比的被選擇概率(繁殖概率) (5)根據(jù)概率選擇個體，所選個體通過交叉/變異等操作產(chǎn)生新一代種群 (6)如果找到了解或者某種限制已到，則過程結(jié)束；否則轉(zhuǎn)(3),第2章 搜索技術(shù),21,遺傳算法的特點(diǎn),遺傳算法也結(jié)合了“上山”趨勢和隨機(jī)搜索，并在并行搜索線程之間交換信息 遺傳算法的主要優(yōu)勢來自于雜交 數(shù)學(xué)上可以證明，如果基因編碼的位置在初始時就隨機(jī)轉(zhuǎn)換的話，雜交就沒有優(yōu)勢 雜交的優(yōu)勢在于它能夠?qū)ⅹ?dú)立發(fā)展的若干個相對固定的字符(能夠執(zhí)行有用的功能“磚塊”)組合起來，提高了搜索的粒度 所謂有用的磚塊，就是幾個結(jié)合起來可以構(gòu)造問題的解參見書中的八皇后問題舉例,第2章 搜索技術(shù),22,遺傳算法的模式,遺傳算法上述特點(diǎn)可以用模式(schema)來解釋模式是某些位置上的數(shù)字尚未確定的一個狀態(tài)子串 能夠匹配模式的字符串稱為該模式的實(shí)例 如果一個模式的實(shí)例的平均適應(yīng)值超過均值，則種群內(nèi)這個模式的實(shí)例數(shù)量會隨時間而增長 遺傳算法在模式和解的有意義成分相對應(yīng)時才會工作得最好 遺傳算法有很多應(yīng)用，但是在什么情況下它會達(dá)到好效果，還有很多研究要做,第2章 搜索技術(shù),2.5 約束滿足問題 2.5.1 約束滿足問題的定義 2.5.2 CSP的回溯搜索 2.5.3 變量賦值次序的啟發(fā)式 2.5.4 變量約束的啟發(fā)式 2.5.5 關(guān)于失敗變量的啟發(fā)式,第2章 搜索技術(shù),24,2.5.1 約束滿足問題的定義,約束滿足問題(Constraint Satisfying Problem, CSP)由一個變量集合X1Xn和一個約束集合C1Cm定義 每個變量都有一個非空可能值域Di 每個約束指定了包含若干變量的一個子集內(nèi)各變量的賦值范圍 CSP的一個狀態(tài)對一些或全部變量的賦值 Xi=vi, Xj=vj, ,第2章 搜索技術(shù),25,CSP問題的解,一個不違反任何約束的對變量的賦值稱為相容賦值或合法賦值 對每個變量都進(jìn)行賦值稱為完全賦值 一個(一組)既是相容賦值又是完全賦值的對變量的賦值就是CSP問題的解 CSP問題常?？梢钥梢暬?，表示為約束圖，更直觀地顯示問題，幫助思考問題的答案,第2章 搜索技術(shù),26,從搜索角度看待CSP問題,CSP看作搜索問題的形式化 初始狀態(tài)空賦值集合，所有變量都是未賦值的 后繼函數(shù)給未賦值的變量一個賦值，要求該賦值與先前的變量賦值不沖突 目標(biāo)測試測試當(dāng)前的賦值(組)是否是完全賦值 路徑耗散每步耗散均為常數(shù)(1) 每個解必須為完全賦值 / 如果有n個變量，則解出現(xiàn)的深度為n(有限) / 常使用深度優(yōu)先搜索,第2章 搜索技術(shù),27,例1：澳大利亞地圖染色問題(1),澳大利亞地圖：用紅綠藍(lán)3色標(biāo)出各省，相鄰者顏色不同,第2章 搜索技術(shù),28,對應(yīng)于澳大利亞地圖的約束圖,相互關(guān)聯(lián)的節(jié)點(diǎn)用邊連接,第5章 搜索技術(shù),例1：澳大利亞地圖染色問題(2),WA,NT,SA,NSW,Q,V,T,西澳大利亞 WA 北領(lǐng)地 NT 南澳大利亞 SA 昆士蘭 Q 新南威爾士 NSW 維多利亞 V 塔斯馬尼亞 T 一組滿足約束的完全賦值 WA=R, NT=G, Q=R, SA=B, NSW=G, V=R, T=R,29,例2：密碼算術(shù)問題(1),算式 T W O + T W O F O U R 直觀地求解此問題： F=1 如不考慮O/U有進(jìn)位，則R/U/O為偶數(shù) R=4,6,8 O=2?,3?,4! R=8/O=4則T=7(由O/R/U/W共同限制) T=7則U=6/W=3 由此得到一組解1468 | 734 考慮U有進(jìn)位：R=0,2,4,6,8 O=5, R=0/O=5(有進(jìn)位)/T=7/W=6/U=3 解=1530 | 765,第2章 搜索技術(shù),30,各算式約束,四列算式約束 O+O=R+10*X1 X1+W+W=U+10*X2 X2+T+T=O+10*X3 X3=F 對應(yīng)的約束超圖如右 六個變量互不相等約束可化為兩兩不等約束二元約束,第2章 搜索技術(shù),例2：密碼算術(shù)問題(2),F,T,W,U,O,R,X3,X1,X2,約束：互不相等，兩兩不等,31,CSP問題的分類,變量離散值域 有限值域如地圖染色問題 無限值域如作業(yè)規(guī)劃，要使用約束語言(線性約束/非線性約束) 變量連續(xù)值域 如哈勃望遠(yuǎn)鏡實(shí)驗(yàn)日程安排 / 線性規(guī)劃問題 約束的類型 一元約束只限制一個變量的取值 二元約束與2個變量相關(guān) 高階約束涉及3個或更多變量,第2章 搜索技術(shù),32,CSP問題求解的復(fù)雜度,搜索相容的完全賦值，最樸素的想法是依次取變量的賦值組合并檢查其是否滿足約束條件指數(shù)級計(jì)算量 若CSP問題的任何一個變量的最大值域?yàn)閐，那么可能的完全賦值數(shù)量為O(dn) 有限值域CSP問題包括布爾CSP問題其中有一些NP完全問題，如3SAT問題(命題邏輯語句的可滿足性) / 最壞情況下不會指望低于指數(shù)級時間復(fù)雜性解決該問題,第2章 搜索技術(shù),33,2.5.2 CSP的回溯搜索,CSP問題具有一個性質(zhì)：可交換性變量賦值的順序?qū)Y(jié)果沒有影響 / 所有CSP搜索算法生成后繼節(jié)點(diǎn)時，在搜索樹每個節(jié)點(diǎn)上只考慮單個變量的可能賦值 CSP問題的求解使用深度優(yōu)先的回溯搜索 算法思想： 每次給一個變量賦值，當(dāng)沒有合法賦值(不滿足約束時)就要推翻前一個變量的賦值，重新給其賦值，這就是回溯,第2章 搜索技術(shù),34,簡單回溯法生成的搜索樹,澳大利亞地圖染色問題的搜索樹,第2章 搜索技術(shù),35,回溯搜索的通用算法,可以改善上述無信息搜索算法的性能，這些改進(jìn)是一些通用性的考慮： 變量賦值的次序?qū)π阅艿挠绊懺谌舾勺兞恳呀?jīng)賦值的條件下，如果下一步賦值有多個選擇，該選擇哪一個？ 當(dāng)前變量的賦值會對其他未賦值變量產(chǎn)生什么約束？怎樣利用這種約束以提高效率？ 當(dāng)遇到某個失敗的變量賦值時，怎樣避免同樣的失敗？就是說找到對這種失敗起到關(guān)鍵作用的某個變量賦值,第2章 搜索技術(shù),36,2.5.3 變量賦值次序的啟發(fā)式,隨機(jī)的變量賦值排序難以產(chǎn)生高效率的搜索 如：在WA=red/NT=green條件下選取SA賦值比Q要減少賦值次數(shù)(1:2) / 并且一旦給定SA賦值以后，Q/NSW/V的賦值只有一個選擇 因此，選擇合法取值最少的變量或者稱為最少剩余值(MRV)啟發(fā)式，或者稱為最受約束變量/失敗優(yōu)先啟發(fā)式 稱為失敗優(yōu)先啟發(fā)式是因?yàn)樗梢院芸煺业绞〉淖兞?，從而引起搜索的剪枝，避免更多?dǎo)致同樣失敗的搜索,第2章 搜索技術(shù),37,MRV啟發(fā)式,當(dāng)有多個變量需要選擇時優(yōu)先選擇在當(dāng)前約束下取值最少的變量 當(dāng)賦值的變量有多個值選擇時優(yōu)先選擇為剩余變量的賦值留下最多選擇的賦值 如，WA=red/NT=green時，如果給Q賦值，則Q=blue的選擇不好，此時SA沒有一個可選擇的了 如果要找出問題的所有解，則排序問題無所謂,第2章 搜索技術(shù),38,度啟發(fā)式,對于初始節(jié)點(diǎn)，選擇什么變量更合適？ 度啟發(fā)式選擇涉及對其他未賦值變量的約束數(shù)量大(與其他變量關(guān)聯(lián)最多)的變量 地圖染色例子中，度(SA)=5 / 其他均為2/3 實(shí)際上，一旦選擇了SA作為初始節(jié)點(diǎn)，應(yīng)用度啟發(fā)式求解本問題，則可以不經(jīng)任何回溯就找到解 SA=red NT=green Q=blue NSW=green WA=blue V=blue,第2章 搜索技術(shù),39,2.5.4 變量約束的啟發(fā)式,在搜索中盡可能早地考慮某些約束，以便減少搜索空間 前向檢驗(yàn)如果X被賦值，前向檢驗(yàn)就是檢查與X相連的那些變量Y，看看它們是否滿足相關(guān)約束，去掉Y中不滿足約束的賦值,第2章 搜索技術(shù),WA=red Q=green V=blue,藍(lán)色字體為賦值結(jié)果,40,前向檢驗(yàn),地圖染色問題中的前向檢驗(yàn) 前向檢驗(yàn)與MRV啟發(fā)式相結(jié)合實(shí)際上，MRV要做的就是向前找合適的變量 賦值V=blue引起矛盾，此時SA賦值為空，不滿足問題約束算法就要立刻回溯 注意這里只是檢驗(yàn)一步，即和當(dāng)前節(jié)點(diǎn)是否矛盾 / 至于被檢驗(yàn)節(jié)點(diǎn)之間的約束檢驗(yàn)還不能進(jìn)行改進(jìn)：約束傳播,第2章 搜索技術(shù),41,約束傳播弧相容,約束傳播將一個變量的約束內(nèi)容傳播到其他變量 希望約束傳播檢驗(yàn)更多的變量 / 花費(fèi)的代價更少快速 弧相容依次檢驗(yàn)約束圖中各個相關(guān)節(jié)點(diǎn)對(這里弧是有向弧) 例如：給定SA/NSW當(dāng)前值域，對于SA的每個取值x，NSW都有某個y和x相容，則SA到NSW的弧是相容的 / 反過來是NSW到SA的弧相容,第2章 搜索技術(shù),42,弧相容(1),在地圖染色約束的前向檢驗(yàn)圖中：第三行SA=blue/NSW=red,blue，則SA的取值有一個NSW=red與之相容 / 反過來NSW=blue，則SA為空值，即不相容通過刪除NSW值域中的blue可使其相容 同樣，弧相容檢測也能更早地發(fā)現(xiàn)矛盾如第二行SA/NT值域均為blue，如必須刪去SA=blue，則發(fā)現(xiàn)不相容 保持弧相容(MAC)算法思想反復(fù)檢測某個變量值域中的不相容弧，進(jìn)行值刪除，直到不再有矛盾,第2章 搜索技術(shù),43,弧相容(2),弧相容算法思想： 用隊(duì)列記錄需要檢驗(yàn)不相容的弧 每條弧Xi, Xj依次從隊(duì)列中刪除并被檢驗(yàn)，如果任何一個Xi值域中的值需要刪除，則每個指向Xi的弧Xk, Xi都必須重新插入隊(duì)列進(jìn)行檢驗(yàn)因?yàn)橹赶蜻@個變量的弧可能產(chǎn)生新的不相容(因?yàn)樵瓉砜赡芫褪且驗(yàn)檫@個值產(chǎn)生了它們之間的相容) 時間復(fù)雜度二元CSP約束至多有O(n2)條弧 / 每條弧至多插入隊(duì)列d次(d個取值)，檢驗(yàn)一條弧為O(d2) /算法最壞情況下為O(n2d2),第2章 搜索技術(shù),44,特殊約束,實(shí)際問題中出現(xiàn)的特殊約束，其效率要比通用的約束高很多 變量取值各不相同AllDiff，如果約束涉及m個變量，所有變量共有n個取值，如果mn則此約束不能被滿足 相應(yīng)算法刪除約束中只有單值值域的變量，將其取值從其余變量值域中刪去；對單值變量重復(fù)此過程；如果得到空值域或剩下的變量數(shù)大于取值數(shù)，則產(chǎn)生矛盾 其他約束資源約束/邊界約束,第2章 搜索技術(shù),45,2.5.5 關(guān)于失敗變量的啟發(fā)式,在回溯算法中，當(dāng)發(fā)現(xiàn)不滿足約束即搜索失敗時，則回到上一個變量并嘗試下一個取值稱為歷時回溯 / 在很多情況下這樣做是效率很低的因?yàn)閱栴}并不決定于上一個(甚至幾個)變量的取值 所以，回溯應(yīng)該倒退到導(dǎo)致失敗的變量集合中的一個變量該集合稱為沖突集 變量X的沖突集是通過約束與X相連接的先前已賦值變量的集合,第2章 搜索技術(shù),46,沖突集,對于地圖染色問題，設(shè)有不完全賦值Q=red, NSW=green, V=blue, T=red / 此時，SA賦值將發(fā)現(xiàn)不滿足任何約束SA的沖突集=Q, NSW, V 對于前向檢驗(yàn)算法，可以很容易得到?jīng)_突集 基于X賦值的前向檢驗(yàn)從變量Y的值域中刪除一個值時，說明X和Y存在沖突，則顯然X是Y的沖突集中的一個變量 當(dāng)?shù)竭_(dá)Y時，可知回溯到哪個變量,第2章 搜索技術(shù),47,后向跳轉(zhuǎn),回溯檢驗(yàn)導(dǎo)致失敗的變量的賦值后向跳轉(zhuǎn)：回溯到?jīng)_突集中時間最近(最后賦值)的變量 每個被后向跳轉(zhuǎn)剪枝的分支在前向檢驗(yàn)算法中也被剪枝簡單的后向跳轉(zhuǎn)在前向檢驗(yàn)(弧相容性檢驗(yàn))搜索中是多余的 因?yàn)槎际亲鋈≈迪嗳莸臋z測，只要在弧相容檢驗(yàn)時增加一個變量集合記錄即可,第2章 搜索技術(shù),48,沖突指導(dǎo)的后向跳轉(zhuǎn),變量的沖突集更一般的情況前面的變量集合中全部變量(不是其中一個變量)使得當(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例子),第2章 搜索技術(shù),2.6 博弈搜索 2.6.1 極大極小決策 2.6.2 -剪枝,第2章 搜索技術(shù),50,博弈搜索問題與方法,從智能體角度看，博弈是多智能體之間的競爭和對抗 / 在競爭的環(huán)境中，每個智能體的目的是沖突的，由此引出對抗搜索問題稱為博弈 本節(jié)探討兩個問題如何搜索到取勝的路徑 / 如何提高搜索效率 相應(yīng)的方法最優(yōu)策略(極大極小決策)/-剪枝,第2章 搜索技術(shù),51,博弈游戲的描述,兩個游戲者的博弈可以定義為一類搜索問題，其中包括： 初始狀態(tài)棋盤局面和哪個游戲者出招 后繼函數(shù)返回(招數(shù),狀態(tài))對的一個列表，其中每對表示一個合法招數(shù)和相應(yīng)的結(jié)果狀態(tài) 終止測試判斷游戲是否結(jié)束 效用函數(shù)或稱目標(biāo)函數(shù)，對終止?fàn)顟B(tài)給出一個數(shù)值如輸贏和平局(以-1/+1/0表示) 雙方的初始狀態(tài)和合法招數(shù)定義了游戲的博弈樹此為博弈搜索,第2章 搜索技術(shù),52,井字棋的博弈樹,第2章 搜索技術(shù),53,2.6.1 極大極小決策,博弈搜索中，最優(yōu)解是導(dǎo)致取勝的終止?fàn)顟B(tài)的一系列招數(shù) 在井字棋搜索樹中，因?yàn)镸AX先行，所以MAX的任務(wù)是利用搜索樹確定最佳招數(shù) / 但是另一方MIN也有發(fā)言權(quán) 因此MAX制定取勝策略時必須不斷地考慮MIN應(yīng)對條件下如何取勝即MAX初始狀態(tài)下應(yīng)該采取什么招數(shù)，然后是MIN應(yīng)對造成的狀態(tài)下MAX采取的招數(shù)，接著繼續(xù)考慮下一步應(yīng)對后的招數(shù).,第2章 搜索技術(shù),54,極大極小值(1),假設(shè)一個兩層的博弈樹(因?yàn)榧词故蔷制宓牟┺臉湟蔡珡?fù)雜了)，其中有MAX節(jié)點(diǎn)和MIN節(jié)點(diǎn) 博弈樹中，每個單方的招數(shù)(或稱走步)是一層 / 雙方各走一招稱為一步(博弈樹的深度是一步的) 給定一棵博弈樹，最優(yōu)策略可以通過檢查每個節(jié)點(diǎn)的極大極小值來決定記為MAX-MIN(n)，所以也稱為極大極小決策,第2章 搜索技術(shù),55,極大極小值(2),如果博弈雙方都按照最優(yōu)策略進(jìn)行，那么一個節(jié)點(diǎn)的極大極小值就是對應(yīng)狀態(tài)的效用值(對應(yīng)MAX) 對于某個節(jié)點(diǎn)，極大極小函數(shù)如下定義 MAX優(yōu)先選擇有極大值的狀態(tài) / MIN則選擇有極小值的狀態(tài),第5章 搜索技術(shù),56,極大極小值(3),第2章 搜索技術(shù),3 12 8 2 4 6 14 5 2,MAX,MIN,MAX,57,極大極小值(4),圖中MAX先行，有3個后繼MIN節(jié)點(diǎn)，此時MAX的取值必須看MIN如何取值 每個MIN節(jié)點(diǎn)亦有3個后繼MAX節(jié)點(diǎn)，假設(shè)其取值已知 因?yàn)镸IN節(jié)點(diǎn)只取其后繼節(jié)點(diǎn)中之最小者(讓MAX效用最小)，故B=3/C=2/D=2 MAX節(jié)點(diǎn)取A/B/C中最大者，故A=3 最后根節(jié)點(diǎn)A的極大極小函數(shù)值=3引向具有最高極大極小值的后繼,第2章 搜索技術(shù),58,極大極小值算法說明,簡單的遞歸算法按照定義計(jì)算每個后繼節(jié)點(diǎn)的極大極小值 / 搜索是從目標(biāo)到初始節(jié)點(diǎn)的反向推導(dǎo) 算法對博弈樹實(shí)行了深度優(yōu)先搜索 如果博弈樹的最大深度為m，每個節(jié)點(diǎn)的合法招數(shù)為b，則 算法的時間復(fù)雜度是O(bm) 每次生成全部后繼節(jié)點(diǎn)的空間復(fù)雜度是O(bm) 每次只生成一個后繼節(jié)點(diǎn)的空間復(fù)雜度是O(m),第2章 搜索技術(shù),59,極大極小值算法,Function MAX-MIN-DECISION(state) returns an action inputs: state (current state in game) v MAX-VALUE(state) return the action in SUCCESSORS(state) with value v Function MAX-VALUE(state) returns a utility value if 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 value if TERMINAL-TEST(state) then return UTILITY(state) v + for a, s in SUCCESSORS(state) do v MIN(v, MAX-VALUE(s) return v,第2章 搜索技術(shù),60,2.6.2 -剪枝,極大極小值搜索的問題是狀態(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ù),61,博弈樹的剪枝(1),第2章 搜索技術(shù),62,博弈樹的剪枝(2),第2章 搜索技術(shù),63,博弈樹的剪枝(3),第2章 搜索技術(shù),64,-剪枝算法(1),在極大極小值算法基礎(chǔ)上增加了剪枝功能，即在返回值基礎(chǔ)上增加了判斷 Function ALPHA-BETA-SEARCH(state) returns an action inputs: state (current state in game) v MAX-VALUE(state, -, +) return the action in SUCCESSORS(state) with value v,第2章 搜索技術(shù),65,-剪枝算法(2),Function MAX-VALUE(state, ) returns a utility value inputs: 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 state if TERMINAL-TEST(state) then return UTILITY(state) v - for a, s in SUCCESSORS(state) do v MAX(v, MIN-VALUE(s, ) if v then return v MAX(, v) return v,第2章 搜索技術(shù),66,-剪枝算法(3),Function MIN-VALUE(state, , ) returns a utility value inputs: 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 state if TERMINAL-TEST(state) then return UTILITY(state) v + for a, s in SUCCESSORS(state) do v MIN(v, MAX-VALUE(s, , ) if v then return v MIN(, v) return v,第2章 搜索技術(shù),67,-剪枝算法的說明,-剪枝可以應(yīng)用樹的任何深度，許多情況下可以剪掉整個子樹 / 其原則是如果在節(jié)點(diǎn)n的父節(jié)點(diǎn)或者更上層的節(jié)點(diǎn)有一個更好的選擇m，則在實(shí)際游戲(搜索)中永遠(yuǎn)不會到達(dá)n =到目前為止在路徑上任意點(diǎn)發(fā)現(xiàn)的MAX最佳選擇 =到目前為止在路徑上任意點(diǎn)發(fā)現(xiàn)的MIN最佳選擇 -搜索不斷更新/值，當(dāng)某個節(jié)點(diǎn)的值分別比/值更差時剪掉該節(jié)點(diǎn)的剩余分支,第2章 搜索技術(shù),68,-剪枝的效率,-剪枝的效率很大程度上取決于檢查后繼節(jié)點(diǎn)的次序應(yīng)該先檢查那些可能最好的后繼 如果能夠先檢查那些最好的后繼，則-剪枝算法只需檢查O(bd/2)個節(jié)點(diǎn)以決定最佳招數(shù) / 極大極小值算法為O(bd)有效分支因子b到b的平方根效率大大提高,第2章 搜索技術(shù),69,本章復(fù)習(xí)提示,嘗試使用搜索方式求解問題 / 注意本章的搜索算法都是通用算法，即沒有考慮具體任務(wù)的相關(guān)知識 具體搜索問題的形式化表示(初始狀態(tài)/后繼函數(shù)/搜索代價等) 了解各種搜索算法(包括局部搜索和博弈搜索)的思想、相關(guān)性質(zhì)和性能 嘗試用啟發(fā)式搜索算法(A*算法)解決一些游戲問題 約束滿足問題的相關(guān)概念,第2章 搜索技術(shù),70,參考書目,Stuart Russell / Peter Norvig: AIMA 第3章 / 第4章 / 第5章 / 第6章 陸汝鈐 編著: 人工智能(上冊) 第5章 / 第6章 / 第8章 / 第9章 田盛豐、黃厚寬，人工智能與知識工程，中國鐵道出版社，1999年8月第1版，第4章 / 第9章,第2章 搜索技術(shù),附錄 A*算法可采納性的證明,第2章 搜索技術(shù),72,A*算法可采納性,定理： A*算法是可采納的，即若存在從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)點(diǎn)Sg的路徑，則A*算法必能結(jié)束在最佳路徑上 證明的過程： 首先證明A*算法必定成功結(jié)束 其次證明A*算法結(jié)束時中止于最佳路徑,第2章 搜索技術(shù),73,證明的步驟,證明分為三步： (1)對于有限圖，A*算法一定成功結(jié)束 (2)對于無限圖，A*算法一定成功結(jié)束 (3)A*算法必定終止于最佳路徑上 對于無限圖情況的證明，引入2個引理 (1)如果A*算法不終止，則存在f值任意大的節(jié)點(diǎn) (2)A*算法結(jié)束前，仍有耗散值更小的節(jié)點(diǎn)待擴(kuò)展,第2章 搜索技術(shù),74,定理1的證明(1),定理1對于有限圖，如果從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)點(diǎn)Sg有路徑存在，則A*算法一定成功結(jié)束 證明： 首先證明算法必定會結(jié)束 由于搜索圖為有限圖，如果算法能找到解，則會成功結(jié)束；如果算法找不到解，則必然會由于Open表變空而結(jié)束。因此，A*算法必然會結(jié)束,第2章 搜索技術(shù),75,定理1的證明(2),然后證明算法一定會成功結(jié)束 由于至少存在一條由初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑，設(shè)此路徑為 S0= n0，n1 ，nk =Sg 算法開始時，節(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表中 / 因此，算法必定會成功結(jié)束 ,第2章 搜索技術(shù),76,引理1的證明(1),引理1對無限圖，如果從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)點(diǎn)Sg有路徑存在，且A*算法不終止的話，則從Open表中選出的節(jié)點(diǎn)必將具有任意大