第3章_約束推理

1、2024/4/2,史忠植 高級(jí)人工智能,1,高級(jí)人工智能,第三章 約束推理,Advanced Artificial Intelligence,史忠植 中國科學(xué)院計(jì)算技術(shù)研究所,2024/4/2,史忠植 高級(jí)人工智能,2,第三章 約束推理,3.1 概述3.2 回溯法 3.3 約束傳播 3.4 回跳法 3.5 約束推理系統(tǒng)COPS 3.6 ILOG SOLVER,2024/4/2,史忠植

2、 高級(jí)人工智能,3,3.1 概 述,最優(yōu)化問題 經(jīng)濟(jì)學(xué)所推崇的帕累托最優(yōu): 幾個(gè)人拎著水桶在一個(gè)水龍頭前面排隊(duì)打水，水桶有大有小。他們?cè)鯓优抨?duì)，才能使得總的排隊(duì)時(shí)間最短。這是一個(gè)尋求“最優(yōu)化”的題目，目標(biāo)是節(jié)省總的排隊(duì)時(shí)間，達(dá)到最優(yōu)。,2024/4/2,史忠植 高級(jí)人工智能,4,3.1 概 述,優(yōu)化問題 ? 運(yùn)籌學(xué)? 遺傳算法? 神經(jīng)網(wǎng)絡(luò)? 約束推理,2024/4/2,史忠植

3、 高級(jí)人工智能,5,運(yùn)籌學(xué)的工作步驟,1）提出和形成問題，2）建立模型，3）求解，4）解的檢驗(yàn)，5）解的控制，6）解的實(shí)施。,,2024/4/2,史忠植 高級(jí)人工智能,6,線性規(guī)劃問題,例1(廣告方式的選擇) 中華家電公司推銷一種新型洗衣機(jī)，有關(guān)數(shù)據(jù)見下表。銷售部第一月的廣告預(yù)算為20000元，要求至少有8個(gè)電視商業(yè)節(jié)目，15家報(bào)紙廣告；電視廣告費(fèi)不得超過12000元，電臺(tái)廣播至少隔日有一次?，F(xiàn)問該公司銷售部

4、應(yīng)當(dāng)采用怎樣的廣告宣傳計(jì)劃，才能取得最好的效果?,2024/4/2,史忠植 高級(jí)人工智能,7,線性規(guī)劃問題,,表1 中華家電公司推銷新型洗衣機(jī)廣告方式選擇的數(shù)據(jù)表,2024/4/2,史忠植 高級(jí)人工智能,8,線性規(guī)劃問題,,解：設(shè)x1, x2, x3, x4, x5分別是第一個(gè)月內(nèi)電視臺(tái)a，電視臺(tái)b，每日晨報(bào)，星期日?qǐng)?bào)，廣播電臺(tái)進(jìn)行廣告宣傳的次數(shù)，則其數(shù)學(xué)模型為 max 50x1+80x2+30x3

5、+ 40x4+15x5,s.t. 50x1+80x2+30x3+ 40x4+15x5 ≤20000， x1+x2≥8， x3+ x4 ≥15， 500x1+1000x2≤12000， x1≤16, x2≤10, x3 ≤24, x4≤4, 15≤x5≤25, x1, x2, x3, x4, x5 ≥0。,,2024/4/2,史忠植 高級(jí)人工智能,9,線性規(guī)劃問

6、題,,線性規(guī)劃問題(LP)的一般形式為：,min(max) z= c1x1+c2x2+ … +cnxn,s.t. a11x1+a12x2+…+ a1nxn≤(≥,＝ )b1 a21x1+a22x2+…+a2nxn≤ (≥,＝ )b2 … am1x1+am2x2+…+amnxn≤ (≥,＝)bm,xj≥0, j=1,2,…,n,2024/4/2,史忠植 高級(jí)人工智

