ch5 約束滿足問題 人工智能課程 北大計算機研究所

1、第五章、約束滿足問題pCh3&4：通過搜索狀態(tài)空間求解問題l把狀態(tài)看作一個黑盒子，只能由問題特定的例行程序來訪問后繼函數(shù)、啟發(fā)函數(shù)和目標測試。p約束滿足問題：利用狀態(tài)的結(jié)構(gòu)以及通用的、而不是問題特定的啟發(fā)式來定義搜索算法。第五章、約束滿足問題p約束滿足問題（CSP）pCSP問題的回溯搜索p約束滿足問題的局部搜索p問題的結(jié)構(gòu)約束滿足問題pCSP由一個變量集合和一個約束集合組成p問題的一個狀態(tài)是由對一些或全部變量的一個賦值定義的l完全賦值：每個變量都參與的賦值p問題的解是滿足所有約束的完全賦值，或更進一步，使目標函數(shù)最大化。例子：澳大利亞地圖的染色p對每個區(qū)域染上紅、綠或藍色，使得沒有相鄰的區(qū)域顏

2、色相同。將問題形式化為CSPCSP問題的增量形式化p初始狀態(tài)p后繼函數(shù)：給任何未賦值的變量賦值（滿足約束）p目標測試p路徑耗散CSP（續(xù)）p經(jīng)常用深度優(yōu)先搜索算法求解p變量l離散或連續(xù)l值域：有限或無限p約束l線性或非線性l一元或多元：通過引入輔助變量，轉(zhuǎn)為二元約束。l絕對vs偏好第五章、約束滿足問題p約束滿足問題（CSP）pCSP問題的回溯搜索p約束滿足問題的局部搜索p問題的結(jié)構(gòu)CSP問題的回溯搜索p一次為一個變量選擇值，當沒合法值可以再賦給該變量時就回溯。一個簡單的回溯算法以遞歸深度優(yōu)先算法為模型討論p一般的回溯是無信息算法，不期望它對大型問題有效 (見課本圖5.5)p不用領(lǐng)域特定的知識而

3、用通用方法解決以下問題:l下步該給哪個變量賦值，按什么順序來嘗試它的值？l當前的變量賦值對其它未賦值的變量意味著什么？l當一條路徑失敗時，在后面的路徑中能避免同樣的失敗嗎？變量和取值順序pvarSELECT-UNASSIGNED-VARIBLE (VARIBLEcsp, assignment, csp)l選擇“合法”取值最少的變量，稱為最少剩余式（MRV）l在初始時選擇涉及對其它未賦值變量的約束數(shù)最大的變量來試圖降低未來選擇的分支因子（度啟發(fā)式）。p變量被選定后，如何決定它的取值順序？l最少約束值啟發(fā)式：優(yōu)先選擇的值是在約束圖中排除鄰居變量的可選值最少的。通過約束傳播信息p在搜索的早些時候，或

4、開始之前就考慮某些約束，從而降低搜索空間。l向前檢驗l約束傳播l處理特殊約束l智能回溯：向后看向前檢驗p只要變量X被賦值，向前檢驗考察每個通過約束和X相連的未賦值變量Y，并從Y的值域中刪除與X的取值矛盾的值。約束傳播：將一個變量的約束傳播到其它變量上p前向檢驗看得不夠遠p比前向檢驗更強的約束傳播的方法：弧相容（MAC）p弧相容算法AC-3的時間復雜度是O(n2d3)。p推廣到k相容弧相容算法AC-3k相容p如果對于任何k1個變量的相容賦值，第k個變量總能被賦予一個與前k1個變量相容的值，那么該CSP問題是k相容的。p弧相容2相容處理特殊約束：應(yīng)用專門算法p刪除約束中只有單值值域的變量，然后將這

5、些變量的取值從其余變量的值域中刪去（重復該過程）。l例子：WA=red, NSW=red，高階約束。智能回溯：向后看p對歷時回溯的改進l歷時回溯：重新訪問的是時間最近的決策點p例子：按照Q,NSW,V,T,SA,WA,NT的順序訪問節(jié)點，并且假設(shè)Q=r,NSW=g,V=b,T=rl在SA時出現(xiàn)矛盾，如何回溯？l回溯到導致失敗的變量集合中的一個變量：沖突集p提前發(fā)現(xiàn)失敗HWp5.2,5.6第五章、約束滿足問題p約束滿足問題（CSP）pCSP問題的回溯搜索p約束滿足問題的局部搜索p問題的結(jié)構(gòu)基本思想p完全狀態(tài)的形式化p初始狀態(tài)給每個變量賦值，后繼函數(shù)一次改變一個變量的取值。p在為變量選擇新值時，可

