6約束滿足問題解析

1、約束滿足問題（約束滿足問題（CSP）概要概要 CSP定義 標(biāo)準(zhǔn)搜索 方法改進(jìn) 回溯 向前查看 約束傳播 啟發(fā)式算法 變量排序 值排序 CSP實例 樹結(jié)構(gòu)CSP 解CSP的局域搜索CSP：定義：定義范例：圖形著色范例：圖形著色 考慮一個圖形中的N個結(jié)點。 把變量V1,VN的值賦給N個結(jié)點。 值取自R,G,B 約束：如果i與j之間有邊，則Vi與Vj必不同。范例：圖形著色范例：圖形著色CSP定義定義 CSP=V,D,C 變量：V=V1,VN 例如：圖中結(jié)點的值 域：每個變量能取的d個值的集 例如：D=R,G,B 約束：C=C1,CK 每個約束由一組變量與一列該組變量允許取的值組成 例如：(V2,V3

2、),(R,B),(R,G),(B,R),(B,G),(G,R),(G,B) 通常隱式地定義約束，即，定義一個函數(shù)來測試一組變量是否滿足該約束 例如：對每條邊(i,j)，有ViVjCSP定義定義 CSP的解：每個變量有一個滿足所有相關(guān)約束的值 特點： 狀態(tài)的分解表示：一組變量及其值 利用狀態(tài)的結(jié)構(gòu)和通用啟發(fā)方式 通過確定違反約束的變量與值組合可取消大部分搜索空間二元二元CSP 如果變量V與V出現(xiàn)在一個約束中，則它們是有聯(lián)系的。 V近鄰=與V有聯(lián)系的變量。 V域，記為D(V)，為變量V可取值的集。 Di=D(Vi) 二元CSP問題的約束圖： 結(jié)點是變量 連線代表約束 與圖形著色問題相同實例：實例：

3、N個皇后個皇后 變量：Qi 域：Di=1,2,3,4 約束 Qi Qj，即不能在同一行 |Qi Qj| |i j|，即不能在對角上 (Q1,Q2)的合法值是(1,3)，(1,4)，(2,4)，(3,1)，(4,1)，(4,2)實例：密算（實例：密算（Cryptarithmetic）S E N D M O R EM O N E Y 變量：D,E,M,N,O,R,S,Y 域：0,1,2,3,4,5,6,7,8,9 約束 M 0，S 0，單元約束 Y = D E 或Y = D E 10 D E，D M，D N 等更多實例更多實例 調(diào)度 產(chǎn)品設(shè)計 資產(chǎn)分配 電路設(shè)計 受約束機(jī)器人的規(guī)劃 CSP：標(biāo)準(zhǔn)搜

4、索：標(biāo)準(zhǔn)搜索搜索空間搜索空間 狀態(tài)：給出k個變量賦值，而第k+1,N個變量未賦值。 后續(xù)態(tài)：通過給第k+1個變量賦值，而保持其它變量不變，來獲得一個態(tài)的后續(xù)態(tài)。 始態(tài)： (V1=?,V2=?,V3=?,V4=?,V5=?,V6=?) 終態(tài)：所有變量已賦值，且約束也已滿足。 無任何關(guān)于轉(zhuǎn)換代價的概念。即，只想找到一個解，而不擔(dān)心是怎樣找到的。樣本狀態(tài)：(V1=G,V2=B,V3=?,V4=?,V5=?,V6=?)V1V2V3V4V5V6B?V1V2V3V4V5V6R?V1V2V3V4V5V6G?V1V2V3V4V5V6BB?V1V2V3V4V5V6?壞值值次序：(B,R,G)深度優(yōu)先搜索（深度優(yōu)

5、先搜索（DFS） 采用遞歸方式：對D中每個可能值：為后續(xù)態(tài)中的下個未賦值變量賦該值賦值后，評估當(dāng)前態(tài)的后續(xù)態(tài)一旦找到解，就停止V1V2V3V4V5V6B?V1V2V3V4V5V6R?V1V2V3V4V5V6G?V1V2V3V4V5V6BB?V1V2V3V4V5V6?值次序：(B,R,G)DFS 改進(jìn)： 只評估那些賦值，它們不違反任何與目前已賦值相關(guān)的約束。 不搜索那些明顯不可能通往解的分枝。 預(yù)測合法的賦值。 控制變量與值的次序。CSP：改進(jìn)：改進(jìn)V1V2V3V4V5V6B?V1V2V3V4V5V6BR?V1V2V3V4V5V6BRRB?V1V2V3V4V5V6BB?V1V2V3V4V5V6?

