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

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