第6章 約束滿足問題

1、第第6章章 約束滿足問題約束滿足問題中國科大中國科大 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院第第部分部分 問題求解問題求解本章內(nèi)容本章內(nèi)容 6.1 約束滿足問題約束滿足問題 6.2 約束傳播：約束傳播：csp中的推理中的推理 6.3 csp的回溯搜索的回溯搜索 6.4 csp的局部搜索的局部搜索 6.5 問題的結(jié)構(gòu)問題的結(jié)構(gòu)例例1、澳大利亞地圖染色問題、澳大利亞地圖染色問題(1) 澳大利亞地圖染色問題：用澳大利亞地圖染色問題：用紅紅綠綠藍(lán)藍(lán)3色標(biāo)出各省，色標(biāo)出各省，相鄰者顏色不同。相鄰者顏色不同。塔斯馬尼亞西澳大利亞北領(lǐng)地南澳大利亞昆士蘭新南威爾士維多利亞 對應(yīng)于澳大利亞地圖的對應(yīng)于澳大利亞地圖的約束圖約束圖，

2、相互關(guān)聯(lián)的節(jié)點(diǎn)，相互關(guān)聯(lián)的節(jié)點(diǎn)用邊連接。用邊連接。wantsanswqvt 西澳大利亞西澳大利亞 wa wa 北領(lǐng)地北領(lǐng)地 nt nt 南澳大利亞南澳大利亞 sa sa 昆士蘭昆士蘭 q q 新南威爾士新南威爾士 nsw nsw 維多利亞維多利亞 v v 塔斯馬尼亞塔斯馬尼亞 t t例例1、澳大利亞地圖染色問題、澳大利亞地圖染色問題(2) 一組滿足約束的完全賦值：一組滿足約束的完全賦值： wa=r, nt=g, q=r, sa=b, nsw=g, v=r, t=r 約束滿足問題的定義約束滿足問題的定義 約束滿足問題約束滿足問題（constraint satisfying problem, cs

3、p）：）： 由一個(gè)變量集合由一個(gè)變量集合x1xn和一個(gè)約束集合和一個(gè)約束集合c1cm定義；定義；每個(gè)變量都有一個(gè)非空可能值域每個(gè)變量都有一個(gè)非空可能值域d di i；每個(gè)約束指定了包含若干變量的一個(gè)子集內(nèi)各變量的賦值每個(gè)約束指定了包含若干變量的一個(gè)子集內(nèi)各變量的賦值范圍。范圍。 例如：例如：地圖染色問題，地圖染色問題，n-n-皇后問題?；屎髥栴}。 csp的一個(gè)狀態(tài)的一個(gè)狀態(tài)：對一些或全部變量的賦值：對一些或全部變量的賦值 xi=vi, xj=vj, 。csp問題的解問題的解 一個(gè)不違反任何約束的對變量的賦值稱為一個(gè)不違反任何約束的對變量的賦值稱為相容賦值相容賦值或合法賦值或合法賦值。 對每個(gè)變

4、量都進(jìn)行賦值稱為對每個(gè)變量都進(jìn)行賦值稱為完全賦值完全賦值。 一個(gè)一個(gè)（一組）（一組）對變量的賦值，若既是相容賦值又是對變量的賦值，若既是相容賦值又是完全賦值，則這個(gè)（組）賦值是完全賦值，則這個(gè)（組）賦值是csp問題的解問題的解。 某些某些csp問題要求問題的解能使目標(biāo)函數(shù)最大問題要求問題的解能使目標(biāo)函數(shù)最大化化約束優(yōu)化約束優(yōu)化。 csp問題常?？梢钥梢暬?，表示為問題常?？梢钥梢暬?，表示為約束圖約束圖，更直觀，更直觀地顯示問題，幫助思考問題的答案。地顯示問題，幫助思考問題的答案。csp問題的分類問題的分類 根據(jù)變量的類型劃分：根據(jù)變量的類型劃分：離散值域離散值域和和連續(xù)值域連續(xù)值域。 變量變量離

5、散值域離散值域 有限值域有限值域，如地圖染色問題，八皇后問題。，如地圖染色問題，八皇后問題。無限值域無限值域，如整數(shù)集合或者字符串集合。，如整數(shù)集合或者字符串集合。 例如，對于作業(yè)規(guī)劃問題，無法枚舉所有可能取值，要例如，對于作業(yè)規(guī)劃問題，無法枚舉所有可能取值，要使用使用約束語言約束語言( (線性約束線性約束/ /非線性約束非線性約束) )描述，如描述，如startjobstartjob1 1+5stratjob+5stratjob3 3。 有限值域有限值域csp問題包括問題包括布爾布爾csp問題，它的變量的取值可以是問題，它的變量的取值可以是true或或false。 布爾布爾csp包括一些包括

6、一些典型典型np完全問題完全問題，如，如3-sat問題（命題問題（命題邏輯語句的可滿足性問題），邏輯語句的可滿足性問題），最壞情況下最壞情況下不能指望低于指不能指望低于指數(shù)級時(shí)間復(fù)雜性解決該問題。數(shù)級時(shí)間復(fù)雜性解決該問題。csp問題的分類問題的分類 變量變量連續(xù)值域連續(xù)值域 最著名的連續(xù)值域最著名的連續(xù)值域cspcsp是是線性規(guī)劃線性規(guī)劃問題。問題。線性規(guī)劃線性規(guī)劃中的約束必須是構(gòu)成一個(gè)凸多邊形的中的約束必須是構(gòu)成一個(gè)凸多邊形的一組線性不等式。一組線性不等式。線性規(guī)劃問題可以在變量個(gè)數(shù)的多項(xiàng)式時(shí)間內(nèi)線性規(guī)劃問題可以在變量個(gè)數(shù)的多項(xiàng)式時(shí)間內(nèi)求解。求解。csp問題的分類問題的分類 根據(jù)約束的類型劃

7、分：根據(jù)約束的類型劃分： 線性線性或或非線性約束非線性約束。 一元一元或或多元約束多元約束。 一元約束：只限制一個(gè)變量的取值一元約束：只限制一個(gè)變量的取值 二元約束與二元約束與2 2個(gè)變量相關(guān)個(gè)變量相關(guān) 高階約束：涉及高階約束：涉及3 3個(gè)或更多變量。個(gè)或更多變量。通過引入輔助變量，轉(zhuǎn)為二元約束。通過引入輔助變量，轉(zhuǎn)為二元約束。 絕對絕對約束約束 vs 偏好約束偏好約束。 我們僅討論絕對約束。我們僅討論絕對約束。高階約束的例子高階約束的例子 算式算式t w o+t w o f o u r例例2、密碼算術(shù)問題。、密碼算術(shù)問題。每個(gè)字母表示不同的數(shù)字。目標(biāo)是找到每個(gè)字母表示不同的數(shù)字。目標(biāo)是找到能

