【正文】 := Backjumping(f,P) 3 return answer 2022/5/30 史忠植 高級人工智能 40 Backjumping Backjumping(f,P) 1 if f is a total assignment of the variables in P 2 answer := f,? 3 else 4 v := some variable in P that is not yet assigned a value by f 5 answer := Unsat 6 conflictset := ? 7 for each value 8 f(v) := x 9 if f satisfies the constraints in P 10 answer, newconflicts := Backjumping(f,P) 2022/5/30 史忠植 高級人工智能 41 Backjumping 11 else 12 newconflicts := the set of variables in a violated constraint 13 if answer ? Unsat 14 return answer, ? 15 else if v ? newconflicts 16 return Unsat, newconflicts 17 else 18 conflictset := conflictset ? (newconflicts {v}) 19 return Unsat, conflictset 2022/5/30 史忠植 高級人工智能 42 COPS Constraint : predicate expression P(t1, ..., tn) where P is built in function, such as sum times eq(equal) neq(not equal) ge(great than or equal to) gt(great than) also can be defined by users 2022/5/30 史忠植 高級人工智能 43 COPS Conditional constraint condition1: constraint1。 2 While Q not empty 3 Select and delete any arc(Vk,Vm) from Q。 4 for each (Vi, Vj) ? Q do 5 CHANGE ? REVISE(Vi, Vj) ? CHANGE。 7 DELETE ? true。 弧一致性的概念是有向的。 存在域中一個值 vi不滿足該約束 。 其原因在于搜索空間中不同路徑的搜索重復(fù)相同的失敗子路徑 。 ExhaustiveSearchTop(P) {where P is a CSP of the form(V,D,C)} 1. f:= the null assignment 2. return ExhaustiveSearch(f,P) 2022/5/30 史忠植 高級人工智能 26 窮盡搜索方法 ExhaustiveSearch(f,P) 1. if f is a total assignment of the variables in P 2. if f satisfies the constraints in P 3. answer := f 4. else 5. answer := Unsat 6. else 7. v := some variable in P that is not yet assigned a value by f 8. answer := Unsat 9. for each value while answer = Unsat 10. f(v) := 11. answer := ExhaustiveSearch(f,P) 12. return answer 2022/5/30 史忠植 高級人工智能 27 貪心法 貪心法把構(gòu)造可行解的工作分階段來完成。人們最關(guān)心的就是程序所用算法運行時所要花費的 時間代價 和程序中使用的數(shù)據(jù)結(jié)構(gòu)占有的 空間代價 。 COPS系統(tǒng)同時是一個 漸增式的開放系統(tǒng)，用戶能通過類型層次定義，實現(xiàn)新的數(shù)據(jù)類 型和新的約束關(guān)系。 2022/5/30 史忠植 高級人工智能 21 面向?qū)ο蠹s束語言 COPS COPS系統(tǒng)利用面向?qū)ο蠹夹g(shù)，將說明性約束表達與類型層次 結(jié)合起來。它通過提供幾種新的計算域而增強邏輯程序設(shè) 計的能力；有限域、布爾項及有理項，對于每個計算域，都提供 有效的約束求解技術(shù)，即有限域上的一致性技術(shù)，布爾域的布爾 合一技術(shù)及有理數(shù)域上的單純型法。 2022/5/30 史忠植 高級人工智能 19 CONSTRAINTS約束語言 CONSTRAINTS 的一個優(yōu)點是在類型層次中表示約束，用約束 來表示物理對象的功能與結(jié)構(gòu)。也有一些取離散值的變量。 作為一個約束表示語言， 它使用了符號處理技術(shù)來求解數(shù)學(xué)方程。 ? 智能回溯與真值維護。 2022/5/30 史忠植 高級人工智能 15 約束推理 ? 約束搜索 約束搜索主要研究有限域上的約束滿足。 ? 適合于遞增型系統(tǒng)。 ? 約束表示允許變量的域包含任意多個值，而不像命題 只取真假二值。 ?約束的布爾組合。 ?序關(guān)系語言，只包含偏序關(guān)系或?qū)嵶兞可系拇笮￡P(guān)系。 一個變量的值域可能是有限的，例如一個布爾變量的值 域包含兩個值；也可能是離散無限的，如整數(shù)域；也可 能是連續(xù)的，如實數(shù)域。這是一個尋求“最優(yōu)化”的題目，目標 是節(jié)省總的排隊時間，達到最優(yōu)。他們怎樣排隊，才能使得總的排隊 時間最短。 ?變量表示領(lǐng)域參數(shù)，每個變量都有一個固定的值域。 ?一元謂詞。 ?任意系數(shù)的線性方程與不等式。因而具有邏輯表示的類似性質(zhì)。因為約束網(wǎng)絡(luò)上的信息傳播可以認為是 同時的。各種數(shù)學(xué)規(guī)劃技 術(shù)，方程求解技術(shù)等 , 都可以自然地嵌入約束系統(tǒng)。 ? 約束傳播。 2022/5/30 史忠植 高級人工智能 17 約束語言 CONSTRAINTS CHIP COPS ILOG 2022/5/30 史忠植 高級人工智能 18 CONSTRAINTS約束語言 CONSTR