【正文】 := Backjumping(f,P) 3 return answer 2022/5/30 史忠植 高級(jí)人工智能 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 史忠植 高級(jí)人工智能 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 史忠植 高級(jí)人工智能 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 史忠植 高級(jí)人工智能 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。 弧一致性的概念是有向的。 存在域中一個(gè)值 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 史忠植 高級(jí)人工智能 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 史忠植 高級(jí)人工智能 27 貪心法 貪心法把構(gòu)造可行解的工作分階段來(lái)完成。人們最關(guān)心的就是程序所用算法運(yùn)行時(shí)所要花費(fèi)的 時(shí)間代價(jià) 和程序中使用的數(shù)據(jù)結(jié)構(gòu)占有的 空間代價(jià) 。 COPS系統(tǒng)同時(shí)是一個(gè) 漸增式的開放系統(tǒng)，用戶能通過(guò)類型層次定義，實(shí)現(xiàn)新的數(shù)據(jù)類 型和新的約束關(guān)系。 2022/5/30 史忠植 高級(jí)人工智能 21 面向?qū)ο蠹s束語(yǔ)言 COPS COPS系統(tǒng)利用面向?qū)ο蠹夹g(shù)，將說(shuō)明性約束表達(dá)與類型層次 結(jié)合起來(lái)。它通過(guò)提供幾種新的計(jì)算域而增強(qiáng)邏輯程序設(shè) 計(jì)的能力；有限域、布爾項(xiàng)及有理項(xiàng)，對(duì)于每個(gè)計(jì)算域，都提供 有效的約束求解技術(shù)，即有限域上的一致性技術(shù)，布爾域的布爾 合一技術(shù)及有理數(shù)域上的單純型法。 2022/5/30 史忠植 高級(jí)人工智能 19 CONSTRAINTS約束語(yǔ)言 CONSTRAINTS 的一個(gè)優(yōu)點(diǎn)是在類型層次中表示約束，用約束 來(lái)表示物理對(duì)象的功能與結(jié)構(gòu)。也有一些取離散值的變量。 作為一個(gè)約束表示語(yǔ)言， 它使用了符號(hào)處理技術(shù)來(lái)求解數(shù)學(xué)方程。 ? 智能回溯與真值維護(hù)。 2022/5/30 史忠植 高級(jí)人工智能 15 約束推理 ? 約束搜索 約束搜索主要研究有限域上的約束滿足。 ? 適合于遞增型系統(tǒng)。 ? 約束表示允許變量的域包含任意多個(gè)值，而不像命題 只取真假二值。 ?約束的布爾組合。 ?序關(guān)系語(yǔ)言，只包含偏序關(guān)系或?qū)嵶兞可系拇笮￡P(guān)系。 一個(gè)變量的值域可能是有限的，例如一個(gè)布爾變量的值 域包含兩個(gè)值；也可能是離散無(wú)限的，如整數(shù)域；也可 能是連續(xù)的，如實(shí)數(shù)域。這是一個(gè)尋求“最優(yōu)化”的題目，目標(biāo) 是節(jié)省總的排隊(duì)時(shí)間，達(dá)到最優(yōu)。他們?cè)鯓优抨?duì)，才能使得總的排隊(duì) 時(shí)間最短。 ?變量表示領(lǐng)域參數(shù)，每個(gè)變量都有一個(gè)固定的值域。 ?一元謂詞。 ?任意系數(shù)的線性方程與不等式。因而具有邏輯表示的類似性質(zhì)。因?yàn)榧s束網(wǎng)絡(luò)上的信息傳播可以認(rèn)為是 同時(shí)的。各種數(shù)學(xué)規(guī)劃技 術(shù)，方程求解技術(shù)等 , 都可以自然地嵌入約束系統(tǒng)。 ? 約束傳播。 2022/5/30 史忠植 高級(jí)人工智能 17 約束語(yǔ)言 CONSTRAINTS CHIP COPS ILOG 2022/5/30 史忠植 高級(jí)人工智能 18 CONSTRAINTS約束語(yǔ)言 CONSTR