7、能,10,線性規(guī)劃問題,,線性規(guī)劃問題的標(biāo)準(zhǔn)形式為：,min,,,注：任何形式的線性規(guī)劃問題均可化為標(biāo)準(zhǔn)型。,,,AX=bs.t. X≥0 (假定b為非負(fù)),,2024/4/2,史忠植 高級(jí)人工智能,11,求解--單純形法,將所給問題化為標(biāo)準(zhǔn)形找出一個(gè)初始可行基，建立初始單純形表檢查所有檢驗(yàn)數(shù)(若全為非負(fù)，則已得到最優(yōu)解,計(jì)算停止。否則繼續(xù)下一步)考察是否無解(若是，計(jì)算停止，否則繼續(xù)下一步)確定入基變量，出基變量對(duì)

8、初始單純形表進(jìn)行單純形變換,,,2024/4/2,史忠植 高級(jí)人工智能,12,3.1 概 述,一個(gè)約束(Constraint)通常是指一個(gè)包含若干變量的關(guān)系表達(dá)式，用以表示這些變量所必須滿足的問題。 ? 約束表示廣泛地應(yīng)用于人工智能的各個(gè)領(lǐng)域，包括定性推理、機(jī)械與電子設(shè)備的設(shè)計(jì)與分析等。 ? 約束滿足系統(tǒng)的設(shè)計(jì)是一項(xiàng)困難而復(fù)雜的任務(wù)，因?yàn)榧s束滿足問題在一般情況下是一個(gè)NP (Nonpolynomia)問題，所以必

9、須使用各種策略與啟發(fā)式信息。,2024/4/2,史忠植 高級(jí)人工智能,13,3.1 概 述,一個(gè)約束滿足問題(Constraint Satisfaction Problem, 簡稱CSP) 包含一組變量與一組變量間的約束。 ? 變量表示領(lǐng)域參數(shù)，每個(gè)變量都有一個(gè)固定的值域。 一個(gè)變量的值域可能是有限的，例如一個(gè)布爾變量的值域包含兩個(gè)值；也可能是離散無限的，如整數(shù)域；也可能是連續(xù)的，如實(shí)數(shù)域。

10、 { x1, x2, …, xn }, { D1, D2,…, Dn }, . { 4, 5, 6, 7 } { red, green, blue },2024/4/2,史忠植 高級(jí)人工智能,14,3.1 概 述,? 約束可用于描述領(lǐng)域?qū)ο蟮男再|(zhì)、相互關(guān)系、任務(wù)要求、目標(biāo)等。約束滿足問題的目標(biāo)就是找到所有變量的一個(gè)（或多個(gè)）賦值，使所有約束都得到滿足。,? 現(xiàn)

11、有的約束表示可分為幾類，按復(fù)雜性的次序列舉如下： ? 一元謂詞。 ? 序關(guān)系語言，只包含偏序關(guān)系或?qū)嵶兞可系拇笮￡P(guān)系。 ? 形如“x - y > c”或 “x - y ≥ c”的方程。 ? 單位系數(shù)的線性方程與不等式，即所有的系數(shù)為-1,0,1。 ? 任意系數(shù)的線性方程與不等式。 ? 約束的布爾組合。 ? 代數(shù)與三角方程。,2024/4/2,史忠植 高級(jí)人工智能,15,3.1 概

12、述,約束表示易于理解、編碼及有效實(shí)現(xiàn)，具有以下優(yōu)點(diǎn): 約束表示允許以說明性的方式來表達(dá)領(lǐng)域知識(shí)，表達(dá)能力較強(qiáng)，應(yīng)用程序只需指定問題的目標(biāo)條件及數(shù)據(jù)間的相互關(guān)系。因而具有邏輯表示的類似性質(zhì)。 約束表示允許變量的域包含任意多個(gè)值，而不像命題只取真假二值。它保存了問題的一些結(jié)構(gòu)信息，如變量域的大小、變量間的相關(guān)性等，從而為問題求解提供啟發(fā)式信息。 易于并行實(shí)現(xiàn)。因?yàn)榧s束網(wǎng)絡(luò)上的信息傳播可以認(rèn)為是同時(shí)的。? 適合于遞增型系統(tǒng)。約束可以遞

