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

人工智能原理

第2章搜索技術(shù)

（下）

1人工智能原理

第2章搜索技術(shù)

（下）1

本章內(nèi)容

2.1搜索與問題求解

2.2無信息搜索策略

2.3啟發(fā)式搜索策略

2.4局部搜索算法

2.5約束滿足問題

2.6博弈搜索

參考書目

附錄A*算法可采納性的證明第2章搜索技術(shù)2 本章內(nèi)容

2.1搜索與問題求解

2.2無信息2.4局部搜索算法

2.4.1局部搜索與最優(yōu)化

2.4.2爬山法搜索

2.4.3模擬退火搜索

2.4.4局部剪枝搜索

2.4.5遺傳算法第2章搜索技術(shù)32.4局部搜索算法

2.4.1局部搜索與最優(yōu)化

2.4局部搜索算法前面的搜索算法都是保留搜索路徑的，到達目標的路徑就是問題的解—然而許多問題中到達目標的路徑是無關(guān)緊要的與系統(tǒng)地搜索狀態(tài)空間(保留各種路徑)相對，不關(guān)心路徑的搜索算法就是局部搜索算法局部搜索從一個單獨的當前狀態(tài)出發(fā)，通常只移動到相鄰狀態(tài)典型情況下搜索的路徑不保留第2章搜索技術(shù)4局部搜索算法前面的搜索算法都是保留搜索路徑的，到達目標的路徑局部搜索算法的應(yīng)用集成電路設(shè)計工廠場地布局車間作業(yè)調(diào)度自動程序設(shè)計電信網(wǎng)絡(luò)優(yōu)化車輛尋徑文件夾管理第2章搜索技術(shù)5局部搜索算法的應(yīng)用集成電路設(shè)計第2章搜索技術(shù)52.4.1局部搜索與最優(yōu)化問題局部搜索算法的優(yōu)點：只使用很少的內(nèi)存(通常是一個常數(shù))經(jīng)常能在不適合系統(tǒng)化算法的很大或無限的狀態(tài)空間中找到合理的解最優(yōu)化問題—根據(jù)一個目標函數(shù)找到最佳狀態(tài)/只有目標函數(shù)，而不考慮(沒有)“目標測試”和“路徑耗散”局部搜索算法適用于最優(yōu)化問題第2章搜索技術(shù)62.4.1局部搜索與最優(yōu)化問題局部搜索算法的優(yōu)點：第2章狀態(tài)空間地形圖(1)第2章搜索技術(shù)山肩目標函數(shù)全局最大值局部最大值“平坦”局部最大值狀態(tài)空間當前狀態(tài)7狀態(tài)空間地形圖(1)第2章搜索技術(shù)山肩目標函數(shù)全局最大值局狀態(tài)空間地形圖(2)在狀態(tài)圖中，既有“位置”(用狀態(tài)表示)又有“高度”(用耗散值或目標函數(shù)值表示)如果高度對應(yīng)于耗散值，則目標是找到全局最小值，即圖中最低點如果高度對應(yīng)于目標函數(shù)，則目標是找到全局最大值，即圖中最高峰如果存在解，則完備的局部搜索算法能夠找到解而最優(yōu)的局部搜索算法能夠找到全局最大或最小值第2章搜索技術(shù)8狀態(tài)空間地形圖(2)在狀態(tài)圖中，既有“位置”(用狀態(tài)表示)又局部搜索算法本節(jié)簡要介紹以下4種局部搜索算法/介紹其算法思想爬山法搜索模擬退火搜索局部剪枝搜索遺傳算法從搜索的角度看遺傳算法也是搜索假設(shè)空間的一種方法(學(xué)習(xí)問題歸結(jié)為搜索問題)—生成后繼假設(shè)的方式第2章搜索技術(shù)9局部搜索算法本節(jié)簡要介紹以下4種局部搜索算法/介紹其算法2.4.2爬山法搜索爬山法(hill-climbing)—就是向值增加的方向持續(xù)移動—登高過程/如果相鄰狀態(tài)中沒有比它更高的值，則算法結(jié)束于頂峰爬山法搜索算法思想：(1)令初始狀態(tài)S0為當前狀態(tài)(2)若當前狀態(tài)已經(jīng)達標，則算法運行結(jié)束，搜索成功(3)若存在一個動作可以作用于當前狀態(tài)以產(chǎn)生一個新狀態(tài)，使新狀態(tài)的估計值優(yōu)于當前狀態(tài)的估計值，則放棄當前狀態(tài)，并令剛產(chǎn)生的新狀態(tài)為當前狀態(tài)，轉(zhuǎn)(2)(4)取當前狀態(tài)為相對最優(yōu)解，停止執(zhí)行算法第2章搜索技術(shù)102.4.2爬山法搜索爬山法(hill-climbing)—爬山法搜索的局限爬山法是一種局部貪婪搜索，不是最優(yōu)解算法(或是不完備的)/其問題是：局部極大值—比其鄰居狀態(tài)都高的頂峰，但是小于全局最大值(參照狀態(tài)空間地形圖)山脊—一系列的局部極大值高原—評價函數(shù)平坦的一塊區(qū)域(或者山肩)第2章搜索技術(shù)11爬山法搜索的局限爬山法是一種局部貪婪搜索，不是最優(yōu)解算法(或爬山法搜索的變形爬山法的變形隨機爬山法—隨機選擇下一步首選爬山法—隨機選擇直到有優(yōu)于當前節(jié)點的下一步隨機重新開始爬山法—隨機生成初始狀態(tài)，進行一系列爬山法搜索—這時算法是完備的概率接近1第2章搜索技術(shù)12爬山法搜索的變形爬山法的變形第2章搜索技術(shù)122.4.3模擬退火搜索將爬山法(停留在局部山峰)和隨機行走以某種方式結(jié)合，以同時獲得完備性和效率模擬退火的思想想象在不平的表面上如何使一個乒乓球掉到最深的裂縫中—如果只讓其在表面滾動，則它只會停留在局部極小點/如果晃動平面，可以使乒乓球彈出局部極小點/技巧是晃動足夠大使乒乓球彈出局部極小點，但又不能太大把它從全局極小點中趕出第2章搜索技術(shù)132.4.3模擬退火搜索將爬山法(停留在局部山峰)和隨機行走模擬退火的解決思路(1)思路—開始使勁晃動(先高溫加熱)然后慢慢降低搖晃的強度(逐漸降溫)[退火過程]算法的核心—移動選擇選擇隨機移動，如果評價值改善，則移動被接受，否則以某個小于1的概率接受概率按照移動評價值變壞的梯度ΔE而呈指數(shù)級下降/同時也會隨著作為控制的參數(shù)—“溫度”T的降低(數(shù)值減小)而降低接受概率=eΔE/T(注意此時ΔE

<0)第5章搜索技術(shù)14模擬退火的解決思路(1)思路—開始使勁晃動(先高溫加熱)然后模擬退火的解決思路(2)溫度T是時間的函數(shù)，按照模擬退火的思想，數(shù)值應(yīng)該逐漸減小(降溫)因為接受概率=eΔE/T且ΔE

<0，所以當溫度高時，接受概率較大(接近1)/而T越來越低時，ΔE/T變大，因而接受概率降低可以證明，如果T下降得足夠慢，則算法找到全局最優(yōu)解的概率接近1第5章搜索技術(shù)15模擬退火的解決思路(2)溫度T是時間的函數(shù)，按照模擬退火的思2.4.4局部剪枝搜索基本思想—與只從一個單獨的起始狀態(tài)出發(fā)不同，局部剪枝搜索從k個隨機生成的狀態(tài)開始，每步生成全部k個狀態(tài)的所有后繼狀態(tài)/如果其中之一是目標狀態(tài)，算法停止；否則從全部后繼狀態(tài)中選擇最佳的k個狀態(tài)繼續(xù)搜索在局部剪枝搜索過程中，有用的信息在k個并行的搜索線程之間傳遞—算法會很快放棄沒有成果的搜索而把資源放在取得最大進展的搜索上第2章搜索技術(shù)162.4.4局部剪枝搜索基本思想—與只從一個單獨的起始狀態(tài)出隨機剪枝搜索如果k個狀態(tài)缺乏多樣性，則局部剪枝搜索會受其影響，性能變差算法的變種—隨機剪枝搜索幫助緩解這一問題—隨機剪枝搜索不是選擇最好的k個后代，而是按照一定概率隨機地選擇k個后繼狀態(tài)/選擇給定后繼狀態(tài)的概率是狀態(tài)值的遞增函數(shù)類似于自然選擇過程—狀態(tài)對應(yīng)生物體，其值對應(yīng)于適應(yīng)性，后代就是后繼狀態(tài)第2章搜索技術(shù)17隨機剪枝搜索如果k個狀態(tài)缺乏多樣性，則局部剪枝搜索會受其影響2.4.5遺傳算法遺傳算法(genericalgorithm/GA)是隨機剪枝的變種—不是通過修改單一狀態(tài)而是通過把兩個父狀態(tài)結(jié)合以生成后繼狀態(tài)與剪枝搜索一樣，遺傳算法也是從k個隨機狀態(tài)開始—這k個狀態(tài)稱為種群，每個狀態(tài)稱為個體個體用有限長的字符串(通常為0/1串)表示每個狀態(tài)用其評價函數(shù)(適應(yīng)度函數(shù))給出評價值(適應(yīng)值)隨后的操作包括—選擇/雜交/變異第2章搜索技術(shù)182.4.5遺傳算法遺傳算法(genericalgorit遺傳算法的操作選擇(或者稱繁殖)—按照一定概率隨機地選擇兩對個體進行繁殖(即生成后繼狀態(tài))雜交(或者稱交叉)—雜交點是在表示狀態(tài)的字符串中隨機選擇的一個位置，以此形成新狀態(tài)—后代是父串在雜交點上進行雜交(各取一部分)得來的變異—在新生成的串中各個位置都會按照一個獨立的小概率隨機變異第2章搜索技術(shù)19遺傳算法的操作選擇(或者稱繁殖)—按照一定概率隨機地選擇兩對遺傳算法簡要描述(1)定義問題和目標函數(shù)(2)選擇候選解作為初始種群，每個解作為個體用二進制串表示(個體相當于染色體，其中的元素相當于基因)(3)根據(jù)目標函數(shù)，對于每個個體計算適應(yīng)函數(shù)值(4)為每個個體指定一個與其適應(yīng)值成正比的被選擇概率(繁殖概率)(5)根據(jù)概率選擇個體，所選個體通過交叉/變異等操作產(chǎn)生新一代種群(6)如果找到了解或者某種限制已到，則過程結(jié)束；否則轉(zhuǎn)(3)第2章搜索技術(shù)20遺傳算法簡要描述(1)定義問題和目標函數(shù)第2章搜索技術(shù)20遺傳算法的特點遺傳算法也結(jié)合了“上山”趨勢和隨機搜索，并在并行搜索線程之間交換信息遺傳算法的主要優(yōu)勢來自于雜交數(shù)學(xué)上可以證明，如果基因編碼的位置在初始時就隨機轉(zhuǎn)換的話，雜交就沒有優(yōu)勢雜交的優(yōu)勢在于它能夠?qū)ⅹ毩l(fā)展的若干個相對固定的字符(能夠執(zhí)行有用的功能—“磚塊”)組合起來，提高了搜索的粒度所謂有用的磚塊，就是幾個結(jié)合起來可以構(gòu)造問題的解—參見書中的八皇后問題舉例第2章搜索技術(shù)21遺傳算法的特點遺傳算法也結(jié)合了“上山”趨勢和隨機搜索，并在并遺傳算法的模式遺傳算法上述特點可以用模式(schema)來解釋—模式是某些位置上的數(shù)字尚未確定的一個狀態(tài)子串能夠匹配模式的字符串稱為該模式的實例如果一個模式的實例的平均適應(yīng)值超過均值，則種群內(nèi)這個模式的實例數(shù)量會隨時間而增長遺傳算法在模式和解的有意義成分相對應(yīng)時才會工作得最好遺傳算法有很多應(yīng)用，但是在什么情況下它會達到好效果，還有很多研究要做第2章搜索技術(shù)22遺傳算法的模式遺傳算法上述特點可以用模式(schema)來解2.5約束滿足問題

2.5.1約束滿足問題的定義

2.5.2CSP的回溯搜索

2.5.3變量賦值次序的啟發(fā)式

2.5.4變量約束的啟發(fā)式

2.5.5關(guān)于失敗變量的啟發(fā)式第2章搜索技術(shù)232.5約束滿足問題

2.5.1約束滿足問題的定義

2.2.5.1約束滿足問題的定義約束滿足問題(ConstraintSatisfyingProblem,CSP)由一個變量集合{X1~Xn}和一個約束集合{C1~Cm}定義每個變量都有一個非空可能值域Di每個約束指定了包含若干變量的一個子集內(nèi)各變量的賦值范圍CSP的一個狀態(tài)—對一些或全部變量的賦值{Xi=vi,Xj=vj,…}第2章搜索技術(shù)242.5.1約束滿足問題的定義約束滿足問題(ConstraiCSP問題的解一個不違反任何約束的對變量的賦值稱為相容賦值或合法賦值對每個變量都進行賦值稱為完全賦值一個(一組)既是相容賦值又是完全賦值的對變量的賦值就是CSP問題的解CSP問題常?？梢钥梢暬硎緸榧s束圖，更直觀地顯示問題，幫助思考問題的答案第2章搜索技術(shù)25CSP問題的解一個不違反任何約束的對變量的賦值稱為相容賦值或從搜索角度看待CSP問題CSP看作搜索問題的形式化初始狀態(tài)—空賦值集合，所有變量都是未賦值的后繼函數(shù)—給未賦值的變量一個賦值，要求該賦值與先前的變量賦值不沖突目標測試—測試當前的賦值(組)是否是完全賦值路徑耗散—每步耗散均為常數(shù)(1)每個解必須為完全賦值/如果有n個變量，則解出現(xiàn)的深度為n(有限)/常使用深度優(yōu)先搜索第2章搜索技術(shù)26從搜索角度看待CSP問題CSP看作搜索問題的形式化第2章搜例1：澳大利亞地圖染色問題(1)澳大利亞地圖：用紅綠藍3色標出各省，相鄰者顏色不同第2章搜索技術(shù)西澳大利亞北領(lǐng)地南澳大利亞昆士蘭新南威爾士維多利亞塔斯馬尼亞27例1：澳大利亞地圖染色問題(1)澳大利亞地圖：用紅綠藍3色標對應(yīng)于澳大利亞地圖的約束圖,相互關(guān)聯(lián)的節(jié)點用邊連接第5章搜索技術(shù)例1：澳大利亞地圖染色問題(2)WANTSANSWQVT西澳大利亞–WA北領(lǐng)地–NT南澳大利亞–SA昆士蘭–Q新南威爾士–NSW維多利亞–V塔斯馬尼亞–T一組滿足約束的完全賦值{WA=R,NT=G,Q=R,SA=B,NSW=G,V=R,T=R}28對應(yīng)于澳大利亞地圖的約束圖,相互關(guān)聯(lián)的節(jié)點用邊連接第5章搜例2：密碼算術(shù)問題(1)算式

TWO + TWO

——————— FOUR直觀地求解此問題：F=1 如不考慮O/U有進位，則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有進位：R={0,2,4,6,8}O={5,……}R=0/O=5(有進位)/T=7/W=6/U=3解={1530|765}第2章搜索技術(shù)29例2：密碼算術(shù)問題(1)算式 TWO第2章搜各算式約束四列算式約束O+O=R+10*X1X1+W+W=U+10*X2X2+T+T=O+10*X3X3=F對應(yīng)的約束超圖如右六個變量互不相等約束可化為兩兩不等約束—二元約束第2章搜索技術(shù)例2：密碼算術(shù)問題(2)FTWUORX3X1X2約束：互不相等，兩兩不等30各算式約束四列算式約束第2章搜索技術(shù)例2：密碼算術(shù)問題(2CSP問題的分類變量—離散值域

有限值域—如地圖染色問題無限值域—如作業(yè)規(guī)劃，要使用約束語言(線性約束/非線性約束)變量—連續(xù)值域如哈勃望遠鏡實驗日程安排/線性規(guī)劃問題約束的類型一元約束—只限制一個變量的取值二元約束與2個變量相關(guān)高階約束—涉及3個或更多變量第2章搜索技術(shù)31CSP問題的分類變量—離散值域第2章搜索技術(shù)31CSP問題求解的復(fù)雜度搜索相容的完全賦值，最樸素的想法是依次取變量的賦值組合并檢查其是否滿足約束條件指數(shù)級計算量若CSP問題的任何一個變量的最大值域為d，那么可能的完全賦值數(shù)量為O(dn)有限值域CSP問題包括布爾CSP問題—其中有一些NP完全問題，如3SAT問題(命題邏輯語句的可滿足性)/最壞情況下不會指望低于指數(shù)級時間復(fù)雜性解決該問題第2章搜索技術(shù)32CSP問題求解的復(fù)雜度搜索相容的完全賦值，最樸素的想法是依次2.5.2CSP的回溯搜索CSP問題具有一個性質(zhì)：可交換性—變量賦值的順序?qū)Y(jié)果沒有影響/所有CSP搜索算法生成后繼節(jié)點時，在搜索樹每個節(jié)點上只考慮單個變量的可能賦值CSP問題的求解使用深度優(yōu)先的回溯搜索算法思想：每次給一個變量賦值，當沒有合法賦值(不滿足約束時)就要推翻前一個變量的賦值，重新給其賦值，這就是回溯第2章搜索技術(shù)332.5.2CSP的回溯搜索CSP問題具有一個性質(zhì)：可交換性簡單回溯法生成的搜索樹澳大利亞地圖染色問題的搜索樹第2章搜索技術(shù)WA=redWA=redNT=greenWA=RedNT=blueWA=redNT=greenQ=redWA=redNT=greenQ=blueWA=greenWA=blue34簡單回溯法生成的搜索樹澳大利亞地圖染色問題的搜索樹第2章搜回溯搜索的通用算法可以改善上述無信息搜索算法的性能，這些改進是一些通用性的考慮：變量賦值的次序?qū)π阅艿挠绊憽谌舾勺兞恳呀?jīng)賦值的條件下，如果下一步賦值有多個選擇，該選擇哪一個？當前變量的賦值會對其他未賦值變量產(chǎn)生什么約束？怎樣利用這種約束以提高效率？當遇到某個失敗的變量賦值時，怎樣避免同樣的失??？就是說找到對這種失敗起到關(guān)鍵作用的某個變量賦值第2章搜索技術(shù)35回溯搜索的通用算法可以改善上述無信息搜索算法的性能，這些改進2.5.3變量賦值次序的啟發(fā)式隨機的變量賦值排序難以產(chǎn)生高效率的搜索如：在WA=red/NT=green條件下選取SA賦值比Q要減少賦值次數(shù)(1:2)/并且一旦給定SA賦值以后，Q/NSW/V的賦值只有一個選擇因此，選擇合法取值最少的變量—或者稱為最少剩余值(MRV)啟發(fā)式，或者稱為最受約束變量/失敗優(yōu)先啟發(fā)式稱為失敗優(yōu)先啟發(fā)式是因為它可以很快找到失敗的變量，從而引起搜索的剪枝，避免更多導(dǎo)致同樣失敗的搜索第2章搜索技術(shù)362.5.3變量賦值次序的啟發(fā)式隨機的變量賦值排序難以產(chǎn)生高MRV啟發(fā)式當有多個變量需要選擇時—優(yōu)先選擇在當前約束下取值最少的變量當賦值的變量有多個值選擇時—優(yōu)先選擇為剩余變量的賦值留下最多選擇的賦值如，WA=red/NT=green時，如果給Q賦值，則Q=blue的選擇不好，此時SA沒有一個可選擇的了如果要找出問題的所有解，則排序問題無所謂第2章搜索技術(shù)37MRV啟發(fā)式當有多個變量需要選擇時—優(yōu)先選擇在當前約束下取值度啟發(fā)式對于初始節(jié)點，選擇什么變量更合適？度啟發(fā)式—選擇涉及對其他未賦值變量的約束數(shù)量大(與其他變量關(guān)聯(lián)最多)的變量地圖染色例子中，度(SA)=5/其他均為2/3實際上，一旦選擇了SA作為初始節(jié)點，應(yīng)用度啟發(fā)式求解本問題，則可以不經(jīng)任何回溯就找到解SA=redNT=greenQ=blue