8、使如下加法式子成立的數(shù)字，附加的約束條件是最前面的數(shù)能使如下加法式子成立的數(shù)字，附加的約束條件是最前面的數(shù)字不能為字不能為0。高階約束的例子高階約束的例子 算式算式t w o+t w o f o u r f=1。 如不考慮如不考慮o/u有進(jìn)位：有進(jìn)位： r/u/o均為偶數(shù)，均為偶數(shù)，r=4, 6, 8，o=2?, 3?, 4!。 r=8/o=4，則，則t=7（由（由o/r/u/w共同限制）。共同限制）。 t=7，則，則u=6/w=3，由此得到一組解，由此得到一組解1468 | 734。 考慮考慮o/u有進(jìn)位：有進(jìn)位： r=0, 2, 4, 6, 8，o=5, 6, 7, 8, 9。 若若r=0

9、/o=5(有進(jìn)位有進(jìn)位)，則，則t=7/w=6/u=3，由此得，由此得到一組解到一組解=1530 | 765。 四列算式約束：四列算式約束： o+o=r+10*x1 x1+w+w=u+10*x2 x2+t+t=o+10*x3 x3=f 對應(yīng)的對應(yīng)的約束超圖約束超圖如右圖。如右圖。 六個(gè)變量互不相等約六個(gè)變量互不相等約束可化為兩兩不等約束可化為兩兩不等約束額的二元約束。束額的二元約束。高階約束的例子高階約束的例子各算式約束ftwuorx3x1x2約束：互不相等，兩兩不等每個(gè)約束在圖中用方塊表示，每個(gè)約束在圖中用方塊表示，連接至它所約束的變量。連接至它所約束的變量。csp問題求解的復(fù)雜度問題求解的

10、復(fù)雜度 csp問題的求解目標(biāo)是找到問題的求解目標(biāo)是找到相容的完全賦值相容的完全賦值，最，最樸素的想法是依次取變量的賦值組合并檢查其是樸素的想法是依次取變量的賦值組合并檢查其是否滿足約束條件。否滿足約束條件。 若若csp問題的任何一個(gè)變量的最大值域?yàn)閱栴}的任何一個(gè)變量的最大值域?yàn)閐，那，那么可能的完全賦值數(shù)量為么可能的完全賦值數(shù)量為o(dn)。 指數(shù)級指數(shù)級計(jì)算量。計(jì)算量。本章內(nèi)容本章內(nèi)容 6.1 約束滿足問題約束滿足問題 6.2 約束傳播：約束傳播：csp中的推理中的推理 6.3 csp的回溯搜索的回溯搜索 6.4 csp的局部搜索的局部搜索 6.5 問題的結(jié)構(gòu)問題的結(jié)構(gòu)約束傳播約束傳播 約束

11、傳播：約束傳播：使用約束來使用約束來減小一個(gè)變量的合法取值范減小一個(gè)變量的合法取值范圍圍，從而影響到，從而影響到與此變量有約束關(guān)系的另一變量與此變量有約束關(guān)系的另一變量的的取值。取值。 弧相容：弧相容：依次檢驗(yàn)約束圖中各個(gè)相關(guān)節(jié)點(diǎn)對依次檢驗(yàn)約束圖中各個(gè)相關(guān)節(jié)點(diǎn)對。注意，。注意，弧是有向弧?；∈怯邢蚧?。 例如，給定例如，給定sa/nsw當(dāng)前值域，如果對于當(dāng)前值域，如果對于sa的每個(gè)取值的每個(gè)取值x，nsw都有某個(gè)都有某個(gè)y和和x相容，則相容，則sa到到nsw的弧是相容的；的弧是相容的；反過來是反過來是nsw到到sa的弧相容。的弧相容。wantsanswqvt弧相容弧相容 在地圖染色約束的賦值過程

12、中：第在地圖染色約束的賦值過程中：第4行行sa=blue，nsw=red, blue，則，則sa的取值有一個(gè)的取值有一個(gè)nsw=red與之相容；反過來與之相容；反過來nsw=blue，則，則sa為空值，即不相容，為空值，即不相容，通過刪除通過刪除nsw值域中值域中的的blue可使其相容?？墒蛊湎嗳?。 弧相容檢測也能較早發(fā)現(xiàn)矛盾，如第弧相容檢測也能較早發(fā)現(xiàn)矛盾，如第4行行sa和和nt值域均為值域均為blue，則必須刪去，則必須刪去sa=blue，其值域變?yōu)榭?。，其值域變?yōu)榭铡?用弧相容能夠更早地檢測到矛盾。用弧相容能夠更早地檢測到矛盾。wantqnswvsargbrgbrgbrgbrgbrgb

13、gbrgbrgb rgb gb b r brgb bwa=redwa=redq=greenq=greenv=bluev=blue藍(lán)色字體為賦藍(lán)色字體為賦值結(jié)果值結(jié)果弧相容算法思想弧相容算法思想1. 用隊(duì)列記錄需要檢驗(yàn)不相容的弧。用隊(duì)列記錄需要檢驗(yàn)不相容的弧。2. 每條弧每條弧xi, xj依次從隊(duì)列中刪除并被檢驗(yàn)。依次從隊(duì)列中刪除并被檢驗(yàn)。如果如果xi值域中的任何一個(gè)值需要?jiǎng)h除，則每個(gè)值域中的任何一個(gè)值需要?jiǎng)h除，則每個(gè)指指向向xi的弧的弧xk, xi都必須重新插入隊(duì)列進(jìn)行檢驗(yàn)。都必須重新插入隊(duì)列進(jìn)行檢驗(yàn)。 因?yàn)橹赶蜻@個(gè)變量的弧可能產(chǎn)生新的不相容（原因?yàn)橹赶蜻@個(gè)變量的弧可能產(chǎn)生新的不相容（原來可能

