6約束滿足問(wèn)題解析

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

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

3、N個(gè)皇后個(gè)皇后 變量：Qi 域：Di=1,2,3,4 約束 Qi Qj，即不能在同一行 |Qi Qj| |i j|，即不能在對(duì)角上 (Q1,Q2)的合法值是(1,3)，(1,4)，(2,4)，(3,1)，(4,1)，(4,2)實(shí)例：密算（實(shí)例：密算（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 等更多實(shí)例更多實(shí)例 調(diào)度 產(chǎn)品設(shè)計(jì) 資產(chǎn)分配 電路設(shè)計(jì) 受約束機(jī)器人的規(guī)劃 CSP：標(biāo)準(zhǔn)搜

4、索：標(biāo)準(zhǔn)搜索搜索空間搜索空間 狀態(tài)：給出k個(gè)變量賦值，而第k+1,N個(gè)變量未賦值。 后續(xù)態(tài)：通過(guò)給第k+1個(gè)變量賦值，而保持其它變量不變，來(lái)獲得一個(gè)態(tài)的后續(xù)態(tài)。 始態(tài)： (V1=?,V2=?,V3=?,V4=?,V5=?,V6=?) 終態(tài)：所有變量已賦值，且約束也已滿足。 無(wú)任何關(guān)于轉(zhuǎn)換代價(jià)的概念。即，只想找到一個(gè)解，而不擔(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） 采用遞歸方式：對(duì)D中每個(gè)可能值：為后續(xù)態(tài)中的下個(gè)未賦值變量賦該值賦值后，評(píng)估當(dāng)前態(tài)的后續(xù)態(tài)一旦找到解，就停止V1V2V3V4V5V6B?V1V2V3V4V5V6R?V1V2V3V4V5V6G?V1V2V3V4V5V6BB?V1V2V3V4V5V6?值次序：(B,R,G)DFS 改進(jìn)： 只評(píng)估那些賦值，它們不違反任何與目前已賦值相關(guān)的約束。 不搜索那些明顯不可能通往解的分枝。 預(yù)測(cè)合法的賦值。 控制變量與值的次序。CSP：改進(jìn)：改進(jìn)V1V2V3V4V5V6B?V1V2V3V4V5V6BR?V1V2V3V4V5V6BRRB?V1V2V3V4V5V6BB?V1V2V3V4V5V6?

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

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

8、4V5V6RO?XX?BOX?X?G?向前查看向前查看 對(duì)未賦值的變量，跟蹤余下的合法值。 當(dāng)變量無(wú)合法值時(shí)，回溯。V1V2V3V4V5V6ROOXXXBO?X?G?向前查看向前查看 對(duì)未賦值的變量，跟蹤余下的合法值。 當(dāng)變量無(wú)合法值時(shí)，回溯。V1V2V3V4V5V6ROOXXBOOXXG?向前查看向前查看 對(duì)未賦值的變量，跟蹤余下的合法值。 當(dāng)變量無(wú)合法值時(shí)，回溯。V1V2V3V4V5V6ROOXBOOXGOX無(wú)合法值能賦給V6，因此需要回溯約束傳播（約束傳播（CP） 向前查看不檢查所有不一致性，因?yàn)樗荒懿榭茨切┡c該當(dāng)前賦值變量相關(guān)的約束。 能查看得更遠(yuǎn)些嗎？V1V2V3V4V5V6ROO

9、XXBOOXXG?在該處已可看出，此路徑不通向解，因?yàn)橛蛑惺Ｓ嘀翟谫x給V5與V6后不能保持一致性。約束傳播約束傳播 V=在搜索的當(dāng)前層次，需賦值的變量。 將D(V)中的一個(gè)值賦給V 對(duì)與V相連的每個(gè)變量V： 去掉D(V )中與已賦值變量不一致的值 對(duì)與V 相連的每個(gè)變量V”： 去掉D(V”)中不再可能的候選值 對(duì)與V” 相連的每個(gè)變量： 直到不再有能被去掉的值為止注：清理D(V )是屬于已有的向前查看清理D(V”)則是屬于新的約束傳播解圖形著色問(wèn)題的解圖形著色問(wèn)題的CPPropagate(node, color)1. 從node的所有近鄰的值域中去掉color2. 對(duì)每個(gè)近鄰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后，無(wú)需更多搜索，只需一步CP就直接得到一個(gè)解。 一些問(wèn)題甚至可無(wú)需任何搜索，直接由CP來(lái)解。V1V2V3V4V5V6ROXXX?BOX?XXG?X?X在傳播(V2,B)后：更一般的更一般的CP：邊一致性：邊一致性 A=活躍邊(Vi,Vj)的隊(duì)列 當(dāng)A不空時(shí)，重復(fù)執(zhí)行： (Vi,Vj)A的下一個(gè)組元 對(duì)D(Vi)中每個(gè)x： 如果D

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

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

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

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

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ò)展：處理陰影與切點(diǎn)接觸。有10種交點(diǎn)類(lèi)型，且大得多的合法構(gòu)形。 關(guān)鍵點(diǎn)：隨邊的增加，計(jì)算呈線性增長(zhǎng)。例子：調(diào)度例子：調(diào)度 需完成一組N項(xiàng)任務(wù)J1,JN。 每項(xiàng)任務(wù)j是由順序執(zhí)行的一組Lj項(xiàng)操作Oj1,OjLj組成。 每項(xiàng)操作Oji有一個(gè)已知的時(shí)間段Tji。 操作可能需要從一項(xiàng)有M個(gè)資源R1,RM的庫(kù)中使用資源。 一個(gè)

16、資源不能同時(shí)被兩項(xiàng)操作使用。 所有的任務(wù)必須在時(shí)間t之前完成。 問(wèn)題：用離散時(shí)間0,T來(lái)安排每項(xiàng)操作的起始時(shí)間Sji。 4項(xiàng)任務(wù) 4個(gè)資源 10項(xiàng)操作優(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ù)直到所有變量已被賦值為止： 采用一個(gè)一致性實(shí)施程序 向前查看 約束傳播 if 無(wú)解： 回溯到前一個(gè)變量 else 選擇下一個(gè)需賦值

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

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