约束传播智能科学与人工智能PPT课件

1、2021-11-5史忠植 约束推理1第三章第三章 约束推理约束推理3.1 3.1 概述概述3.2 3.2 回溯法回溯法 3.3 3.3 约束传播约束传播 3.4 3.4 回跳法回跳法 3.5 3.5 约束推理系统约束推理系统COPS COPS 3.6 3.6 ILOG SOLVERILOG SOLVER3.7 3.7 约束逻辑程序设计约束逻辑程序设计第1页/共79页在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合法布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探， 每试探一步形成一个新的状态， 整个试探过程形成了一棵隐

2、含的状态树。八皇后问题八皇后问题765432100 1 23 4 5 6 7第2页/共79页The DFS/BFS tree will enumerate up to 648 combinations (assume limit depth to 8).648 = 248 = 2.8 x 1014Note redundancy: Q1 in (1,3), Q2 in (2,7) vs. Q1 in (2,7), Q2 in (1,3) 第3页/共79页2021-11-5史忠植 约束推理4概概 述述一个约束满足问题一个约束满足问题(Constraint Satisfaction (Constra

3、int Satisfaction Problem, Problem, 简称简称CSP) CSP) 包含一组变量与一组变量间的约包含一组变量与一组变量间的约束。束。 变量表示领域参数，每个变量都有一个固定的值变量表示领域参数，每个变量都有一个固定的值域。一个变量的值域可能是有限的，例如一个布尔变域。一个变量的值域可能是有限的，例如一个布尔变量的值域包含两个值；也可能是离散无限的，如整数量的值域包含两个值；也可能是离散无限的，如整数域；也可能是连续的，如实数域。域；也可能是连续的，如实数域。 x1,x2,x1,x2,xnxn , , D1,D2,D1,D2,DnDn , ., . 4,5,6,74

4、,5,6,7 red, green,bluered, green,blue 第4页/共79页约束满足问题约束满足问题C CSPGiven: (1) set of variables, (2) domains of the variables (3) constraints that the variables have to satisfyFind: An assignment of values to the variables, so that these values satisfy all the given constraints. In optimisation problems,

5、 also specify optimisation criterion 2021-11-55史忠植 约束推理第5页/共79页2021-11-5史忠植 约束推理6概概 述述 约束可用于描述领域对象的性质、相互关系、任务约束可用于描述领域对象的性质、相互关系、任务要求、目标等。约束要求、目标等。约束 满足问题满足问题 的目标就是找到所有的目标就是找到所有变量的一个（或多个）赋值，使所有约束都得到满足。变量的一个（或多个）赋值，使所有约束都得到满足。 一元谓词。一元谓词。 序关系语言，只包含偏序关系或实变量上的大小关序关系语言，只包含偏序关系或实变量上的大小关系。系。 形如形如“x - y cx

6、- y c” 的方程。的方程。 单位系数的线性方程与不等式，即所有的系数为单位系数的线性方程与不等式，即所有的系数为 -1,0,1-1,0,1。 任意系数的线性方程与不等式。任意系数的线性方程与不等式。 约束的布尔组合。约束的布尔组合。 代数与三角方程。代数与三角方程。第6页/共79页2021-11-5史忠植 约束推理7概概 述述约束表示易于理解、编码及有效实现，它具有以下优点约束表示易于理解、编码及有效实现，它具有以下优点: : 约束表示允许以说明性的方式来表达领域知识，表达约束表示允许以说明性的方式来表达领域知识，表达能力较强，应用程序只需指定问题的目标条件及数据间能力较强，应用程序只需指

7、定问题的目标条件及数据间的相互关系。因而具有逻辑表示的类似性质。的相互关系。因而具有逻辑表示的类似性质。 约束表示允许变量的域包含任意多个值，而不像命题约束表示允许变量的域包含任意多个值，而不像命题 只取真假二值。所以它保存了问题的一些结构信息，如只取真假二值。所以它保存了问题的一些结构信息，如变量域的大小、变量间的相关性等，从而为问题求解提供变量域的大小、变量间的相关性等，从而为问题求解提供启发式信息。启发式信息。 易于并行实现。因为约束网络上的信息传播可以认为是易于并行实现。因为约束网络上的信息传播可以认为是同时的。同时的。 适合于递增型系统。约束可以递增式地加入到约束网络。适合于递增型系