14、就是因?yàn)檫@個(gè)值產(chǎn)生了它們之間的相容）。來可能就是因?yàn)檫@個(gè)值產(chǎn)生了它們之間的相容）。時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：二元二元csp約束至多有約束至多有o(n2)條??；條??； 每每條弧至多插入隊(duì)列條弧至多插入隊(duì)列d次（次（d個(gè)取值），檢驗(yàn)一條弧為個(gè)取值），檢驗(yàn)一條弧為o(d2)，因此算法的最壞情況下為，因此算法的最壞情況下為o(n2d3)?；∠嗳菟惴ɑ∠嗳菟惴╝c-31. function ac-3(csp) returns the csp, possibly with reduced domains2. inputs: csp, a binary csp with variables x1, x2, .

15、, xn3. local variables: queue, a queue of arcs, initially all the arcs in csp4. while queue is not empty do5. (xi, xj) remove-first( queue )6. if rm-inconsistent-values(xi, xj) then7. for each xk in neighborsxi do8. add (xk, xi) to queue1. function rm-inconsistent-values(xi, xj) returns true iff rem

16、ove a value1. removed false2. for each x in domainxi do3. if no value y in domainxj allows (x,y) to satisfy constraint(xi, xj)4. then delete x from domainxi; removed true5. return removed弧相容的使用弧相容的使用 弧相容檢驗(yàn)可以用作開始弧相容檢驗(yàn)可以用作開始搜索之前搜索之前的的預(yù)處理預(yù)處理。 弧相容檢驗(yàn)也可以在弧相容檢驗(yàn)也可以在搜索過程中搜索過程中每次賦值后用作一個(gè)每次賦值后用作一個(gè)約束傳播步驟約束傳播步驟。

17、即反復(fù)檢測某個(gè)變量值域中的不相容弧，進(jìn)行值即反復(fù)檢測某個(gè)變量值域中的不相容弧，進(jìn)行值刪除，直到不再有矛盾。刪除，直到不再有矛盾。 稱為稱為保持弧相容（保持弧相容（mac）。從弧相容推廣到從弧相容推廣到k相容相容 如果對于如果對于任何任何k1個(gè)變量的相容賦值個(gè)變量的相容賦值，第，第k個(gè)變量總個(gè)變量總能被賦予一個(gè)與前能被賦予一個(gè)與前k1個(gè)變量相容的值，那么該個(gè)變量相容的值，那么該csp問題是問題是k相容相容的。的。 1相容是指每個(gè)單獨(dú)的變量自己是不矛盾的，也稱為相容是指每個(gè)單獨(dú)的變量自己是不矛盾的，也稱為節(jié)點(diǎn)相容節(jié)點(diǎn)相容。 弧相容弧相容2相容。相容。 3相容是指任何一對相鄰的變量總可以擴(kuò)展到第三個(gè)

18、相容是指任何一對相鄰的變量總可以擴(kuò)展到第三個(gè)鄰居變量，也稱為鄰居變量，也稱為路徑相容路徑相容。 如果一個(gè)圖是如果一個(gè)圖是k相容的，也是相容的，也是k-1相容的、相容的、k-2相容相容的，的，直到，直到1相容，那么這個(gè)圖是相容，那么這個(gè)圖是強(qiáng)強(qiáng)k相容相容的。的。從弧相容推廣到從弧相容推廣到k相容相容 如果一個(gè)如果一個(gè)csp問題有問題有n個(gè)結(jié)點(diǎn)，而且它是強(qiáng)個(gè)結(jié)點(diǎn)，而且它是強(qiáng)n相容的，相容的，則不需要回溯就能求解這個(gè)問題。則不需要回溯就能求解這個(gè)問題。 可以在可以在o(nd)時(shí)間內(nèi)找到解。時(shí)間內(nèi)找到解。 no free lunch：任何建立任何建立n相容的算法在最壞情況相容的算法在最壞情況下必須花費(fèi)

19、下必須花費(fèi)n的指數(shù)級時(shí)間。的指數(shù)級時(shí)間。 從弧相容到從弧相容到n相容：相容：執(zhí)行較強(qiáng)的相容性檢驗(yàn)會(huì)花費(fèi)更執(zhí)行較強(qiáng)的相容性檢驗(yàn)會(huì)花費(fèi)更多的時(shí)間，但是會(huì)更有效地降低分支因子和檢測出多的時(shí)間，但是會(huì)更有效地降低分支因子和檢測出矛盾的不完全賦值。矛盾的不完全賦值。特殊約束特殊約束 實(shí)際問題中出現(xiàn)的實(shí)際問題中出現(xiàn)的特殊約束特殊約束，用，用專用算法專用算法處理其效率處理其效率要比要比通用的約束處理算法通用的約束處理算法高很多。高很多。特殊約束特殊約束 例如，例如，alldiff約束約束，變量取值各不相同變量取值各不相同 假設(shè)約束涉及假設(shè)約束涉及m個(gè)變量，所有變量共有個(gè)變量，所有變量共有n個(gè)取值，個(gè)取值，如

20、果如果mn，則此約束不能被滿足。，則此約束不能被滿足。 引出相應(yīng)的引出相應(yīng)的算法算法： 刪除約束中只有單值值域的變量，將這些變量的刪除約束中只有單值值域的變量，將這些變量的取值從其余變量值域中刪去；取值從其余變量值域中刪去； 對單值變量重復(fù)此過程；對單值變量重復(fù)此過程； 如果得到空的值域或剩下的變量數(shù)大于取值數(shù)，如果得到空的值域或剩下的變量數(shù)大于取值數(shù)，則產(chǎn)生矛盾。則產(chǎn)生矛盾。特殊約束特殊約束 資源約束資源約束，有時(shí)稱為，有時(shí)稱為atmost約束約束。 例如，例如，用用pa1, , pa4表示分配給四項(xiàng)任務(wù)的人員個(gè)表示分配給四項(xiàng)任務(wù)的人員個(gè)數(shù)，人員數(shù)總計(jì)不超過數(shù)，人員數(shù)總計(jì)不超過10人的約束記

21、為人的約束記為atmost(10, pa1, , pa4)。 如果每個(gè)變量的賦值為如果每個(gè)變量的賦值為3, 4, 5, 6，就不能，就不能滿足滿足atmost約束。約束。 通過檢驗(yàn)當(dāng)前值域中的最小值之和就能檢測出矛通過檢驗(yàn)當(dāng)前值域中的最小值之和就能檢測出矛盾。盾。特殊約束特殊約束 對于大型的整數(shù)值的資源限制問題，用整數(shù)集合來表示每個(gè)對于大型的整數(shù)值的資源限制問題，用整數(shù)集合來表示每個(gè)變量的值域然后通過相容性檢驗(yàn)方法逐步削減集合，通常是變量的值域然后通過相容性檢驗(yàn)方法逐步削減集合，通常是不可能的。不可能的。 取代辦法：值域用上界和下界來表示，并通過取代辦法：值域用上界和下界來表示，并通過邊界傳播

