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

第五章、約束滿足問題Ch3&4：通過搜索狀態(tài)空間求解問題把狀態(tài)看作一個黑盒子，只能由問題特定的例行程序來訪問—后繼函數、啟發(fā)函數和目標測試。約束滿足問題：利用狀態(tài)的結構以及通用的、而不是問題特定的啟發(fā)式來定義搜索算法。第五章、約束滿足問題約束滿足問題（CSP）CSP問題的回溯搜索約束滿足問題的局部搜索問題的結構約束滿足問題CSP由一個變量集合和一個約束集合組成問題的一個狀態(tài)是由對一些或全部變量的一個賦值定義的完全賦值：每個變量都參與的賦值問題的解是滿足所有約束的完全賦值，或更進一步，使目標函數最大化。將問題形式化為CSPCSP問題的增量形式化初始狀態(tài)后繼函數：給任何未賦值的變量賦值（滿足約束）目標測試路徑耗散CSP（續(xù)）經常用深度優(yōu)先搜索算法求解變量離散或連續(xù)值域：有限或無限約束線性或非線性一元或多元：通過引入輔助變量，轉為二元約束。絕對vs偏好第五章、約束滿足問題約束滿足問題（CSP）CSP問題的回溯搜索約束滿足問題的局部搜索問題的結構一個簡單的回溯算法以遞歸深度優(yōu)先算法為模型變量和取值順序var←SELECT-UNASSIGNED-VARIBLE(VARIBLE[csp],assignment,csp)選擇“合法”取值最少的變量，稱為最少剩余式（MRV）在初始時選擇涉及對其它未賦值變量的約束數最大的變量來試圖降低未來選擇的分支因子（度啟發(fā)式）。變量被選定后，如何決定它的取值順序？最少約束值啟發(fā)式：優(yōu)先選擇的值是在約束圖中排除鄰居變量的可選值最少的。向前檢驗只要變量X被賦值，向前檢驗考察每個通過約束和X相連的未賦值變量Y，并從Y的值域中刪除與X的取值矛盾的值。約束傳播：將一個變量的約束傳播到其它變量上前向檢驗看得不夠遠比前向檢驗更強的約束傳播的方法：弧相容（MAC）弧相容算法AC-3的時間復雜度是O(n2d3)。推廣到k相容弧相容算法AC-3k相容如果對于任何k－1個變量的相容賦值，第k個變量總能被賦予一個與前k－1個變量相容的值，那么該CSP問題是k相容的。弧相容＝2相容處理特殊約束：應用專門算法刪除約束中只有單值值域的變量，然后將這些變量的取值從其余變量的值域中刪去（重復該過程）。例子：{WA=red,NSW=red}，高階約束。智能回溯：向后看對歷時回溯的改進歷時回溯：重新訪問的是時間最近的決策點例子：按照Q,NSW,V,T,SA,WA,NT的順序訪問節(jié)點，并且假設{Q=r,NSW=g,V=b,T=r}在SA時出現矛盾，如何回溯？回溯到導致失敗的變量集合中的一個變量：沖突集提前發(fā)現失敗

第五章、約束滿足問題約束滿足問題（CSP）CSP問題的回溯搜索約束滿足問題的局部搜索問題的結構基本思想完全狀態(tài)的形式化初始狀態(tài)給每個變量賦值，后繼函數一次改變一個變量的取值。在為變量選擇新值時，可能的啟發(fā)式函數：導致與其它變量的沖突最小的值用最小沖突算法解決八皇后問題的一個兩步的解。每步選擇一個皇后，在它所在的列中重新分配位置。算法將皇后移到最小沖突的方格中。例子：八皇后問題第五章、約束滿足問題約束滿足問題（CSP）CSP問題的回溯搜索約束滿足問題的局部搜索問題的結構問題的結構：利用來找到問題的解假設一個CSP問題的變量個數為n，所有變量的值域大小d，則問題的可能的完全賦值的數量為O(dn)。將約束圖分解為連通分支的并集以降低問題的復雜度例子：澳大利亞地圖中Tasmania與大陸不相連然而，完全獨立的子問題很少見?？紤]約束圖是樹的情景，即任何兩個變量最多通過一條路徑連通。樹狀結構的CSP問題的求解任選一個節(jié)點作為根節(jié)點，從根節(jié)點到葉節(jié)點按順序排列，每個節(jié)點的父節(jié)點都在它前面。按順序把它們標為X1，，Xn。令j從n到2，在弧(Xi,Xj)上應用弧相容算法，其中Xi是Xj的父節(jié)點，從DOMAIN[Xi]中刪除必要的值。令j從1到n，賦給Xj與Xi的值相容的值。賦值不需要回溯被刪掉的值不會危及已處理過的弧的相容性基于刪除節(jié)點的先對某些變量賦值，使剩下的變量構成一棵樹。例子：澳大利亞的約束圖，給SA賦值，并從其它變量的值域中刪去與該值不相容的值。一般算法從VARIABLES[csp]中選澤一個子集S，使得約束圖在刪除S之后成為一顆樹。S稱為環(huán)割集。對于滿足S所有約束條件的S中變量的每個可能的賦值，從剩余變量的值域中刪除與S的賦值不相容的值，并且如果去掉S后的剩余CSP有解，把解和S的賦值一起返回。算法的時間復雜度如果環(huán)割集的大小為c，那么總的運行時間為O(dc(n-c)d2)。尋找最小環(huán)割集是個NP難題基于合并節(jié)點把約束圖分解為相關聯(lián)的子問題集獨立求解每個子問題合并結果澳大利亞約束圖的分解一個樹分解須滿足：每個原始問題中的變量至少在一個子問題中出現如果兩個變量在原問題中由一個約束相連，那么它們至少同時出現在同一個子問題中（連同約束）如果一個變量出現在樹中的兩個子問題中，它必須出現在連接這些子問題的路徑上的所有子問題里。任何給定的變量在每個子問題中必須取值相同從各個子問題的解得到全局的解把每個子問題視為一個大變量，它的值域是問題所有可能的解的集合。例如：上圖最左邊的子問題的值域大小為6?？偨Y約束