13、增式地加入到約束網(wǎng)絡(luò)。 易于與領(lǐng)域相關(guān)的問題求解模型相銜接。各種數(shù)學(xué)規(guī)劃技術(shù)，方程求解技術(shù)等, 都可以自然地嵌入約束系統(tǒng)。,2024/4/2,史忠植 高級(jí)人工智能,16,3.1 概 述,目前，約束推理的研究主要集中于兩個(gè)方面：約束搜索與約束語言。 約束搜索主要研究有限域上的約束滿足。對(duì)有限域而言，約束滿足問題一般情況下是一個(gè)NP問題。大體包括下列方法： ① 回溯法； ② 約束傳播；

14、 ③ 智能回溯與真值維護(hù)； ④ 可變次序例示； ⑤ 局部修正法；,2024/4/2,史忠植 高級(jí)人工智能,17,3.1 概 述,約束推理研究的另一個(gè)主要方面是約束語言。以下是幾個(gè)比較典型的約束語言： ⑴ CONSTRAINTS：面向電路描述的約束表示語言。 ⑵ Bertrand：Leler開發(fā)的一個(gè)高級(jí)約束語言。 ⑶ CHIP：約束邏輯程序設(shè)計(jì)語言。 ⑷ 約束層次

15、與HCLP：層次型約束邏輯程序設(shè)計(jì)語言。 ⑸ COPS：面向?qū)ο蟮某绦蛟O(shè)計(jì)語言的基本形式。 ⑹ ILOG ：使用建模語言來表示約束問題。,2024/4/2,史忠植 高級(jí)人工智能,18,CONSTRAINTS約束語言,CONSTRAINTS是一個(gè)面向電路描述的約束表示語言。作為一個(gè)約束表示語言，它使用了符號(hào)處理技術(shù)來求解數(shù)學(xué)方程。 在CONSTRAITS中，物理部件的功能及器件的結(jié)構(gòu)都用約束表示。

16、 這些約束一般是線性方程與不等式, 也包括條件表達(dá)式。約束變量一般是表示物理量的實(shí)變量。也有一些取離散值的變量。如開關(guān)的狀態(tài)、三極管的工作狀態(tài)等。系統(tǒng)采用表達(dá)式推理與值推理。并實(shí)現(xiàn)相關(guān)制導(dǎo)的回溯。,2024/4/2,史忠植 高級(jí)人工智能,19,CONSTRAINTS約束語言,CONSTRAINTS的一個(gè)優(yōu)點(diǎn)：在類型層次中表示約束，用約束來表示物理對(duì)象的功能與結(jié)構(gòu)。缺點(diǎn)：是該語言缺乏類似于面向?qū)ο笳Z言中的方法那樣的成

17、分，不能定義特定于某個(gè)類的概念。 同時(shí)，約束傳播方法比較單一，既缺乏實(shí)域上的區(qū)間傳播機(jī)制，也缺乏有限域上的 域傳播機(jī)制。,2024/4/2,史忠植 高級(jí)人工智能,20,約束邏輯程序設(shè)計(jì)語言CHIP,CHIP(Constraint handling in Prolog) 就是這樣較有影響一個(gè)約束邏輯程序設(shè)計(jì)語言，其目的是簡便、靈活而有效地解決一大類組合問題。它通過提供幾種新的計(jì)算域而增強(qiáng)邏輯程序設(shè)計(jì)的能力；有限域、布爾項(xiàng)及有

18、理項(xiàng)，對(duì)于每個(gè)計(jì)算域，都提供有效的約束求解技術(shù)，即有限域上的一致性技術(shù)，布爾域的布爾合一技術(shù)及有理數(shù)域上的單純型法。除此以外，CHIP還包含一個(gè)一般的延遲計(jì)算機(jī)制。 CHIP 主要應(yīng)用于兩個(gè)領(lǐng)域：運(yùn)籌學(xué)與硬件設(shè)計(jì)。 CHIP 缺乏類型機(jī)制，而這種機(jī)制對(duì)于表達(dá)領(lǐng)域概念是極其重要的。,2024/4/2,史忠植 高級(jí)人工智能,21,面向?qū)ο蠹s束語言COPS,COPS系統(tǒng)利用面向?qū)ο蠹夹g(shù)，將說明性約束表達(dá)與

