1、2020/8/7,史忠植 高級(jí)人工智能,1,高級(jí)人工智能,第三章 約束推理,Advanced Artificial Intelligence,史忠植 中國(guó)科學(xué)院計(jì)算技術(shù)研究所,2020/8/7,史忠植 高級(jí)人工智能,2,主要內(nèi)容,3.1 概述 3.2 回溯法 3.3 約束傳播 3.4 約束傳播在樹(shù)搜索中的作用 3.6 變量例示次序與賦值次序 3.7 局部修正搜索法 3.8 基于圖的回跳法 3.9 基于影響的回跳法 3.10 約束關(guān)系運(yùn)算的處理 3.11 約束推理系統(tǒng)COPS 3.12 ILOG SOLVER,2020/8/7,史忠植 高級(jí)人工智能,3,3.1 概 述,最優(yōu)化問(wèn)題 經(jīng)濟(jì)學(xué)所推崇的

2、帕累托最優(yōu): 幾個(gè)人拎著水桶在一個(gè)水龍頭前面排隊(duì)打水，水桶有大有小。他們?cè)鯓优抨?duì)，才能使得總的排隊(duì)時(shí)間最短。這是一個(gè)尋求“最優(yōu)化”的題目，目標(biāo)是節(jié)省總的排隊(duì)時(shí)間，達(dá)到最優(yōu)。,2020/8/7,史忠植 高級(jí)人工智能,4,3.1 概 述,優(yōu)化問(wèn)題 運(yùn)籌學(xué) 遺傳算法 神經(jīng)網(wǎng)絡(luò) 約束推理,2020/8/7,史忠植 高級(jí)人工智能,5,3.1 概 述,1）提出和形成問(wèn)題， 2）建立模型， 3）求解， 4）解的檢驗(yàn)， 5）解的控制， 6）解的實(shí)施。,運(yùn)籌學(xué)的工作步驟,2020/8/7,史忠植 高級(jí)人工智能,6,3.1 概 述,例1 (廣告方式的選擇) 中華家電公司推銷一種新型洗衣機(jī)，有關(guān)數(shù)據(jù)見(jiàn)下表。銷售部第

3、一月的廣告預(yù)算為20000元，要求至少有8個(gè)電視商業(yè)節(jié)目，15家報(bào)紙廣告；電視廣告費(fèi)不得超過(guò)12000元，電臺(tái)廣播至少隔日有一次?，F(xiàn)問(wèn)該公司銷售部應(yīng)當(dāng)采用怎樣的廣告宣傳計(jì)劃，才能取得最好的效果?,線性規(guī)劃問(wèn)題,2020/8/7,史忠植 高級(jí)人工智能,7,3.1 概 述,表1 中華家電公司推銷新型洗衣機(jī)廣告方式選擇的數(shù)據(jù)表,線性規(guī)劃問(wèn)題,2020/8/7,史忠植 高級(jí)人工智能,8,3.1 概 述,解：設(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 50 x1+80 x2+30 x3+ 40 x4+1

4、5x5,s.t. 50 x1+80 x2+30 x3+ 40 x4+15x5 20000， x1+x28， x3+ x4 15， 500 x1+1000 x212000， x116, x210, x3 24, x44, 15x525, x1, x2, x3, x4, x5 0。,線性規(guī)劃問(wèn)題,2020/8/7,史忠植 高級(jí)人工智能,9,3.1 概 述,線性規(guī)劃問(wèn)題(LP)的一般形式為：,min(max) z= c1x1+c2x2+ +cnxn,s.t. a11x1+a12x2+ a1nxn(, )b1 a21x1+a22x2+a2nxn (, )b2 am1x1+am2x2+amnxn (,)

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

6、高級(jí)人工智能,12,3.1 概 述,一個(gè)約束(Constraint)通常是指一個(gè)包含若干變量的關(guān)系表達(dá)式，用以表示這些變量所必須滿足的問(wèn)題。 約束表示廣泛地應(yīng)用于人工智能的各個(gè)領(lǐng)域，包括定性推理、基于模型的診斷、自然語(yǔ)言理解、景物分析、任務(wù)調(diào)度、系統(tǒng)配置、科學(xué)實(shí)驗(yàn)規(guī)劃、機(jī)械與電子設(shè)備的設(shè)計(jì)與分析等。 約束滿足系統(tǒng)的設(shè)計(jì)是一項(xiàng)困難而復(fù)雜的任務(wù)，因?yàn)榧s束滿足問(wèn)題在一般情況下是一個(gè)NP (Nonpolynomia)問(wèn)題，所以必須使用各種策略與啟發(fā)式信息。,2020/8/7,史忠植 高級(jí)人工智能,13,3.1 概 述,一個(gè)約束滿足問(wèn)題(Constraint Satisfaction Problem,

7、CSP) 包含一組變量與一組變量間的約束。 變量表示領(lǐng)域參數(shù)，每個(gè)變量都有一個(gè)固定的值域。 一個(gè)變量的值域可能是有限的，例如一個(gè)布爾變量的值域包含兩個(gè)值；也可能是離散無(wú)限的，如整數(shù)域；也可能是連續(xù)的，如實(shí)數(shù)域。 x1, x2, , xn , D1, D2, Dn , 4, 5, 6, 7 red, green, blue 約束可用于描述領(lǐng)域?qū)ο蟮男再|(zhì)、相互關(guān)系、任務(wù)要求、目標(biāo)等。,2020/8/7,史忠植 高級(jí)人工智能,14,3.1 概 述, 約束滿足問(wèn)題(Constraint Satisfaction Problem, CSP)的目標(biāo)就是找到所有變量的一個(gè)（或多個(gè)）賦值，使所有約束都得到滿足

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

