【正文】 r。 ... // method definition method_name。 } 2022/5/30 史忠植 高級人工智能 62 Algorithm Program CtBoolean IsMoreUrgent(CtActivity* act1, CtActivity* act2){ // Returns true if act1 is more urgent than act2. // Returns true if act2 is unbound (==0) if (act2 == 0) return CtTrue。 act = SelectActivity(schedule)。 // To state that only cap (here 20220) is available prior to a // given date (here 15). ressetCapacityMax(0,date,cap)。 } 2022/5/30 史忠植 高級人工智能 45 COPS For example: RULE multiple(INTEGER: *x, INTEGER: y, INTEGER: z) (neq(y, 0)) { equal(x, divide(z, y))。 8 endif 9 endfor 10 return DELETE。在各個階段，選擇那些在某些意義下是局部最優(yōu)的方案，期望各階段的局部最優(yōu)的選擇帶來整體最優(yōu)。除此以外， CHIP還包含一個 一般的延遲計算機制。 ? 可變次序例示。 ?代數(shù)與三角方程。2022/5/30 史忠植 高級人工智能 1 高級人工智能 第三章 約束推理 史忠植 中國科學院計算技術(shù)所 2022/5/30 史忠植 高級人工智能 2 第三章 約束推理 概述 回溯法 約束傳播 回跳法 約束推理系統(tǒng) COPS ILOG SOLVER 2022/5/30 史忠植 高級人工智能 3 概述 最優(yōu)化問題 經(jīng)濟學所推崇的帕累托最優(yōu) : 幾個人拎著水桶在一個水龍頭前面排隊打水，水 桶有大有小。 2022/5/30 史忠植 高級人工智能 14 概述 約束表示易于理解、編碼及有效實現(xiàn)，它具有以下優(yōu)點 : ? 約束表示允許以說明性的方式來表達領(lǐng)域知識，表達 能力較強，應(yīng)用程序只需指定問題的目標條件及數(shù)據(jù)間 的相互關(guān)系。 ? 局部修正法。 CHIP 主要應(yīng)用于兩個領(lǐng)域 : 運籌學與硬件設(shè)計。 例： Dijkstra的最短路徑算法、 Kruskal的求最小生成樹算法、信號燈問題 2022/5/30 史忠植 高級人工智能 28 回溯算法 有些問題需要徹底的搜索才能解決問題，然而，徹底的搜索要以大量的運算時間為代價，對于這種情況可以通過回溯法來去掉一些分支，從而大大減少搜索的次數(shù)。 11 end REVISE 2022/5/30 史忠植 高級人工智能 37 AC1 1 Q ? 。 } z = x * y 2022/5/30 史忠植 高級人工智能 46 COPS CLASS [class_name][:superclass_name] { // attributes definition date type: attribute_name。 // To state that an activity act consumes c units of res. actconsumes(res, c)。 } } 2022/5/30 史忠植 高級人工智能 65 Optimal Solution to the Scheduling Problem 。 else return CtTrue。 ... //function definition function_name。 4 for each (Vi, Vj) ? Q do 5 CHANGE ? REVISE(Vi, Vj) ? CHANGE。 其原因在于搜索空間中不同路徑的搜索重復相同的失敗子路徑 。 2022/5/30 史忠植 高級人工智能 21 面向?qū)ο蠹s束語言 COPS COPS系統(tǒng)利用面向?qū)ο蠹夹g(shù)，將說明性約束表達與類型層次 結(jié)合起來。 作為一個約束表示語言， 它使用了符號處理技術(shù)來求解數(shù)學方程。 ? 約束表示允許變量的域包含任意多個值，而不像命題 只取真假二值。這是一個尋求“最優(yōu)化”的題目，目標 是節(jié)省總的排隊時間，達到最優(yōu)。 ?任意系數(shù)的線性方程與不等式。 ? 約束傳播。 2022/5/30 史忠植 高級人工智能 20 約束邏輯程序設(shè)計語言 CHIP CHIP(Constraint handling in Prolog) 就是這樣較有影響 一個約束邏輯程序設(shè)計語言，其目的是簡便、靈活而有效地解決 一大類組合問題。 2022/5/30 史忠植 高級人工智能 25 窮盡搜索方法 窮盡搜索方法 即產(chǎn)生所有可能的樹，然后根據(jù)評價標準選擇一棵最優(yōu)的樹。 2 for each x ? Di do 3 if there is no such yj ? Dj 4 such that(x,yj) is consistent, 5 then 6 delete x from Di。 CASE boolean expression_1: constraint_1。 //To post a precedence constraint between act1 and act2. act2startsAfterEnd(act1,0)。 } 2022/5/30 史忠植 高級人工智能 64 Algorithm Program void SolveProblem(CtSchedule* schedule){ // Solve the problem assuming constraints have been posted. CtActivity* act = SelectActivity(schedule)。 else return CtFalse。 6 Allocate memories for global variables. 2022/5/30 史忠植 高級人工智能 49 COPS 7 Interprte the program with the internal structures. 8 Constraint works are built up for Unsolved 9 constraints and variables. 10 while some constraints in the constraint works are triggered, 11 inteprete the triggered constraints. 12 } 2022/5/30 史忠植 高級人工智能 50 COPS Interpreter: 1 { 2 switch (constraint type)