6、能的啟發(fā)式函數(shù)：l導致與其它變量的沖突最小的值一個用局部搜索解決CSP問題的Min-conflicts算法function MIN-CONFLICTS(csp, max_steps) return solution or failureinputs: csp, a constraint satisfaction problemmax_steps, the number of steps allowed before giving upcurrent an initial complete assignment for cspfor i = 1 to max_steps doif current

7、 is a solution for csp then return currentvar a randomly chosen, conflicted variable from VARIABLEScspvalue the value v for var that minimizes CONFLICTS(var,v,current,csp)set var = value in currentreturn faiilureSource：Tom Lenaerts course slides用最小沖突算法解決八皇后問題的一個兩步的解。每步選擇一個皇后，在它所在的列中重新分配位置。算法將皇后移到最小沖

8、突的方格中。例子：八皇后問題局部搜索算法的表現(xiàn)pMiniconflict算法對許多CSP都驚人地有效，尤其在給定了合理的初始狀態(tài)下。l例如八皇后問題，如果不計算皇后的初始狀態(tài)，算法的運行時間大體上獨立于問題的大小。p局部搜索算法的另一個優(yōu)勢是當問題改變時可用于聯(lián)機設(shè)置l在調(diào)度問題中尤其重要第五章、約束滿足問題p約束滿足問題（CSP）pCSP問題的回溯搜索p約束滿足問題的局部搜索p問題的結(jié)構(gòu)問題的結(jié)構(gòu)：利用來找到問題的解p假設(shè)一個CSP問題的變量個數(shù)為n，所有變量的值域大小d，則問題的可能的完全賦值的數(shù)量為O(dn)。p將約束圖分解為連通分支的并集以降低問題的復雜度l例子：澳大利亞地圖中Tasm

9、ania與大陸不相連p然而，完全獨立的子問題很少見。p考慮約束圖是樹的情景，即任何兩個變量最多通過一條路徑連通。樹狀結(jié)構(gòu)的CSP問題的求解p任選一個節(jié)點作為根節(jié)點，從根節(jié)點到葉節(jié)點按順序排列，每個節(jié)點的父節(jié)點都在它前面。按順序把它們標為X1，Xn。p令j從n到2，在弧(Xi, Xj)上應(yīng)用弧相容算法，其中Xi是Xj的父節(jié)點，從DOMAINXi中刪除必要的值。p令j從1到n，賦給Xj與Xi的值相容的值。l賦值不需要回溯被刪掉的值不會危及已處理過的弧的相容性將一般的約束圖簡化為樹形式p基于刪除節(jié)點的p基于合并節(jié)點的基于刪除節(jié)點的p先對某些變量賦值，使剩下的變量構(gòu)成一棵樹。p例子：澳大利亞的約束圖，

10、給SA賦值，并從其它變量的值域中刪去與該值不相容的值。一般算法p從VARIABLEScsp中選澤一個子集S，使得約束圖在刪除S之后成為一顆樹。S稱為環(huán)割集。p對于滿足S所有約束條件的S中變量的每個可能的賦值，l從剩余變量的值域中刪除與S的賦值不相容的值，并且l如果去掉S后的剩余CSP有解，把解和S的賦值一起返回。算法的時間復雜度p如果環(huán)割集的大小為c，那么總的運行時間為O(dc(n-c)d2)。p尋找最小環(huán)割集是個NP難題基于合并節(jié)點p把約束圖分解為相關(guān)聯(lián)的子問題集p獨立求解每個子問題p合并結(jié)果澳大利亞約束圖的分解一個樹分解須滿足：p每個原始問題中的變量至少在一個子問題中出現(xiàn)p如果兩個變量在原問題中由一個約束相連，那么它們至少同時出現(xiàn)在同一個子問題中（連同約束）p如果一個變量出現(xiàn)在樹中的兩個子問題中，它必須出現(xiàn)在連接這些子問題的路徑上的所有子問題里。任何給定的變量在每個子問題中必須取值相同從各個子問題的解得到全局的解p把每個子問題視為一個大