9、嵌入約束系統(tǒng)。,2020/8/7,史忠植 高級(jí)人工智能,16,3.1 概 述,經(jīng)過(guò)多年的研究，人們提出了不少約束推理的方法。根據(jù)聯(lián)系于約束網(wǎng)絡(luò)節(jié)點(diǎn)上的數(shù)據(jù)類型，可以將約束推理分為以下幾種： 關(guān)系推理：推理過(guò)程中推出的新的約束關(guān)系，并將其加到約束網(wǎng)絡(luò)中。 標(biāo)記推理：每個(gè)節(jié)點(diǎn)標(biāo)注以可能值的集合，在傳播過(guò)程中約束用于限制這些集合。 值推理：節(jié)點(diǎn)標(biāo)記以常量值。約束用以標(biāo)記節(jié)點(diǎn)的值求出標(biāo)記節(jié)點(diǎn)的值。 表達(dá)式推理：是值推理的推廣。其中節(jié)點(diǎn)可能標(biāo)以關(guān)于其它節(jié)點(diǎn)的表達(dá)式。,2020/8/7,史忠植 高級(jí)人工智能,17,3.1 概 述, 現(xiàn)有的約束表示可分為以下七類(按復(fù)雜性的次序) ： 一元謂詞。 序關(guān)系語(yǔ)言

10、，只包含偏序關(guān)系或?qū)嵶兞可系拇笮￡P(guān)系。 形如“x - y c”或 “x - y c”的方程。 單位系數(shù)的線性方程與不等式，即所有的系數(shù)為-1,0,1。 任意系數(shù)的線性方程與不等式。 約束的布爾組合。 代數(shù)與三角方程。,2020/8/7,史忠植 高級(jí)人工智能,18,3.1 概 述,目前，約束推理的研究主要集中于兩個(gè)方面：約束搜索與約束語(yǔ)言。 約束搜索主要研究有限域上的約束滿足。對(duì)有限域而言，約束滿足問(wèn)題一般情況下是一個(gè)NP問(wèn)題。大體包括下列方法： 回溯法； 約束傳播； 智能回溯與真值維護(hù)； 可變次序例示； 局部修正法；,2020/8/7,史忠植 高級(jí)人工智能,19,3.1 概 述,約束推理研究的

11、另一個(gè)主要方面是約束語(yǔ)言。以下是幾個(gè)比較典型的約束語(yǔ)言： CONSTRAINTS：面向電路描述的約束表示語(yǔ)言。 Bertrand：Leler開(kāi)發(fā)的一個(gè)高級(jí)約束語(yǔ)言。 CHIP：約束邏輯程序設(shè)計(jì)語(yǔ)言。 約束層次與HCLP：層次型約束邏輯程序設(shè)計(jì)語(yǔ)言。 COPS：面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言的基本形式。 ILOG ：使用建模語(yǔ)言來(lái)表示約束問(wèn)題。,2020/8/7,史忠植 高級(jí)人工智能,20,3.1 概 述,CONSTRAINTS是一個(gè)面向電路描述的約束表示語(yǔ)言。作為一個(gè)約束表示語(yǔ)言，它使用了符號(hào)處理技術(shù)來(lái)求解數(shù)學(xué)方程。 在CONSTRAITS中，物理部件的功能及器件的結(jié)構(gòu)都用約束表示。 這些約束一般是線

12、性方程與不等式，也包括條件表達(dá)式。約束變量一般是表示物理量的實(shí)變量。也有一些取離散值的變量。如開(kāi)關(guān)的狀態(tài)、三極管的工作狀態(tài)等。系統(tǒng)采用表達(dá)式推理與值推理。并實(shí)現(xiàn)相關(guān)制導(dǎo)的回溯。,1）CONSTRAINTS約束語(yǔ)言,2020/8/7,史忠植 高級(jí)人工智能,21,3.1 概 述,CONSTRAINTS的一個(gè) 優(yōu)點(diǎn)：在類型層次中表示約束，用約束來(lái)表示物理對(duì)象的功能與結(jié)構(gòu)。 缺點(diǎn)：是該語(yǔ)言缺乏類似于面向?qū)ο笳Z(yǔ)言中的方法那樣的成分，不能定義特定于某個(gè)類的概念。 同時(shí)，約束傳播方法比較單一，既缺乏實(shí)域上的區(qū)間傳播機(jī)制，也缺乏有限域上的 域傳播機(jī)制。,2020/8/7,史忠植 高級(jí)人工智能,22,3.1 概

13、 述,CHIP(Constraint handling in Prolog) 就是這樣較有影響一個(gè)約束邏輯程序設(shè)計(jì)語(yǔ)言，其目的是簡(jiǎn)便、靈活而有效地解決一大類組合問(wèn)題。它通過(guò)提供幾種新的計(jì)算域而增強(qiáng)邏輯程序設(shè)計(jì)的能力；有限域、布爾項(xiàng)及有理項(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)域概念是極其重要的。,3）約束邏輯程序設(shè)計(jì)語(yǔ)言CHIP,2020/8/7,史忠植 高級(jí)人工智能,23,3.

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