19、類型層次結(jié)合起來。在形式上吸收了常規(guī)語言，主要是面向?qū)ο蟮某绦蛟O(shè)計(jì)語言的基本形式。內(nèi)部求解時(shí)采用約束推理機(jī)制，使說明性約束表達(dá)式與類型層次相結(jié)合，實(shí)現(xiàn)知識(shí)的結(jié)構(gòu)化封裝，充分發(fā)揮兩者的優(yōu)點(diǎn)，力圖實(shí)現(xiàn)一個(gè)具有較強(qiáng)表達(dá)能力和較高求解效率的約束滿足系統(tǒng)。,2024/4/2,史忠植 高級(jí)人工智能,22,面向?qū)ο蠹s束語言COPS,COPS的設(shè)計(jì)考慮了軟件工程的應(yīng)用要求，盡量將一個(gè)不確定問題確定化：它允許條件語句與循環(huán)語句，而不是單純以遞歸的形

20、式來實(shí)現(xiàn)迭代計(jì)算； 通過類方法的重栽實(shí)現(xiàn)同一約束的不同實(shí)現(xiàn)，提高了程序的執(zhí)行效率。COPS系統(tǒng)同時(shí)是一個(gè)漸增式的開放系統(tǒng)，用戶能通過類型層次定義，實(shí)現(xiàn)新的數(shù)據(jù)類型和新的約束關(guān)系。約束語言COPS具有許多人工智能程序設(shè)計(jì)語言的特點(diǎn)，如約束傳播、面向目標(biāo)和數(shù)據(jù)驅(qū)動(dòng)的問題求解、有限步的回溯、對(duì)象分層中的繼承等。,2024/4/2,史忠植 高級(jí)人工智能,23,常用的算法,在實(shí)際應(yīng)用中，算法的表現(xiàn)形式千變?nèi)f化，但是算法的情況也和數(shù)據(jù)結(jié)構(gòu)類似

21、，許多算法的設(shè)計(jì)思想具有相似之處，我們可以對(duì)它們分類進(jìn)行學(xué)習(xí)和研究。 常用的算法大致有如下一些： 貪心法 分治法（如二分法檢索） 回溯法 動(dòng)態(tài)規(guī)劃法 局部搜索法 分支限界法,2024/4/2,史忠植 高級(jí)人工智能,24,算法分析,評(píng)價(jià)一個(gè)程序優(yōu)劣的重要依據(jù)是看這個(gè)程序的執(zhí)行需要占用多少機(jī)器資源。人們最關(guān)心的就是程序所用算法運(yùn)行時(shí)所要花費(fèi)的時(shí)間代價(jià)和程序中使用的數(shù)據(jù)結(jié)構(gòu)占有的空間代價(jià)。 算法的空間代價(jià)(

22、或稱空間復(fù)雜性)：當(dāng)被解決問題的規(guī)模(以某種單位計(jì)算)由1增至n時(shí)，解該問題的算法所需占用的空間也以某種單位由f(1) 增至f(n)，這時(shí)我們稱該算法的空間代價(jià)是f(n)。 算法的時(shí)間代價(jià)(或稱時(shí)間復(fù)雜性)：當(dāng)問題規(guī)模以某種單位由1增至n時(shí)，對(duì)應(yīng)算法所耗費(fèi)的時(shí)間也以某種單位由g(1)增至g(n)，這時(shí)我們稱算法的時(shí)間代價(jià)是g(n)。,2024/4/2,史忠植 高級(jí)人工智能,25,窮盡搜索方法,窮盡搜索方法

23、 即產(chǎn)生所有可能的樹，然后根據(jù)評(píng)價(jià)標(biāo)準(zhǔn)選擇一棵最優(yōu)的樹。 Exhaustive-Search-Top(P) {where P is a CSP of the form(V,D,C)}1. f:= the null assignment2. return Exhaustive-Search(f,P),2024/4/2,史忠植 高級(jí)人工智能,26,窮盡搜索方法,Exhaustive-Search(f,

24、P)1. if f is a total assignment of the variables in P2. if f satisfies the constraints in P3. answer := f4. else 5. answer := Unsat6. else 7. v :=