6、V1V2V3V4V5V6BRRBG?值次序：(B,R,G)回溯回溯DFSV1V2V3V4V5V6B?V1V2V3V4V5V6BR?V1V2V3V4V5V6BRRB?V1V2V3V4V5V6BB?V1V2V3V4V5V6?V1V2V3V4V5V6BRRBG?值次序：(B,R,G)不考慮該樹枝，因為V2=B與目前已賦值相關(guān)的約束不符?；厮莸角耙粋€狀態(tài)，因為不能給V6賦合法的值?；厮莼厮軩FS 對D中每個可能值x： 如果將x賦給下個未賦值變量Vk+1后，不違反與k個已賦值變量相關(guān)的任何約束： 給Vk+1賦x。 賦值后，評估當(dāng)前態(tài)的后續(xù)態(tài)。 如果找不到合法賦值，則回溯到前一個狀態(tài)。 一旦找到解，就停止

7、?；厮莼厮軩FS評論評論 額外的計算：每步都需評估與當(dāng)前候選賦值(變量=值)相關(guān)的約束。 用預(yù)測來改進(jìn)不知情搜索： 一個變量的賦值對所有其它變量有什么影響？ 下一個應(yīng)賦值的變量是誰？并且應(yīng)遵循什么次序來評估值？ 當(dāng)一條路徑失敗，怎樣避免犯同樣錯誤？向前查看向前查看 對未賦值的變量，跟蹤余下的合法值。 當(dāng)變量無合法值時，回溯。V1V2V3V4V5V6R?B?G?值次序：(R,B,G)向前查看向前查看 對未賦值的變量，跟蹤余下的合法值。 當(dāng)變量無合法值時，回溯。V1V2V3V4V5V6ROX?XX?B?G?向前查看向前查看 對未賦值的變量，跟蹤余下的合法值。 當(dāng)變量無合法值時，回溯。V1V2V3V

8、4V5V6RO?XX?BOX?X?G?向前查看向前查看 對未賦值的變量，跟蹤余下的合法值。 當(dāng)變量無合法值時，回溯。V1V2V3V4V5V6ROOXXXBO?X?G?向前查看向前查看 對未賦值的變量，跟蹤余下的合法值。 當(dāng)變量無合法值時，回溯。V1V2V3V4V5V6ROOXXBOOXXG?向前查看向前查看 對未賦值的變量，跟蹤余下的合法值。 當(dāng)變量無合法值時，回溯。V1V2V3V4V5V6ROOXBOOXGOX無合法值能賦給V6，因此需要回溯約束傳播（約束傳播（CP） 向前查看不檢查所有不一致性，因為它只能查看那些與該當(dāng)前賦值變量相關(guān)的約束。 能查看得更遠(yuǎn)些嗎？V1V2V3V4V5V6ROO

9、XXBOOXXG?在該處已可看出，此路徑不通向解，因為域中剩余值在賦給V5與V6后不能保持一致性。約束傳播約束傳播 V=在搜索的當(dāng)前層次，需賦值的變量。 將D(V)中的一個值賦給V 對與V相連的每個變量V： 去掉D(V )中與已賦值變量不一致的值 對與V 相連的每個變量V”： 去掉D(V”)中不再可能的候選值 對與V” 相連的每個變量： 直到不再有能被去掉的值為止注：清理D(V )是屬于已有的向前查看清理D(V”)則是屬于新的約束傳播解圖形著色問題的解圖形著色問題的CPPropagate(node, color)1. 從node的所有近鄰的值域中去掉color2. 對每個近鄰N:if 第1步后