15、PS系統(tǒng)同時(shí)是一個(gè)漸增式的開(kāi)放系統(tǒng)，用戶能通過(guò)類型層次定義，實(shí)現(xiàn)新的數(shù)據(jù)類型和新的約束關(guān)系。約束語(yǔ)言COPS具有許多人工智能程序設(shè)計(jì)語(yǔ)言的特點(diǎn)，如約束傳播、面向目標(biāo)和數(shù)據(jù)驅(qū)動(dòng)的問(wèn)題求解、有限步的回溯、對(duì)象分層中的繼承等。,5）面向?qū)ο蠹s束語(yǔ)言COPS,2020/8/7,史忠植 高級(jí)人工智能,25,3.1 概 述,ILOG公司創(chuàng)建于1987年，總部位于法國(guó)巴黎和美國(guó)加利福尼亞州，是全球領(lǐng)先的優(yōu)化、互動(dòng)圖像界面以及商業(yè)規(guī)則應(yīng)用領(lǐng)域的軟件組件供應(yīng)商，也是全球?qū)?yōu)化算法運(yùn)用到商業(yè)應(yīng)用軟件中的公司。產(chǎn)品應(yīng)用遍布于電信、交通、國(guó)防、電力、物流等領(lǐng)域。 ILOG公司的ILOG Solver使用建模語(yǔ)言來(lái)表示

16、約束問(wèn)題。,5）ILOG,2020/8/7,史忠植 高級(jí)人工智能,26,算法分析,評(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à)(或稱空間復(fù)雜性)：當(dāng)被解決問(wèn)題的規(guī)模(以某種單位計(jì)算)由1增至n時(shí)，解該問(wèn)題的算法所需占用的空間也以某種單位由f(1) 增至f(n)，這時(shí)我們稱該算法的空間代價(jià)是f(n)。 算法的時(shí)間代價(jià)(或稱時(shí)間復(fù)雜性)：當(dāng)問(wèn)題規(guī)模以某種單位由1增至n時(shí)，對(duì)應(yīng)算法所耗費(fèi)的時(shí)間也以某種單位由g(1)增至g(n)，這時(shí)我們稱算法的時(shí)間代價(jià)是g(n)。,2020

17、/8/7,史忠植 高級(jí)人工智能,27,常用的算法,在實(shí)際應(yīng)用中，算法的表現(xiàn)形式千變?nèi)f化，但是算法的情況也和數(shù)據(jù)結(jié)構(gòu)類似，許多算法的設(shè)計(jì)思想具有相似之處，我們可以對(duì)它們分類進(jìn)行學(xué)習(xí)和研究。 常用的算法大致有如下一些： 貪心法 分治法（如二分法檢索） 回溯法 動(dòng)態(tài)規(guī)劃法 局部搜索法 分支限界法,2020/8/7,史忠植 高級(jí)人工智能,28,窮盡搜索方法,窮盡搜索方法 即產(chǎn)生所有可能的樹(shù)，然后根據(jù)評(píng)價(jià)標(biāo)準(zhǔn)選擇一棵最優(yōu)的樹(shù)。 Exhaustive-Search-Top(P) where P is a CSP of the form(V,D,C) 1. f:= the null assignment 2

18、. return Exhaustive-Search(f,P),2020/8/7,史忠植 高級(jí)人工智能,29,窮盡搜索方法,Exhaustive-Search(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

19、 := Unsat 9. for each value while answer = Unsat 10. f(v) := x 11. answer := Exhaustive-Search(f,P) 12. return answer,2020/8/7,史忠植 高級(jí)人工智能,30,貪 心 法,貪心法把構(gòu)造可行解的工作分階段來(lái)完成。在各個(gè)階段，選擇那些在某些意義下是局部最優(yōu)的方案，期望各階段的局部最優(yōu)的選擇帶來(lái)整體最優(yōu)。 例：Dijkstra的最短路徑算法、Kruskal的求最小生成樹(shù)算法、信號(hào)燈問(wèn)題,2020/8/7,史忠植 高級(jí)人工智能,31,3.2 回溯法,有些問(wèn)題需要徹底的搜索才能解決問(wèn)

20、題，然而，徹底的搜索要以大量的運(yùn)算時(shí)間為代價(jià)，對(duì)于這種情況可以通過(guò)回溯法來(lái)去掉一些分支，從而大大減少搜索的次數(shù)。 八皇后問(wèn)題 迷宮問(wèn)題 深度優(yōu)先周游樹(shù)或圖,2020/8/7,史忠植 高級(jí)人工智能,32,3.2 Backtracking Algorithm,Based on depth-first recursive search Approach Tests whether solution has been found If found solution, return it Else for each choice that can be made Make that choice Rec

21、ur If recursion returns a solution, return it If no choices remain, return failure Some times called “search tree”,2020/8/7,史忠植 高級(jí)人工智能,33,3.2 Solution to 8-Queens Puzzle,八皇后問(wèn)題，是一個(gè)古老而著名的問(wèn)題，是回溯算法的典型例題。該問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在88格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法。 高斯認(rèn)為有76種方案。1854年

22、在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來(lái)有人用圖論的方法解出92種結(jié)果。計(jì)算機(jī)發(fā)明后，有多種方法可以解決此問(wèn)題。,2020/8/7,史忠植 高級(jí)人工智能,34,4-Queens Puzzle,Figure6-13 Finding a solution to the 4-queens puzzle,Figure6-14 Solution to the 4-queens puzzle,0 1 2 3,0 123,0 123,0 1 2 3,2020/8/7,史忠植 高級(jí)人工智能,35,4-Queens Tree,1,2,9,3,4,5,10,11,12,6,8,7,13,14,Fig

23、ure6-15 4-queens tree,x1=0,x2=1,x2=1,x2=2,x2=3,x3=1,x2=3,x2=2,x2=0,x3=0,x4=2,Solution,(0),(1),(1,3),(1,3,0),(1,3,0,2),(0,3),(0,3,1),2020/8/7,史忠植 高級(jí)人工智能,36,3.2 回溯法,求解有限約束滿足問(wèn)題的最簡(jiǎn)單直接的方法是生成測(cè)試法，即依次生成所有變量的值的各種組合，對(duì)其進(jìn)行測(cè)試，直到一個(gè)測(cè)試成功的組合。這種方法顯然是低效的。一種直接的改進(jìn)是順序回溯法。 順序回溯法以固定次序?qū)ψ兞窟M(jìn)行示例，當(dāng)新的變量與先前賦值的變量不一致時(shí)，它嘗試其變量域中的其它值，