8、统。约束可以递增式地加入到约束网络。 易于与领域相关的问题求解模型相衔接。各种数学规划技易于与领域相关的问题求解模型相衔接。各种数学规划技术，方程求解技术等术，方程求解技术等, , 都可以自然地嵌入约束系统。都可以自然地嵌入约束系统。第7页/共79页2021-11-5史忠植 约束推理8约束推理约束推理 约束搜索约束搜索约束搜索主要研究有限域上的约束满足。对有限域而言，约束搜索主要研究有限域上的约束满足。对有限域而言，约束满足问题一般情况下是约束满足问题一般情况下是 一个一个 NP NP 问题。问题。 约束语言约束语言第8页/共79页2021-11-5史忠植 约束推理9约束搜索约束搜索 回溯法。

9、 约束传播。 智能回溯与真值维护。 可变次序例示。 局部修正法。第9页/共79页2021-11-5史忠植 约束推理10约束语言约束语言CONSTRAINTSCHIPCOPSILOG第10页/共79页2021-11-5史忠植 约束推理11CONSTRAINTSCONSTRAINTS约束语言约束语言 CONSTRAINTSCONSTRAINTS是一个面向电路描述的约束表示语言。是一个面向电路描述的约束表示语言。作为一个约束表示语言，作为一个约束表示语言，它使用了符号处理技术来求解数它使用了符号处理技术来求解数学方程。在学方程。在CONSTRAITSCONSTRAITS中，物理部件的功能及器件的结构

10、都用中，物理部件的功能及器件的结构都用约束表示。这些约束一般是线性方程与不等式约束表示。这些约束一般是线性方程与不等式, , 也包括条件表也包括条件表达式。约束变量一般是表示物理量的实变量。也有一些取离散达式。约束变量一般是表示物理量的实变量。也有一些取离散值的变量。如开关的状态、三极管的工作状态等。系统采用表值的变量。如开关的状态、三极管的工作状态等。系统采用表达式推理与值推理。并实现相关制导的回溯。达式推理与值推理。并实现相关制导的回溯。 第11页/共79页2021-11-5史忠植 约束推理12CONSTRAINTSCONSTRAINTS约束语言约束语言 CONSTRAINTS CONST

11、RAINTS 的一个优点是在类型层次中表示约束，用约束的一个优点是在类型层次中表示约束，用约束来表示物理对象的功能与结构。其缺点是该语言缺乏类似于面向来表示物理对象的功能与结构。其缺点是该语言缺乏类似于面向对象语言中的方法那样的成分，不能定义特定于某个类的概念。对象语言中的方法那样的成分，不能定义特定于某个类的概念。同时，约束传播方法比较单一，既缺乏实域上的区间传播机制，同时，约束传播方法比较单一，既缺乏实域上的区间传播机制，也缺乏有限域上的也缺乏有限域上的 域传播机制。域传播机制。 第12页/共79页2021-11-5史忠植 约束推理13约束逻辑程序设计语言约束逻辑程序设计语言CHIPCHI

12、P CHIP(Constraint handling in Prolog) CHIP(Constraint handling in Prolog) 就是这样较有影响就是这样较有影响一个约束逻辑程序设计语言，其目的是简便、灵活而有效地解决一个约束逻辑程序设计语言，其目的是简便、灵活而有效地解决一大类组合问题。它通过提供几种新的计算域而增强逻辑程序设一大类组合问题。它通过提供几种新的计算域而增强逻辑程序设计的能力；有限域、布尔项及有理项，对于每个计算域，都提供计的能力；有限域、布尔项及有理项，对于每个计算域，都提供有效的约束求解技术，即有限域上的一致性技术，布尔域的布尔有效的约束求解技术，即有限域

13、上的一致性技术，布尔域的布尔合一技术及有理数域上的单纯型法。除此以外，合一技术及有理数域上的单纯型法。除此以外，CHIPCHIP还包含一个还包含一个一般的延迟计算机制。一般的延迟计算机制。 CHIP CHIP 主要应用于两个领域主要应用于两个领域: : 运筹学与硬件设计。运筹学与硬件设计。 CHIP CHIP 缺乏类型机制，而这种机制对于表达领域概念是极其重缺乏类型机制，而这种机制对于表达领域概念是极其重要的。要的。第13页/共79页2021-11-5史忠植 约束推理14面向对象约束语言面向对象约束语言COPSCOPS COPSCOPS系统利用面向对象技术，将说明性约束表达与类型层次系统利用面

