【文章內(nèi)容簡介】 為最受約束變量 /失敗優(yōu)先啟發(fā)式 ? 稱為失敗優(yōu)先啟發(fā)式是因為它可以很快找到失敗的變量，從而引起搜索的剪枝，避免更多導(dǎo)致同樣失敗的搜索 第 2章 搜索技術(shù) 38 MRV啟發(fā)式 ? 當(dāng)有多個變量需要選擇時 — 優(yōu)先選擇在當(dāng)前約束下取值最少的變量 ? 當(dāng)賦值的變量有多個值選擇時 — 優(yōu)先選擇為剩余變量的賦值留下最多選擇的賦值 ? 如， WA=red/NT=green時，如果給 Q賦值，則 Q=blue的選擇不好，此時 SA沒有一個可選擇的了 ? 如果要找出問題的所有解，則排序問題無所謂 第 2章 搜索技術(shù) 39 度啟發(fā)式 ? 對于初始節(jié)點(diǎn)，選擇什么變量更合適？ ? 度啟發(fā)式 — 選擇涉及對其他未賦值變量的約束數(shù)量大 (與其他變量關(guān)聯(lián)最多 )的變量 ? 地圖染色例子中，度 (SA)=5 / 其他均為 2/3 ? 實際上，一旦選擇了 SA作為初始節(jié)點(diǎn)，應(yīng)用度啟發(fā)式求解本問題，則可以不經(jīng)任何回溯就找到解 ? SA=red ? NT=green ? Q=blue ? NSW=green ? WA=blue ? V=blue 第 2章 搜索技術(shù) 40 約束傳播 ? 檢查當(dāng)前的變量賦值組合是否會對尚未賦值的變量產(chǎn)生新約束 — 要盡早地檢查一些約束，使得一旦發(fā)現(xiàn)某些賦值不滿足這樣的約束，就及早地刪除這些對變量的賦值，從而減少搜索空間 ? 假設(shè) CSP中所有的約束都是二元約束（多元約束均可以轉(zhuǎn)化為二元約束），則 CSP可以表示為一個只含有二元約束的圖，這些二元約束就是圖中兩個節(jié)點(diǎn)之間的弧 ? 因此，不斷刪除那些不被滿足的約束就是不斷刪除圖中的不相容弧 —稱為弧相容（ arc consistency）技術(shù) 第 2章 搜索技術(shù) 41 相容的概念（ 1） ? K相容（ Kconsistency）：一個 CSP問題，對于其中任意 K1個變量的每一組取值，如果它們滿足這些變量之間的所有約束，則對任意第K個變量，存在一個值，使得 K個變量之間的所有約束均被滿足 —此時該 CSP稱為 K相容的 ? 弧相容（ arc consistency，簡寫為 AC）或 2相容：如果對于變量 X的任意賦值 v(x)，和該變量有約束關(guān)系的某個變量 Y總有一個賦值 v(y)與其相容，則稱 Y是與 X弧相容的（或者 2相容） 第 2章 搜索技術(shù) 42 相容的概念（ 2） ? 弧相容是有方向的， Y與 X弧相容，并不等于 X與 Y弧相容，即反過來不一定成立 / 也就是說，對于變量 Y的任意賦值，變量 X不一定總有一個賦值與其相容 ? 對于一個具有 N個節(jié)點(diǎn)的 CSP約束圖來說，獲得 N相容的算法的復(fù)雜性是指數(shù)級的 ? 一個 CSP約束圖是強(qiáng) K相容的，如果對于所有都是 J相容的 第 2章 搜索技術(shù) 43 約束傳播與前向檢驗 ? 將相容的思想應(yīng)用于 CSP回溯搜索，就產(chǎn)生了約束傳播（ constraint propagation）的方法 ? 其中最簡單的方法是把弧相容的概念應(yīng)用于搜索基本算法，構(gòu)成前向檢驗（ forward checking）方法 第 2章 搜索技術(shù) 44 前向檢驗 ? 前向檢驗原理：每次給一個變量賦值（不妨稱為當(dāng)前變量和當(dāng)前賦值）時，所有與該變量連接（或者稱為相鄰，即有約束關(guān)系）的其他變量都進(jìn)行約束檢查，那些與當(dāng)前約束沖突的變量取值均被暫時刪除 / 如果此時某個其他變量的值域為空，則當(dāng)前賦值必須改變，要選擇其他賦值。如果當(dāng)前變量沒有賦值可選，則說明上一層的賦值是不滿足約束的，必須回溯，那些被臨時刪除的變量賦值全部恢復(fù) ? 以這樣的方式，前向檢驗可以預(yù)測哪些賦值會導(dǎo)致失敗，從而將其剪枝 ? 這種預(yù)測來得越早，則可以減少越多的搜索空間 / 前向檢驗通常和 MRV啟發(fā)式一起使用 第 2章 搜索技術(shù) 45 約束傳播 ? 如果前向檢驗不止向前看一個相鄰變量，而且看相鄰變量的相鄰變量，直至遍歷全部變量以檢查它們之間的弧相容關(guān)系 — 部分向前看 /完全向前看 ? 約束傳播 —將一個變量的約束內(nèi)容傳播到其他變量 ? 不斷檢驗變量之間的約束并將其作用于更大范圍，故稱為約束傳播 第 2章 搜索技術(shù) 46 前向檢驗例子 第 2章 搜索技術(shù) 4皇后問題 47 智能回溯 ? 在回溯算法中，當(dāng)發(fā)現(xiàn)不滿足約束即搜索失敗時，則回到上一個變量并嘗試下一個取值 — 稱為歷時回溯 / 在很多情況下這樣做是效率很低的 — 因為問題并不決定于上一個 (甚至幾個 )變量的取值 ? 所以，回溯應(yīng)該倒退到導(dǎo)致失敗的變量集合中的一個變量（沖突集） — 稱為后向跳轉(zhuǎn)方法 ? 沖突集引導(dǎo)的后向跳轉(zhuǎn)（回跳） — 智能回溯 第 2章 搜索技術(shù) 48 沖突集 ? 變量 X的沖突集：當(dāng)變量 X的賦值集合為空時，那些通過約束與 X相連的先前已賦值的變量就構(gòu)成了 X的沖突集 ? 基于沖突集的回跳方法：設(shè)變量 是當(dāng)前失敗變量， 是其父節(jié)點(diǎn)， 是 的沖突集 ? 從 開始回跳，回跳至 中離最近的節(jié)點(diǎn) （除去 ）；設(shè)置 的沖突集為： ? 在新沖突集中選擇一個變量作為回跳點(diǎn)變量，進(jìn)行重新賦值 第 2章 搜索技術(shù) jXk )( jXconfjXk )( jXconfjXiX kX i }{)()()( ijii XXconfXconfXconf ???49 沖突集指導(dǎo)的后向跳轉(zhuǎn) — 例子 ? 對于澳大利亞地圖染色問題中的各變量，假設(shè)賦值次序是： ? {WA=red, NSW=red} → {NT}→ {Q} → {SA} ? 則因為 WA和 NSW不能為相同顏色，而導(dǎo)致 SA失敗 / SA是失敗變量，離 SA最近的沖突集中的變量是 Q，于是從 Q回溯，得到各變量的沖突集如下： 第 2章 搜索技術(shù) 50 沖突集指導(dǎo)的后向跳轉(zhuǎn) — 例子 ? 由此可跳至回跳點(diǎn) ——變量 NSW，重新賦值后可不產(chǎn)生沖突 第 2章 搜索技術(shù) },{}{}{},{}{)()()(,},{)(NSWWANTWANTNSWWANTNTconfSAconfNTconfQNTQNTQNSWWASAconf???????? 去掉返回到從51 博弈搜索 極大極小決策 ??剪枝 第 2章 搜索技術(shù) 52 博弈搜索問題與方法 ? 從智能體角度看，博弈是多智能體之間的競爭和對抗 / 在競爭的環(huán)境中，每個智能體的目的是沖突的，由此引出對抗搜索問題 — 稱為博弈 ? 本節(jié)探討兩個問題 — 如何搜索到取勝的路徑 / 如何提高搜索效率 ? 相應(yīng)的方法 — 最優(yōu)策略 (極大極小決策 )/??剪枝 第 2章 搜索技術(shù) 53 博弈游戲的描述 ? 兩個游戲者的博弈可以定義為一類搜索問題，其中包括： ? 初始狀態(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ù) 54 井字棋的博弈樹 第 2章 搜索技術(shù) … … … … … … X X X X X X X X X X O O X X O X O X X O X X O X X O X X O O X O O X X X X O O X X O X O O X … MAX(X) MIN(O) MAX(X) MIN(O) TERMINAL 效用 1 0 +1 55 極大極小決策 ? 博弈搜索中，最優(yōu)解是導(dǎo)致取勝的終