24、直到域中所有的值都被窮盡。當(dāng)所有的值都失敗，則回到上一個(gè)賦值的變量，并對(duì)該變量重新賦值。,2020/8/7,史忠植 高級(jí)人工智能,37,3.2 回溯法,算法3.1 回溯算法BACKTRACK。 輸入：一個(gè)CSP問(wèn)題 輸出：一個(gè)完全解或無(wú)解返回,2020/8/7,史忠植 高級(jí)人工智能,38,3.2 回溯法,procedure BACKTRACK begin k=1; while k0 do if xk 存在未檢驗(yàn)過(guò)的值時(shí) xkT(x1,x2, ,xk-1) and BTk(x1,x2, ,xk) =true then if (x1,x2, ,xk) 滿足所有約束條件 then return(0)

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

26、020/8/7,史忠植 高級(jí)人工智能,40,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)是一致的。,2020/8/7,史忠植 高級(jí)人工智能,41,3.3 約束傳播,圖3-1 弧一致性（Arc consistency）,v1,v2,v3,v1與v3之間的約束為不等關(guān)系，則(v1,v3)是弧一致的，而(v3,v1)則不是；v2與v3之間的約束為不等關(guān)系，則(v2,v3

27、)是弧一致的，而(v3,v2)則不是。 因?yàn)閷?duì)v3=blue，不存在v1域中任何值，使其不等關(guān)系成立。顯然(vi,vj)之間可以通過(guò)刪除不滿足彼此之間不滿足約束的值而實(shí)現(xiàn)其弧一致行，而且刪除這些值不影響原來(lái)CSP的任何解。以下就是實(shí)現(xiàn)這種刪除操作的算法。,2020/8/7,史忠植 高級(jí)人工智能,42,3.3 約束傳播,procedure REVISE(Vi, Vj) 1 DELETE false; 2 for each x Di do 3 if there is no such yj Dj 4such that(x, yj) is consistent, 5 then 6 delete x f

28、rom Di; 7 DELETE true; 8 endif 9 endfor 10 return DELETE; 11 end REVISE,算法3.2 約束傳播修改算法Mackworth 1977,2020/8/7,史忠植 高級(jí)人工智能,43,3.3 約束傳播,procedure AC-1 1 Q (Vi,Vj)arcs(G), ij; 2 repeat 3 CHANGE false; 4 for each (Vi, Vj) Q do 5 CHANGE REVISE(Vi, Vj)CHANGE; 6 endfor; 7 until not(CHANGE); 8 end AC-1,算法3.3

29、 約束傳播AC-1算法Mackworth 1977,2020/8/7,史忠植 高級(jí)人工智能,44,3.3 約束傳播,procedure AC-3 1 Q (Vi,Vj) arcs(G), ij; 2 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), ik, im; 6 endif; 7 endwhile; 8 end AC-3,算法3.4 約束傳播AC-3算法Mackworth 1977,2020/8/7

30、,史忠植 高級(jí)人工智能,45,3.4 約束傳播在樹(shù)搜索中的作用,回溯法：通過(guò)測(cè)試變量的不同組合來(lái)得到一個(gè)完整的解。 缺陷：搜索路徑的重復(fù)。 約束傳播：通過(guò)傳播變量間的約束，從而降低問(wèn)題的復(fù)雜性。,一種綜合的辦法是將給傳播嵌入到回溯法中，具體做法： 首先生成一個(gè)根搜索節(jié)點(diǎn)，求解最初的CSP。當(dāng)一個(gè)搜索節(jié)點(diǎn)被訪問(wèn)，使用傳播算法以達(dá)到預(yù)期程度的一致性。 如果存在一個(gè)搜索節(jié)點(diǎn)，每個(gè)變量恰包含一個(gè)值，而且對(duì)應(yīng)的CSP是弧一致性的，則該搜索節(jié)點(diǎn)表示一個(gè)解。 如果在約束傳播過(guò)程中，某些變量的域變?yōu)榭?，則該搜索節(jié)點(diǎn)被剪枝。否則，選擇一個(gè)變量，對(duì)該變量的每一個(gè)可能的值生成新的搜索節(jié)點(diǎn)。每個(gè)新的CSP搜索節(jié)點(diǎn)表示