25、some variable in P that is not yet assigned a value by f8. answer := Unsat9. for each value while answer = Unsat10. f(v) := x11. answer := Exhaustive-Search(f,P)12.

26、 return answer,2024/4/2,史忠植 高級(jí)人工智能,27,貪 心 法,貪心法把構(gòu)造可行解的工作分階段來完成。在各個(gè)階段，選擇那些在某些意義下是局部最優(yōu)的方案，期望各階段的局部最優(yōu)的選擇帶來整體最優(yōu)。例：Dijkstra的最短路徑算法、Kruskal的求最小生成樹算法、信號(hào)燈問題,2024/4/2,史忠植 高級(jí)人工智能,28,3.2 回 溯 法,有些問題需要徹底的搜索才能解決問題，然而，徹底的搜索要

27、以大量的運(yùn)算時(shí)間為代價(jià)，對(duì)于這種情況可以通過回溯法來去掉一些分支，從而大大減少搜索的次數(shù)。 八皇后問題 迷宮問題 深度優(yōu)先周游樹或圖,2024/4/2,史忠植 高級(jí)人工智能,29,3.2 Backtracking Algorithm,Based on depth-first recursive searchApproachTests whether solution has been foundIf found sol

28、ution, return itElse for each choice that can be madeMake that choiceRecurIf recursion returns a solution, return itIf no choices remain, return failureSome times called “search tree”,,2024/4/2,史忠植 高級(jí)人工智能,30,3.2

29、 Solution to 8-Queens Puzzle,八皇后問題，是一個(gè)古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8×8格的國際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。 高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法解出92種結(jié)果。計(jì)算機(jī)發(fā)明后，有多種方法

30、可以解決此問題。,2024/4/2,史忠植 高級(jí)人工智能,31,4-Queens Puzzle,2024/4/2,史忠植 高級(jí)人工智能,32,4-Queens Tree,2024/4/2,史忠植 高級(jí)人工智能,33,3.2 回 溯 法,Backtracking-Top(P)1 f := the null assignment2 return Backtracking(f,P),2024/4/2,史忠植

31、 高級(jí)人工智能,34,3.2 回溯法,Backtracking(f,P)1 if f is a total assignment of the variables in P2 answer := f3 else 4 v := some variable in P that is not yet assigned a value by f5 answer :=

32、 Unsat6 for each value while answer = Umsat7 f(v) := x8 if f satisfies the constraints in P9 answer := Backtracking(f,P)10 return answer,2024/4/2

33、,史忠植 高級(jí)人工智能,35,3.2 回溯法,盡管回溯法好于生成測試法，但對(duì)于非平凡問題仍然是低效的。其原因在于搜索空間中不同路徑的搜索重復(fù)相同的失敗子路徑。一些研究者認(rèn)為，造成這種反復(fù)的原因是所謂的局部不一致性。最簡單的情形是所謂的結(jié)點(diǎn)不一致性。對(duì)一個(gè)變量vi的一個(gè)一元約束。存在域中一個(gè)值vi不滿足該約束。這樣，每當(dāng)vi取到 a 時(shí)就會(huì)出現(xiàn)不一致性。 另一種重復(fù)的情形是所謂的弧不一致性。,2024/4/2,史忠植

34、 高級(jí)人工智能,36,3.3 約束傳播,如果對(duì)vi 的當(dāng)前域中的所有值x，存在vj的當(dāng)前域中的某值y使得 vi=x和vj=y是vi與vj之間的約束所允許的，則弧(vi, vj)是弧一致的。 弧一致性的概念是有向的。即(vi, vj)是弧一致的并不自動(dòng)地意味著(vj, vi)是一致的。,2024/4/2,史忠植 高級(jí)人工智能,37,3.3 約束傳播CONSTRAINT PROPAGATION,,,,弧一致性

35、（Arc consistency）,2024/4/2,史忠植 高級(jí)人工智能,38,3.3 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, Le

