第6章 約束滿足問題

1、第第6章章 約束滿足問題約束滿足問題中國科大中國科大 計算機學院計算機學院第第部分部分 問題求解問題求解本章內(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) 澳大利亞地圖染色問題：用澳大利亞地圖染色問題：用紅紅綠綠藍藍3色標出各省，色標出各省，相鄰者顏色不同。相鄰者顏色不同。塔斯馬尼亞西澳大利亞北領(lǐng)地南澳大利亞昆士蘭新南威爾士維多利亞 對應于澳大利亞地圖的對應于澳大利亞地圖的約束圖約束圖，

2、相互關(guān)聯(lián)的節(jié)點，相互關(guān)聯(lián)的節(jié)點用邊連接。用邊連接。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）：）： 由一個變量集合由一個變量集合x1xn和一個約束集合和一個約束集合c1cm定義；定義；每個變量都有一個非空可能值域每個變量都有一個非空可能值域d di i；每個約束指定了包含若干變量的一個子集內(nèi)各變量的賦值每個約束指定了包含若干變量的一個子集內(nèi)各變量的賦值范圍。范圍。 例如：例如：地圖染色問題，地圖染色問題，n-n-皇后問題?；屎髥栴}。 csp的一個狀態(tài)的一個狀態(tài)：對一些或全部變量的賦值：對一些或全部變量的賦值 xi=vi, xj=vj, 。csp問題的解問題的解 一個不違反任何約束的對變量的賦值稱為一個不違反任何約束的對變量的賦值稱為相容賦值相容賦值或合法賦值或合法賦值。 對每個變

4、量都進行賦值稱為對每個變量都進行賦值稱為完全賦值完全賦值。 一個一個（一組）（一組）對變量的賦值，若既是相容賦值又是對變量的賦值，若既是相容賦值又是完全賦值，則這個（組）賦值是完全賦值，則這個（組）賦值是csp問題的解問題的解。 某些某些csp問題要求問題的解能使目標函數(shù)最大問題要求問題的解能使目標函數(shù)最大化化約束優(yōu)化約束優(yōu)化。 csp問題常?？梢钥梢暬硎緸閱栴}常?？梢钥梢暬硎緸榧s束圖約束圖，更直觀，更直觀地顯示問題，幫助思考問題的答案。地顯示問題，幫助思考問題的答案。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ù)級時間復雜性解決該問題。csp問題的分類問題的分類 變量變量連續(xù)值域連續(xù)值域 最著名的連續(xù)值域最著名的連續(xù)值域cspcsp是是線性規(guī)劃線性規(guī)劃問題。問題。線性規(guī)劃線性規(guī)劃中的約束必須是構(gòu)成一個凸多邊形的中的約束必須是構(gòu)成一個凸多邊形的一組線性不等式。一組線性不等式。線性規(guī)劃問題可以在變量個數(shù)的多項式時間內(nèi)線性規(guī)劃問題可以在變量個數(shù)的多項式時間內(nèi)求解。求解。csp問題的分類問題的分類 根據(jù)約束的類型劃

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

8、使如下加法式子成立的數(shù)字，附加的約束條件是最前面的數(shù)能使如下加法式子成立的數(shù)字，附加的約束條件是最前面的數(shù)字不能為字不能為0。高階約束的例子高階約束的例子 算式算式t w o+t w o f o u r f=1。 如不考慮如不考慮o/u有進位：有進位： 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有進位：有進位： r=0, 2, 4, 6, 8，o=5, 6, 7, 8, 9。 若若r=0

9、/o=5(有進位有進位)，則，則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 對應的對應的約束超圖約束超圖如右圖。如右圖。 六個變量互不相等約六個變量互不相等約束可化為兩兩不等約束可化為兩兩不等約束額的二元約束。束額的二元約束。高階約束的例子高階約束的例子各算式約束ftwuorx3x1x2約束：互不相等，兩兩不等每個約束在圖中用方塊表示，每個約束在圖中用方塊表示，連接至它所約束的變量。連接至它所約束的變量。csp問題求解的復雜度問題求解的

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

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

12、中：第在地圖染色約束的賦值過程中：第4行行sa=blue，nsw=red, blue，則，則sa的取值有一個的取值有一個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藍色字體為賦藍色字體為賦值結(jié)果值結(jié)果弧相容算法思想弧相容算法思想1. 用隊列記錄需要檢驗不相容的弧。用隊列記錄需要檢驗不相容的弧。2. 每條弧每條弧xi, xj依次從隊列中刪除并被檢驗。依次從隊列中刪除并被檢驗。如果如果xi值域中的任何一個值需要刪除，則每個值域中的任何一個值需要刪除，則每個指指向向xi的弧的弧xk, xi都必須重新插入隊列進行檢驗。都必須重新插入隊列進行檢驗。 因為指向這個變量的弧可能產(chǎn)生新的不相容（原因為指向這個變量的弧可能產(chǎn)生新的不相容（原來可能

14、就是因為這個值產(chǎn)生了它們之間的相容）。來可能就是因為這個值產(chǎn)生了它們之間的相容）。時間復雜度：時間復雜度：二元二元csp約束至多有約束至多有o(n2)條??；條??； 每每條弧至多插入隊列條弧至多插入隊列d次（次（d個取值），檢驗一條弧為個取值），檢驗一條弧為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弧相容的使用弧相容的使用 弧相容檢驗可以用作開始弧相容檢驗可以用作開始搜索之前搜索之前的的預處理預處理。 弧相容檢驗也可以在弧相容檢驗也可以在搜索過程中搜索過程中每次賦值后用作一個每次賦值后用作一個約束傳播步驟約束傳播步驟。

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

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

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

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

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

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