14、向对象技术，将说明性约束表达与类型层次结合起来。在形式上吸收了常规语言，主要是面向对象的程序设结合起来。在形式上吸收了常规语言，主要是面向对象的程序设计语言的基本形式。内部求解时采用约束推理机制，使说明性约计语言的基本形式。内部求解时采用约束推理机制，使说明性约束表达式与类型层次相结合，实现知识的结构化封装，充分发挥束表达式与类型层次相结合，实现知识的结构化封装，充分发挥两者的优点，力图实现一个具有较强表达能力和较高求解效率的两者的优点，力图实现一个具有较强表达能力和较高求解效率的约束满足系统。约束满足系统。第14页/共79页2021-11-5史忠植 约束推理15面向对象约束语言面向对象约束语

15、言COPSCOPSCOPSCOPS的设计考虑了软件工程的应用要求，尽量将一个不确定问的设计考虑了软件工程的应用要求，尽量将一个不确定问题确定化：它允许条件语句与循环语句，而不是单题确定化：它允许条件语句与循环语句，而不是单纯以递归的形式来实现迭代计算；纯以递归的形式来实现迭代计算； 通过类方法的重栽实现同一通过类方法的重栽实现同一约束的不同实现，提高了程序的执行效率。约束的不同实现，提高了程序的执行效率。COPSCOPS系统同时是一个系统同时是一个渐增式的开放系统，用户能通过类型层次定义，实现新的数据类渐增式的开放系统，用户能通过类型层次定义，实现新的数据类型和新的约束关系。约束语言型和新的约

16、束关系。约束语言COPSCOPS具有许多人工智能程序设计语具有许多人工智能程序设计语言的特点，如约束传播、面向目标和数据驱动的问题求解、有限言的特点，如约束传播、面向目标和数据驱动的问题求解、有限步的回溯、对象分层中的继承等。步的回溯、对象分层中的继承等。 第15页/共79页2021-11-5史忠植 约束推理16 在实际应用中，算法的表现形式千变万化，在实际应用中，算法的表现形式千变万化，但是算法的情况也和数据结构类似，许多算法但是算法的情况也和数据结构类似，许多算法的设计思想具有相似之处，我们可以对它们分的设计思想具有相似之处，我们可以对它们分类进行学习和研究。类进行学习和研究。 常用的算法

17、大致有如下一些：常用的算法大致有如下一些：贪心法贪心法分治法：如二分法检索分治法：如二分法检索回溯法回溯法动态规划法动态规划法局部搜索法局部搜索法分支限界法分支限界法常用的算法常用的算法第16页/共79页2021-11-5史忠植 约束推理17 评价一个程序优劣的重要依据是看这个程序的执行需要占用多少机器资源。人们最关心的就是程序所用算法运行时所要花费的时间代价和程序中使用的数据结构占有的空间代价。 算法的空间代价算法的空间代价(或称空间复杂性空间复杂性)：当被解决问题的规模(以某种单位计算)由1增至n时，解该问题的算法所需占用的空间也以某种单位由f(1) 增至f(n)，这时我们称该算法的空间代

18、价是f(n)。 算法的时间代价算法的时间代价(或称时间复杂性时间复杂性)：当问题规模以某种单位由1增至n时，对应算法所耗费的时间也以某种单位由g(1)增至g(n)，这时我们称算法的时间代价是g(n)。 算法分析算法分析第17页/共79页2021-11-5史忠植 约束推理18穷尽搜索方法穷尽搜索方法穷尽搜索方法穷尽搜索方法 即产生所有可能的树，然后根据评价即产生所有可能的树，然后根据评价标准选择一棵最优的树。标准选择一棵最优的树。 Exhaustive-Search-Top(P) where P is a CSP of the form(V,D,C)1. f:= the null assignm