NSW=green

WA=blue

V=blue第2章搜索技術(shù)38度啟發(fā)式對于初始節(jié)點，選擇什么變量更合適？第2章搜索技術(shù)32.5.4變量約束的啟發(fā)式在搜索中盡可能早地考慮某些約束，以便減少搜索空間前向檢驗—如果X被賦值，前向檢驗就是檢查與X相連的那些變量Y，看看它們是否滿足相關(guān)約束，去掉Y中不滿足約束的賦值第2章搜索技術(shù)WANTQNSWVSARGBRGBRGBRGBRGBRGB

R

GBRGBRGBRGBGBRBGRBRGBBRBGR

B--WA=redQ=greenV=blue藍色字體為賦值結(jié)果392.5.4變量約束的啟發(fā)式在搜索中盡可能早地考慮某些約束，前向檢驗地圖染色問題中的前向檢驗前向檢驗與MRV啟發(fā)式相結(jié)合—實際上，MRV要做的就是向前找合適的變量賦值V=blue引起矛盾，此時SA賦值為空，不滿足問題約束—算法就要立刻回溯注意這里只是檢驗一步，即和當前節(jié)點是否矛盾/至于被檢驗節(jié)點之間的約束檢驗還不能進行—改進：約束傳播第2章搜索技術(shù)40前向檢驗地圖染色問題中的前向檢驗第2章搜索技術(shù)40約束傳播—弧相容約束傳播—將一個變量的約束內(nèi)容傳播到其他變量希望約束傳播檢驗更多的變量/花費的代價更少—快速弧相容—依次檢驗約束圖中各個相關(guān)節(jié)點對(這里弧是有向弧)例如：給定SA/NSW當前值域，對于SA的每個取值x，NSW都有某個y和x相容，則SA到NSW的弧是相容的/反過來是NSW到SA的弧相容第2章搜索技術(shù)41約束傳播—弧相容約束傳播—將一個變量的約束內(nèi)容傳播到其他變量弧相容(1)在地圖染色約束的前向檢驗圖中：第三行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ù)檢測某個變量值域中的不相容弧，進行值刪除，直到不再有矛盾第2章搜索技術(shù)42弧相容(1)在地圖染色約束的前向檢驗圖中：第三行SA={bl弧相容(2)弧相容算法思想：用隊列記錄需要檢驗不相容的弧每條弧[Xi,Xj]依次從隊列中刪除并被檢驗，如果任何一個Xi值域中的值需要刪除，則每個指向Xi的弧[Xk,Xi]都必須重新插入隊列進行檢驗—因為指向這個變量的弧可能產(chǎn)生新的不相容(因為原來可能就是因為這個值產(chǎn)生了它們之間的相容)時間復(fù)雜度—二元CSP約束至多有O(n2)條弧/每條弧至多插入隊列d次(d個取值)，檢驗一條弧為O(d2)/算法最壞情況下為O(n2d2)第2章搜索技術(shù)43弧相容(2)弧相容算法思想：第2章搜索技術(shù)43特殊約束實際問題中出現(xiàn)的特殊約束，其效率要比通用的約束高很多變量取值各不相同—AllDiff，如果約束涉及m個變量，所有變量共有n個取值，如果m>n則此約束不能被滿足相應(yīng)算法—刪除約束中只有單值值域的變量，將其取值從其余變量值域中刪去；對單值變量重復(fù)此過程；如果得到空值域或剩下的變量數(shù)大于取值數(shù)，則產(chǎn)生矛盾其他約束—資源約束/邊界約束第2章搜索技術(shù)44特殊約束實際問題中出現(xiàn)的特殊約束，其效率要比通用的約束高很多2.5.5關(guān)于失敗變量的啟發(fā)式在回溯算法中，當發(fā)現(xiàn)不滿足約束即搜索失敗時，則回到上一個變量并嘗試下一個取值—稱為歷時回溯/在很多情況下這樣做是效率很低的—因為問題并不決定于上一個(甚至幾個)變量的取值所以，回溯應(yīng)該倒退到導(dǎo)致失敗的變量集合中的一個變量—該集合稱為沖突集變量X的沖突集是通過約束與X相連接的先前已賦值變量的集合第2章搜索技術(shù)452.5.5關(guān)于失敗變量的啟發(fā)式在回溯算法中，當發(fā)現(xiàn)不滿足約沖突集對于地圖染色問題，設(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的沖突集中的一個變量當?shù)竭_Y時，可知回溯到哪個變量第2章搜索技術(shù)46沖突集對于地圖染色問題，設(shè)有不完全賦值{Q=red,NSW后向跳轉(zhuǎn)回溯檢驗導(dǎo)致失敗的變量的賦值—后向跳轉(zhuǎn)：回溯到?jīng)_突集中時間最近(最后賦值)的變量每個被后向跳轉(zhuǎn)剪枝的分支在前向檢驗算法中也被剪枝—簡單的后向跳轉(zhuǎn)在前向檢驗(弧相容性檢驗)搜索中是多余的因為都是做取值相容的檢測，只要在弧相容檢驗時增加一個變量集合記錄即可第2章搜索技術(shù)47后向跳轉(zhuǎn)回溯檢驗導(dǎo)致失敗的變量的賦值—后向跳轉(zhuǎn)：回溯到?jīng)_突集沖突指導(dǎo)的后向跳轉(zhuǎn)變量的沖突集更一般的情況—前面的變量集合中全部變量(不是其中一個變量)使得當前變量與之沖突沖突指導(dǎo)的后向跳轉(zhuǎn)處理令Xj是當前變量，conf(Xj)是其沖突集，如果Xj每個可能取值都失敗了，則后向跳轉(zhuǎn)到conf(Xj)中最近的一個變量Xi令conf(Xi)=conf(Xi)conf(Xj)-{Xi}從Xi向前是無解的/從Xi回到某個以前的變量賦值(參考p116例子)第2章搜索技術(shù)48沖突指導(dǎo)的后向跳轉(zhuǎn)變量的沖突集更一般的情況—前面的變量集合中2.6博弈搜索