22、邊界傳播來來管理。管理。 例、例、假設(shè)有假設(shè)有2次航班，次航班，271和和272，它們分別有，它們分別有165和和385個(gè)座個(gè)座位。每次航班可承載的初始值域?yàn)槲?。每次航班可承載的初始值域?yàn)閒light2710, 165，flight2720, 385。 設(shè)又增加一個(gè)約束，兩次航班所承載的總乘客數(shù)必須是設(shè)又增加一個(gè)約束，兩次航班所承載的總乘客數(shù)必須是420。通過邊界傳播約束，可以把這兩個(gè)值域削減到通過邊界傳播約束，可以把這兩個(gè)值域削減到flight27135, 165，flight272255, 385。 如果對于每個(gè)變量如果對于每個(gè)變量x和它的取值的上下界，每個(gè)變量和它的取值的上下界，每個(gè)變量

23、y都存在都存在某個(gè)取值滿足某個(gè)取值滿足x和和y之間的約束，我們稱該之間的約束，我們稱該csp問題是問題是邊界相邊界相容容的。的。本章內(nèi)容本章內(nèi)容 6.1 約束滿足問題約束滿足問題 6.2 約束傳播：約束傳播：csp中的推理中的推理 6.3 csp的回溯搜索的回溯搜索 6.4 csp的局部搜索的局部搜索 6.5 問題的結(jié)構(gòu)問題的結(jié)構(gòu)csp的回溯搜索的回溯搜索 csp問題具有一個(gè)性質(zhì)：問題具有一個(gè)性質(zhì)：可交換性可交換性，變量賦值的，變量賦值的順序?qū)Y(jié)果沒有影響。順序?qū)Y(jié)果沒有影響。 所有所有csp搜索算法生成后繼節(jié)點(diǎn)時(shí)，在搜索樹搜索算法生成后繼節(jié)點(diǎn)時(shí)，在搜索樹每個(gè)節(jié)點(diǎn)上只考慮每個(gè)節(jié)點(diǎn)上只考慮單個(gè)變

24、量單個(gè)變量的可能賦值。的可能賦值。 csp問題的求解：問題的求解：深度優(yōu)先的回溯搜索深度優(yōu)先的回溯搜索。每次給一個(gè)變量賦值，當(dāng)沒有合法賦值每次給一個(gè)變量賦值，當(dāng)沒有合法賦值( (不滿不滿足約束時(shí)足約束時(shí)) )就要推翻前一個(gè)變量的賦值，重新就要推翻前一個(gè)變量的賦值，重新給其賦值，這就是回溯。給其賦值，這就是回溯。簡單回溯法生成的搜索樹簡單回溯法生成的搜索樹 澳大利亞地圖染色問題的搜索樹澳大利亞地圖染色問題的搜索樹wa=redwa=rednt=greenwa=rednt=bluewa=rednt=greenq=redwa=rednt=greenq=bluewa=greenwa=bluewantsa

25、nswqvt一個(gè)簡單的回溯算法一個(gè)簡單的回溯算法（深度優(yōu)先）（深度優(yōu)先）1. function backtracking-search( csp ) returns a solution, or failure2. return recursive-backtracking( , csp )1. function recursive-backtracking( assignment, csp ) returns a solution, or failure2. if assignment is complete then return assignment3. varselect-unassi

26、gned-variable(variablescsp, assignment, csp)4. for each value in order-domain-values( var, assignment, csp ) do5. if value is consistent with assignment according to constraintscsp then6. add var=value to assignment7. result recursive-backtracking( assignment, csp )8. if result != failure then retur

27、n result9. remove var=value from assignment10. return failure回溯搜索的通用算法回溯搜索的通用算法 需改善需改善無信息無信息回溯搜索算法的性能?；厮菟阉魉惴ǖ男阅?。 通用改進(jìn)方法通用改進(jìn)方法的思路：的思路：下一步該給下一步該給哪個(gè)變量哪個(gè)變量賦值，按賦值，按什么順序什么順序給該變量給該變量賦值？賦值？每步搜索應(yīng)該做怎樣的推理？每步搜索應(yīng)該做怎樣的推理？當(dāng)前變量的賦值會(huì)當(dāng)前變量的賦值會(huì)對其他未賦值變量產(chǎn)生什么約束，怎樣利用這種對其他未賦值變量產(chǎn)生什么約束，怎樣利用這種約束以提高效率。約束以提高效率。當(dāng)遇到某個(gè)失敗的變量賦值時(shí)，怎樣當(dāng)遇到

28、某個(gè)失敗的變量賦值時(shí)，怎樣避免同樣的避免同樣的失敗失??？就是說如何找到對這種失敗起到關(guān)鍵作用？就是說如何找到對這種失敗起到關(guān)鍵作用的某個(gè)變量賦值。的某個(gè)變量賦值。csp回溯搜索的改進(jìn)回溯搜索的改進(jìn)基于變量和賦值次序的啟發(fā)式基于變量和賦值次序的啟發(fā)式搜索與推理交錯(cuò)進(jìn)行搜索與推理交錯(cuò)進(jìn)行智能回溯：向后看智能回溯：向后看csp回溯搜索的改進(jìn)回溯搜索的改進(jìn)基于變量和賦值次序的啟發(fā)式基于變量和賦值次序的啟發(fā)式mrv（最少剩余值）啟發(fā)式（最少剩余值）啟發(fā)式最少約束值啟發(fā)式最少約束值啟發(fā)式度啟發(fā)式度啟發(fā)式搜索與推理交錯(cuò)進(jìn)行搜索與推理交錯(cuò)進(jìn)行智能回溯：向后看智能回溯：向后看mrv啟發(fā)式啟發(fā)式 隨機(jī)的變量賦值排

