【正文】 時(shí) SA沒有一個(gè)可選擇的了 ? 如果要找出問題的所有解，則排序問題無所謂 第 2章 搜索技術(shù) 37 度啟發(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ù) 38 變量約束的啟發(fā)式 ? 在搜索中盡可能早地考慮某些約束，以便減少搜索空間 ? 前向檢驗(yàn) — 如果 X被賦值，前向檢驗(yàn)就是檢查與 X相連的那些變量 Y，看看它們是否滿足相關(guān)約束，去掉 Y中不滿足約束的賦值 第 2章 搜索技術(shù) WA NT Q NSW V SA RGB RGB RGB RGB RGB RGB R GB RGB RGB RGB GB R B G R B RGB B R B G R B WA=red Q=green V=blue 藍(lán)色字體為賦值結(jié)果 39 前向檢驗(yàn) ? 地圖染色問題中的前向檢驗(yàn) ? 前向檢驗(yàn)與 MRV啟發(fā)式相結(jié)合 —實(shí)際上，MRV要做的就是向前找合適的變量 ? 賦值 V=blue引起矛盾，此時(shí) SA賦值為空，不滿足問題約束 —算法就要立刻回溯 ? 注意這里只是檢驗(yàn)一步，即和當(dāng)前節(jié)點(diǎn)是否矛盾 / 至于被檢驗(yàn)節(jié)點(diǎn)之間的約束檢驗(yàn)還不能進(jìn)行 —改進(jìn)：約束傳播 第 2章 搜索技術(shù) 40 約束傳播 — 弧相容 ? 約束傳播 — 將一個(gè)變量的約束內(nèi)容傳播到其他變量 ? 希望約束傳播檢驗(yàn)更多的變量 / 花費(fèi)的代價(jià)更少 — 快速 ? 弧相容 — 依次檢驗(yàn)約束圖中各個(gè)相關(guān)節(jié)點(diǎn)對 (這里弧是有向弧 ) ? 例如：給定 SA/NSW當(dāng)前值域，對于 SA的每個(gè)取值 x， NSW都有某個(gè) y和 x相容，則 SA到NSW的弧是相容的 / 反過來是 NSW到 SA的弧相容 第 2章 搜索技術(shù) 41 弧相容 (1) ? 在地圖染色約束的前向檢驗(yàn)圖中：第三 行SA={blue}/NSW={red,blue}，則 SA的取值有一個(gè) NSW=red與之相容 / 反過來 NSW=blue，則 SA為空值，即不相容 —通過刪除 NSW值域中的 blue可使其相容 ? 同樣，弧相容檢測也能更早地發(fā)現(xiàn)矛盾 —如第二行 SA/NT值域均為 {blue}，如必須刪去SA=blue，則發(fā)現(xiàn)不相容 ? 保持弧相容 (MAC)算法思想 —反復(fù)檢測某個(gè)變量值域中的不相容弧，進(jìn)行值刪除，直到不再有矛盾 第 2章 搜索技術(shù) 42 弧相容 (2) ? 弧相容算法思想： ? 用隊(duì)列記錄需要檢驗(yàn)不相容的弧 ? 每條弧 [Xi, Xj]依次從隊(duì)列中刪除并被檢驗(yàn)，如果任何一個(gè) Xi值域中的值需要刪除，則每個(gè)指向 Xi的弧 [Xk, Xi]都必須重新插入隊(duì)列進(jìn)行檢驗(yàn) —因?yàn)橹赶蜻@個(gè)變量的弧可能產(chǎn)生新的不相容 (因?yàn)樵瓉砜赡芫褪且驗(yàn)檫@個(gè)值產(chǎn)生了它們之間的相容 ) ? 時(shí)間復(fù)雜度 —二元 CSP約束至多有 O(n2)條弧 / 每條弧至多插入隊(duì)列 d次 (d個(gè)取值 )，檢驗(yàn)一條弧為 O(d2) /算法最壞情況下為 O(n2d2) 第 2章 搜索技術(shù) 43 特殊約束 ? 實(shí)際問題中出現(xiàn)的特殊約束，其效率要比通用的約束高很多 ? 變量取值各不相同 —AllDiff，如果約束涉及m個(gè)變量，所有變量共有 n個(gè)取值，如果 mn則此約束不能被滿足 ? 相應(yīng)算法 —刪除約束中只有單值值域的變量，將其取值從其余變量值域中刪去；對單值變量重復(fù)此過程；如果得到空值域或剩下的變量數(shù)大于取值數(shù)，則產(chǎn)生矛盾 ? 其他約束 —資源約束 /邊界約束 第 2章 搜索技術(shù) 44 關(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 沖突集 ? 對于地圖染色問題，設(shè)有不完全賦值{Q=red, NSW=green, V=blue, T=red} / 此時(shí)， SA賦值將發(fā)現(xiàn)不滿足任何約束 —SA的沖突集 ={Q, NSW, V} ? 對于前向檢驗(yàn)算法，可以很容易得到?jīng)_突集 ? 基于 X賦值的前向檢驗(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測，只要在弧相容檢驗(yàn)時(shí)增加一個(gè)變量集合記錄即可 第 2章 搜索技術(shù) 47 沖突指導(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向前是無解的 / 從 Xi回到某個(gè)以前的變量賦值 (參考 p116例子 ) 第 2章 搜索技術(shù) 48 博弈搜索 極大極小決策 ??剪枝 第 2章 搜索技術(shù) 49 博弈搜索問題與方法 ? 從智能體角度看，博弈是多智能體之間的競爭和對抗 / 在競爭的環(huán)境中，每個(gè)智能體的目的是沖突的，由此引出對抗搜索問題 — 稱為博弈 ? 本節(jié)探討兩個(gè)問題 — 如何搜索到取勝的路徑 / 如何提高搜索效率 ? 相應(yīng)的方法 — 最優(yōu)策略 (極大極小決策 )/??剪枝 第 2章 搜索技術(shù) 50 博弈游戲的描述 ? 兩個(gè)游戲者的博弈可以定義為一類搜索問題，其中包括： ? 初始狀態(tài) — 棋盤局面和哪個(gè)游戲者出招 ? 后繼函數(shù) — 返回 (招數(shù) ,狀態(tài) )對的一個(gè)列表，其中每對表示一個(gè)合法招數(shù)和相應(yīng)的結(jié)果狀態(tài) ? 終止測試 — 判斷游戲是否結(jié)束 ? 效用函數(shù) — 或稱目標(biāo)函數(shù)，對終止?fàn)顟B(tài)給出一個(gè)數(shù)值如輸贏和平局 (以 1/+1/0表示 ) ? 雙方的初始狀態(tài)和合法招數(shù)定義了游戲的博弈樹 — 此為博弈搜索 第 2章 搜索技術(shù) 51 井字棋的博弈樹 第 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 52 極大極小決策 ? 博弈搜索中，最優(yōu)解是導(dǎo)致取勝的終止?fàn)顟B(tài)的一系列招數(shù) ? 在井字棋搜索樹中， 因?yàn)?MAX先行，所以 MAX的任務(wù)是利用搜索樹確定最佳招數(shù) / 但是另一方 MIN也有發(fā)言權(quán) ? 因此 MAX制定取勝策略時(shí)必須不斷地考