約束滿足問題解析PPT課件

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

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

3、) 二元CSP問題的約束圖： 結(jié)點(diǎn)是變量 連線代表約束 與圖形著色問題相同第9頁/共80頁實(shí)例：實(shí)例：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)第10頁/共80頁實(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 1

4、0 D E，D M，D N 等第11頁/共80頁更多實(shí)例更多實(shí)例 調(diào)度 產(chǎn)品設(shè)計(jì) 資產(chǎn)分配 電路設(shè)計(jì) 受約束機(jī)器人的規(guī)劃 第12頁/共80頁CSP：標(biāo)準(zhǔn)搜索：標(biāo)準(zhǔn)搜索第13頁/共80頁搜索空間搜索空間 狀態(tài)：給出k個(gè)變量賦值，而第k+1,N個(gè)變量未賦值。 后續(xù)態(tài)：通過給第k+1個(gè)變量賦值，而保持其它變量不變，來獲得一個(gè)態(tài)的后續(xù)態(tài)。 始態(tài)： (V1=?,V2=?,V3=?,V4=?,V5=?,V6=?) 終態(tài)：所有變量已賦值，且約束也已滿足。 無任何關(guān)于轉(zhuǎn)換代價(jià)的概念。即，只想找到一個(gè)解，而不擔(dān)心是怎樣找到的。樣本狀態(tài)：(V1=G,V2=B,V3=?,V4=?,V5=?,V6=?)第14頁/共8

5、0頁V1V2V3V4V5V6B?V1V2V3V4V5V6R?V1V2V3V4V5V6G?V1V2V3V4V5V6BB?V1V2V3V4V5V6?壞值值次序：(B,R,G)第15頁/共80頁深度優(yōu)先搜索（深度優(yōu)先搜索（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)第16頁/共80頁DFS 改進(jìn)： 只評(píng)估那些賦值，它們不違反任何與目前已賦值相關(guān)的約束。 不搜索那些明顯

6、不可能通往解的分枝。 預(yù)測(cè)合法的賦值。 控制變量與值的次序。第17頁/共80頁CSP：改進(jìn)：改進(jìn)第18頁/共80頁V1V2V3V4V5V6B?V1V2V3V4V5V6BR?V1V2V3V4V5V6BRRB?V1V2V3V4V5V6BB?V1V2V3V4V5V6?V1V2V3V4V5V6BRRBG?值次序：(B,R,G)第19頁/共80頁回溯回溯DFSV1V2V3V4V5V6B?V1V2V3V4V5V6BR?V1V2V3V4V5V6BRRB?V1V2V3V4V5V6BB?V1V2V3V4V5V6?V1V2V3V4V5V6BRRBG?值次序：(B,R,G)不考慮該樹枝，因?yàn)閂2=B與目前已賦值相關(guān)

7、的約束不符?；厮莸角耙粋€(gè)狀態(tài)，因?yàn)椴荒芙oV6賦合法的值。第20頁/共80頁回溯回溯DFS 對(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)。 一旦找到解，就停止。第21頁/共80頁回溯回溯DFS評(píng)論評(píng)論 額外的計(jì)算：每步都需評(píng)估與當(dāng)前候選賦值(變量=值)相關(guān)的約束。 用預(yù)測(cè)來改進(jìn)不知情搜索： 一個(gè)變量的賦值對(duì)所有其它變量有什么影響？ 下一個(gè)應(yīng)賦值的變量是誰？并且應(yīng)遵循什么次序來評(píng)估值？ 當(dāng)一條路徑失敗，怎樣避免犯同樣錯(cuò)誤？第22頁/共80頁向前查看向前查看

8、對(duì)未賦值的變量，跟蹤余下的合法值。 當(dāng)變量無合法值時(shí)，回溯。V1V2V3V4V5V6R?B?G?值次序：(R,B,G)第23頁/共80頁向前查看向前查看 對(duì)未賦值的變量，跟蹤余下的合法值。 當(dāng)變量無合法值時(shí)，回溯。V1V2V3V4V5V6ROX?XX?B?G?第24頁/共80頁向前查看向前查看 對(duì)未賦值的變量，跟蹤余下的合法值。 當(dāng)變量無合法值時(shí)，回溯。V1V2V3V4V5V6RO?XX?BOX?X?G?第25頁/共80頁向前查看向前查看 對(duì)未賦值的變量，跟蹤余下的合法值。 當(dāng)變量無合法值時(shí)，回溯。V1V2V3V4V5V6ROOXXXBO?X?G?第26頁/共80頁向前查看向前查看 對(duì)未賦值的