36、t P be the constraint predicate that holds between v and w, then Revise updates Dv as follows:,Dv:={x?Dv.?y?Dw such that P(x,y)},2024/4/2,史忠植 高級(jí)人工智能,39,3.3 CONSTRAINT PROPAGATION,Mackworth 1977 AC-1 AC-2

37、 AC-3,2024/4/2,史忠植 高級(jí)人工智能,40,約束傳播修改算法,procedure REVISE(Vi, Vj)1 DELETE ? false;2 for each x ? Di do 3 if there is no such yj ? Dj4such that(x, yj) is consistent,5 then 6 del

38、ete x from Di;7 DELETE ? true;8 endif 9 endfor 10 return DELETE; 11 end REVISE,2024/4/2,史忠植 高級(jí)人工智能,41,約束傳播AC-1算法,procedure AC-11 Q ? {(Vi,Vj)?arcs(G), i?j};2 repeat 3

39、 CHANGE ? false;4 for each (Vi, Vj) ? Q do5 CHANGE ? REVISE(Vi, Vj)?CHANGE;6 endfor;7 until not(CHANGE);8 end AC-1,2024/4/2,史忠植 高級(jí)人工智能,42,約束傳播AC-3算法,procedure AC-31 Q ?{(Vi,Vj) ?arcs(G), i?j};2

40、 while Q not empty 3 select and delete any arc(Vk,Vm) from Q;4 if (REVISE(Vk,Vm)) then Q?{(Vi,Vk) such that (Vi,Vk)?arcs(G), i?k, i?m};6 endif;7 endwhile;8 en

41、d AC-3,2024/4/2,史忠植 高級(jí)人工智能,43,回跳法Backjumping,Backjumping-Top(P)1 f := the null assignment2 := Backjumping(f,P)3 return answer,2024/4/2,史忠植 高級(jí)人工智能,44,Backjumping,Backjumping(f,P)1 if f is a total as

42、signment of the variables in P2 answer := 3 else 4 v:=some variable in P that is not yet assigned a value by f5 answer := Unsat6 conflict-set := ?7 for each value 8

43、 f(v) := x9 if f satisfies the constraints in P10 := Backjumping(f,P),2024/4/2,史忠植 高級(jí)人工智能,45,Backjumping,11 else12 new-conflicts := the set of va

44、riables in a violated constraint13 if answer ? Unsat14 return 15 else if v ? new-conflicts16

45、 return 17 else18 conflict-set:=conflict-set?(new-conflicts{v}) 19 return ,2024/4/2,史忠植 高級(jí)人工智能,

46、46,3.11 約束推理系統(tǒng)COPS,1. 約束與規(guī)則 約束是謂詞表達(dá)式： P(t1, ..., tn)其中，t1, ..., tn是項(xiàng)，典型情況時(shí)包含變量；P是謂詞符號(hào)，謂詞可以是內(nèi)部函數(shù)，如 sum times eq(equal)

47、neq(not equal) ge(great than or equal to) gt(great than)也可以由用戶定義。,2024/4/2,史忠植 高級(jí)人工智能,47,3.11 約束推理系統(tǒng)COPS,條件約束具有下面的形式： if { condition1:

48、 constraint1; … conditionn: constraintn  } where condition1, ..., conditionn are boolean expressions. constraint1,…,constr

49、aintn are constraints or contraints table.,2024/4/2,史忠植 高級(jí)人工智能,48,3.11 約束推理系統(tǒng)COPS,RULE Rule is used to define new function, method, predicate, or add

50、new constraint into object.  RULE [class::] predicate(variables)( boolean expression) { constraint1; … constraintn; CASE boolean expression1: constraint

51、1;… boolean expressionm: constraintm; },2024/4/2,史忠植 高級(jí)人工智能,49,3.11 約束推理系統(tǒng)COPS,For example:  RULE multiple(INTEGER: *x, INTEGER: y, INTEGER: z) (neq(y,0)) { equal(x, divide(

52、z, y)); } 這段程序定義了三個(gè)變量x、y、z之間的約束關(guān)系：x =z /y。,2024/4/2,史忠植 高級(jí)人工智能,50,3.11 約束推理系統(tǒng)COPS,2. 類定義 CLASS [class_name][:superclass_name]{ // attributes definition date type: a

53、ttribute_name; ... // rule definition rule_name; ... //function definition function_name; ... // method definition method_name;

54、 ... },2024/4/2,史忠植 高級(jí)人工智能,51,3.11 約束推理系統(tǒng)COPS,Implementation Program written by COPS consists of classes and rules. COPS constraint programming la