10、，D(N)中只剩一種顏色，即D(N)=c：Propagate(N, c)V1V2V3V4V5V6ROX?XX?B?G?在傳播(V1,R)后：V1V2V3V4V5V6ROXXX?BOX?XXG?X?X在傳播(V2,B)后：傳播次序：23546365354注： 在設(shè)置V2后，無需更多搜索，只需一步CP就直接得到一個解。 一些問題甚至可無需任何搜索，直接由CP來解。V1V2V3V4V5V6ROXXX?BOX?XXG?X?X在傳播(V2,B)后：更一般的更一般的CP：邊一致性：邊一致性 A=活躍邊(Vi,Vj)的隊列 當(dāng)A不空時，重復(fù)執(zhí)行： (Vi,Vj)A的下一個組元 對D(Vi)中每個x： 如果D

11、(Vj)中無y能使(x,y)滿足Vi,與Vj間的約束，則從D(Vi)中去掉x 如果D(Vi)有改變： 添加所有(Vk,Vi)對到A中，其中Vk (kj) 是Vi的一個近鄰更一般的更一般的CP：k一致性一致性 查看含有k個變量組之間的一致性，而不是變量偶對（邊）之間一致性。 權(quán)衡： CP時間隨k增加而迅速增加 搜索時間隨k增加可能會下降，但可能不會像上面那樣快 完全約束傳播，時間開銷是問題尺寸的指數(shù)CSP：啟發(fā)方式：啟發(fā)方式變量與值的啟發(fā)式算法變量與值的啟發(fā)式算法目前，是以一個固定次序來選擇下一個變量和下一個值。問題：有更好的方法來選擇下一個變量嗎？有更好的方法來選擇下一個賦給當(dāng)前變量的值嗎？C

12、SP啟發(fā)式算法：變量排序啟發(fā)式算法：變量排序1V1V2V3V4V5V6V7R?CSP啟發(fā)式算法：變量排序啟發(fā)式算法：變量排序1 最多約束變量（MCV） 選擇一個貢獻(xiàn)最多約束數(shù)的變量，會對其它變量有極大的影響。因此，有希望修剪掉大部分搜索。 這要求：在約束圖形中找到與最多變量相連接的變量。V1V2V3V4V5V6V7R?變量V5影響5個變量。變量V2、V3或V4只影響較少的變量。CSP啟發(fā)式算法：變量排序啟發(fā)式算法：變量排序2V1V2V3V4V5V6V7ROXXX?OBO?X?G?CSP啟發(fā)式算法：變量排序啟發(fā)式算法：變量排序2 最少余下值（MRV） 選擇一個候選值最少的變量，由此，極可能導(dǎo)致一

13、個早期失?。ㄊ?yōu)先啟發(fā)方式）。V1V2V3V4V5V6V7ROXXX?OBO?X?G?變量V5是最受約束的變量，并且最可能用來剪枝搜索樹。CSP啟發(fā)式算法：值排序啟發(fā)式算法：值排序V1V2V3V4V5V6GR?四種顏色：D=R,G,B,YCSP啟發(fā)式算法：值排序啟發(fā)式算法：值排序 最少約束值（LCV） 選擇使相鄰變量可用值減少最少的值 優(yōu)先選用最可能的值（也即為隨后的變量賦值提供最大靈活性）來獲得一個解V1V2V3V4V5V6GR?四種顏色：D=R,G,B,Y要給V3賦哪個值？CP實例：白描解釋實例：白描解釋凹邊凹邊凸邊凸邊?假設(shè)假設(shè) 無陰影 公共面之間無邊 一般觀察點 只考慮三面頂點特殊觀

14、察點一般觀察點不允許的邊3種可能的邊標(biāo)記種可能的邊標(biāo)記 +：凸邊 ：凹邊 ：邊界按規(guī)定，當(dāng)沿著箭頭方向看時，面在右側(cè)。4種可能的交點類型種可能的交點類型TVYW1+2-3-4-5- 存在34342=208種可能的邊標(biāo)記與交點類型的組合。 例如，在一個Y交點處，有43種可能的邊標(biāo)記組合。但僅有5種實際上可能的組合。1+2-3-4-5-CSP形式形式 域D=18種交點構(gòu)形的字典。 約束：連接兩交點的線必須是,+,中的某單一標(biāo)記。 問題：把值賦給所有交點，從而所有邊都被標(biāo)記。 用約束傳播來求解：Waltz標(biāo)記算法。+-+-+-+VYTW 僅有18種可能的交點構(gòu)形 Huffman-Clowes交點字典