29、序難以產(chǎn)生高效率的搜索。隨機(jī)的變量賦值排序難以產(chǎn)生高效率的搜索。 例如：例如：在在wa=red/nt=green條件下選取條件下選取sa賦值比賦值比q要減少賦要減少賦值次數(shù)值次數(shù)(1:2)，并且一旦給定，并且一旦給定sa賦值以后，賦值以后，q、nsw和和v的賦的賦值只有一個(gè)選擇。值只有一個(gè)選擇。wantsanswqvt因此，應(yīng)當(dāng)選擇合法取值最少的變量，即因此，應(yīng)當(dāng)選擇合法取值最少的變量，即最少剩余值最少剩余值(mrv)啟啟發(fā)式發(fā)式，也稱為，也稱為最受約束變量最受約束變量啟發(fā)式啟發(fā)式或或失敗優(yōu)先啟發(fā)式失敗優(yōu)先啟發(fā)式。稱為稱為失敗優(yōu)先啟發(fā)式失敗優(yōu)先啟發(fā)式是因?yàn)樗梢院芸煺业绞〉淖兞?，從是因?yàn)樗?/p>

30、以很快找到失敗的變量，從而引起搜索的剪枝，避免更多導(dǎo)致同樣失敗的搜索。而引起搜索的剪枝，避免更多導(dǎo)致同樣失敗的搜索。最少約束值啟發(fā)式最少約束值啟發(fā)式 mrv啟發(fā)式啟發(fā)式當(dāng)有多個(gè)變量需要選擇時(shí)，優(yōu)先選擇在當(dāng)前約當(dāng)有多個(gè)變量需要選擇時(shí)，優(yōu)先選擇在當(dāng)前約束下取值最少的變量。束下取值最少的變量。 問題：問題：一旦變量被選定，算法就要決定它的取值的次序。一旦變量被選定，算法就要決定它的取值的次序。 最少約束值啟發(fā)式：最少約束值啟發(fā)式：當(dāng)賦值的變量有多個(gè)值選擇時(shí)，優(yōu)先的當(dāng)賦值的變量有多個(gè)值選擇時(shí)，優(yōu)先的值應(yīng)是約束圖中排除鄰居變量的可選值最少的，即優(yōu)先選擇值應(yīng)是約束圖中排除鄰居變量的可選值最少的，即優(yōu)先選擇

31、為剩余變量的賦值留下最多選擇的賦值。為剩余變量的賦值留下最多選擇的賦值。 例如，例如，wa=red且且nt=green時(shí)，如果給時(shí)，如果給q賦值，可以為賦值，可以為blue或或red，而，而q=blue的選擇不好，因?yàn)榇藭r(shí)的選擇不好，因?yàn)榇藭r(shí)sa沒有一個(gè)沒有一個(gè)可選擇的了?？蛇x擇的了。wantsanswqvt 如果要找出問題的所有如果要找出問題的所有解，則排序問題無所謂。解，則排序問題無所謂。度啟發(fā)式度啟發(fā)式 mrv啟發(fā)式：啟發(fā)式：當(dāng)有多個(gè)變量需要選擇時(shí)，優(yōu)先選擇在當(dāng)前約當(dāng)有多個(gè)變量需要選擇時(shí)，優(yōu)先選擇在當(dāng)前約束下取值最少的變量。束下取值最少的變量。 問題：問題：對澳大利亞地圖著色問題中選擇第

32、一個(gè)染色問題根對澳大利亞地圖著色問題中選擇第一個(gè)染色問題根本沒有幫助，因?yàn)槌跏嫉臅r(shí)候每個(gè)區(qū)域都有本沒有幫助，因?yàn)槌跏嫉臅r(shí)候每個(gè)區(qū)域都有3種選擇。種選擇。 度啟發(fā)式度啟發(fā)式：選擇涉及對其他未賦值變量的約束數(shù)量大：選擇涉及對其他未賦值變量的約束數(shù)量大（與其（與其他變量關(guān)聯(lián)最多）他變量關(guān)聯(lián)最多）的變量。的變量。地圖染色例子中，度地圖染色例子中，度(sa)=5(sa)=5，其他均為，其他均為2 2或或3 3。實(shí)際上，一旦選擇了實(shí)際上，一旦選擇了sasa作為初始節(jié)點(diǎn)，應(yīng)用度啟發(fā)式求解作為初始節(jié)點(diǎn)，應(yīng)用度啟發(fā)式求解本問題，則可以不經(jīng)任何回溯就找到解。本問題，則可以不經(jīng)任何回溯就找到解。wantsanswq

33、vtsa=red nt=green q=blue nsw=green wa=blue v=blue tredcsp回溯搜索的改進(jìn)回溯搜索的改進(jìn)基于變量和賦值次序的啟發(fā)式基于變量和賦值次序的啟發(fā)式搜索與推理交錯(cuò)進(jìn)行搜索與推理交錯(cuò)進(jìn)行智能回溯：向后看智能回溯：向后看搜索與推理交錯(cuò)進(jìn)行搜索與推理交錯(cuò)進(jìn)行一般的回溯算法：一般的回溯算法：只有在選擇了一個(gè)變量的時(shí)候才只有在選擇了一個(gè)變量的時(shí)候才考慮變量的約束?？紤]變量的約束。變量約束的啟發(fā)式變量約束的啟發(fā)式：在搜索的早些時(shí)候，或開始之在搜索的早些時(shí)候，或開始之前就考慮某些約束，從而降低搜索空間。前就考慮某些約束，從而降低搜索空間。 約束傳播約束傳播 最簡

34、單的推理形式：最簡單的推理形式：前向檢驗(yàn)前向檢驗(yàn)前向檢驗(yàn)前向檢驗(yàn) 前向檢驗(yàn)：前向檢驗(yàn)：如果如果x被賦值，前向檢驗(yàn)就是檢查與被賦值，前向檢驗(yàn)就是檢查與x相相連的那些變量連的那些變量y，看看它們是否滿足相關(guān)約束，并從，看看它們是否滿足相關(guān)約束，并從y的值域中刪去與的值域中刪去與x取值矛盾的那些賦值。取值矛盾的那些賦值。wantqnswvsargbrgbrgbrgbrgbrgb gbrgbrgb rgb gb b r brgb b b r -wa=redwa=redq=greenq=greenv=bluev=blue藍(lán)色字體為賦藍(lán)色字體為賦值結(jié)果值結(jié)果 賦值賦值v=blue引起矛盾，此時(shí)引起矛盾，此

