【正文】 高級人工智能 15 約束邏輯程序設計語言 CHIP CHIP(Constrant handling in Prolog) 就是這樣較有影響 一個約束邏輯程序設計語言，其目的是簡便、靈活而有效地解決 一大類組合問題。它通過提供幾種新的計算域而增強邏輯程序設 計的能力；有限域、布爾項及有理項，對于每個計算域，都提供 有效的約束求解技術(shù)，即有限域上的一致性技術(shù)，布爾域的布爾 合一技術(shù)及有理數(shù)域上的單純型法。除此以外， CHIP還包含一個 一般的延遲計算機制。 CHIP 主要應用于兩個領(lǐng)域 : 運籌學與硬件設計。 CHIP 缺乏類型機制，而這種機制對于表達領(lǐng)域概念是極其重 要的。 2022/8/21 史忠植 高級人工智能 16 面向?qū)ο蠹s束語言 COPS COPS系統(tǒng)利用面向?qū)ο蠹夹g(shù)，將說明性約束表達與類型層次 結(jié)合起來。在形式上吸收了常規(guī)語言，主要是面向?qū)ο蟮某绦蛟O 計語言的基本形式。內(nèi)部求解時采用約束推理機制，使說明性約 束表達式與類型層次相結(jié)合，實現(xiàn)知識的結(jié)構(gòu)化封裝，充分發(fā)揮 兩者的優(yōu)點，力圖實現(xiàn)一個具有較強表達能力和較高求解效率的 約束滿足系統(tǒng)。 2022/8/21 史忠植 高級人工智能 17 面向?qū)ο蠹s束語言 COPS COPS的設計考慮了軟件工程的應用要求，盡量將一個不確定問 題確定化：它允許條件語句與循環(huán)語句，而不是單 純以遞歸的形式來實現(xiàn)迭代計算； 通過類方法的重栽實現(xiàn)同一 約束的不同實現(xiàn)，提高了程序的執(zhí)行效率。 COPS系統(tǒng)同時是一個 漸增式的開放系統(tǒng)，用戶能通過類型層次定義，實現(xiàn)新的數(shù)據(jù)類 型和新的約束關(guān)系。約束語言 COPS具有許多人工智能程序設計語 言的特點，如約束傳播、面向目標和數(shù)據(jù)驅(qū)動的問題求解、有限 步的回溯、對象分層中的繼承等。 2022/8/21 史忠植 高級人工智能 18 Exhaustive Search ExhaustiveSearchTop(P) {where P is a CSP of the form(V,D,C)} 1. f:= the null assignment 2. return ExhaustiveSearch(f,P) 2022/8/21 史忠植 高級人工智能 19 Exhaustive Search 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/8/21 史忠植 高級人工智能 20 Backtracking BacktrackingTop(P) 1 f := the null assignment 2 return Backtracking(f,P) 2022/8/21 史忠植 高級人工智能 21 Backtracking Backtracking(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 for each value while answer = Umsat 7 f(v) := x 8 if f satisfies the constraints in P 9 answer := Backtracking(f,P) 10 return answer 2022/8/21 史忠植 高級人工智能 22 Backtracking 盡管回溯法好于生成測試法 ， 但對于非平凡問題仍然是低效的 。 其原因在于搜索空間中不同路徑的搜索重復相同的失敗子路徑 。 一些研究者認為 ， 造成這種反復的原因是所謂的局部不一致性 。 最簡單的情形是所謂的結(jié)點不一致性 。 對一個變量 vi的一個一元約束 。 存在域中一個值 vi不滿足該約束 。 這樣 ， 每當 vi取到 a 時就會出現(xiàn) 不一致性 。 另一種重復的情形 是所謂的弧不一致性 。 2022/8/21 史忠植 高級人工智能 23 CONSTRAINT PROPAGATION ( r e d , g r e e n )( r e d ,b l u e )( r e d , g r e e n ,b l u e ) 弧一致性 Arc consistency 2022/8/21 史忠植 高級人工智能 24 弧一致性 Arc consistency 如果對 vi 的當前域中的所有值 x，存在 vj的當前域中的某值 y使得 vi=x和 vj=y是 vi與 vj之間的約束所允許的，則弧 (vi, vj)是弧一致的。 弧一致性的概念是有向的。即 (vi, vj) 是弧一致的并不自動地意味著 (vj, vi)是一致的。 2022/8/21 史忠植 高級人工智能 25 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/8/21 史忠植 高級人工智能 26 CONSTRAINT PROPAGATION Mackworth 1977 AC1 AC2 AC3 2022/8/21 史忠植 高級人工智能 27 約束傳播修改算法 REVISE(Vi,Vj) 1 DELETE ? false。 2 for each x ? Di do 3 if