第3章_约束推理.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,史忠植 高级人工智能,*,高级人工智能,第三章,约束推理,Advanced Artificial Intelligence,史忠植,中国科学院计算技术研究所,1/15/2026,1,史忠植 高级人工智能,第三章,约束推理,3.1,概述,3.2,回溯法,3.3,约束传播,3.4,回跳法,3.5,约束推理系统,COPS,3.6 ILOG SOLVER,1/15/2026,2,史忠植 高级人工智能,3.1 概 述,最优化问题,经济学所推崇的,帕累托,最优,:,几个人拎着水桶在一个水龙头前面排队打水，水桶有大有小。他们怎样排队，才能使得总的排队时间最短。这是一个寻求“最优化”的题目，目标是节省总的排队时间，达到最优。,1/15/2026,3,史忠植 高级人工智能,3.1 概 述,优化问题,运筹学,遗传算法,神经网络,约束推理,1/15/2026,4,史忠植 高级人工智能,运筹学的工作步骤,1,）提出和形成问题，,2,）建立模型，,3,）求解，,4,）解的检验，,5,）解的控制，,6,）解的实施。,1/15/2026,5,史忠植 高级人工智能,线性规划问题,例1,(,广告方式的选择)中华家电公司推销一种新型洗衣机，有关数据见下表。销售部第一月的广告预算为,20000,元，要求至少有,8,个电视商业节目，15家报纸广告；电视广告费不得超过,12000,元，电台广播至少隔日有一次。现问该公司销售部应当采用怎样的广告宣传计划，才能取得最好的效果?,1/15/2026,6,史忠植 高级人工智能,线性规划问题,广告方式,广告费用,(元/次),可用最高次数,/月,期望的宣传效果,/,单位,电视台,a(,白天,1,分钟,),500,16,50,电视台,b(,晚上,30钞),1000,10,80,每日晨报,/(,半版,),100,24,30,星期日报,/(,半版,),300,4,40,广播电台,/(1,分钟,),80,25,15,表1,中华家电公司推销新型洗衣机广告方式选择的数据表,1/15/2026,7,史忠植 高级人工智能,线性规划问题,解：,设,x,1,x,2,x,3,x,4,x,5,分别是第一个月内电视台,a，,电视台,b，,每日晨报，星期日报，广播电台进行广告宣传的次数，则其数学模型为,max,50,x,1,+80,x,2,+30,x,3,+40,x,4,+15,x,5,s.t.,50,x,1,+80,x,2,+30,x,3,+40,x,4,+15,x,5,20000，,x,1,+,x,2,8，,x,3,+,x,4,15，,500,x,1,+1000,x,2,12000，,x,1,16,x,2,10,x,3,24,x,4,4,15,x,5,25,x,1,x,2,x,3,x,4,x,5,0。,1/15/2026,8,史忠植 高级人工智能,线性规划问题,线性规划问题(,LP),的一般形式为,：,min(max),z,=,c,1,x,1,+,c,2,x,2,+,+,c,n,x,n,s.t.,a,11,x,1,+a,12,x,2,+a,1n,x,n,(,),b,1,a,21,x,1,+a,22,x,2,+a,2n,x,n,(,),b,2,a,m1,x,1,+a,m2,x,2,+,a,mn,x,n,(,),b,m,x,j,0,j,=,1,2,n,1/15/2026,9,史忠植 高级人工智能,线性规划问题,线性规划问题的标准形式为：,min,X,C,z,T,=,注：任何形式的线性规划问题均可化为标准型。,AX,=,b,s.t.,X,0 (,假定,b,为非负,),1/15/2026,10,史忠植 高级人工智能,求解,-,单纯形法,将所给,问题化为标准形,找出一个初始可行基，建立初始单纯形表,检查所有检验数,(,若全为非负，则已得到最优解,计算停止。否则继续下一步,),考察是否无解,(,若是，计算停止，否则继续下一步,),确定入基变量，出基变量,对初始单纯形表进行单纯形变换,1/15/2026,11,史忠植 高级人工智能,3.1,概 述,一个,约束,(,Constraint,),通常是指一个包含若干变量的关系表达式，用以表示这些变量所必须满足的问题。,约束表示广泛地应用于人工智能的各个领域，包括定性推理、机械与电子设备的设计与分析等。,约束满足系统的设计是一项困难而复杂的任务，因为约束满足问题在一般情况下是一个,NP,(,Nonpolynomia,),问题，所以必须使用各种策略与启发式信息。,1/15/2026,12,史忠植 高级人工智能,3.1 概 述,一个约束满足问题,(,Constraint Satisfaction Problem,简称,CSP),包含一组变量与一组变量间的约束。,变量表示领域参数，每个变量都有一个固定的值域。,一个变量的值域可能是,有限的,，例如一个布尔变量的值域包含两个值；也可能是,离散无限,的，如整数域；也可能是连续的，如实数域。,x,1,x,2,x,n,D,1,D,2,D,n,.,4,5,6,7,red,green,blue,1/15/2026,13,史忠植 高级人工智能,3.1 概 述,约束可用于描述领域对象的性质、相互关系、任务要求、目标等。约束满足问题的,目标,就是,找,到所有变量的一个（或多个）,赋值,，使所有约束都得到满足。,现有的约束表示可分为几类，,按复杂性的次序列举如下：,一元谓词。,序关系语言，只包含偏序关系或实变量上的大小关系。,形如“,x,-,y,c,”,或“,x,-,y,c,”,的方程。,单位系数的线性方程与不等式，即所有的系数为-1,0,1。,任意系数的线性方程与不等式。,约束的布尔组合。,代数与三角方程。,1/15/2026,14,史忠植 高级人工智能,3.1 概 述,约束表示易于理解、编码及有效实现，具有以下,优点:,约束表示允许,以说明性的方式,来表达领域知识，表达能力较强，应用程序只需指定问题的目标条件及数据间的相互关系。因而具有逻辑表示的类似性质。,约束表示允许,变量的域包含任意多个值,，而不像命题只取真假二值。它保存了问题的一些结构信息，如变量域的大小、变量间的相关性等，从而为问题求解提供启发式信息。,易于并行实现,。因为约束网络上的信息传播可以,认为是同时的。,适合于,递增型系统,。约束可以递增式地加入到约束网络。,易于,与领域相关的问题求解模型,相衔接。各种数学规划技术，方程求解技术等,都可以自然地嵌入约束系统。,1/15/2026,15,史忠植 高级人工智能,3.1 概 述,目前，,约束推理的研究主要集中于两个方面：,约束搜索,与,约束语言,。,约束搜索,主要研究有限域上的约束满足。对有限域而言，约束满足问题一般情况下是一个,NP,问题。大体包括下列方法：,回溯法；,约束传播；,智能回溯与真值维护；,可变次序例示；,局部修正法；,1/15/2026,16,史忠植 高级人工智能,3.1 概 述,约束推理研究的另一个主要方面是,约束语言,。以下是几个比较典型的约束语言：,CONSTRAINTS：,面向电路描述的约束表示语言。,Bertrand：,Leler,开发的一个高级约束语言。,CHIP：,约束逻辑程序设计语言。,约束层次与,HCLP：,层次型,约束逻辑程序设计语言。,COPS：,面向对象的程序设计语言的基本形式。,ILOG：,使用建模语言来表示约束问题。,1/15/2026,17,史忠植 高级人工智能,CONSTRAINTS,约束语言,CONSTRAINTS,是一个面向电路描述的约束表示语言。作为一个约束表示语言，它使用了符号处理技术来求解数学方程。,在,CONSTRAITS,中，物理部件的功能及器件的结构都用约束表示。,这些约束一般是线性方程与不等式,也包括条件表达式。约束变量一般是表示物理量的实变量。也有一些取离散值的变量。如开关的状态、三极管的工作状态等。系统采用表达式推理与值推理。并实现相关制导的回溯。,1/15/2026,18,史忠植 高级人工智能,CONSTRAINTS,约束语言,CONSTRAINTS,的一个,优点：,在类型层次中表示约束，用约束来表示物理对象的功能与结构。,缺点：,是该语言缺乏类似于面向对象语言中的方法那样的成分，不能定义特定于某个类的概念。,同时，约束传播方法比较单一，既缺乏实域上的区间传播机制，也缺乏有限域上的 域传播机制。,1/15/2026,19,史忠植 高级人工智能,约束逻辑程序设计语言,CHIP,CHIP(Constraint handling in Prolog),就是这样较有影响一个约束逻辑程序设计语言，其目的是简便、灵活而有效地解决一大类组合问题。它通过提供几种新的计算域而增强逻辑程序设计的能力；有限域、布尔项及有理项，对于每个计算域，都提供有效的约束求解技术，即有限域上的一致性技术，布尔域的布尔合一技术及有理数域上的单纯型法。除此以外，,CHIP,还包含一个一般的延迟计算机制。,CHIP,主要应用于两个领域：运筹学与硬件设计。,CHIP,缺乏类型机制，而这种机制对于表达领域概念是极其重要的。,1/15/2026,20,史忠植 高级人工智能,面向对象约束语言,COPS,COPS,系统利用面向对象技术，将说明性约束表达与类型层次结合起来。在形式上吸收了常规语言，主要是面向对象的程序设计语言的基本形式。内部求解时采用约束推理机制，使说明性约束表达式与类型层次相结合，实现知识的结构化封装，充分发挥两者的优点，力图实现一个具有较强表达能力和较高求解效率的约束满足系统。,1/15/2026,21,史忠植 高级人工智能,面向对象约束语言,COPS,COPS,的设计考虑了软件工程的应用要求，尽量将一个不确定问题确定化：它允许条件语句与循环语句，而不是单纯以递归的形式来实现迭代计算；通过类方法的重栽实现同一约束的不同实现，提高了程序的执行效率。,COPS,系统同时是一个渐增式的开放系统，用户能通过类型层次定义，实现新的数据类型和新的约束关系。约束语言,COPS,具有许多人工智能程序设计语言的特点，如约束传播、面向目标和数据驱动的问题求解、有限步的回溯、对象分层中的继承等。,1/15/2026,22,史忠植 高级人工智能,常用的算法,在实际应用中，算法的表现形式千变万化，但是算法的情况也和数据结构类似，许多算法的设计思想具有相似之处，我们可以对它们分类进行学习和研究。常用的算法大致有如下一些：,贪心法,分治法（如二分法检索）,回溯法,动态规划法,局部搜索法,分支限界法,1/15/2026,23,史忠植 高级人工智能,算法分析,评价一个程序优劣的重要依据是看这个程序的执行需要占用多少机器资源。人们最关心的就是程序所用算法运行时所要花费的,时间代价,和程序中使用的数据结构占有的,空间代价,。,算法的空间代价,(,或称,空间复杂性,),：当被解决问题的规模,(,以某种单位计算,)由1,增至,n,时，解该问题的算法所需占用的空间也以某种单位由,f,(1),增至,f,(,n,)，,这时我们称该算法的,空间代价是,f,(,n,),。,算法的时间代价,(,或称,时间复杂性,),：当问题规模以某种单位由,1,增至,n,时，对应算法所耗费的时间也以某种单位由,g,(1),增至,g,(,n,)，,这时我们称算法的,时间代价是,g,(,n,),。,1/15/2026,24,史忠植 高级人工智能,穷尽搜索方法,穷尽搜索方法,即产生所有可能的树，然后根据评价标准选择一棵最优的树。,Exhaustive-Search-Top(P),where P is a CSP of the form(V,D,C),1.f:=the null assignment,2.return Exhaustive-Search(f,P),1/15/2026,25,史忠植 高级人工智能,穷尽搜索方法,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:=,Unsat,9.for each value while answer=,Unsat,10.f(v):=,x,11.answer:=Exhaustive-Search(f,P),12.return answer,1/15/2026,26,史忠植 高级人工智能,贪 心 法,贪心法把构造可行解的工作分阶段来完成。在各个阶段，选择那些在某些意义下是局部最优的方案，期望各阶段的局部最优的选择带来整体最优。,例：,Dijkstra,的最短路径算法,、,Kruskal,的求最小生成树算法,、,信号灯问题,1/15/2026,27,史忠植 高级人工智能,3.2 回 溯 法,有些问题需要彻底的搜索才能解决问题，然而，彻底的搜索要以大量的运算时间为代价，对于这种情况可以通过回溯法来去掉一些分支，从而大大减少搜索的次数。,八皇后问题,迷宫问题,深度优先周游树或图,1/15/2026,28,史忠植 高级人工智能,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,Recur,If recursion returns a solution,return it,If no choices remain,return failure,Some times called“search tree”,1/15/2026,29,史忠植 高级人工智能,3.2 Solution to 8-Queens Puzzle,八,皇后,问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家,高斯,1850,年提出：在8,8,格的,国际象棋,上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有,76,种,方案。,1854,年在,柏林,的象棋杂志上不同的作者发表了,40,种不同的解，后来有人用图论的方法解出,92,种,结果。计算机发明后，有多种方法可以解决此问题。,1/15/2026,30,史忠植 高级人工智能,4-Queens Puzzle,1/15/2026,31,史忠植 高级人工智能,4-Queens Tree,1/15/2026,32,史忠植 高级人工智能,3.2 回 溯 法,Backtracking-Top(P),1 f:=the null assignment,2 return Backtracking(f,P),1/15/2026,33,史忠植 高级人工智能,3.2 回溯法,Backtracking(f,P),1 if f is a total assignment of the variables in P,2 answer:=f,3 else,4 v:=,some variable in P that is not yet assigned a value by f,5 answer:=,Unsat,6 for each value while answer=,Umsat,7 f(v):=x,8 if f satisfies the constraints in P,9 answer:=Backtracking(f,P),10 return answer,1/15/2026,34,史忠植 高级人工智能,3.2 回溯法,尽管回溯法好于生成测试法，但对于非平凡问题仍然是低效的。其原因在于搜索空间中不同路径的搜索重复相同的失败子路径。一些研究者认为，造成这种反复的原因是所谓的局部不一致性。最简单的情形是所谓的结点不一致性。对一个变量,v,i,的一个一元约束。存在域中一个值,v,i,不满足该约束。这样，每当,v,i,取到,a,时就会出现不一致性。,另一种重复的情形是所谓的弧不一致性。,1/15/2026,35,史忠植 高级人工智能,3.3 约束传播,如果对,v,i,的当前域中的所有值,x,，,存在,v,j,的当前域中的某值,y,使得,v,i,=,x,和,v,j,=,y,是,v,i,与,v,j,之间的约束所允许的，则弧,(,v,i,v,j,),是,弧一致的,。,弧一致性的概念是,有向的,。即,(,v,i,v,j,),是弧一致的并不自动地意味着,(,v,j,v,i,),是一致的。,1/15/2026,36,史忠植 高级人工智能,3.3,约束传播,CONSTRAINT PROPAGATION,(red,green),(red,blue),(red,green,blue),弧一致性（,Arc consistency,）,1/15/2026,37,史忠植 高级人工智能,3.3,CONSTRAINT PROPAGATION,All of the,Mackworth,algorithms make use of a Revise procedure.,Let,D,v,be the current domain of v,Let,D,w,be the current domain of w,Let P be the constraint predicate that holds between v and w,then Revise updates,D,v,as follows,:,D,v,:=,x,D,v,.,y,D,w,such that,P,(,x,y,),1/15/2026,38,史忠植 高级人工智能,3.3,CONSTRAINT PROPAGATION,Mackworth,1977,AC-1,AC-2,AC-3,1/15/2026,39,史忠植 高级人工智能,约束传播修改算法,procedure,REVISE(V,i,V,j,),1 DELETE,false;,2 for each x,D,i,do,3 if there is no such,y,j,D,j,4such that(x,y,j,)is consistent,5 then,6 delete x from D,i,;,7 DELETE,true;,8,endif,9,endfor,10 return DELETE;,11 end REVISE,1/15/2026,40,史忠植 高级人工智能,约束传播,AC-1,算法,procedure AC-1,1,Q,(,V,i,V,j,),arcs(,G,),i,j,;,2 repeat,3,CHANGE,false;,4 for each(V,i,V,j,),Q do,5 CHANGE,REVISE(V,i,V,j,),CHANGE;,6,endfor,;,7 until not(CHANGE);,8 end AC-1,1/15/2026,41,史忠植 高级人工智能,约束传播,AC-3,算法,procedure AC-3,1,Q,(,V,i,V,j,),arcs(,G,),i,j,;,2 while Q not empty,3 select and delete any arc(,V,k,V,m,)from Q;,4 if(REVISE(,V,k,V,m,),then Q,(V,i,V,k,)such that(V,i,V,k,),arcs(,G,),i,k,i,m,;,6,endif,;,7,endwhile,;,8 end AC-3,1/15/2026,42,史忠植 高级人工智能,回跳法,Backjumping,Backjumping,-Top(P),1 f:=the null assignment,2 :=,Backjumping,(f,P),3 return answer,1/15/2026,43,史忠植 高级人工智能,Backjumping,Backjumping,(f,P),1 if f is a total assignment of the variables in P,2 answer:=,3 else,4,v:=some variable in P that is not yet assigned a value by f,5 answer:=,Unsat,6 conflict-set:=,7 for each value,8 f(v):=x,9 if f satisfies the constraints in P,10 :=,Backjumping,(f,P),1/15/2026,44,史忠植 高级人工智能,Backjumping,11,else,12 new-conflicts:=the set of variables in a,violated constraint,13,if answer,Unsat,14,return,15 else if v,new-conflicts,16,return,17 else,18 conflict-set:=conflict-set,(new-conflictsv),19 return ,1/15/2026,45,史忠植 高级人工智能,3.11 约束推理系统,COPS,1.,约束与规则,约束是谓词表达式：,P,(,t,1,.,t,n,),其中，,t,1,.,t,n,是项，典型情况时包含变量；,P,是,谓词符号，谓词可以是内部函数，如,sum,times,eq,(equal),neq,(not equal),ge,(great than or equal to),gt,(great than),也可以由用户定义。,1/15/2026,46,史忠植 高级人工智能,3.11 约束推理系统,COPS,条件约束具有下面的形式：,if,condition,1,:constraint,1,;,condition,n,:,constraint,n,where,condition,1,.,condition,n,are,boolean,expressions.,constraint,1,constraint,n,are constraints,or,contraints,table.,1/15/2026,47,史忠植 高级人工智能,3.11 约束推理系统,COPS,RULE,Rule is used to define new function,method,predicate,or add new constraint into object.,RULE class:predicate(variables)(,boolean,expression),constraint,1,;,constraint,n,;,CASE,boolean,expression,1,:constraint,1,;,boolean,expression,m,:,constraint,m,;,1/15/2026,48,史忠植 高级人工智能,3.11 约束推理系统,COPS,For example:,RULE multiple(INTEGER:*,x,INTEGER:,y,INTEGER:,z,)(,neq,(,y,0),equal(x,divide(,z,y,);,这段程序定义了三个变量,x,、,y,、,z,之间的约束关系：,x,=,z,/,y,。,1/15/2026,49,史忠植 高级人工智能,3.11 约束推理系统,COPS,2.,类定义,CLASS class_name:,superclass,_name,/attributes definition,date type:attribute_name;,.,/rule definition,rule_name;,.,/function definition,function_name;,.,/method definition,method_name;,.,1/15/2026,50,史忠植 高级人工智能,3.11 约束推理系统,COPS,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:,constraint,object oriented,logic programming,production system,1/15/2026,51,史忠植 高级人工智能,3.11 约束推理系统,COPS,算法,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,的约束推理,1/15/2026,52,史忠植 高级人工智能,3.11 约束推理系统,COPS,算法中的解释器如下：,Interpreter:,1 ,2 switch(constraint 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:,1/15/2026,53,史忠植 高级人工智能,3.11 约束推理系统,COPS,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 .,18 default:,20 report error,21 ,1/15/2026,54,史忠植 高级人工智能,3.12,ILOG Solver,约束程序,是关于,约束的计算系统,，它的,输入,是,一组约束条件,和,需要求解的若干问题,，,输出,问题的,解决方案,。,至于具体解决问题的,算法,等都是约束程序设计语言的,基本功能。,程序员所要面对的，就是,如何把问题描述,为一组约束构成的模型，而描述的语言可以很接近自然语言。,如果把问题的解决方案,也看做是,一种约束,，那么,问题的求解,就是,求,得,一个或若干个约束,。,ILOG,公司是法国优化、互动图像界面以及商业规则应用领域的软件组件供应商，成立于1987年。,1/15/2026,55,史忠植 高级人工智能,3.12,ILOG Solver,ILOG Solver,是嵌入式过程性语言的约束设计语言，将面向对象程序设计和约束逻辑程序设计结合起来，包含逻辑变量，通过增量式约束满足和回溯实现问题求解。,ILOG Solver,中主要语言成分如下：,variables:C+object,/*,变量*/,integer variable,CtIntVar,floating variable,CtFloatVar,boolean,variable,CtBoolVar,Memory Management,/*,存储管理*/,new:,delete:,1/15/2026,56,史忠植 高级人工智能,3.12,ILOG SOLVER,Constraints,/*,约束*/,CtTell,(x=(y+z);,Basic constraints:=,+,-,*,/,subset,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);,1/15/2026,58,史忠植 高级人工智能,ILOG Schedule 1.0,Schedule,/*,调度*/,CtSchedule,class,Global object:time original,tineMin,time horizon,timeMax,Resources,/*,资源*/,CtResource,CtDiscreteResource,CtUnaryResource,CtDiscreteEnergy,CtStateResource,1/15/2026,59,史忠植 高级人工智能,ILOG Schedule 1.0,Activities,/*,工序*/,CtActivity,class,CtIntervalActivity,An activity is defined by its start time,end time and duration,Activities require,provide,consume and produce resources.,1/15/2026,60,史忠植 高级人工智能,Scheduling Problem,下面以房屋装修为例，如图3.1所示，采用,ILOG Schedule,给出规划方案，说明约束问题求解的原理。假定任务开始每天的开销是1000元，资金总额为20000元。工程进行到第15天，可以增加9000元。,1/15/2026,61,史忠植 高级人工智能,Constraints,/,To create a schedule with origin 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);,1/15/2026,62,史忠植 高级人工智能,Constraints,/,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 state that an activity act consumes c units of res.,act-consumes(,res,c);,1/15/2026,63,史忠植 高级人工智能,Algorithm Program,CtBoolean IsUnScheduled,(,CtActivity,*act),/Return true if act does not have a fixed start time.,if(act-,getStartVariable,()-,isBound,(),return,CtFalse,;,else,return,CtTrue,;,1/15/2026,64,史忠植 高级人工智能,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,;,else if(act1-,getStartMax,(),getStartMax,(),return,CtTrue,;,else,return,CtFalse,;,1/15/2026,65,史忠植 高级人工智能,Algorithm Program,CtActivity,*,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 iterate on all activities.,CtActivityIterator,*,iterator,(schedule);,CtActivity,*,newActivity,;,while(,iterator,.next(,newactivity,),if(,IsUnScheduled,(,newActivity,),&(,IsMoreUgent,(,newActivity,bestActivity,),bestactivity,=,newActivity,;,return,bestActivity,;,1/15/2026,66,史忠植 高级人工智能,Algorithm Program,void,SolveProblem,(,CtSchedule,*schedule),/Solve the problem assuming constraints have been posted.,CtActivity,*act=,SelectActivity,(sche