【正文】 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。 6 endfor。 2 While Q not empty 3 Select and delete any arc(Vk,Vm) from Q。 7 until not(CHANGE)。 4 for each (Vi, Vj) ? Q do 5 CHANGE ? REVISE(Vi, Vj) ? CHANGE。 11 end REVISE 2022/5/30 史忠植 高級人工智能 37 AC1 1 Q ? 。 7 DELETE ? true。 2022/5/30 史忠植 高級人工智能 34 CONSTRAINT PROPAGATION All of the Mackworth algorithms make use of a Revise procedure. Let Dv be the current domain of v, Let Dw be the current domain of w, Let P be the constraint predicate that holds between v and w, then Revise updates Dv as follows: ? ?? ?yxPDDxD wyvv ,s uc h t ha t :: ???? 2022/5/30 史忠植 高級人工智能 35 CONSTRAINT PROPAGATION Mackworth 1977 AC1 AC2 AC3 2022/5/30 史忠植 高級人工智能 36 約束傳播修改算法 REVISE(Vi,Vj) 1 DELETE ? false。 弧一致性的概念是有向的。 另一種重復的情形 是所謂的弧不一致性 。 存在域中一個值 vi不滿足該約束 。 最簡單的情形是所謂的結點不一致性 。 其原因在于搜索空間中不同路徑的搜索重復相同的失敗子路徑 。 例： Dijkstra的最短路徑算法、 Kruskal的求最小生成樹算法、信號燈問題 2022/5/30 史忠植 高級人工智能 28 回溯算法 有些問題需要徹底的搜索才能解決問題，然而，徹底的搜索要以大量的運算時間為代價，對于這種情況可以通過回溯法來去掉一些分支，從而大大減少搜索的次數。 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 貪心法 貪心法把構造可行解的工作分階段來完成。 算法的時間代價 (或稱 時間復雜性 )：當問題規(guī)模以某種單位由 1增至 n時，對應算法所耗費的時間也以某種單位由 g(1)增至 g(n)，這時我們稱算法的時間代價是 g(n)。人們最關心的就是程序所用算法運行時所要花費的 時間代價 和程序中使用的數據結構占有的 空間代價 。 2022/5/30 史忠植 高級人工智能 23 在實際應用中，算法的表現形式千變萬化，但是算法的情況也和數據結構類似，許多算法的設計思想具有相似之處，我們可以對它們分類進行學習和研究。 COPS系統(tǒng)同時是一個 漸增式的開放系統(tǒng)，用戶能通過類型層次定義，實現新的數據類 型和新的約束關系。內部求解時采用約束推理機制，使說明性約 束表達式與類型層次相結合，實現知識的結構化封裝，充分發(fā)揮