19、ent2. return Exhaustive-Search(f,P)第18页/共79页2021-11-5史忠植 约束推理19穷尽搜索方法穷尽搜索方法 Exhaustive-Search(f,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 := some variable in P that is not yet assigned a value by f8

20、. answer := Unsat9. for each value while answer = Unsat10. f(v) := 11. answer := Exhaustive-Search(f,P)12. return answer第19页/共79页2021-11-5史忠植 约束推理20贪心法贪心法贪心法把构造可行解的工作分阶段来完成。在各个阶段，选择那些在某些意义下是局部最优的方案，期望各阶段的局部最优的选择带来整体最优。例：Dijkstra的最短路径算法、Kruskal的求最小生成树算法、信号灯问题第20页/共79页2021-11-5史忠植 约束推理21回溯算法回溯算法有些问题需要

21、彻底的搜索才能解决问题，然而，彻底的搜索要以大量的运算时间为代价，对于这种情况可以通过回溯法来去掉一些分支，从而大大减少搜索的次数。八皇后问题迷宫问题深度优先周游树或图约束推理 ppt第21页/共79页 四皇后问题中隐含的状态树 四皇后问题四皇后问题第22页/共79页2021-11-5史忠植 约束推理234-Queens Puzzle第23页/共79页2021-11-5史忠植 约束推理244-Queens Tree第24页/共79页回溯算法回溯算法empty assignment1st variable2nd variable3rd variableAssignment = 第25页/共79页

22、回溯算法回溯算法empty assignment1st variable2nd variable3rd variableAssignment = (var1=v11)第26页/共79页回溯算法回溯算法empty assignment1st variable2nd variable3rd variableAssignment = (var1=v11),(var2=v21)第27页/共79页回溯算法回溯算法empty assignment1st variable2nd variable3rd variableAssignment = (var1=v11),(var2=v21),(var3=v31)

23、第28页/共79页回溯算法回溯算法empty assignment1st variable2nd variable3rd variableAssignment = (var1=v11),(var2=v21),(var3=v32)第29页/共79页回溯算法回溯算法empty assignment1st variable2nd variable3rd variableAssignment = (var1=v11),(var2=v22)第30页/共79页回溯算法回溯算法empty assignment1st variable2nd variable3rd variableAssignment = (

24、var1=v11),(var2=v22),(var3=v31)第31页/共79页2021-11-5史忠植 约束推理32回溯算法回溯算法 Backtracking-Top(P)1 f := the null assignment2 return Backtracking(f,P)第32页/共79页2021-11-5史忠植 约束推理33回溯算法回溯算法 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

25、 yet assigned a value by f5 answer := Unsat6 for each value while answer = Umsat7 f(v) := x8 if f satisfies the constraints in P9 answer := Backtracking(f,P)10 return answer第33页/共79页2021-11-5史忠植 约束推理34Backtracking AlgorithmBased on depth-first recursive searchApproach1.Tests whether solution has bee

26、n found2.If found solution, return it3.Else for each choice that can be madea)Make that choiceb)Recurc)If recursion returns a solution, return it4.If no choices remain, return failureSome times called “search tree”第34页/共79页2021-11-5史忠植 约束推理35回溯算法回溯算法 尽管回溯法好于生成测试法，但对于非平凡问题仍尽管回溯法好于生成测试法，但对于非平凡问题仍然是低效的

27、。其原因在于搜索空间中不同路径的搜索重然是低效的。其原因在于搜索空间中不同路径的搜索重复相同的失败子路径。一些研究者认为，造成这种反复复相同的失败子路径。一些研究者认为，造成这种反复的原因是所谓的局部不一致性。最简单的情形是所谓的的原因是所谓的局部不一致性。最简单的情形是所谓的结点不一致性。对一个变量结点不一致性。对一个变量vivi的一个一元约束。存在域的一个一元约束。存在域中一个值中一个值vivi不满足该约束。这样，每当不满足该约束。这样，每当vivi取到取到 a a 时就时就会出现会出现不一致性。不一致性。 另一种重复的情形另一种重复的情形 是所谓的弧不一致性。是所谓的弧不一致性。第35页

28、/共79页2021-11-5史忠植 约束推理36 约束传播约束传播CONSTRAINT PROPAGATION(red, green)(red,blue)(red, green,blue) 弧一致性Arc consistency 第36页/共79页2021-11-5史忠植 约束推理37弧一致性弧一致性 Arc consistency 如果对vi vi 的当前域中的所有值x x，存在vjvj的当前域中的某值y y使得 vi=xvi=x和vj=yvj=y是vivi与vjvj之间的约束所允许的，则弧(vi, vj)(vi, vj)是弧一致的。 弧一致性的概念是有向的。即(vi, vj)(vi, vj

29、)是弧一致的并不自动地意味着(vj, vi)(vj, vi)是一致的。第37页/共79页2021-11-5史忠植 约束推理38 CONSTRAINT PROPAGATION CONSTRAINT PROPAGATIONAll of the Mackworth algorithms make use All of the Mackworth algorithms make use of a Revise procedure.of a Revise procedure. Let Dv be the current domain of v, Let Dv be the current domain

30、of v, Let Dw be the current domain of w, Let Dw be the current domain of w, Let P be the constraint predicate that Let P be the constraint predicate that holds between v and w, then Revise updates holds between v and w, then Revise updates Dv as followsDv as follows: :yxPDDxDwyvv,such that : 第38页/共7