31、當(dāng)前CSP搜索節(jié)點(diǎn)的后繼節(jié)點(diǎn)。 所有這些搜索節(jié)點(diǎn)通過(guò)使用深度優(yōu)先的回溯法來(lái)訪問(wèn)。,2020/8/7,史忠植 高級(jí)人工智能,46,3.6 變量例示次序與賦值次序,對(duì)標(biāo)準(zhǔn)回溯法的另一個(gè)可以改進(jìn)的方面是變量的例示次序。實(shí)驗(yàn)表明這種次序?qū)厮菟阉鞯男视兄薮蟮挠绊?，已提出多種啟發(fā)式策略。,選擇當(dāng)前域最小的變量最先例示。這樣，變量的例示次序一般是動(dòng)態(tài)確定的，而且對(duì)于搜索樹(shù)中的不同分支可能是不同的。 優(yōu)先例示參與約束最多的變量。這種方法的出發(fā)點(diǎn)是不成功的分支盡可能早地剪除。 前面提到過(guò)樹(shù)結(jié)構(gòu)約束網(wǎng)絡(luò)可以不回溯，而對(duì)于求解任何一個(gè)約束網(wǎng)絡(luò)可以通過(guò)刪除某些節(jié)點(diǎn)而使其成為樹(shù)，這些節(jié)點(diǎn)的集合稱圈割集。 如果能找

32、到一個(gè)小的圈割集，則一個(gè)好的啟發(fā)式是先例示割集中的變量，然后求解剩下的樹(shù)結(jié)構(gòu)CSP。,2020/8/7,史忠植 高級(jí)人工智能,47,3.7 局部修正搜索法,目前絕大部分算法是基于樹(shù)搜索的構(gòu)造性求解方法。但近來(lái)一種求解問(wèn)題的方法以其驚人的實(shí)驗(yàn)結(jié)果引起了人們的注意，這就是所謂的“局部修正法”Gu1992。 這種方法首先生成一個(gè)全部的，但可能是不一致的變量賦值，然后針對(duì)所出現(xiàn)的矛盾改變某個(gè)變量的值，以減少所違反約束的個(gè)數(shù)，如此反復(fù)，直到達(dá)到一個(gè)一致的賦值。 該方法遵循一個(gè)簡(jiǎn)單的法則：找到一個(gè)引起矛盾的變量，然后選一個(gè)新值賦給它，使得結(jié)果賦值將矛盾減到最少。,2020/8/7,史忠植 高級(jí)人工智能,4

33、8,3.7 局部修正搜索法,該方法的基本思想如下： 給定 一個(gè)變量的集合、一個(gè)二元約束的集合及對(duì)每個(gè)變量的一個(gè)賦值。兩個(gè)變量相矛盾如果它們的值違反了一個(gè)約束。 過(guò)程 選一個(gè)矛盾變量，并為它賦一個(gè)值使得將矛盾的個(gè)數(shù)減到最小。,局部修正搜索法十分有效的主要原因在于對(duì)每個(gè)變量的賦值提出了較多的信息，因而下一個(gè)所轉(zhuǎn)換的狀態(tài)較大幅度地減少了矛盾的個(gè)數(shù)。 局部修正搜索法也有其局限性。這種策略是不完備的：當(dāng)問(wèn)題沒(méi)有解時(shí)，該過(guò)程可能不終止。當(dāng)問(wèn)題的解密度比較小時(shí)，搜索的效率也很低。,2020/8/7,史忠植 高級(jí)人工智能,49,3.8 基于圖的回跳法,基于圖的回跳法(graph-based backjumpi

34、ng)屬于相關(guān)制導(dǎo)的回溯中的一種。其中的相關(guān)信息來(lái)自約束網(wǎng)絡(luò)的圖結(jié)構(gòu)。 一個(gè)約束圖是指由約束關(guān)系所隱含的圖。其中的頂點(diǎn)為變量，邊為約束（這里假定所有的約束都是二元的）。即兩個(gè)頂點(diǎn)有一條邊僅當(dāng)它們所代表的變量存在約束。 在基于圖的回溯跳法中，每當(dāng)在某個(gè)變量X出現(xiàn)失敗，算法總是回到在圖中與X聯(lián)結(jié)的最近賦值變量。,2020/8/7,史忠植 高級(jí)人工智能,50,3.8 基于圖的回跳法,算法3.5 前向傳播算法Forward Forward(x1,xi,P) begin if i=n then 退出并返回當(dāng)前賦值; Ci+1 computerCandidates(x1,xi,xi+1); if Ci+1

35、 非空, then xi+1 Ci+1 中的第一個(gè)元素; Ci+1 中刪除 xi+1; Forward(x1,xi,xi+1, P) else jumpback(x1,xi,P); end if end,下面是基于圖的回跳法的算法。,其中，P用以保留將回溯的變量的集合。,2020/8/7,史忠植 高級(jí)人工智能,51,3.8 基于圖的回跳法,算法3.6 回跳算法Jumpback。 Jumpback(x1,xi,xi+1,P) begin if i = 0, then 退出無(wú)解; PARENTS Parents(xi+1); P P PARENTS; 設(shè)j是 P中編號(hào)最大的變量, P P-xj;

36、if Cj , then xj = first in Cj; 從Cj 中刪除 xj; Forward(x1,xj,P) else jumpback(x1,xj,xj+1,P); end if; end,2020/8/7,史忠植 高級(jí)人工智能,52,3.9 基于影響的回跳法,對(duì)基于圖的回跳法的改進(jìn)，形成新的基于影響的回跳法。首先，我們的目標(biāo)是利用動(dòng)態(tài)相關(guān)信息，而不僅僅是靜態(tài)聯(lián)結(jié)關(guān)系。 基于影響的回跳法IBMD(influence-based-backjumping, most-constrained-first,domain filtering)將三者策略綜合在一起: 最約束者優(yōu)先(most-c

37、onstrained-first)是指每次選“自由度”最小的變量加以賦值。 “自由度”主要用變量當(dāng)前取值域的大小加以衡量。 域篩減法(domain filtering)是指從變量域中刪除與已賦值的變量不一致的值（代價(jià)較小的約束傳播技術(shù)）。 回跳法(backjump)是根據(jù)篩減過(guò)程中賦值變量對(duì)賦值變量的實(shí)際影響來(lái)回跳。,2020/8/7,史忠植 高級(jí)人工智能,53,3.9 基于影響的回跳法,算法3.7基于影響的回跳法IBMD IMBD(x1,xi,P) int var, failvar; while (uninstantiated !=nil ) var=mostConstrained(); /