35、時(shí)sa賦值為空，不滿足賦值為空，不滿足問題約束，此時(shí)算法就要立刻回溯。問題約束，此時(shí)算法就要立刻回溯。前向檢驗(yàn)前向檢驗(yàn) 前向檢驗(yàn)可與前向檢驗(yàn)可與mrv啟發(fā)式啟發(fā)式相結(jié)合。相結(jié)合。 實(shí)際上，實(shí)際上，mrv要做的就是向前找合適的變量。要做的就是向前找合適的變量。 注意：注意：這里只是檢驗(yàn)一步這里只是檢驗(yàn)一步，即和當(dāng)前節(jié)點(diǎn)是否矛盾。，即和當(dāng)前節(jié)點(diǎn)是否矛盾。 前向檢驗(yàn)看得不夠遠(yuǎn)。雖然前向檢驗(yàn)?zāi)軝z驗(yàn)出許前向檢驗(yàn)看得不夠遠(yuǎn)。雖然前向檢驗(yàn)?zāi)軝z驗(yàn)出許多矛盾，它還是不能檢驗(yàn)出所有的矛盾。多矛盾，它還是不能檢驗(yàn)出所有的矛盾。 被檢驗(yàn)節(jié)點(diǎn)之間的約束檢驗(yàn)還不能進(jìn)行。被檢驗(yàn)節(jié)點(diǎn)之間的約束檢驗(yàn)還不能進(jìn)行。 改進(jìn)：改進(jìn)：約

36、束傳播約束傳播。csp回溯搜索的改進(jìn)回溯搜索的改進(jìn)基于變量和賦值次序的啟發(fā)式基于變量和賦值次序的啟發(fā)式搜索與推理交錯(cuò)進(jìn)行搜索與推理交錯(cuò)進(jìn)行智能回溯：向后看智能回溯：向后看向后看智能回溯向后看智能回溯 在回溯算法中，當(dāng)發(fā)現(xiàn)不滿足約束即搜索失敗時(shí)，在回溯算法中，當(dāng)發(fā)現(xiàn)不滿足約束即搜索失敗時(shí)，則回到上一個(gè)變量并嘗試下一個(gè)取值，這稱為則回到上一個(gè)變量并嘗試下一個(gè)取值，這稱為歷時(shí)歷時(shí)回溯回溯。 在很多情況下這樣做是效率很低的，因?yàn)閱栴}并在很多情況下這樣做是效率很低的，因?yàn)閱栴}并不決定于上一個(gè)不決定于上一個(gè)（甚至幾個(gè)）（甚至幾個(gè)）變量的取值。變量的取值。 回溯應(yīng)倒退到回溯應(yīng)倒退到導(dǎo)致失敗的變量的集合導(dǎo)致失

37、敗的變量的集合中的一個(gè)變量。中的一個(gè)變量。 該集合稱為該集合稱為沖突集沖突集。 變量變量x的的沖突集沖突集是通過約是通過約束與束與x相連接的、先前已賦相連接的、先前已賦值變量的集合。值變量的集合。沖突集沖突集 對于地圖染色問題，設(shè)有不完全賦值對于地圖染色問題，設(shè)有不完全賦值q=red, nsw=green, v=blue, t=red 。wantsanswqvt 此時(shí)，給此時(shí)，給sa賦值將發(fā)現(xiàn)無法滿足任何約束，賦值將發(fā)現(xiàn)無法滿足任何約束，sa的的沖突集沖突集=q, nsw, v。后向跳轉(zhuǎn)后向跳轉(zhuǎn) 后向跳轉(zhuǎn)：后向跳轉(zhuǎn)：回溯到回溯到?jīng)_突集沖突集中時(shí)間最近中時(shí)間最近（最后賦值）（最后賦值）的變量。的

38、變量。 對于對于前向檢驗(yàn)前向檢驗(yàn)算法，可以很容易得到?jīng)_突集。算法，可以很容易得到?jīng)_突集?；诨趚 x賦值的前向檢驗(yàn)從變量賦值的前向檢驗(yàn)從變量y y的值域中刪除一個(gè)值時(shí)，說的值域中刪除一個(gè)值時(shí)，說明明x x和和y y存在沖突，則顯然存在沖突，則顯然x x是是y y的沖突集中的一個(gè)變量。的沖突集中的一個(gè)變量。當(dāng)?shù)竭_(dá)當(dāng)?shù)竭_(dá)y y時(shí)，可知回溯到哪個(gè)變量。時(shí)，可知回溯到哪個(gè)變量。 對于對于弧相容檢驗(yàn)弧相容檢驗(yàn)，因?yàn)槎际亲鋈≈迪嗳莸臋z測，只要在弧相，因?yàn)槎际亲鋈≈迪嗳莸臋z測，只要在弧相容檢驗(yàn)時(shí)增加一個(gè)變量集合記錄即可。容檢驗(yàn)時(shí)增加一個(gè)變量集合記錄即可。后向跳轉(zhuǎn)后向跳轉(zhuǎn) 問題：問題：后向跳轉(zhuǎn)后向跳轉(zhuǎn)只出現(xiàn)

39、在值域中的每個(gè)值都和當(dāng)前只出現(xiàn)在值域中的每個(gè)值都和當(dāng)前的賦值有沖突的情況下，但是的賦值有沖突的情況下，但是前向檢驗(yàn)前向檢驗(yàn)?zāi)軝z測到這能檢測到這個(gè)事件并且一旦到達(dá)這樣的結(jié)點(diǎn)就阻止搜索。個(gè)事件并且一旦到達(dá)這樣的結(jié)點(diǎn)就阻止搜索。 可以證明：可以證明：每個(gè)被每個(gè)被后向跳轉(zhuǎn)后向跳轉(zhuǎn)剪枝的分支在剪枝的分支在前向檢前向檢驗(yàn)驗(yàn)算法中也被剪枝。算法中也被剪枝。 因此，因此，簡單的后向跳轉(zhuǎn)簡單的后向跳轉(zhuǎn)在在前向檢驗(yàn)前向檢驗(yàn)搜索中，或者搜索中，或者在諸如在諸如mac（保持弧相容保持弧相容）這樣使用更強(qiáng)的相容）這樣使用更強(qiáng)的相容性檢驗(yàn)的搜索中是性檢驗(yàn)的搜索中是多余的多余的。沖突指導(dǎo)的后向跳轉(zhuǎn)沖突指導(dǎo)的后向跳轉(zhuǎn) 很多情

40、況下，一個(gè)分支發(fā)生很久以前就已經(jīng)注定要失敗了。很多情況下，一個(gè)分支發(fā)生很久以前就已經(jīng)注定要失敗了。 例，例，考慮不完全賦值考慮不完全賦值wa=red, nsw=red。 假設(shè)下一個(gè)賦值嘗試假設(shè)下一個(gè)賦值嘗試t=red，然后給，然后給nt，q，v，sa賦值。賦值。wantsanswqvt因?yàn)樽詈蟮乃膫€(gè)變量因?yàn)樽詈蟮乃膫€(gè)變量nt，q，v，sa沒有相容的賦值，因沒有相容的賦值，因此最終我們嘗試了此最終我們嘗試了nt的所有可能取值。的所有可能取值?，F(xiàn)在的問題是向哪里回溯？現(xiàn)在的問題是向哪里回溯？后向跳轉(zhuǎn)行不通后向跳轉(zhuǎn)行不通：nt確實(shí)確實(shí)有有和已賦值變量相容的值，但和已賦值變量相容的值，但nt沒有沒有完