31、9页2021-11-5史忠植 约束推理39CONSTRAINT PROPAGATIONCONSTRAINT PROPAGATIONMackworth 1977Mackworth 1977 AC-1 AC-1 AC-2AC-2 AC-3 AC-3第39页/共79页2021-11-5史忠植 约束推理40约束传播修改算法约束传播修改算法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 delete x from Di;7 D

32、ELETE true;8 endif 9 endfor 10 return DELETE; 11 end REVISE第40页/共79页2021-11-5史忠植 约束推理41弧一致性算法弧一致性算法AC-11 Q ;2 repeat 3 CHANGE false;4 for each (Vi, Vj) Q do5 CHANGE REVISE(Vi, Vj) CHANGE;6 endfor;7 until not(CHANGE);8 end AC-1 V VGijij, arcs 第41页/共79页2021-11-5史忠植 约束推理42弧一致性算法弧一致性算法AC-31 Q ;2 While Q

33、 not empty 3 Select and delete any arc(Vk,Vm) from Q;4 If (REVISE(Vk,Vm)5 Then Q (Vi,Vk) such that (Vi,Vk)arcs(G),6 ik, im;6 endfor;7 endwhile;8 end AC-3 V VGijij, arcs 第42页/共79页弧一致性算法弧一致性算法AC-3If Xis domain is filtered all the constraints associated with it andother variables are added to the queue

34、 Binary constraintXi, Xj第43页/共79页弧一致性算法弧一致性算法AC-3 时间复杂性: n2= number of constraints (edges; n is the # of variables)d = number of values per variableREMOVE-ARC-INCONSISTENCY takes O(d2) timeEach variable is inserted in Queue up to d times, since at most d values can be deletedAC3 takes O(n2d3) time t

35、o run第44页/共79页2021-11-5史忠植 约束推理45BackjumpingBackjumpingBackjumping-Top(P)1 f := the null assignment2 := Backjumping(f,P)3 return answer 第45页/共79页2021-11-5史忠植 约束推理46BackjumpingBackjumpingBackjumping(f,P)1 if f is a total assignment of the variables in P2 answer := 3 else 4 v := some variable in P tha

36、t is not yet assigned a value by f5 answer := Unsat6 conflict-set := 7 for each value 8 f(v) := x9 if f satisfies the constraints in P10 := Backjumping(f,P) 第46页/共79页2021-11-5史忠植 约束推理47BackjumpingBackjumping11 else12 new-conflicts := the set of variables in a violated constraint13 if answer Unsat14

37、return 15 else if v new-conflicts16 return 17 else 18 conflict-set := conflict-set (new-conflicts v)19 return 第47页/共79页2021-11-5史忠植 约束推理48COPSCOPS Constraint : predicate expression P(t1, ., tn) where P is built in function, such as sum times eq(equal) neq(not equal) ge(great than or equal to) gt(gre

38、at than) also can be defined by users第48页/共79页2021-11-5史忠植 约束推理49COPS Conditional constraint condition1: constraint1; . . conditionn: constraintn where condition1, ., conditionn are boolean expressions. constraint1,. constraintn are constraints or contraints table. 第49页/共79页2021-11-5史忠植 约束推理50COPS R

39、ULE Rule is used to define new function, method, predicate, or add new constraint into object. RULE class: predicate(varibles) (boolean expression)constraint_1;constraint_n; CASEboolean expression_1: constraint_1; boolean expression_m: constraint_m; 第50页/共79页2021-11-5史忠植 约束推理51COPS For example: RULE

40、 multiple(INTEGER: *x, INTEGER: y, INTEGER: z) (neq(y, 0) equal(x, divide(z, y); z = x * y第51页/共79页2021-11-5史忠植 约束推理52COPS CLASS class_name:superclass_name / attributes definition date type: attribute_name; . / rule definition rule_name; . /function definition function_name; . / method definition me

41、thod_name; . 第52页/共79页2021-11-5史忠植 约束推理53COPS Implementation Program written by COPS consists of classes and rules. COPS constraint programming language is a declarative language, providing classes, methods which are exist in object oriented language. It is similar with C+ . COPS has the features: c

42、onstraint object oriented logic programming production system 第53页/共79页2021-11-5史忠植 约束推理54COPS COPS_Compiler1 2 Call yacc to parse the program and 3 to generate internal structures.4 Initializatiion5 Create Cops Constant trueNode;6 Allocate memories for global variables. 第54页/共79页2021-11-5史忠植 约束推理55

43、COPS7 Interprte the program with the internal structures.8 Constraint networks are built up for Unsolved 9 constraints and variables.10 while some constraints in the constraint networks are triggered,11 inteprete the triggered constraints.12 第55页/共79页2021-11-5史忠植 约束推理56COPSInterpreter: 1 2 switch (c

44、onstraint type)3 case Constant:4 return Constant:5 case global variable:6 interprete global variable:7 case local variable or argument:8 interprete local variable or argument:9 case object-attribute pair;10 interprete object-attribute pair:11 case function call:第56页/共79页2021-11-5史忠植 约束推理57COPS12 int

45、erprete function call:13 case method call:14 interprete method call:15 case CASE expression:16 interprete CASE expression:17 .18 default:20 report error21 第57页/共79页2021-11-5史忠植 约束推理58ILOG SOLVERCombines object oriented programming with constraint logic programming, containing logic variables, increm

46、ental constraint satisfaction and backtracking. variables : C+ object integer variable CtIntVar floating variable CtFloatVar boolean variable CtBoolVarMemory Management new: delete:第58页/共79页2021-11-5史忠植 约束推理59ILOG SOLVERConstraints CtTell(x = (y + z); Basic constraints: =, , , , +, -, *, /, subset,

47、superset, union, intersection, member, boolean or, boolean and, boolean not, boolean xor, CtTell(x=0) | (y=0); CtIfThen (x chooseValue(); CtOr(Constraint(x = a), CtAnd(Constraint(x != a), CtInstantiate(x); 第60页/共79页2021-11-5史忠植 约束推理61 ILOG Schedule 1.0Schedule CtSchedule class Global object: time or

48、iginal -tineMin time horizon -timeMax 第61页/共79页2021-11-5史忠植 约束推理62 ILOG Schedule 1.0Resources CtResource CtDiscreteResource CtUnaryResource CtDiscreteEnergy CtStateResource 第62页/共79页2021-11-5史忠植 约束推理63 ILOG Schedule 1.0Activities CtActivity class CtIntervalActivity An activity is defined by its star

49、t time, end time and duration Activities require, provide, consume and produce resources第63页/共79页2021-11-5史忠植 约束推理64 Scheduling Problem Prices paid as tasks begin $1000 per day Availability: Day 0:$20000, Day 15: +$9000第64页/共79页2021-11-5史忠植 约束推理65ConstraintsConstraints / To create a schedule with or

50、igin 0 and given horizon.CtSchedule* schedule = new CtSchedule(0, horizon); / To create an activity with the given duration.CtIntervalActivity* act = new CtIntervalActivity(schedule, duration); /To post a precedence constraint between act1 and act2.act2-startsAfterEnd(act1,0); 第65页/共79页2021-11-5史忠植

51、约束推理66ConstraintsConstraints/To create a total budget of limited capacity (here 29000).CtDiscreteResource* res = new CtDiscreteResource(schedule, CtRequiredResource, capacity); / To state that only cap (here 20000) is available prior to a / given date (here 15).res-setCapacityMax(0,date,cap); / To s

52、tate that an activity act consumes c units of res.act-consumes(res, c);第66页/共79页2021-11-5史忠植 约束推理67Algorithm ProgramAlgorithm ProgramCtBoolean IsUnScheduled(CtActivity* act) / Return true if act does not have a fixed start time. if (act-getStartVariable()-isBound() return CtFalse; else return CtTrue

53、;第67页/共79页2021-11-5史忠植 约束推理68Algorithm ProgramAlgorithm ProgramCtBoolean 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; else if (act1-getStartMax() getStartMax() return CtTrue; else

54、 return CtFalse;第68页/共79页2021-11-5史忠植 约束推理69Algorithm ProgramAlgorithm ProgramCtActivity* SelectActivity(CtSchedule* schedule) / Returns the unscheduled activity with the smallest latest / statrt time. Returns 0 if all activities are scheduled. CtActivity* bestActivity = 0; /Creates an iterator to i

55、terate on all activities. CtActivityIterator* iterator(schedule); CtActivity* newActivity; while(iterator.next(newactivity) if(IsUnScheduled(newActivity) & (IsMoreUgent(newActivity, bestActivity) bestactivity = newActivity; return bestActivity;第69页/共79页2021-11-5史忠植 约束推理70Algorithm ProgramAlgorithm Programvoid SolveProblem(CtSchedule* schedule) / Solve the problem assumi