38、 *選擇一個(gè)例示變量*/ avar=domainvar0; /*對(duì)變量賦值*/ While (failvar=propagate(var)!=SUCCESS) /*當(dāng)不一致時(shí)*/ if var=backjump(failvar)=nil) return(0); /*如果返回頂端,退出*/ avar=domainvar0; /*否則重新例示變量*/ return(1) ,2020/8/7,史忠植 高級(jí)人工智能,54,3.9 基于影響的回跳法,算法3.8 回跳算法backjump1994 backjump(failvar) int failvar int assignedVar,sourceVar

39、; failedVarSet = makeVariableSet(); addVariableSet(failvar,failedVarSet); /*初始化失敗的變量集*/ while (assignedVar=lastAssignedASSIGNEDHEAD)!=TOP) /*直到達(dá)到頂端*/ retract(assignedVar); /*撤銷變量的影響*/ if (relevant) /*例示影響failedVarSet*/ if (!exhausted(assignedVar) break; else addVariableSet(assignedVar,failedVarSet);

40、 ,2020/8/7,史忠植 高級(jí)人工智能,55,3.10 約束關(guān)系運(yùn)算的處理,1. 恒等關(guān)系的單元共享策略 在約束推理中，如果兩個(gè)變量總是取相同的值，這兩個(gè)變量是恒等關(guān)系。恒等關(guān)系是一類重要的約束關(guān)系。 例如，電路中兩個(gè)部件的串聯(lián)關(guān)系，意味著流過(guò)兩個(gè)部件的電流相等。一個(gè)正方形可以定義為其長(zhǎng)和寬相等的矩形。盡管恒等關(guān)系可以通過(guò)普通的約束關(guān)系處理，但是它應(yīng)用的廣泛性和特殊的語(yǔ)義性，有必要進(jìn)行特殊處理。這樣不僅可以避免通用約束問(wèn)題求解器帶來(lái)的低效性，更重要的是，它可以直接用來(lái)降低問(wèn)題的計(jì)算規(guī)模。因?yàn)閮蓚€(gè)相等的變量必須取相同的值，所以可以在計(jì)算上將其視為同一個(gè)變量。這就是單元共享策略的基本思想。,2

41、020/8/7,史忠植 高級(jí)人工智能,56,3.10 約束關(guān)系運(yùn)算的處理,實(shí)現(xiàn)單元共享策略的一種簡(jiǎn)單方法是將兩個(gè)相等的變量用一個(gè)新的變量代替，但這導(dǎo)致約束網(wǎng)絡(luò)的全局變量代換。同時(shí)，考慮到有些相等關(guān)系是在進(jìn)行進(jìn)行了某些賦值假設(shè)后作出的，因而必須保存原有的未等同前的變量信息。因此我們采用了二叉樹(shù)表示。對(duì)等式 x = y， if x、y都已賦值，則判斷其是否相等，并返回其真值。 if x已賦值，而y沒(méi)有賦值，則看x的值是否落在y的域中，如果不是，則返回不一致(失敗)信息。否則，將x的值賦予y。 if x、y都未賦值，則生成一個(gè)新的節(jié)點(diǎn)com(x, y)稱為x和y的公共節(jié)點(diǎn)，它的兩個(gè)分支節(jié)點(diǎn)分別為x和

42、y。com(x,y)的域?yàn)閤和y的交集。如果該交集為空，則返回不一致(失敗)信息。x與y別的節(jié)點(diǎn)的約束聯(lián)結(jié)都被合并到com(x,y)中。,2020/8/7,史忠植 高級(jí)人工智能,57,3.10 約束關(guān)系運(yùn)算的處理,這種策略具有的優(yōu)點(diǎn)： (1)由于約束搜索的復(fù)雜性取決于約束變量的個(gè)數(shù)，而單元共享策略將兩個(gè)或更多具有恒等關(guān)系的變量合并成一個(gè)變量，因而降低了搜索空間。 (2)使得約束推理器在變量未賦值的情形下也能發(fā)現(xiàn)與恒等關(guān)系有關(guān)的不一致性。 (3)使得約束傳播可以提前進(jìn)行。恒等關(guān)系的單元共享策略減少了未知變量的個(gè)數(shù)，也減少了一個(gè)約束關(guān)系中未知變量的個(gè)數(shù)。 (4) 使得約束語(yǔ)言具有模式匹配等符號(hào)處理

43、的能力。,2020/8/7,史忠植 高級(jí)人工智能,58,3.10 約束關(guān)系運(yùn)算的處理,定性值的加運(yùn)算可如下定義： qualsum(x,y,z) enum qualitative x,y,z; if (x=y) z=x; if (x=zero) z=y; if (y=zero) z=x; ,如果我們有如下約束程序： main(x,y,z) enum qualitative u,v,w; w=zero; qualsum(u,w,v); qualsum(u,v,w); ,一個(gè)在實(shí)數(shù)域上變化的物理量可以用定性變量來(lái)刻畫(huà)其正負(fù)性。一個(gè)定性變量取正(pos)、負(fù)(neg)、零(zero)三個(gè)值： enum