9、變量，跟蹤余下的合法值。 當(dāng)變量無合法值時(shí)，回溯。V1V2V3V4V5V6ROOXXBOOXXG?第27頁/共80頁向前查看向前查看 對(duì)未賦值的變量，跟蹤余下的合法值。 當(dāng)變量無合法值時(shí)，回溯。V1V2V3V4V5V6ROOXBOOXGOX無合法值能賦給V6，因此需要回溯第28頁/共80頁約束傳播（約束傳播（CP） 向前查看不檢查所有不一致性，因?yàn)樗荒懿榭茨切┡c該當(dāng)前賦值變量相關(guān)的約束。 能查看得更遠(yuǎn)些嗎？V1V2V3V4V5V6ROOXXBOOXXG?在該處已可看出，此路徑不通向解，因?yàn)橛蛑惺Ｓ嘀翟谫x給V5與V6后不能保持一致性。第29頁/共80頁約束傳播約束傳播V=在搜索的當(dāng)前層次，需賦

10、值的變量。 將D(V)中的一個(gè)值賦給V 對(duì)與V相連的每個(gè)變量V： 去掉D(V )中與已賦值變量不一致的值 對(duì)與V 相連的每個(gè)變量V”： 去掉D(V”)中不再可能的候選值 對(duì)與V” 相連的每個(gè)變量： 直到不再有能被去掉的值為止注：清理D(V )是屬于已有的向前查看清理D(V”)則是屬于新的約束傳播第30頁/共80頁解圖形著色問題的解圖形著色問題的CPPropagate(node, color)1.從node的所有近鄰的值域中去掉color2.對(duì)每個(gè)近鄰N:if 第1步后，D(N)中只剩一種顏色，即D(N)=c：Propagate(N, c)第31頁/共80頁V1V2V3V4V5V6ROX?XX?

11、B?G?在傳播(V1,R)后：第32頁/共80頁V1V2V3V4V5V6ROXXX?BOX?XXG?X?X在傳播(V2,B)后：傳播次序：23546365354第33頁/共80頁注： 在設(shè)置V2后，無需更多搜索，只需一步CP就直接得到一個(gè)解。 一些問題甚至可無需任何搜索，直接由CP來解。V1V2V3V4V5V6ROXXX?BOX?XXG?X?X在傳播(V2,B)后：第34頁/共80頁更一般的更一般的CP：邊一致性：邊一致性A=活躍邊(Vi,Vj)的隊(duì)列 當(dāng)A不空時(shí)，重復(fù)執(zhí)行： (Vi,Vj)A的下一個(gè)組元 對(duì)D(Vi)中每個(gè)x： 如果D(Vj)中無y能使(x,y)滿足Vi,與Vj間的約束，則從

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

13、頁/共80頁CSP啟發(fā)式算法：變量排序啟發(fā)式算法：變量排序1V1V2V3V4V5V6V7R?第39頁/共80頁CSP啟發(fā)式算法：變量排序啟發(fā)式算法：變量排序1 最多約束變量（MCV） 選擇一個(gè)貢獻(xiàn)最多約束數(shù)的變量，會(huì)對(duì)其它變量有極大的影響。因此，有希望修剪掉大部分搜索。 這要求：在約束圖形中找到與最多變量相連接的變量。V1V2V3V4V5V6V7R?變量V5影響5個(gè)變量。變量V2、V3或V4只影響較少的變量。第40頁/共80頁CSP啟發(fā)式算法：變量排序啟發(fā)式算法：變量排序2V1V2V3V4V5V6V7ROXXX?OBO?X?G?第41頁/共80頁CSP啟發(fā)式算法：變量排序啟發(fā)式算法：變量排序2