41、整的由前面能導(dǎo)致失敗的變量組成的沖突集。完整的由前面能導(dǎo)致失敗的變量組成的沖突集。沖突指導(dǎo)的后向跳轉(zhuǎn)沖突指導(dǎo)的后向跳轉(zhuǎn) 變量沖突集更一般的情況：變量沖突集更一般的情況：前面的變量集合前面的變量集合使得使得當(dāng)當(dāng)前變量前變量連同連同任何后繼變量任何后繼變量一起沒有相容解。一起沒有相容解。 沖突指導(dǎo)的后向跳轉(zhuǎn)處理：沖突指導(dǎo)的后向跳轉(zhuǎn)處理： 令令xj是當(dāng)前變量，是當(dāng)前變量，conf(xj)是其沖突集。是其沖突集。 如果如果xj每個(gè)可能取值都失敗了，則后向跳轉(zhuǎn)到每個(gè)可能取值都失敗了，則后向跳轉(zhuǎn)到conf(xj)中最近的一個(gè)變量中最近的一個(gè)變量xi，令，令conf(xi)=conf(xi)conf(xj)

42、 - xi。 從從xi向前是無解的，從向前是無解的，從xi回到某個(gè)以前的變量賦回到某個(gè)以前的變量賦值。值。沖突指導(dǎo)的后向跳轉(zhuǎn)沖突指導(dǎo)的后向跳轉(zhuǎn) 例，例，考慮不完全賦值考慮不完全賦值wa=red, nsw=red。 假設(shè)下一個(gè)賦值嘗試假設(shè)下一個(gè)賦值嘗試t=red，然后給，然后給nt，q，v，sa賦值。賦值。 因?yàn)樽詈笏膫€(gè)變量因?yàn)樽詈笏膫€(gè)變量nt，q，v，sa沒有相容的賦值，回溯。沒有相容的賦值，回溯。 sa的沖突集是的沖突集是wa, nt, q，后向跳轉(zhuǎn)到，后向跳轉(zhuǎn)到q。 q將將sa的沖突集（減去的沖突集（減去q）吸收到自己的沖突集里，則）吸收到自己的沖突集里，則q的新的沖突集為的新的沖突集為w

43、a, nt, nsw。 給定了給定了wa, nt, nsw的賦值后，從的賦值后，從q向前是無解的。向前是無解的。 回溯到回溯到nt，nt的沖突集變?yōu)榈臎_突集變?yōu)閣a, nt, nsw - nt+ wa = wa, nsw。 后向跳轉(zhuǎn)到后向跳轉(zhuǎn)到nsw。wantsanswqvt本章內(nèi)容本章內(nèi)容 6.1 約束滿足問題約束滿足問題 6.2 約束傳播：約束傳播：csp中的推理中的推理 6.3 csp的回溯搜索的回溯搜索 6.4 csp的局部搜索的局部搜索 6.5 問題的結(jié)構(gòu)問題的結(jié)構(gòu)約束滿足問題的局部搜索約束滿足問題的局部搜索 完全狀態(tài)的形式化：完全狀態(tài)的形式化：初始狀態(tài)給每個(gè)變量賦值，后初始狀態(tài)給每

44、個(gè)變量賦值，后繼函數(shù)一次繼函數(shù)一次改變改變一個(gè)變量的取值。一個(gè)變量的取值。 在為變量選擇新值時(shí)，最明顯的啟發(fā)式是：在為變量選擇新值時(shí)，最明顯的啟發(fā)式是： 選擇與其它變量的沖突最小的值，選擇與其它變量的沖突最小的值，最小沖突啟發(fā)最小沖突啟發(fā)式式。 用最小沖突算法解決八皇后問題。用最小沖突算法解決八皇后問題。 每一步選擇一個(gè)皇后，在它所在的列中重新分配位置。每一步選擇一個(gè)皇后，在它所在的列中重新分配位置。 算法將皇后移到算法將皇后移到最小沖突最小沖突的方格中，最小沖突值有多個(gè)的方格中，最小沖突值有多個(gè)方格時(shí)則隨機(jī)地選取一個(gè)。方格時(shí)則隨機(jī)地選取一個(gè)。例、八皇后問題例、八皇后問題約束滿足問題的局部搜索

45、約束滿足問題的局部搜索1.function min-conflicts(csp, max_steps) return solution or failure2. inputs: csp, a constraint satisfaction problem3.max_steps, the number of steps allowed before giving up4. current an initial complete assignment for csp5. for i = 1 to max_steps do6. if current is a solution for csp the

46、n return current7.var a randomly chosen, conflicted variable from 8. variables csp 9.value the value v for var that minimizes 10. conflicts( var, v, current, csp )11.set var = value in current12. return faiilure 一個(gè)用局部搜索解決一個(gè)用局部搜索解決csp問題的問題的min-conflicts算法算法。局部搜索算法的表現(xiàn)局部搜索算法的表現(xiàn) miniconflict算法對許多算法對許多cs

47、p都驚人地有效，尤其是給定都驚人地有效，尤其是給定了了合理的初始狀態(tài)合理的初始狀態(tài)時(shí)。時(shí)。 例如，對于八皇后問題，如果不計(jì)算皇后的初始位置，算例如，對于八皇后問題，如果不計(jì)算皇后的初始位置，算法的運(yùn)行時(shí)間大體上獨(dú)立于問題的大小。法的運(yùn)行時(shí)間大體上獨(dú)立于問題的大小。 百萬皇后問題，平均百萬皇后問題，平均50步（給定了初始賦值后）步（給定了初始賦值后） 局部搜索算法的另一個(gè)優(yōu)勢是當(dāng)問題改變時(shí)可用于局部搜索算法的另一個(gè)優(yōu)勢是當(dāng)問題改變時(shí)可用于聯(lián)機(jī)設(shè)置聯(lián)機(jī)設(shè)置。 這在這在調(diào)度問題調(diào)度問題中尤其重要。中尤其重要。 例如，惡劣天氣導(dǎo)致航班日程表要修改，總是希望以最小例如，惡劣天氣導(dǎo)致航班日程表要修改，總是