44、 qualitative pos, neg, zero;,則不進(jìn)行任何試探性搜索，就能求得唯一解，該解為u=zero, v=zero, w=zero。因?yàn)橛蓂ualsum(u, w, v)及w=zero，得u=v，該等式使得qualsum(u, w, v)推出u=w=zero，從而v=u=zero。,2020/8/7,史忠植 高級(jí)人工智能,59,3.10 約束關(guān)系運(yùn)算的處理,2. 區(qū)間傳播 除了等式關(guān)系，數(shù)域上最通常的關(guān)系是不等式，特別是機(jī)械電子設(shè)備的分析與設(shè)計(jì)中，不等式的應(yīng)用尤為重要。 不等式表示最基本的推理形式是用于對(duì)變量值的測(cè)試。即已知變量的值，計(jì)算并檢查變量的值是否滿足該不等式。單純這

45、種計(jì)算方式只能用于約束滿足的生成測(cè)試策略，而這種策略效率是最低的。這里我們實(shí)現(xiàn)了較強(qiáng)形式的不等式推理。,2020/8/7,史忠植 高級(jí)人工智能,60,3.10 約束關(guān)系運(yùn)算的處理,比較常用的不等式的一種推理形式是區(qū)間推理，即約束網(wǎng)絡(luò)上的區(qū)間傳播。給定一些變量的區(qū)間限制，由變量間的序關(guān)系，推出對(duì)另一些變量的區(qū)間限制。例如，設(shè)有約束xy，且變量x與y的區(qū)間分別為lx, gx與ly, gy，則對(duì)該約束進(jìn)行約束傳播后x與y的新區(qū)間為 max(lx, ly), gx ly, min(lx, gy) 如果gx ly ，則意味著矛盾。,2020/8/7,史忠植 高級(jí)人工智能,61,3.10 約束關(guān)系運(yùn)算的處

46、理,這種推理同樣可以推廣到更復(fù)雜的的方程式或不等式?？紤]方程x+y=z，且x、y、z的當(dāng)前區(qū)間為lx, gx、ly, gy、lz, gz。如果lx+ ly gz ，或gx+ gy lz，則意味著矛盾。否則z的新區(qū)間值l ,z, g,z為 l ,z = max(lx+ ly, lz) g,z = min(gx+ gy, gz) x的新區(qū)間值l ,x, g,x為 l ,x = max(lz- gy, lx) g,x = min(gz- ly, gx) y的新區(qū)間值l ,y, g,y為 l ,y = max(lz- gx, ly) g,y = min(gy- lx, gy),2020/8/7,史忠植

47、 高級(jí)人工智能,62,3.10 約束關(guān)系運(yùn)算的處理,3. 不等式圖 將所有形如xy與xy的不等式組成一個(gè)不等式圖。關(guān)系xy表示為yx，xy表示為yx與xy。 定義3.1 遞增圈 一個(gè)不等式圖是一個(gè)標(biāo)記圖。其中，V是變量節(jié)點(diǎn)的集合。邊集E是關(guān)系表達(dá)式 x r y 的集合，x, yV，r為關(guān)系或。網(wǎng)絡(luò)中的一條遞增路徑是變量節(jié)點(diǎn)的序列v1,v2,vl，使得對(duì)任意的i=2,l，vi-1vi是網(wǎng)絡(luò)中的一條邊。如果v1=vl，則稱該路徑為一遞增圈。,2020/8/7,史忠植 高級(jí)人工智能,63,3.10 約束關(guān)系運(yùn)算的處理,性質(zhì)3.1 一個(gè)遞增圈如果其中任意兩個(gè)變量節(jié)點(diǎn)之間都不含邊，則遞增圈中所有的節(jié)點(diǎn)都

48、表示相同的變量。 性質(zhì)3.2 如果不等式圖中存在一個(gè)遞增圈，其中某兩個(gè)變量節(jié)點(diǎn)之間含邊，則不等式圖蘊(yùn)涵不一致性。 定義3.2 一個(gè)不等式圖是圖不一致的，當(dāng)且僅當(dāng)圖中存在一個(gè)遞增圈，其中某兩個(gè)變量節(jié)點(diǎn)之間含邊。 定理3.1 一個(gè)不等式圖是圖不一致的，當(dāng)且僅當(dāng)其精簡(jiǎn)圖中，存在一個(gè)變量節(jié)點(diǎn)，有一個(gè)引向自身的邊。,2020/8/7,史忠植 高級(jí)人工智能,64,3.10 約束關(guān)系運(yùn)算的處理,4. 不等式推理 不等式圖體現(xiàn)了不等式的結(jié)構(gòu)性質(zhì)。 一個(gè)關(guān)系表達(dá)式 x r y。其中x與y為變量或常量，但至少一個(gè)為變量。r為=、之一。 1) if r為=， 若x 與 y都為未賦值的變量，則按單元共享策略將其合并為

