【正文】 約束表示易于理解、編碼及有效實現(xiàn)，它具有以下優(yōu)點 : ? 約束表示允許以說明性的方式來表達領域知識，表達 能力較強，應用程序只需指定問題的目標條件及數(shù)據(jù)間 的相互關系。2022/8/21 史忠植 高級人工智能 1 高級人工智能 第三章 約束推理 史忠植 中國科學院計算技術所 2022/8/21 史忠植 高級人工智能 2 第三章 約束推理 概述 回溯法 約束傳播 回跳法 約束推理系統(tǒng) COPS ILOG SOLVER 2022/8/21 史忠植 高級人工智能 3 概述 Over the years , the theory and application of optimization has grown into an important field of research. We can distinguish following fields of research that pay attention to optimization problem: ? operations research ? constraint program ? geic algorithm ? neural work 2022/8/21 史忠植 高級人工智能 4 概述 Operations Research Traditionally, a lot of the attention in operations research has been paid to optimization problems, particularly, planning, scheduling, that are based on mathematical model. For solving problems, one should write particular program in terms of algorithm. When modeling a practical scheduling problem using classical models, one is often forced to discard many degrees of freedom and side constraints. 2022/8/21 史忠植 高級人工智能 5 概述 Constraint Programming concerned with solving instances of the constraint satisfaction problem. The general Constraint Satisfaction Problem (CSP) ? A set of n variables {x1,x2,…xn} with values in the discrete, finite domains{D1,D2,…Dn}, . : {4,5,6,7} : {red, green,blue} ? A set of m constraints{c1,c2,…cm} which are predicates c1{x1,x2,…xj} defined on the Cartesian production D1xD2x…xDj . If is TRUE, the valuation of the variables is said to be satisfied. C1: color(wood, red) C 2: x y? ? 16 2022/8/21 史忠植 高級人工智能 6 概述 一個約束通常是指一個包含若干變量的關系表達式， 用以表示這些變量所必須滿足的條件。因而具有邏輯表示的類似性質(zhì)。各種數(shù)學規(guī)劃技 術，方程求解技術等 , 都可以自然地嵌入約束系統(tǒng)。 2022/8/21 史忠植 高級人工智能 10 約束推理 ? 約束搜索 約束搜索主要研究有限域上的約束滿足。 作為一個約束表示語言， 它使用了符號處理技術來求解數(shù)學方程。 2022/8/21 史忠植 高級人工智能 14 CONSTRAINTS約束語言 CONSTRAINTS 的一個優(yōu)點是在類型層次中表示約束，用約束 來表示物理對象的功能與結構。 2022/8/21 史忠植 高級人工智能 16 面向對象約束語言 COPS COPS系統(tǒng)利用面向對象技術，將說明性約束表達與類型層次 結合起來。 一些研究者認為 ， 造成這種反復的原因是所謂的局部不一致性 。即 (vi, vj) 是弧一致的并不自動地意味著 (vj, vi)是一致的。 6 endfor。 . . conditionn: constraintn where condition1, ..., conditionn are boolean expressions. constraint1,... constraintn are constraints or contraints table. 2022/8/21 史忠植 高級人工智能 35 COPS RULE Rule is used to define new function, method, predicate, or add new constraint into object. RULE [class::] predicate(varibles) (boolean expression) { constraint_1。 ... // method definition method_name。 } 2022/8/21 史忠植 高級人工智能 46 ILOG Schedule Schedule CtSchedule class Global object: time original tineMin time horizon timeMax 2022/8/21 史忠植 高級人工智能 47 ILOG Schedule Resources CtResource CtDiscreteResource CtUnaryResource CtDiscreteEnergy CtStateResource 2022/8/21 史忠植 高級人工智能 48 ILOG Schedule Activities CtActivity class CtIntervalActivity An activity is