55、nguage is a declarative language, providing classes, methods which are exist in object oriented language. It is similar with C++ . COPS has the features:  constraint object oriented

56、 logic programming production system,2024/4/2,史忠植 高級(jí)人工智能,52,3.11 約束推理系統(tǒng)COPS,算法3.9 COPS的核心算法main-COPS。 procedure main-COPS { 1. Call yacc to parse the program and to

57、generate internal structures. 2. Initializatiion Create Cops Constant trueNode; Allocate memories for global variables. 3. Interprte the program with the internal structures.

58、 4. Constraint networks are built up for Unsolved constraints and variables. 5. while some constraints in the constraint networks are triggered, inteprete the triggered constraints

59、. },3. COPS的約束推理,2024/4/2,史忠植 高級(jí)人工智能,53,3.11 約束推理系統(tǒng)COPS,算法中的解釋器如下：Interpreter:1 {2 switch (constraint type)3 case Constant:4 return Constant:5 case global variable:6 interp

60、rete global variable:7 case local variable or argument:8 interprete local variable or argument:9 case object-attribute pair:10 interprete object-attribute pair:,2024/4/2,史忠植 高級(jí)人工智能,54,3.11 約束推理系統(tǒng)C

61、OPS,11 case function call:12 interprete function call:13 case method call:14 interprete method call:15 case CASE expression:16 interprete CASE expression:17 ...1

62、8 default:20 report error21 },2024/4/2,史忠植 高級(jí)人工智能,55,3.12 ILOG Solver,約束程序是關(guān)于約束的計(jì)算系統(tǒng)，它的 輸入是一組約束條件和需要求解的若干問題， 輸出問題的解決方案。至于具體解決問題的算法等都是約束程序設(shè)計(jì)語言的基本功能。 程序員所要面對(duì)的，就是 如何把問

63、題描述為一組約束構(gòu)成的模型，而描述的語言可以很接近自然語言。 如果把問題的解決方案也看做是一種約束，那么問題的求解就是求得一個(gè)或若干個(gè)約束。 ILOG公司是法國優(yōu)化、互動(dòng)圖像界面以及商業(yè)規(guī)則應(yīng)用領(lǐng)域的軟件組件供應(yīng)商，成立于1987年。,2024/4/2,史忠植 高級(jí)人工智能,56,3.12 ILOG Solver,ILOG Solver是嵌入式過程性語言的約束設(shè)計(jì)語言，將面向?qū)ο蟪绦蛟O(shè)計(jì)和約束邏輯程

64、序設(shè)計(jì)結(jié)合起來，包含邏輯變量，通過增量式約束滿足和回溯實(shí)現(xiàn)問題求解。ILOG Solver中主要語言成分如下：  variables : C++ object /*變量*/  integer variable CtIntVar floating variable CtFloatVar

65、 boolean variable CtBoolVar Memory Management /*存儲(chǔ)管理*/ new: delete:,2024/4/2,史忠植 高級(jí)人工智能,57,3.12 ILOG SOLVER,Constraints /*約束*/  CtT

66、ell(x == (y + z));   Basic constraints: =, ?, ?, , +, -, *, /, subset, superset, union, intersection, member, boolean or, boolean and, boolean not, bool

67、ean xor,    CtTell((x==0) || (y==0));  CtIfThen (x < 100, x = x+1);,2024/4/2,史忠植 高級(jí)人工智能,58,3.12 ILOG SOLVER,Search /*搜索*/ CTGOALn: how to

68、execute  CTGOAL1(CtInstantiate, CtIntVar* x){ CtInt a = x->chooseValue(); CtOr(Constraint(x == a),