49、同一個(gè)變量節(jié)點(diǎn)，并檢查是否生成遞增圈，進(jìn)行可能的不等式圖精簡(jiǎn)與一致性檢查。若新節(jié)點(diǎn)的區(qū)間比x或 y的區(qū)間減小，則沿著不等式網(wǎng)絡(luò)進(jìn)行區(qū)間傳播。 若x 與 y都為已賦值的變量或常量，則判定其值是否相等； 如果二者有且僅有一個(gè)未賦值的變量，若另一個(gè)自變量的值落在該變量的域中，則將值賦予該變量，并進(jìn)行約束傳播；否則，報(bào)告不一致性。,2020/8/7,史忠植 高級(jí)人工智能,65,3.10 約束關(guān)系運(yùn)算的處理,2) if r為， 若x與y都為已賦值的變量，則判定關(guān)系是否成立； 否則，對(duì)x與y的區(qū)間進(jìn)行一致性限定。若限定的結(jié)果x或y的區(qū)間有所減小，則沿著不等式網(wǎng)絡(luò)進(jìn)行區(qū)間傳播。 如果二者都為未賦值的變量，則

50、向不等式網(wǎng)絡(luò)加入一條邊，并檢查是否生成遞增圈，進(jìn)行可能的不等式圖精簡(jiǎn)與一致性檢查。 3) if r為， 若x 與 y都為已賦值的變量，則判定關(guān)系是否成立。 對(duì)xy與xy則將其分別等價(jià)轉(zhuǎn)化為(xy)(xy)、(yx)(xy)、yx。 消除冗余性，降低問(wèn)題的求解規(guī)模。,2020/8/7,史忠植 高級(jí)人工智能,66,3.11 約束推理系統(tǒng)COPS,約束推理系統(tǒng)（COPS）的一個(gè)主要功能是為用戶提供通用而有效的約束推理機(jī)制 。該種推理機(jī)制要克服由于不確定性所引起的搜索問(wèn)題。約束傳播也正是降低不確定的一種技術(shù)。 在COPS中，約束程序設(shè)計(jì)語(yǔ)言COPS將面向?qū)ο蟮募夹g(shù)、邏輯程序設(shè)計(jì)、產(chǎn)生式系統(tǒng)與約束表示結(jié)

51、合起來(lái)，在形式上吸收了面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言的基本形式，內(nèi)部求解時(shí)采用約束傳播和啟發(fā)式機(jī)制，使說(shuō)明性約束表達(dá)式與類型層次相結(jié)合，實(shí)現(xiàn)結(jié)構(gòu)化的知識(shí)封裝。COPS語(yǔ)言具有以下特點(diǎn)： (1)將類型層次與約束表示結(jié)合起來(lái)； (2)實(shí)現(xiàn)默認(rèn)約束推理； (3)實(shí)現(xiàn)條件約束及常規(guī)程序設(shè)計(jì)的其它成分； (4)實(shí)現(xiàn)有效的約束推理。,2020/8/7,史忠植 高級(jí)人工智能,67,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) neq(not

52、 equal) ge(great than or equal to) gt(great than) 也可以由用戶定義。,2020/8/7,史忠植 高級(jí)人工智能,68,3.11 約束推理系統(tǒng)COPS,條件約束具有下面的形式： if condition1: constraint1; conditionn: constraintn where condition1, ., conditionn are boolean expressions. constraint1,constraintn are constraints or contraints table.,2020/8/7,史忠植 高級(jí)人工智

53、能,69,3.11 約束推理系統(tǒng)COPS,規(guī)則是用來(lái)定義新的函數(shù)、方法、謂詞，或者可以將約束加到對(duì)象上。規(guī)則的形式是 RULE class: predicate(variables)(boolean expression) constraint1; constraintn; CASE boolean expression1: constraint1; boolean expressionm: constraintm; ,2020/8/7,史忠植 高級(jí)人工智能,70,3.11 約束推理系統(tǒng)COPS,例如： RULE multiple(INTEGER: *x, INTEGER: y, INTEGE

54、R: z) (neq(y,0) equal(x, divide(z, y); 這段程序定義了三個(gè)變量x、y、z之間的約束關(guān)系：x =z /y。,2020/8/7,史忠植 高級(jí)人工智能,71,3.11 約束推理系統(tǒng)COPS,2. 類定義 CLASS class_name:superclass_name / attributes definition date type: attribute_name; . / rule definition rule_name; . /function definition function_name; . / method definition method_

55、name; . ,2020/8/7,史忠植 高級(jí)人工智能,72,3.11 約束推理系統(tǒng)COPS,整個(gè)COPS程序就是由類的定義和規(guī)則組成。COPS語(yǔ)言保持了關(guān)系式說(shuō)明型語(yǔ)言的風(fēng)格，同時(shí)提供類、方法等面向?qū)ο蟪煞?。這樣，既增強(qiáng)了程序設(shè)計(jì)的規(guī)范性與靈活性，又提高了程序的易用性和可讀性。COPS語(yǔ)言可以使用戶集中于問(wèn)題本身的描述，不必關(guān)心問(wèn)題求解的細(xì)節(jié)。由于COPS語(yǔ)言成分與常規(guī)的 C+語(yǔ)言非常類似，整個(gè)描述直觀、清晰，很容易使用，而且可以充分利用類的封裝性和繼承機(jī)制進(jìn)行擴(kuò)充和復(fù)用。COPS 已經(jīng)成功地進(jìn)行了電路的模擬。,2020/8/7,史忠植 高級(jí)人工智能,73,3.11 約束推理系統(tǒng)COPS,

56、算法3.9 COPS的核心算法main-COPS。 proceduremain-COPS 1. Call yacc to parse the program and to generate internal structures. 2. Initializatiion Create Cops Constant trueNode; Allocate memories for global variables. 3. Interprte the program with the internal structures. 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. ,3. COPS的約束推理,2020/8/7,史忠植 高級(jí)人工智能,74,3.11 約束推理系統(tǒng)COPS,算法中的解釋器如下： Interpreter: 1 2 switch (constraint type) 3 case Constant