14、 最少余下值（MRV） 選擇一個(gè)候選值最少的變量，由此，極可能導(dǎo)致一個(gè)早期失?。ㄊ?yōu)先啟發(fā)方式）。V1V2V3V4V5V6V7ROXXX?OBO?X?G?變量V5是最受約束的變量，并且最可能用來剪枝搜索樹。第42頁/共80頁CSP啟發(fā)式算法：值排序啟發(fā)式算法：值排序V1V2V3V4V5V6GR?四種顏色：D=R,G,B,Y第43頁/共80頁CSP啟發(fā)式算法：值排序啟發(fā)式算法：值排序 最少約束值（LCV） 選擇使相鄰變量可用值減少最少的值 優(yōu)先選用最可能的值（也即為隨后的變量賦值提供最大靈活性）來獲得一個(gè)解V1V2V3V4V5V6GR?四種顏色：D=R,G,B,Y要給V3賦哪個(gè)值？第44頁/共

15、80頁CP實(shí)例：白描解釋實(shí)例：白描解釋凹邊凹邊凸邊凸邊?第45頁/共80頁假設(shè)假設(shè) 無陰影 公共面之間無邊 一般觀察點(diǎn) 只考慮三面頂點(diǎn)特殊觀察點(diǎn)一般觀察點(diǎn)不允許的邊第46頁/共80頁3種可能的邊標(biāo)記種可能的邊標(biāo)記 +：凸邊 ：凹邊 ：邊界按規(guī)定，當(dāng)沿著箭頭方向看時(shí)，面在右側(cè)。第47頁/共80頁4種可能的交點(diǎn)類型種可能的交點(diǎn)類型TVYW第48頁/共80頁1+2-3-4-5-第49頁/共80頁 存在34342=208種可能的邊標(biāo)記與交點(diǎn)類型的組合。 例如，在一個(gè)Y交點(diǎn)處，有43種可能的邊標(biāo)記組合。但僅有5種實(shí)際上可能的組合。1+2-3-4-5-第50頁/共80頁第51頁/共80頁CSP形式形式 域

16、D=18種交點(diǎn)構(gòu)形的字典。 約束：連接兩交點(diǎn)的線必須是,+,中的某單一標(biāo)記。 問題：把值賦給所有交點(diǎn)，從而所有邊都被標(biāo)記。 用約束傳播來求解：Waltz標(biāo)記算法。第52頁/共80頁+-+-+-+VYTW 僅有18種可能的交點(diǎn)構(gòu)形 Huffman-Clowes交點(diǎn)字典第53頁/共80頁+-+-+BA+-+CCBDA+-D(B,A)第54頁/共80頁+-+-+BA+-+CCBDA+-D(C,B)第55頁/共80頁+-+-+BA+-+CCBDA+-D(D,C)第56頁/共80頁+-+-+BA+-+CCBDA+-D(A,D)第57頁/共80頁+-+-+BA+-+CCBDA+-D(B,A)第58頁/共8

17、0頁+-+-+BA+-+CCBDA+-D+-第59頁/共80頁標(biāo)記標(biāo)記 擴(kuò)展：處理陰影與切點(diǎn)接觸。有10種交點(diǎn)類型，且大得多的合法構(gòu)形。 關(guān)鍵點(diǎn)：隨邊的增加，計(jì)算呈線性增長。第60頁/共80頁例子：調(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的庫中使用資源。 一個(gè)資源不能同時(shí)被兩項(xiàng)操作使用。 所有的任務(wù)必須在時(shí)間t之前完成。 問題：用離散時(shí)間0,T來安排每項(xiàng)操作的起始時(shí)間Sji。第61頁/共80頁 4項(xiàng)任務(wù) 4個(gè)資源 10項(xiàng)操作第62頁/共80頁優(yōu)先

18、約束：S11+T11S12S12+T12S13.交付約束：S13+T13tS22+T22tS33+T33t.第63頁/共80頁容量約束：S11+T11S21或者S21+T21S11操作(1,1)和(2,1)享用同一資源R1。因此，要么(1,1)在(2,1)之前全部完成，要么(2,1)在(1,1)之前完成。第64頁/共80頁一般的一般的CSP解解 重復(fù)直到所有變量已被賦值為止： 采用一個(gè)一致性實(shí)施程序 向前查看 約束傳播 if 無解： 回溯到前一個(gè)變量 else 選擇下一個(gè)需賦值的變量利用變量排序啟發(fā) 選擇一個(gè)值賦給該變量利用值排序啟發(fā)第65頁/共80頁CSP：樹結(jié)構(gòu)：樹結(jié)構(gòu)CSP第66頁/共8

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

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