2.6.1極大極小決策

2.6.2-剪枝第2章搜索技術(shù)492.6博弈搜索

2.6.1極大極小決策

2.6.2博弈搜索問題與方法從智能體角度看，博弈是多智能體之間的競爭和對抗/在競爭的環(huán)境中，每個智能體的目的是沖突的，由此引出對抗搜索問題—稱為博弈本節(jié)探討兩個問題—如何搜索到取勝的路徑/如何提高搜索效率相應(yīng)的方法—最優(yōu)策略(極大極小決策)/-剪枝第2章搜索技術(shù)50博弈搜索問題與方法從智能體角度看，博弈是多智能體之間的競爭和博弈游戲的描述兩個游戲者的博弈可以定義為一類搜索問題，其中包括：初始狀態(tài)—棋盤局面和哪個游戲者出招后繼函數(shù)—返回(招數(shù),狀態(tài))對的一個列表，其中每對表示一個合法招數(shù)和相應(yīng)的結(jié)果狀態(tài)終止測試—判斷游戲是否結(jié)束效用函數(shù)—或稱目標函數(shù)，對終止狀態(tài)給出一個數(shù)值如輸贏和平局(以-1/+1/0表示)雙方的初始狀態(tài)和合法招數(shù)定義了游戲的博弈樹—此為博弈搜索第2章搜索技術(shù)51博弈游戲的描述兩個游戲者的博弈可以定義為一類搜索問題，其中包井字棋的博弈樹第2章搜索技術(shù)………………XXXXXXXXXXOOXXOXOXXOXXOXXOXXOOXOOXXXXOOXXOXOOX…MAX(X)MIN(O)MAX(X)MIN(O)TERMINAL效用-10+152井字棋的博弈樹第2章搜索技術(shù)………………XXXXXXXXX2.6.1極大極小決策博弈搜索中，最優(yōu)解是導(dǎo)致取勝的終止狀態(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)下MAX采取的招數(shù)，接著繼續(xù)考慮下一步應(yīng)對后的招數(shù)...第2章搜索技術(shù)532.6.1極大極小決策博弈搜索中，最優(yōu)解是導(dǎo)致取勝的終止狀極大極小值(1)假設(shè)一個兩層的博弈樹(因為即使是井字棋的博弈樹也太復(fù)雜了)，其中有MAX節(jié)點和MIN節(jié)點博弈樹中，每個單方的招數(shù)(或稱走步)是一層/雙方各走一招稱為一步(博弈樹的深度是一步的)給定一棵博弈樹，最優(yōu)策略可以通過檢查每個節(jié)點的極大極小值來決定—記為MAX-MIN(n)，所以也稱為極大極小決策第2章搜索技術(shù)54極大極小值(1)假設(shè)一個兩層的博弈樹(因為即使是井字棋的博弈極大極小值(2)如果博弈雙方都按照最優(yōu)策略進行，那么一個節(jié)點的極大極小值就是對應(yīng)狀態(tài)的效用值(對應(yīng)MAX)對于某個節(jié)點，極大極小函數(shù)如下定義MAX優(yōu)先選擇有極大值的狀態(tài)/MIN則選擇有極小值的狀態(tài)第5章搜索技術(shù)55極大極小值(2)如果博弈雙方都按照最優(yōu)策略進行，那么一個節(jié)點極大極小值(3)第2章搜索技術(shù)

31282461452ABDC3223MAXMINMAX56極大極小值(3)第2章搜索技術(shù)312極大極小值(4)圖中MAX先行，有3個后繼MIN節(jié)點，此時MAX的取值必須看MIN如何取值每個MIN節(jié)點亦有3個后繼MAX節(jié)點，假設(shè)其取值已知因為MIN節(jié)點只取其后繼節(jié)點中之最小者(讓MAX效用最小)，故B=3/C=2/D=2MAX節(jié)點取A/B/C中最大者，故A=3最后根節(jié)點A的極大極小函數(shù)值=3—引向具有最高極大極小值的后繼第2章搜索技術(shù)57極大極小值(4)圖中MAX先行，有3個后繼MIN節(jié)點，此時M極大極小值算法說明簡單的遞歸算法—按照定義計算每個后繼節(jié)點的極大極小值/搜索是從目標到初始節(jié)點的反向推導(dǎo)算法對博弈樹實行了深度優(yōu)先搜索如果博弈樹的最大深度為m，每個節(jié)點的合法招數(shù)為b，則算法的時間復(fù)雜度是O(bm)每次生成全部后繼節(jié)點的空間復(fù)雜度是O(bm)每次只生成一個后繼節(jié)點的空間復(fù)雜度是O(m)第2章搜索技術(shù)58極大極小值算法說明簡單的遞歸算法—按照定義計算每個后繼節(jié)點的極大極小值算法FunctionMAX-MIN-DECISION(state)returnsanaction

inputs:

state(currentstateingame) v←MAX-VALUE(state) returntheactioninSUCCESSORS(state)withvaluevFunctionMAX-VALUE(state)returns

autilityvalue

ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←-∞

for

a,sinSUCCESSORS(state)dov←MAX(v,MIN-VALUE(s))

return

v (a=action招數(shù))FunctionMIN-VALUE(state)returns

autilityvalue ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←+∞ for

a,sinSUCCESSORS(state)dov←MIN(v,MAX-VALUE(s)) returnv第2章搜索技術(shù)59極大極小值算法FunctionMAX-MIN-DECISI2.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ù)602.6.2-剪枝極大極小值搜索的問題是狀態(tài)數(shù)隨著棋局步博弈樹的剪枝(1)第2章搜索技術(shù)3[-∞,+∞]AB[-∞,3](a)[-∞,+∞]12AB3[-∞,3](b)61博弈樹的剪枝(1)第2章搜索技術(shù)3[-∞,+∞]AB[-博弈樹的剪枝(2)第2章搜索技術(shù)12AB[3,+∞]38[3,3](c)12ABC[3,+∞][-∞,2]382[3,3](d)62博弈樹的剪枝(2)第2章搜索技術(shù)12AB[3,+∞]38博弈樹的剪枝(3)第2章搜索技術(shù)[-∞,14]12ABDC[3,14][-∞,2]38214[3,3](e)12ABDC[3,3][-∞,2][2,2]3821452[3,3](f)63博弈樹的剪枝(3)第2章搜索技術(shù)[-∞,14]12ABDC-剪枝算法(1)在極大極小值算法基礎(chǔ)上增加了剪枝功能，即在返回值基礎(chǔ)上增加了判斷FunctionALPHA-BETA-SEARCH(state)returnsanaction

inputs:

state(currentstateingame) v←MAX-VALUE(state,-∞,+∞)

returntheactioninSUCCESSORS(state)withvaluev第2章搜索技術(shù)64-剪枝算法(1)在極大極小值算法基礎(chǔ)上增加了剪枝功能，即-剪枝算法(2)FunctionMAX-VALUE(state,,)returns

autilityvalue inputs:

state ,thevalueofthebestalternativeforMAXalongthepathtostate ,thevalueofthebestalternativeforMINalongthepathtostate ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←-∞ for

a,sinSUCCESSORS(state)do v←MAX(v,MIN-VALUE(s,,))

ifv≥

thenreturnv

←MAX(,v) returnv第2章搜索技術(shù)65-剪枝算法(2)FunctionMAX-VALUE(s-剪枝算法(3)FunctionMIN-VALUE(state,,)returns

autilityvalue inputs:

state ,thevalueofthebestalternativeforMAXalongthepathtostate thevalueofthebestalternativeforMINalongthepathtostate ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←+∞ for

a,sinSUCCESSORS(state)do v←MIN(v,MAX-VALUE(s,

,))

ifv≤

thenreturnv

←MIN(,v) returnv第2章搜索技術(shù)66-剪枝算法(3)FunctionMIN-VALUE(s-剪枝算法的說明-剪枝可以應(yīng)用樹的任何深度，許多情況下可以剪掉整個子樹/其原則是—如果在節(jié)點n的父節(jié)點或者更上層的節(jié)點有一個更好的選擇m，則在實際游戲(搜索)中永遠不會到達n=到目前為止在路徑上任意點發(fā)現(xiàn)的MAX最佳選擇=到目前為止在路徑上任意點發(fā)現(xiàn)的MIN最佳選擇-搜索不斷更新/值，當某個節(jié)點的值分別比/值更差時剪掉該節(jié)點的剩余分支第2章搜索技術(shù)67-剪枝算法的說明-剪枝可以應(yīng)用樹的任何深度，許多情況-剪枝的效率-剪枝的效率很大程度上取決于檢查后繼節(jié)點的次序—應(yīng)該先檢查那些可能最好的后繼如果能夠先檢查那些最好的后繼，則-剪枝算法只需檢查O(bd/2)個節(jié)點以決定最佳招數(shù)/極大極小值算法為O(bd)—有效分支因子b到b的平方根—效率大大提高第2章搜索技術(shù)68-剪枝的效率-剪枝的效率很大程度上取決于檢查后繼節(jié)點本章復(fù)習(xí)提示嘗試使用搜索方式求解問題/注意本章的搜索算法都是通用算法，即沒有考慮具體任務(wù)的相關(guān)知識具體搜索問題的形式化表示(初始狀態(tài)/后繼函數(shù)/搜索代價等)了解各種搜索算法(包括局部搜索和博弈搜索)的思想、相關(guān)性質(zhì)和性能嘗試用啟發(fā)式搜索算法(A*算法)解決一些游戲問題約束滿足問題的相關(guān)概念第2章搜索技術(shù)69本章復(fù)習(xí)提示嘗試使用搜索方式求解問題/注意本章的搜索算法參考書目StuartRussell/PeterNorvig:AIMA第3章/第4章/第5章/第6章陸汝鈐編著:人工智能(上冊)第5章/第6章/第8章/第9章田盛豐、黃厚寬，人工智能與知識工程，中國鐵道出版社，1999年8月第1版，第4章/第9章第2章搜索技術(shù)70參考書目StuartRussell/PeterNor附錄

A*算法可采納性的證明第2章搜索技術(shù)71附錄

A*算法可采納性的證明第2章搜索技術(shù)71A*算法可采納性定理：A*算法是可采納的，即若存在從初始節(jié)點S0到目標節(jié)點Sg的路徑，則A*算法必能結(jié)束在最佳路徑上證明的過程：首先證明A*算法必定成功結(jié)束其次證明A*算法結(jié)束時中止于最佳路徑第2章搜索技術(shù)72A*算法可采納性定理：第2章搜索技術(shù)72證明的步驟證明分為三步：(1)對于有限圖，A*算法一定成功結(jié)束(2)對于無限圖，A*算法一定成功結(jié)束(3)A*算法必定終止于最佳路徑上對于無限圖情況的證明，引入2個引理(1)如果A*算法不終止，則存在f值任意大的節(jié)點(2)A*算法結(jié)束前，仍有耗散值更小的節(jié)點待擴展第2章搜索技術(shù)73證明的步驟證明分為三步：第2章搜索技術(shù)73定理1的證明(1)定理1—對于有限圖，如果從初始節(jié)點S0到目標節(jié)點Sg有路徑存在，則A*算法一定成功結(jié)束證明：首先證明算法必定會結(jié)束由于搜索圖為有限圖，如果算法能找到解，則會成功結(jié)束；如果算法找不到解，則必然會由于Open表變空而結(jié)束。因此，A*算法必然會結(jié)束第2章搜索技術(shù)74定理1的證明(1)定理1—對于有限圖，如果從初始節(jié)點S0到目定理1的證明(2)然后證明算法一定會成功結(jié)束由于至少存在一條由初始節(jié)點到目標節(jié)點的路徑，設(shè)此路徑為S0=n0，n1

，…，nk=Sg算法開始時，節(jié)點n0在Open表中，而且路徑中任一節(jié)點ni離開Open表后，其后繼節(jié)點ni+1必然進入Open表，這樣，在Open表變?yōu)榭罩?，目標?jié)點必然出現(xiàn)在Open表中/因此，算法必定會成功結(jié)束 ★第2章搜索技術(shù)75定理1的證明(2)然后證明算法一定會成功結(jié)束第2章搜索技術(shù)引理1的證明(1)引理1—對無限圖，如果從初始節(jié)點S0到目標節(jié)點Sg有路徑存在，且A*算法不終止的話，則從Open表中選出的節(jié)點必將具有任意大的f值證明：設(shè)d*(n)是A*算法生成的從初始節(jié)點S0到節(jié)點n的最短路徑長度，由于搜索圖中每條邊的代價都是一個正數(shù)，令這些正數(shù)中最小的一個數(shù)是e,則有第2章搜索技術(shù)76引理1的證明(1)引理1—對無限圖，如果從初始節(jié)點S0到目標引理1的證明(2)因為是最佳路徑的代價，故有又因為h(n)≥0，故有如果A*算法不終止的話，從Open表中選出的節(jié)點必將具有任意大的d*(n)值，因此，也將具有任意大的f值 ★第2章搜索技術(shù)77引理1的證明(2)因為是最佳路徑的代價，故有第2章搜索技術(shù)引理2的證明(1)引理2—在A*算法終止前的任何時刻，Open表中總存在節(jié)點n’，它是從初始節(jié)點S0到目標節(jié)點的最佳路徑上的一個節(jié)點，且滿足證明：設(shè)從初始節(jié)點S0到目標節(jié)點t的最佳路徑序列為S0=n0，n1，…，nk=Sg算法開始時，節(jié)點S0在Open表中，當節(jié)點S0離開Open進入Closed表時，節(jié)點n1進入Open表第2章搜索技術(shù)78引理2的證明(1)引理2—在A*算法終止前的任何時刻，Ope引理2的證明(2)因此，A*沒有結(jié)束以前，在Open表中必存在最佳路徑上的節(jié)點 設(shè)這些節(jié)點排在最前面的節(jié)點為n’,則有 f(n’)=g(n’)+h(n’)由于n’在最佳路徑上，故有g(shù)(n’)=g*(n’),從而f(n’)=g*(n’)+h(n’)又由于A*算法滿足h(n’)≤h*(n’),故有f(n’)≤g*(n’)+h*(n’)=f*(n’)因為在最佳路徑上的所有節(jié)點的f*值都應(yīng)相等，因此有f(n’)≤f*(S0) ★第2章搜索技術(shù)79引理2的證明(2)因此，A*沒有結(jié)束以前，在Open表中必存定理2的證明定理2—對于無限圖，如果從初始節(jié)點S0到目標節(jié)點Sg有路徑存在，則A*算法必然會結(jié)束證明：(反證法)假設(shè)A*算法不結(jié)束，由引理1知Open表中的節(jié)點有任意大的f值，這與引理2的結(jié)論相矛盾，因此，A*算法只能成功結(jié)束 ★推論1—Open表中任一具有f(n)≤f(S0)的節(jié)點n，最終都被A*算法選作為擴展節(jié)點第2章搜索技術(shù)80定理2的證明定理2—對于無限圖，如果從初始節(jié)點S0到目標節(jié)點定理3的證明(1)定理3—A*算法是可采納的，即若存在從初始節(jié)點S0到目標節(jié)點Sg的路徑，則A*算法必能結(jié)束在最佳路徑上證明：證明過程分以下兩步進行先證明A*算法一定能夠終止在某個目標節(jié)點上—由定理1和定理2可知，無論是對有限圖還是無限圖，A*算法都能夠找到某個目標節(jié)點而結(jié)束第2章搜索技術(shù)81定理3的證明(1)定理3—A*算法是可采納的，即若存在從初始定理3的證明(2)再證明A*算法只能終止在最佳路徑上(反證法)假設(shè)A*算法未能終止在最佳路徑上，而是終止在某個目標節(jié)點Sg處，則有f(Sg)=g(Sg)>f*(S0)由引理2可知，在A*算法結(jié)束前，必有最佳路徑上的一個節(jié)點n’在Open表中且有f(n’)≤f*(S0)<f(Sg)這時，A*算法一定會選擇n’來擴展，而不可能選擇Sg，從而也不會去測試目標節(jié)點Sg，這就與假設(shè)A*算法終止在目標節(jié)點相矛盾/因此，A*算法只能終止在最佳路徑上★第2章搜索技術(shù)82定理3的證明(2)再證明A*算法只能終止在最佳路徑上(反證法推論2推論2—在A*算法中，對任何被擴展的任一節(jié)點n，都有f(n)≤f*(S0)證明：令n是由A*選作擴展的任一節(jié)點，因此n不會是目標節(jié)點，且搜索沒有結(jié)束/由引理2可知，在Open表中有滿足f(n’)≤f*(S0)的節(jié)點n’若n=n’,則有f(n)≤f*(S0)否則，算法既然選擇n擴展，那就必有f(n)≤f(n’)所以有f(n)≤f*(S0) ★第2章搜索技術(shù)83推論2推論2—在A*算法中，對任何被擴展的任一節(jié)點n，都有f人工智能原理

第2章搜索技術(shù)

（下）

84人工智能原理

第2章搜索技術(shù)

（下）1

本章內(nèi)容

2.1搜索與問題求解

2.2無信息搜索策略

2.3啟發(fā)式搜索策略

2.4局部搜索算法

2.5約束滿足問題

2.6博弈搜索

參考書目

附錄A*算法可采納性的證明第2章搜索技術(shù)85 本章內(nèi)容

2.1搜索與問題求解

2.2無信息2.4局部搜索算法

2.4.1局部搜索與最優(yōu)化

2.4.2爬山法搜索

2.4.3模擬退火搜索

2.4.4局部剪枝搜索

2.4.5遺傳算法第2章搜索技術(shù)862.4局部搜索算法

2.4.1局部搜索與最優(yōu)化

2.4局部搜索算法前面的搜索算法都是保留搜索路徑的，到達目標的路徑就是問題的解—然而許多問題中到達目標的路徑是無關(guān)緊要的與系統(tǒng)地搜索狀態(tài)空間(保留各種路徑)相對，不關(guān)心路徑的搜索算法就是局部搜索算法局部搜索從一個單獨的當前狀態(tài)出發(fā)，通常只移動到相鄰狀態(tài)典型情況下搜索的路徑不保留第2章搜索技術(shù)87局部搜索算法前面的搜索算法都是保留搜索路徑的，到達目標的路徑局部搜索算法的應(yīng)用集成電路設(shè)計工廠場地布局車間作業(yè)調(diào)度自動程序設(shè)計電信網(wǎng)絡(luò)優(yōu)化車輛尋徑文件夾管理第2章搜索技術(shù)88局部搜索算法的應(yīng)用集成電路設(shè)計第2章搜索技術(shù)52.4.1局部搜索與最優(yōu)化問題局部搜索算法的優(yōu)點：只使用很少的內(nèi)存(通常是一個常數(shù))經(jīng)常能在不適合系統(tǒng)化算法的很大或無限的狀態(tài)空間中找到合理的解最優(yōu)化問題—根據(jù)一個目標函數(shù)找到最佳狀態(tài)/只有目標函數(shù)，而不考慮(沒有)“目標測試”和“路徑耗散”局部搜索算法適用于最優(yōu)化問題第2章搜索技術(shù)892.4.1局部搜索與最優(yōu)化問題局部搜索算法的優(yōu)點：第2章狀態(tài)空間地形圖(1)第2章搜索技術(shù)山肩目標函數(shù)全局最大值局部最大值“平坦”局部最大值狀態(tài)空間當前狀態(tài)90狀態(tài)空間地形圖(1)第2章搜索技術(shù)山肩目標函數(shù)全局最大值局狀態(tài)空間地形圖(2)在狀態(tài)圖中，既有“位置”(用狀態(tài)表示)又有“高度”(用耗散值或目標函數(shù)值表示)如果高度對應(yīng)于耗散值，則目標是找到全局最小值，即圖中最低點如果高度對應(yīng)于目標函數(shù)，則目標是找到全局最大值，即圖中最高峰如果存在解，則完備的局部搜索算法能夠找到解而最優(yōu)的局部搜索算法能夠找到全局最大或最小值第2章搜索技術(shù)91狀態(tài)空間地形圖(2)在狀態(tài)圖中，既有“位置”(用狀態(tài)表示)又局部搜索算法本節(jié)簡要介紹以下4種局部搜索算法/介紹其算法思想爬山法搜索模擬退火搜索局部剪枝搜索遺傳算法從搜索的角度看遺傳算法也是搜索假設(shè)空間的一種方法(學(xué)習(xí)問題歸結(jié)為搜索問題)—生成后繼假設(shè)的方式第2章搜索技術(shù)92局部搜索算法本節(jié)簡要介紹以下4種局部搜索算法/介紹其算法2.4.2爬山法搜索爬山法(hill-climbing)—就是向值增加的方向持續(xù)移動—登高過程/如果相鄰狀態(tài)中沒有比它更高的值，則算法結(jié)束于頂峰爬山法搜索算法思想：(1)令初始狀態(tài)S0為當前狀態(tài)(2)若當前狀態(tài)已經(jīng)達標，則算法運行結(jié)束，搜索成功(3)若存在一個動作可以作用于當前狀態(tài)以產(chǎn)生一個新狀態(tài)，使新狀態(tài)的估計值優(yōu)于當前狀態(tài)的估計值，則放棄當前狀態(tài)，并令剛產(chǎn)生的新狀態(tài)為當前狀態(tài)，轉(zhuǎn)(2)(4)取當前狀態(tài)為相對最優(yōu)解，停止執(zhí)行算法第2章搜索技術(shù)932.4.2爬山法搜索爬山法(hill-climbing)—爬山法搜索的局限爬山法是一種局部貪婪搜索，不是最優(yōu)解算法(或是不完備的)/其問題是：局部極大值—比其鄰居狀態(tài)都高的頂峰，但是小于全局最大值(參照狀態(tài)空間地形圖)山脊—一系列的局部極大值高原—評價函數(shù)平坦的一塊區(qū)域(或者山肩)第2章搜索技術(shù)94爬山法搜索的局限爬山法是一種局部貪婪搜索，不是最優(yōu)解算法(或爬山法搜索的變形爬山法的變形隨機爬山法—隨機選擇下一步首選爬山法—隨機選擇直到有優(yōu)于當前節(jié)點的下一步隨機重新開始爬山法—隨機生成初始狀態(tài)，進行一系列爬山法搜索—這時算法是完備的概率接近1第2章搜索技術(shù)95爬山法搜索的變形爬山法的變形第2章搜索技術(shù)122.4.3模擬退火搜索將爬山法(停留在局部山峰)和隨機行走以某種方式結(jié)合，以同時獲得完備性和效率模擬退火的思想想象在不平的表面上如何使一個乒乓球掉到最深的裂縫中—如果只讓其在表面滾動，則它只會停留在局部極小點/如果晃動平面，可以使乒乓球彈出局部極小點/技巧是晃動足夠大使乒乓球彈出局部極小點，但又不能太大把它從全局極小點中趕出第2章搜索技術(shù)962.4.3模擬退火搜索將爬山法(停留在局部山峰)和隨機行走模擬退火的解決思路(1)思路—開始使勁晃動(先高溫加熱)然后慢慢降低搖晃的強度(逐漸降溫)[退火過程]算法的核心—移動選擇選擇隨機移動，如果評價值改善，則移動被接受，否則以某個小于1的概率接受概率按照移動評價值變壞的梯度ΔE而呈指數(shù)級下降/同時也會隨著作為控制的參數(shù)—“溫度”T的降低(數(shù)值減小)而降低接受概率=eΔE/T(注意此時ΔE

<0)第5章搜索技術(shù)97模擬退火的解決思路(1)思路—開始使勁晃動(先高溫加熱)然后模擬退火的解決思路(2)溫度T是時間的函數(shù)，按照模擬退火的思想，數(shù)值應(yīng)該逐漸減小(降溫)因為接受概率=eΔE/T且ΔE

<0，所以當溫度高時，接受概率較大(接近1)/而T越來越低時，ΔE/T變大，因而接受概率降低可以證明，如果T下降得足夠慢，則算法找到全局最優(yōu)解的概率接近1第5章搜索技術(shù)98模擬退火的解決思路(2)溫度T是時間的函數(shù)，按照模擬退火的思2.4.4局部剪枝搜索基本思想—與只從一個單獨的起始狀態(tài)出發(fā)不同，局部剪枝搜索從k個隨機生成的狀態(tài)開始，每步生成全部k個狀態(tài)的所有后繼狀態(tài)/如果其中之一是目標狀態(tài)，算法停止；否則從全部后繼狀態(tài)中選擇最佳的k個狀態(tài)繼續(xù)搜索在局部剪枝搜索過程中，有用的信息在k個并行的搜索線程之間傳遞—算法會很快放棄沒有成果的搜索而把資源放在取得最大進展的搜索上第2章搜索技術(shù)992.4.4局部剪枝搜索基本思想—與只從一個單獨的起始狀態(tài)出隨機剪枝搜索如果k個狀態(tài)缺乏多樣性，則局部剪枝搜索會受其影響，性能變差算法的變種—隨機剪枝搜索幫助緩解這一問題—隨機剪枝搜索不是選擇最好的k個后代，而是按照一定概率隨機地選擇k個后繼狀態(tài)/選擇給定后繼狀態(tài)的概率是狀態(tài)值的遞增函數(shù)類似于自然選擇過程—狀態(tài)對應(yīng)生物體，其值對應(yīng)于適應(yīng)性，后代就是后繼狀態(tài)第2章搜索技術(shù)100隨機剪枝搜索如果k個狀態(tài)缺乏多樣性，則局部剪枝搜索會受其影響2.4.5遺傳算法遺傳算法(genericalgorithm/GA)是隨機剪枝的變種—不是通過修改單一狀態(tài)而是通過把兩個父狀態(tài)結(jié)合以生成后繼狀態(tài)與剪枝搜索一樣，遺傳算法也是從k個隨機狀態(tài)開始—這k個狀態(tài)稱為種群，每個狀態(tài)稱為個體個體用有限長的字符串(通常為0/1串)表示每個狀態(tài)用其評價函數(shù)(適應(yīng)度函數(shù))給出評價值(適應(yīng)值)隨后的操作包括—選擇/雜交/變異第2章搜索技術(shù)1012.4.5遺傳算法遺傳算法(genericalgorit遺傳算法的操作選擇(或者稱繁殖)—按照一定概率隨機地選擇兩對個體進行繁殖(即生成后繼狀態(tài))雜交(或者稱交叉)—雜交點是在表示狀態(tài)的字符串中隨機選擇的一個位置，以此形成新狀態(tài)—后代是父串在雜交點上進行雜交(各取一部分)得來的變異—在新生成的串中各個位置都會按照一個獨立的小概率隨機變異第2章搜索技術(shù)102遺傳算法的操作選擇(或者稱繁殖)—按照一定概率隨機地選擇兩對遺傳算法簡要描述(1)定義問題和目標函數(shù)(2)選擇候選解作為初始種群，每個解作為個體用二進制串表示(個體相當于染色體，其中的元素相當于基因)(3)根據(jù)目標函數(shù)，對于每個個體計算適應(yīng)函數(shù)值(4)為每個個體指定一個與其適應(yīng)值成正比的被選擇概率(繁殖概率)(5)根據(jù)概率選擇個體，所選個體通過交叉/變異等操作產(chǎn)生新一代種群(6)如果找到了解或者某種限制已到，則過程結(jié)束；否則轉(zhuǎn)(3)第2章搜索技術(shù)103遺傳算法簡要描述(1)定義問題和目標函數(shù)第2章搜索技術(shù)20遺傳算法的特點遺傳算法也結(jié)合了“上山”趨勢和隨機搜索，并在并行搜索線程之間交換信息遺傳算法的主要優(yōu)勢來自于雜交數(shù)學(xué)上可以證明，如果基因編碼的位置在初始時就隨機轉(zhuǎn)換的話，雜交就沒有優(yōu)勢雜交的優(yōu)勢在于它能夠?qū)ⅹ毩l(fā)展的若干個相對固定的字符(能夠執(zhí)行有用的功能—“磚塊”)組合起來，提高了搜索的粒度所謂有用的磚塊，就是幾個結(jié)合起來可以構(gòu)造問題的解—參見書中的八皇后問題舉例第2章搜索技術(shù)104遺傳算法的特點遺傳算法也結(jié)合了“上山”趨勢和隨機搜索，并在并遺傳算法的模式遺傳算法上述特點可以用模式(schema)來解釋—模式是某些位置上的數(shù)字尚未確定的一個狀態(tài)子串能夠匹配模式的字符串稱為該模式的實例如果一個模式的實例的平均適應(yīng)值超過均值，則種群內(nèi)這個模式的實例數(shù)量會隨時間而增長遺傳算法在模式和解的有意義成分相對應(yīng)時才會工作得最好遺傳算法有很多應(yīng)用，但是在什么情況下它會達到好效果，還有很多研究要做第2章搜索技術(shù)105遺傳算法的模式遺傳算法上述特點可以用模式(schema)來解2.5約束滿足問題

2.5.1約束滿足問題的定義

2.5.2CSP的回溯搜索

2.5.3變量賦值次序的啟發(fā)式

2.5.4變量約束的啟發(fā)式

2.5.5關(guān)于失敗變量的啟發(fā)式第2章搜索技術(shù)1062.5約束滿足問題

2.5.1約束滿足問題的定義

2.2.5.1約束滿足問題的定義約束滿足問題(ConstraintSatisfyingProblem,CSP)由一個變量集合{X1~Xn}和一個約束集合{C1~Cm}定義每個變量都有一個非空可能值域Di每個約束指定了包含若干變量的一個子集內(nèi)各變量的賦值范圍CSP的一個狀態(tài)—對一些或全部變量的賦值{Xi=vi,Xj=vj,…}第2章搜索技術(shù)1072.5.1約束滿足問題的定義約束滿足問題(ConstraiCSP問題的解一個不違反任何約束的對變量的賦值稱為相容賦值或合法賦值對每個變量都進行賦值稱為完全賦值一個(一組)既是相容賦值又是完全賦值的對變量的賦值就是CSP問題的解CSP問題常常可以可視化，表示為約束圖，更直觀地顯示問題，幫助思考問題的答案第2章搜索技術(shù)108CSP問題的解一個不違反任何約束的對變量的賦值稱為相容賦值或從搜索角度看待CSP問題CSP看作搜索問題的形式化初始狀態(tài)—空賦值集合，所有變量都是未賦值的后繼函數(shù)—給未賦值的變量一個賦值，要求該賦值與先前的變量賦值不沖突目標測試—測試當前的賦值(組)是否是完全賦值路徑耗散—每步耗散均為常數(shù)(1)每個解必須為完全賦值/如果有n個變量，則解出現(xiàn)的深度為n(有限)/常使用深度優(yōu)先搜索第2章搜索技術(shù)109從搜索角度看待CSP問題CSP看作搜索問題的形式化第2章搜例1：澳大利亞地圖染色問題(1)澳大利亞地圖：用紅綠藍3色標出各省，相鄰者顏色不同第2章搜索技術(shù)西澳大利亞北領(lǐng)地南澳大利亞昆士蘭新南威爾士維多利亞塔斯馬尼亞110例1：澳大利亞地圖染色問題(1)澳大利亞地圖：用紅綠藍3色標對應(yīng)于澳大利亞地圖的約束圖,相互關(guān)聯(lián)的節(jié)點用邊連接第5章搜索技術(shù)例1：澳大利亞地圖染色問題(2)WANTSANSWQVT西澳大利亞–WA北領(lǐng)地–NT南澳大利亞–SA昆士蘭–Q新南威爾士–NSW維多利亞–V塔斯馬尼亞–T一組滿足約束的完全賦值{WA=R,NT=G,Q=R,SA=B,NSW=G,V=R,T=R}111對應(yīng)于澳大利亞地圖的約束圖,相互關(guān)聯(lián)的節(jié)點用邊連接第5章搜例2：密碼算術(shù)問題(1)算式

TWO + TWO

——————— FOUR直觀地求解此問題：F=1 如不考慮O/U有進位，則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有進位：R={0,2,4,6,8}O={5,……}R=0/O=5(有進位)/T=7/W=6/U=3解={1530|765}第2章搜索技術(shù)112例2：密碼算術(shù)問題(1)算式 TWO第2章搜各算式約束四列算式約束O+O=R+10*X1X1+W+W=U+10*X2X2+T+T=O+10*X3X3=F對應(yīng)的約束超圖如右六個變量互不相等約束可化為兩兩不等約束—二元約束第2章搜索技術(shù)例2：密碼算術(shù)問題(2)FTWUORX3X1X2約束：互不相等，兩兩不等113各算式約束四列算式約束第2章搜索技術(shù)例2：密碼算術(shù)問題(2CSP問題的分類變量—離散值域

有限值域—如地圖染色問題無限值域—如作業(yè)規(guī)劃，要使用約束語言(線性約束/非線性約束)變量—連續(xù)值域如哈勃望遠鏡實驗日程安排/線性規(guī)劃問題約束的類型一元約束—只限制一個變量的取值二元約束與2個變量相關(guān)高階約束—涉及3個或更多變量第2章搜索技術(shù)114CSP問題的分類變量—離散值域第2章搜索技術(shù)31CSP問題求解的復(fù)雜度搜索相容的完全賦值，最樸素的想法是依次取變量的賦值組合并檢查其是否滿足約束條件指數(shù)級計算量若CSP問題的任何一個變量的最大值域為d，那么可能的完全賦值數(shù)量為O(dn)有限值域CSP問題包括布爾CSP問題—其中有一些NP完全問題，如3SAT問題(命題邏輯語句的可滿足性)/最壞情況下不會指望低于指數(shù)級時間復(fù)雜性解決該問題第2章搜索技術(shù)115CSP問題求解的復(fù)雜度搜索相容的完全賦值，最樸素的想法是依次2.5.2CSP的回溯搜索CSP問題具有一個性質(zhì)：可交換性—變量賦值的順序?qū)Y(jié)果沒有影響/所有CSP搜索算法生成后繼節(jié)點時，在搜索樹每個節(jié)點上只考慮單個變量的可能賦值CSP問題的求解使用深度優(yōu)先的回溯搜索算法思想：每次給一個變量賦值，當沒有合法賦值(不滿足約束時)就要推翻前一個變量的賦值，重新給其賦值，這就是回溯第2章搜索技術(shù)1162.5.2CSP的回溯搜索CSP問題具有一個性質(zhì)：可交換性簡單回溯法生成的搜索樹澳大利亞地圖染色問題的搜索樹第2章搜索技術(shù)WA=redWA=redNT=greenWA=RedNT=blueWA=redNT=greenQ=redWA=redNT=greenQ=blueWA=greenWA=blue117簡單回溯法生成的搜索樹澳大利亞地圖染色問題的搜索樹第2章搜回溯搜索的通用算法可以改善上述無信息搜索算法的性能，這些改進是一些通用性的考慮：變量賦值的次序?qū)π阅艿挠绊憽谌舾勺兞恳呀?jīng)賦值的條件下，如果下一步賦值有多個選擇，該選擇哪一個？當前變量的賦值會對其他未賦值變量產(chǎn)生什么約束？怎樣利用這種約束以提高效率？當遇到某個失敗的變量賦值時，怎樣避免同樣的失敗？就是說找到對這種失敗起到關(guān)鍵作用的某個變量賦值第2章搜索技術(shù)118回溯搜索的通用算法可以改善上述無信息搜索算法的性能，這些改進2.5.3變量賦值次序的啟發(fā)式隨機的變量賦值排序難以產(chǎn)生高效率的搜索如：在WA=red/NT=green條件下選取SA賦值比Q要減少賦值次數(shù)(1:2)/并且一旦給定SA賦值以后，Q/NSW/V的賦值只有一個選擇因此，選擇合法取值最少的變量—或者稱為最少剩余值(MRV)啟發(fā)式，或者稱為最受約束變量/失敗優(yōu)先啟發(fā)式稱為失敗優(yōu)先啟發(fā)式是因為它可以很快找到失敗的變量，從而引起搜索的剪枝，避免更多導(dǎo)致同樣失敗的搜索第2章搜索技術(shù)1192.5.3變量賦值次序的啟發(fā)式隨機的變量賦值排序難以產(chǎn)生高MRV啟發(fā)式當有多個變量需要選擇時—優(yōu)先選擇在當前約束下取值最少的變量當賦值的變量有多個值選擇時—優(yōu)先選擇為剩余變量的賦值留下最多選擇的賦值如，WA=red/NT=green時，如果給Q賦值，則Q=blue的選擇不好，此時SA沒有一個可選擇的了如果要找出問題的所有解，則排序問題無所謂第2章搜索技術(shù)120MRV啟發(fā)式當有多個變量需要選擇時—優(yōu)先選擇在當前約束下取值度啟發(fā)式對于初始節(jié)點，選擇什么變量更合適？度啟發(fā)式—選擇涉及對其他未賦值變量的約束數(shù)量大(與其他變量關(guān)聯(lián)最多)的變量地圖染色例子中，度(SA)=5/其他均為2/3實際上，一旦選擇了SA作為初始節(jié)點，應(yīng)用度啟發(fā)式求解本問題，則可以不經(jīng)任何回溯就找到解SA=redNT=greenQ=blue

NSW=green

WA=blue

V=blue第2章搜索技術(shù)121度啟發(fā)式對于初始節(jié)點，選擇什么變量更合適？第2章搜索技術(shù)32.5.4變量約束的啟發(fā)式在搜索中盡可能早地考慮某些約束，以便減少搜索空間前向檢驗—如果X被賦值，前向檢驗就是檢查與X相連的那些變量Y，看看它們是否滿足相關(guān)約束，去掉Y中不滿足約束的賦值第2章搜索技術(shù)WANTQNSWVSARGBRGBRGBRGBRGBRGB

R

GBRGBRGBRGBGBRBGRBRGBBRBGR

B--WA=redQ=greenV=blue藍色字體為賦值結(jié)果1222.5.4變量約束的啟發(fā)式在搜索中盡可能早地考慮某些約束，前向檢驗地圖染色問題中的前向檢驗前向檢驗與MRV啟發(fā)式相結(jié)合—實際上，MRV要做的就是向前找合適的變量賦值V=blue引起矛盾，此時SA賦值為空，不滿足問題約束—算法就要立刻回溯注意這里只是檢驗一步，即和當前節(jié)點是否矛盾/至于被檢驗