48、希望以最小改動(dòng)來修改日程。改動(dòng)來修改日程。 很容易很容易csp問題轉(zhuǎn)換成問題轉(zhuǎn)換成最優(yōu)化最優(yōu)化問題。這樣，問題。這樣，爬山法、模擬退爬山法、模擬退化和遺傳算法等化和遺傳算法等都可以用來最優(yōu)化目標(biāo)函數(shù)。都可以用來最優(yōu)化目標(biāo)函數(shù)。本章內(nèi)容本章內(nèi)容 6.1 約束滿足問題約束滿足問題 6.2 約束傳播：約束傳播：csp中的推理中的推理 6.3 csp的回溯搜索的回溯搜索 6.4 csp的局部搜索的局部搜索 6.5 問題的結(jié)構(gòu)問題的結(jié)構(gòu)問題的結(jié)構(gòu)問題的結(jié)構(gòu) 問題的結(jié)構(gòu)，如約束圖表示的，可利用來找到問題的解。問題的結(jié)構(gòu)，如約束圖表示的，可利用來找到問題的解。 假設(shè)一個(gè)假設(shè)一個(gè)csp問題的變量個(gè)數(shù)為問題的變

49、量個(gè)數(shù)為n，所有變量的值域大小，所有變量的值域大小 d，則問題的可能的完全賦值的數(shù)量為則問題的可能的完全賦值的數(shù)量為o(dn)。 分解方法：分解方法：將約束圖分解為將約束圖分解為連通域的并集連通域的并集以降低問題的復(fù)雜以降低問題的復(fù)雜度。度。 例子：澳大利亞地圖中例子：澳大利亞地圖中tasmania與大陸不相連。與大陸不相連。 假設(shè)每個(gè)連通域?qū)?yīng)一個(gè)子問題假設(shè)每個(gè)連通域?qū)?yīng)一個(gè)子問題cspi。如果賦值。如果賦值si是是cspi的的一個(gè)解，則一個(gè)解，則isi是是icspi的一個(gè)解。的一個(gè)解。 假設(shè)總計(jì)有假設(shè)總計(jì)有n個(gè)變量，每個(gè)個(gè)變量，每個(gè)si有有c個(gè)變量，則共計(jì)個(gè)變量，則共計(jì)n/c個(gè)子個(gè)子問題，

50、每個(gè)子問題最多花費(fèi)問題，每個(gè)子問題最多花費(fèi)dc步工作，則總工作量為步工作，則總工作量為o(dcn/c)。約束圖是約束圖是樹樹 問題：問題：完全獨(dú)立的子問題很少見完全獨(dú)立的子問題很少見。 考慮約束圖是考慮約束圖是樹樹的情景，即任何兩個(gè)變量最多通過的情景，即任何兩個(gè)變量最多通過一條路徑連通。一條路徑連通。約束圖是約束圖是樹樹求解算法：求解算法：1. 任選一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)，從根節(jié)點(diǎn)到葉節(jié)點(diǎn)按順序排列，任選一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)，從根節(jié)點(diǎn)到葉節(jié)點(diǎn)按順序排列，每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)都在它前面。按順序把它們標(biāo)為每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)都在它前面。按順序把它們標(biāo)為x1，xn。2. 令令j從從n到到2，在弧，在弧(xi, x

51、j)上應(yīng)用上應(yīng)用弧相容弧相容算法，其中算法，其中xi是是xj的的父節(jié)點(diǎn)，從父節(jié)點(diǎn)，從domainxi中刪除必要的值。中刪除必要的值。3. 令令j從從1到到n，賦給，賦給xj與與xi的值相容的值。的值相容的值。 第第2步之后的步之后的csp是是有向弧相容有向弧相容的；的； 被刪掉的值不會(huì)危及已處理過的弧的相容性。被刪掉的值不會(huì)危及已處理過的弧的相容性。 第第3步，賦值不需要回溯。步，賦值不需要回溯。 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：o(nd2)。將一般的約束圖簡化為樹形式將一般的約束圖簡化為樹形式 將一般的約束圖簡化為樹形式，有將一般的約束圖簡化為樹形式，有2中基本方式：中基本方式： 基于刪除節(jié)點(diǎn)的?；?/p>

52、于刪除節(jié)點(diǎn)的。 基于合并節(jié)點(diǎn)的?；诤喜⒐?jié)點(diǎn)的?；趧h除節(jié)點(diǎn)的方式基于刪除節(jié)點(diǎn)的方式 先對某些變量賦值，使剩下的變量構(gòu)成一棵樹。先對某些變量賦值，使剩下的變量構(gòu)成一棵樹。 例：例：澳大利亞的約束圖，給澳大利亞的約束圖，給sa賦值，并從其它變賦值，并從其它變量的值域中刪去與該值不相容的值。量的值域中刪去與該值不相容的值?；趧h除節(jié)點(diǎn)方式的一般算法基于刪除節(jié)點(diǎn)方式的一般算法1.從從variablescsp中選澤一個(gè)子集中選澤一個(gè)子集s，使得約束圖在刪除，使得約束圖在刪除s之后成為一顆樹。之后成為一顆樹。s稱為稱為環(huán)割集環(huán)割集。2.對滿足對滿足s所有約束條件的所有約束條件的s中變量的中變量的每個(gè)可能賦值每個(gè)可能賦值：a)從從剩余變量剩余變量的值域中刪除與的值域中刪除與s的賦值不相容的值；的賦值不相容的值；b)如果去掉如果去掉s后的剩余后的剩余csp有解，把有解，把解和解和s的賦值的賦值一起返回。一起返回。 如果環(huán)割集的大小為如果環(huán)割集的大小為c，那么總的運(yùn)行時(shí)間為，那么總的運(yùn)行時(shí)間為o(dc(n-c)d2)。 尋找最小環(huán)割集是個(gè)尋找最小環(huán)割集是個(gè)np難題難題。 采用一些已有的高效近似算法，即采用一些已有的高效近似算法，即割集調(diào)整割集調(diào)整。基于合并節(jié)點(diǎn)的方式基于合并節(jié)點(diǎn)的方式 基于合并節(jié)點(diǎn)的方式：基于合并節(jié)點(diǎn)的方式：建立在構(gòu)造約束圖的建立在構(gòu)造約束圖的樹分解樹分解的基礎(chǔ)上，的基礎(chǔ)上