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

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

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