23、y都存在都存在某個取值滿足某個取值滿足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問題具有一個性質(zhì)：問題具有一個性質(zhì)：可交換性可交換性，變量賦值的，變量賦值的順序?qū)Y(jié)果沒有影響。順序?qū)Y(jié)果沒有影響。 所有所有csp搜索算法生成后繼節(jié)點時，在搜索樹搜索算法生成后繼節(jié)點時，在搜索樹每個節(jié)點上只考慮每個節(jié)點上只考慮單個變

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

25、nswqvt一個簡單的回溯算法一個簡單的回溯算法（深度優(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回溯搜索的通用算法回溯搜索的通用算法 需改善需改善無信息無信息回溯搜索算法的性能?；厮菟阉魉惴ǖ男阅堋?通用改進方法通用改進方法的思路：的思路：下一步該給下一步該給哪個變量哪個變量賦值，按賦值，按什么順序什么順序給該變量給該變量賦值？賦值？每步搜索應該做怎樣的推理？每步搜索應該做怎樣的推理？當前變量的賦值會當前變量的賦值會對其他未賦值變量產(chǎn)生什么約束，怎樣利用這種對其他未賦值變量產(chǎn)生什么約束，怎樣利用這種約束以提高效率。約束以提高效率。當遇到某個失敗的變量賦值時，怎樣當遇到

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

29、序難以產(chǎn)生高效率的搜索。隨機的變量賦值排序難以產(chǎn)生高效率的搜索。 例如：例如：在在wa=red/nt=green條件下選取條件下選取sa賦值比賦值比q要減少賦要減少賦值次數(shù)值次數(shù)(1:2)，并且一旦給定，并且一旦給定sa賦值以后，賦值以后，q、nsw和和v的賦的賦值只有一個選擇。值只有一個選擇。wantsanswqvt因此，應當選擇合法取值最少的變量，即因此，應當選擇合法取值最少的變量，即最少剩余值最少剩余值(mrv)啟啟發(fā)式發(fā)式，也稱為，也稱為最受約束變量最受約束變量啟發(fā)式啟發(fā)式或或失敗優(yōu)先啟發(fā)式失敗優(yōu)先啟發(fā)式。稱為稱為失敗優(yōu)先啟發(fā)式失敗優(yōu)先啟發(fā)式是因為它可以很快找到失敗的變量，從是因為它可

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

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

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

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

34、單的推理形式：最簡單的推理形式：前向檢驗前向檢驗前向檢驗前向檢驗 前向檢驗：前向檢驗：如果如果x被賦值，前向檢驗就是檢查與被賦值，前向檢驗就是檢查與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藍色字體為賦藍色字體為賦值結(jié)果值結(jié)果 賦值賦值v=blue引起矛盾，此時引起矛盾，此

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

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

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

38、變量。 對于對于前向檢驗前向檢驗算法，可以很容易得到?jīng)_突集。算法，可以很容易得到?jīng)_突集。基于基于x x賦值的前向檢驗從變量賦值的前向檢驗從變量y y的值域中刪除一個值時，說的值域中刪除一個值時，說明明x x和和y y存在沖突，則顯然存在沖突，則顯然x x是是y y的沖突集中的一個變量。的沖突集中的一個變量。當?shù)竭_當?shù)竭_y y時，可知回溯到哪個變量。時，可知回溯到哪個變量。 對于對于弧相容檢驗弧相容檢驗，因為都是做取值相容的檢測，只要在弧相，因為都是做取值相容的檢測，只要在弧相容檢驗時增加一個變量集合記錄即可。容檢驗時增加一個變量集合記錄即可。后向跳轉(zhuǎn)后向跳轉(zhuǎn) 問題：問題：后向跳轉(zhuǎn)后向跳轉(zhuǎn)只出現(xiàn)

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

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

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

42、 - xi。 從從xi向前是無解的，從向前是無解的，從xi回到某個以前的變量賦回到某個以前的變量賦值。值。沖突指導的后向跳轉(zhuǎn)沖突指導的后向跳轉(zhuǎn) 例，例，考慮不完全賦值考慮不完全賦值wa=red, nsw=red。 假設(shè)下一個賦值嘗試假設(shè)下一個賦值嘗試t=red，然后給，然后給nt，q，v，sa賦值。賦值。 因為最后四個變量因為最后四個變量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)給每個變量賦值，后初始狀態(tài)給每

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

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 一個用局部搜索解決一個用局部搜索解決csp問題的問題的min-conflicts算法算法。局部搜索算法的表現(xiàn)局部搜索算法的表現(xiàn) miniconflict算法對許多算法對許多cs

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

48、希望以最小改動來修改日程。改動來修改日程。 很容易很容易csp問題轉(zhuǎn)換成問題轉(zhuǎn)換成最優(yōu)化最優(yōu)化問題。這樣，問題。這樣，爬山法、模擬退爬山法、模擬退化和遺傳算法等化和遺傳算法等都可以用來最優(yōu)化目標函數(shù)。都可以用來最優(yōu)化目標函數(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è)一個假設(shè)一個csp問題的變量個數(shù)為問題的變

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

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

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

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