15、+-+-+BA+-+CCBDA+-D(B,A)+-+-+BA+-+CCBDA+-D(C,B)+-+-+BA+-+CCBDA+-D(D,C)+-+-+BA+-+CCBDA+-D(A,D)+-+-+BA+-+CCBDA+-D(B,A)+-+-+BA+-+CCBDA+-D+-標(biāo)記標(biāo)記 擴(kuò)展：處理陰影與切點接觸。有10種交點類型，且大得多的合法構(gòu)形。 關(guān)鍵點：隨邊的增加，計算呈線性增長。例子：調(diào)度例子：調(diào)度 需完成一組N項任務(wù)J1,JN。 每項任務(wù)j是由順序執(zhí)行的一組Lj項操作Oj1,OjLj組成。 每項操作Oji有一個已知的時間段Tji。 操作可能需要從一項有M個資源R1,RM的庫中使用資源。 一個

16、資源不能同時被兩項操作使用。 所有的任務(wù)必須在時間t之前完成。 問題：用離散時間0,T來安排每項操作的起始時間Sji。 4項任務(wù) 4個資源 10項操作優(yōu)先約束：S11+T11S12S12+T12S13.交付約束：S13+T13tS22+T22tS33+T33t.容量約束：S11+T11S21或者S21+T21S11操作(1,1)和(2,1)享用同一資源R1。因此，要么(1,1)在(2,1)之前全部完成，要么(2,1)在(1,1)之前完成。一般的一般的CSP解解 重復(fù)直到所有變量已被賦值為止： 采用一個一致性實施程序 向前查看 約束傳播 if 無解： 回溯到前一個變量 else 選擇下一個需賦值

17、的變量利用變量排序啟發(fā) 選擇一個值賦給該變量利用值排序啟發(fā)CSP：樹結(jié)構(gòu)：樹結(jié)構(gòu)CSP重要特例：約束樹重要特例：約束樹 約束圖形是一棵樹：兩變量由一條路徑相連。 能用變量數(shù)的線性時間來求解。V2V1V4V5V7V3V6V8將變量排序，使得在序列中一個結(jié)點的父結(jié)點總出現(xiàn)在該結(jié)點之前如果父域中所有的值與所有子域中的值相一致，則很容易從樹根開始來選擇一致性的值。根約束樹算法約束樹算法1.由葉向上到根：由葉開始，對每個變量Vi：Vj=parent(Vi)去掉D(Vj)中所有與D(Vi)不一致的值x2.從根向下到葉：給根賦一個值對每個變量Vi：選擇D(Vi)中一個值x，它應(yīng)與賦給parent(Vi)的值

18、是一致的注：由葉向上到根，只訪問每個變量一次：N為去掉不一致值，在最壞場合，需查看每對賦值：d2總時間復(fù)雜性：O(Nd2)類樹類樹 一旦為V6選擇一個值后，約束圖形就變成約束樹。 不知道要選那個值。因此，嘗試所有可能值。更一般場合更一般場合G 去掉由p個變量組成的連接群G，從而把圖形轉(zhuǎn)換成一個可有效求解的樹問題。G稱為循環(huán)割集（cycle cutset） 不知道怎樣為G中變量賦值： 對于每次可能的為G中變量的一致性賦值：將樹算法應(yīng)用于其余變量 總體算法稱為割集調(diào)節(jié)（cutset conditioning）G 去掉由p個變量組成的連接群G，從而把圖形轉(zhuǎn)換成一個可有效求解的樹問題。 G稱為循環(huán)割集 不知道怎樣為G中變量賦值： 對于每次可能的為G中變量的一致性賦值：將樹算法應(yīng)用于其余變量 總體算法稱為割集調(diào)節(jié)（cutset conditioning）注：為實現(xiàn)一次為G中變量的一致性賦值，在最壞場合下，需查看G中所有可能賦值：dp樹算法： (N-p)d2總時間復(fù)雜性：O(