高级人工智能之约束推理

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,史忠植 高级人工智能,#,高级人工智能,第三章,约束推理,史忠植,中国科学院计算技术所,10/3/2024,1,史忠植 高级人工智能,第三章约束推,理,理,3.1,概,概,述,述,3.2,回,回,溯,溯法,3.3,约,约,束,束传播,3.4,回,回,跳,跳法,3.5,约,约,束,束推理,系,系统COPS,3.6,ILOG SOLVER,1/15/2020,2,史忠植,高,高级,人,人工智,能,能,3.1概述,最优化,问,问题,经济学,所,所推崇,的,的帕累,托,托最优,:,:,几个人,拎,拎着水,桶,桶在一,个,个水龙,头,头前面,排,排队打,水,水，水,桶有大,有,有小。,他,他们怎,样,样排队,，,，才能,使,使得总,的,的排队,时间最,短,短。这,是,是一个,寻,寻求“,最,最优化,”,”的题,目,目，目,标,标,是节省,总,总的排,队,队时间,，,，达到,最,最优。,1/15/2020,3,史忠植,高,高级,人,人工智,能,能,3.1概述,优化问,题,题,运筹学,遗传算,法,法,神经网,络,络,约束推,理,理,1/15/2020,4,史忠植,高,高级,人,人工智,能,能,运筹学,的,的工作,步,步骤,1）提,出,出和形,成,成问题,，,，,2）建,立,立模型,，,，,3）求,解,解，,4）解,的,的检验,，,，,5）解,的,的控制,，,，,6）解,的,的实施,。,。,1/15/2020,5,史忠植,高,高级,人,人工智,能,能,线性规,划,划问题,例1(,广,广告方,式,式的选,择,择)中,华,华家电,公,公司推,销,销一种,新,新型洗,衣,衣机,有,有关数,据,据见下,表,表.销,售,售部第,一,一月的,广,广告预,算,算为20000元,要,要求至,少,少有8,电,电视商,业,业节目,15,家,家报纸,广,广告/,电,电视广,告,告费不,得,得超过12000元,电台,广,广播至,少,少隔日,有,有一次,.,.现问,该,该公司,销,销售部,应,应当采,用,用怎样,的,的广告,宣,宣传计,划,划,才,能,能取得,最,最好的,效,效果?,1/15/2020,6,史忠植,高,高级,人,人工智,能,能,表1,广告方式,广告费用(元/次),可用最高次数/月,期望的宣传效果/单位,电视台a(白天,1 分钟),500,16,50,电视台b(晚上,30钞),1000,10,80,每日晨报/(半版),100,24,30,星期日报/(半版),300,4,40,广播电台/(1分钟),80,25,15,1/15/2020,7,史忠植,高,高级,人,人工智,能,能,1/15/2020,8,史忠植,高,高级,人,人工智,能,能,1/15/2020,9,史忠植,高,高级,人,人工智,能,能,1/15/2020,10,史忠植,高,高级,人,人工智,能,能,求解-,-,-单纯,形,形法,将所给,问,问题化,为,为标准,形,形,找出一,个,个初始,可,可行基,建立,初,初始单,纯,纯形表,检查所,有,有检验,数,数(若,全,全为非,负,负,则,已,已得到,最,最优解,计算,停,停止.,否,否则继,续,续下一,步,步),考察是,否,否无解,(,(若是,计算,停,停止,否,否则继,续,续下一,步,步),确定入,基,基变量,出基,变,变量,对初始,单,单纯形,表,表进行,单,单纯形,变,变换,1/15/2020,11,史忠植,高,高级,人,人工智,能,能,3.1概述,一个约,束,束满足,问,问题(Constraint SatisfactionProblem,简称CSP,),)包含一,组,组变量,与,与一组,变,变量间,的,的约束,。,。,变量,表,表示领,域,域参数,，,，每个,变,变量都,有,有一个,固,固定的,值,值域。,一个变,量,量的值,域,域可能,是,是有限,的,的，例,如,如一个,布,布尔变,量,量的值,域包含,两,两个值,；,；也可,能,能是离,散,散无限,的,的，如,整,整数域,；,；也可,能是连,续,续的，,如,如实数,域,域。,x1,x2,xn,D1,D2,Dn,.,.,4,5,6,7,red, green,blue,1/15/2020,12,史忠植,高,高级,人,人工智,能,能,3.1概述,约束,可,可用于,描,描述领,域,域对象,的,的性质,、,、相互,关,关系、,任,任务,要求、,目,目标等,。,。约束,满,满足,问,问题,的,的目标,就,就是找,到,到所有,变量的,一,一个（,或,或多个,）,）赋值,，,，使所,有,有约束,都,都得到,满,满足。,一元谓,词,词。,序关系,语,语言，,只,只包含,偏,偏序关,系,系或实,变,变量上,的,的大小,关,关系。,形如“x -y, c,”,”的方程,。,。,单位系,数,数的线,性,性方程,与,与不等,式,式，即,所,所有的,系,系数为,-1,0,1,。,。,任意系,数,数的线,性,性方程,与,与不等,式,式。,约束的,布,布尔组,合,合。,代数与,三,三角方,程,程。,1/15/2020,13,史忠植,高,高级,人,人工智,能,能,3.1概述,约束表,示,示易于,理,理解、,编,编码及,有,有效实,现,现，它,具,具有以,下,下优点,:,:,约束表,示,示允许,以,以说明,性,性的方,式,式来表,达,达领域,知,知识，,表,表达,能力较,强,强，应,用,用程序,只,只需指,定,定问题,的,的目标,条,条件及,数,数据间,的相互,关,关系。,因,因而具,有,有逻辑,表,表示的,类,类似性,质,质。,约束表,示,示允许,变,变量的,域,域包含,任,任意多,个,个值，,而,而不像,命,命题,只取真,假,假二值,。,。所以,它,它保存,了,了问题,的,的一些,结,结构信,息,息，如,变量域,的,的大小,、,、变量,间,间的相,关,关性等,，,，从而,为,为问题,求,求解提,供,供,启发式,信,信息。,易于并,行,行实现,。,。因为,约,约束网,络,络上的,信,信息传,播,播可以,认,认为是,同时的,。,。,适合于,递,递增型,系,系统。,约,约束可,以,以递增,式,式地加,入,入到约,束,束网络,。,。,易于与,领,领域相,关,关的问,题,题求解,模,模型相,衔,衔接。,各,各种数,学,学规划,技,技,术，方,程,程求解,技,技术等, 都,可,可以自,然,然地嵌,入,入约束,系,系统。,1/15/2020,14,史忠植,高,高级,人,人工智,能,能,3.1约束推,理,理,约束搜,索,索,约束搜,索,索主要,研,研究有,限,限域上,的,的约束,满,满足。,对,对有限,域,域而言,，,，,约束满,足,足问题,一,一般情,况,况下,是 一,个,个NP问题。,约束语,言,言,1/15/2020,15,史忠植,高,高级,人,人工智,能,能,3.1约束搜,索,索,回溯法,。,。,约束传,播,播。,智能回,溯,溯与真,值,值维护,。,。,可变次,序,序例示,。,。,局部修,正,正法。,1/15/2020,16,史忠植,高,高级,人,人工智,能,能,约束语,言,言,CONSTRAINTS,CHIP,COPS,ILOG,1/15/2020,17,史忠植,高,高级,人,人工智,能,能,CONSTRAINTS约束语,言,言,CONSTRAINTS是一个,面,面向电,路,路描述,的,的约束,表,表示语,言,言。,作为一,个,个约束,表,表示语,言,言，,它,它使用,了,了符号,处,处理技,术,术来求,解,解数学,方,方程。,在CONSTRAITS中，物,理,理部件,的,的功能,及,及器件,的,的结构,都,都用约,束,束表示,。,。,这些约,束,束一般,是,是线性,方,方程与,不,不等式, 也,包,包括条,件,件表达,式,式。约,束,束变量,一般是,表,表示物,理,理量的,实,实变量,。,。也有,一,一些取,离,离散值,的,的变量,。,。如开,关,关的状,态、三,极,极管的,工,工作状,态,态等。,系,系统采,用,用表达,式,式推理,与,与值推,理,理。并,实,实现,相关制,导,导的回,溯,溯。,1/15/2020,18,史忠植,高,高级,人,人工智,能,能,CONSTRAINTS约束语,言,言,CONSTRAINTS的一个,优,优点是,在,在类型,层,层次中,表,表示约,束,束，用,约,约束,来表示,物,物理对,象,象的功,能,能与结,构,构。其,缺,缺点是,该,该语言,缺,缺乏类,似,似于面,向,向,对象语,言,言中的,方,方法那,样,样的成,分,分，不,能,能定义,特,特定于,某,某个类,的,的概念,。,。,同时，,约,约束传,播,播方法,比,比较单,一,一，既,缺,缺乏实,域,域上的,区,区间传,播,播机制,，,，,也缺乏,有,有限域,上,上的,域,域传播,机,机制。,1/15/2020,19,史忠植,高,高级,人,人工智,能,能,约束逻,辑,辑程序,设,设计语,言,言CHIP,CHIP(ConstrainthandlinginProlog)就是这,样,样较有,影,影响,一个约,束,束逻辑,程,程序设,计,计语言,，,，其目,的,的是简,便,便、灵,活,活而有,效,效地解,决,决,一大类,组,组合问,题,题。它,通,通过提,供,供几种,新,新的计,算,算域而,增,增强逻,辑,辑程序,设,设,计的能,力,力；有,限,限域、,布,布尔项,及,及有理,项,项，对,于,于每个,计,计算域,，,，都提,供,供,有效的,约,约束求,解,解技术,，,，即有,限,限域上,的,的一致,性,性技术,，,，布尔,域,域的布,尔,尔,合一技,术,术及有,理,理数域,上,上的单,纯,纯型法,。,。除此,以,以外，CHIP还包含,一,一个,一般的,延,延迟计,算,算机制,。,。,CHIP主要应,用,用于两,个,个领域,:,: 运,筹,筹学与,硬,硬件设,计,计。,CHIP缺乏类,型,型机制,，,，而这,种,种机制,对,对于表,达,达领域,概,概念是,极,极其重,要的。,1/15/2020,20,史忠植,高,高级,人,人工智,能,能,面向对,象,象约束,语,语言COPS,COPS系统利,用,用面向,对,对象技,术,术，将,说,说明性,约,约束表,达,达与类,型,型层次,结合起,来,来。在,形,形式上,吸,吸收了,常,常规语,言,言，主,要,要是面,向,向对象,的,的程序,设,设,计语言,的,的基本,形,形式。,内,内部求,解,解时采,用,用约束,推,推理机,制,制，使,说,说明性,约,约,束表达,式,式与类,型,型层次,相,相结合,，,，实现,知,知识的,结,结构化,封,封装，,充,充分发,挥,挥,两者的,优,优点，,力,力图实,现,现一个,具,具有较,强,强表达,能,能力和,较,较高求,解,解效率,的,的,约束满,足,足系统,。,。,1/15/2020,21,史忠植,高,高级,人,人工智,能,能,面向对,象,象约束,语,语言COPS,COPS的设计,考,考虑了,软,软件工,程,程的应,用,用要求,，,，尽量,将,将一个,不,不确定,问,问,题确定,化,化：它,允,允许条,件,件语句,与,与循环,语,语句，,而,而不是,单,单,纯以递,归,归的形,式,式来实,现,现迭代,计,计算；,通,通过,类,类方法,的,的重栽,实,实现同,一,一,约束的,不,不同实,现,现，提,高,高了程,序,序的执,行,行效率,。,。COPS系统同,时,时是一,个,个,渐增式,的,的开放,系,系统，,用,用户能,通,通过类,型,型层次,定,定义，,实,实现新,的,的数据,类,类,型和新,的,的约束,关,关系。,约,约束语,言,言COPS具有许,多,多人工,智,智能程,序,序设计,语,语,言的特,点,点，如,约,约束传,播,播、面,向,向目标,和,和数据,驱,驱动的,问,问题求,解,解、有,限,限,步的回,溯,溯、对,象,象分层,中,中的继,承,承等。,1/15/2020,22,史忠植,高,高级,人,人工智,能,能,在实际,应,应用中,，,，算法,的,的表现,形,形式千,变,变万化,，,，但是,算,算法的,情,情况也,和,和数据,结,结构类,似,似，许,多,多算法,的,的设计,思,思想具,有,有相似,之,之处，,我,我们可,以,以对它,们,们分类,进,进行学,习,习和研,究,究。,常用的,算,算法大,致,致有如,下,下一些,：,：,贪心法,分治法,：,：如二,分,分法检,索,索,回溯法,动态规,划,划法,局部搜,索,索法,分支限,界,界法,1/15/2020,23,史忠植,高,高级,人,人工智,能,能,算法分,析,析,评价一,个,个程序,优,优劣的,重,重要依,据,据是看,这,这个程,序,序的执,行,行需要,占,占用多,少,少机器,资,资源。,人,人们最,关,关心的,就,就是程,序,序所用,算,算法运,行,行时所,要,要花费,的,的时间代,价,价和程序,中,中使用,的,的数据,结,结构占,有,有的空间代,价,价,。,算法的,空,空间代,价,价(或称空间复,杂,杂性)：当,被,被解决,问,问题的,规,规模(,以,以某种,单,单位计,算,算)由1增至n时，解,该,该问题,的,的算法,所,所需占,用,用的空,间,间也以,某,某种单,位,位由f(1)增至f(n)，这时我,们,们称该,算,算法的,空,空间代,价,价是f(n)。,算法的,时,时间代,价,价(或称时间复,杂,杂性)：当,问,问题规,模,模以某,种,种单位,由,由1增,至,至n时，对,应,应算法,所,所耗费,的,的时间,也,也以某,种,种单位,由,由g(1)增至g(n)，这时我,们,们称算,法,法的时,间,间代价,是,是g(n)。,1/15/2020,24,史忠植,高,高级,人,人工智,能,能,穷尽搜,索,索方法,穷尽搜,索,索方法,即产生,所,所有可,能,能的树,，,，然后,根,根据评,价,价标准,选,选择一,棵,棵最优,的,的树。,Exhaustive-Search-Top,(,(P),where PisaCSPofthe,form(V,D,C),1.f,:,:=thenullassignment,2.returnExhaustive-Search(f,P,),),1/15/2020,25,史忠植,高,高级,人,人工智,能,能,穷尽搜,索,索方法,Exhaustive-Search(f,P,),),1.iff is atotalassignmentofthevariables in P,2.iff satisfiestheconstraintsinP,3.answer,:,:=f,4.else,5.answer :,=,=Unsat,6.else,7.v,:,:=some variable in Pthatisnotyet assigned a,valuebyf,8.answer :,=,=Unsat,9.for eachvaluewhile answer,=,=Unsat,10.f,(,(v),:,:=,11.answer,:,:=Exhaustive-Search(f,P,),),12.returnanswer,1/15/2020,26,史忠植,高,高级,人,人工智,能,能,贪心法,贪心法,把,把构造,可,可行解,的,的工作,分,分阶段,来,来完成,。,。在各,个,个阶段,，,，选择,那,那些在,某,某些意,义,义下是,局,局部最,优,优的方,案,案，期,望,望各阶,段,段的局,部,部最优,的,的选择,带,带来整,体,体最优,。,。,例：Dijkstra的,最,最短路,径,径算法,、,、Kruskal的,求,求最小,生,生成树,算,算法、,信,信号灯,问,问题,1/15/2020,27,史忠植,高,高级,人,人工智,能,能,回溯算,法,法,有些问,题,题需要,彻,彻底的,搜,搜索才,能,能解决,问,问题，,然,然而，,彻,彻底的,搜,搜索要,以,以大量,的,的运算,时,时间为,代,代价，,对,对于这,种,种情况,可,可以通,过,过回溯,法,法来去,掉,掉一些,分,分支，,从,从而大,大,大减少,搜,搜索的,次,次数。,八皇后,问,问题,迷宫问,题,题,深度优,先,先周游,树,树或图,1/15/2020,28,史忠植,高,高级,人,人工智,能,能,回溯算,法,法,Backtracking,-,-Top(P,),),1f,:,:=the nullassignment,2returnBacktracking,(,(f,P),1/15/2020,29,史忠植,高,高级,人,人工智,能,能,回溯算,法,法,Backtracking,(,(f,P),1if fisatotalassignment of thevariablesinP,2answer,:,:=f,3else,4v,:,:=somevariableinPthat is notyetassignedavalue,byf,5answer,:,:=Unsat,6foreach valuewhileanswer,=,=Umsat,7f(v),:,:=x,8iffsatisfies theconstraintsinP,9answer,:,:=Backtracking,(,(f,P),10returnanswer,1/15/2020,30,史忠植,高,高级,人,人工智,能,能,回溯算,法,法,尽管回,溯,溯法好,于,于生成,测,测试法,，,，但对,于,于非平,凡,凡问题,仍,仍然是,低,低效的,。,。其原,因,因在于,搜,搜索空,间,间中不,同,同路径,的,的搜索,重,重复相,同,同的失,败,败子路,径,径。一,些,些研究,者,者认为,，,，造成,这,这种反,复,复的原,因,因是所,谓,谓的局,部,部不一,致,致性。,最,最简单,的,的情形,是,是所谓,的,的结点,不,不一致,性,性。对,一,一个变,量,量vi的一个,一,一元约,束,束。存,在,在域中,一,一个值vi不满足,该,该约束,。,。这样,，,，每当vi取到a时就会,出,出现,不一致,性,性。,另一种,重,重复的,情,情形,是,是所谓,的,的弧不,一,一致性,。,。,1/15/2020,31,史忠植,高,高级,人,人工智,能,能,3.3约束传,播,播,CONSTRAINT PROPAGATION,弧一致,性,性,Arcconsistency,1/15/2020,32,史忠植,高,高级,人,人工智,能,能,弧一致,性,性,Arcconsistency,如果对vi的当前,域,域中的,所,所有值x，存在vj的当前,域,域中的,某,某值y使得vi=x和vj=y是vi与vj之间的,约,约束所,允,允许的,，,，则弧,(,(vi,vj)是弧一,致,致的。,弧一致,性,性的概,念,念是有,向,向的。,即,即(vi,vj),是弧一,致,致的并,不,不自动,地,地意味,着,着(vj, vi)是一致,的,的。,1/15/2020,33,史忠植,高,高级,人,人工智,能,能,3.3CONSTRAINTPROPAGATION,AlloftheMackworthalgorithms makeuse of aRevise procedure.,LetDvbethecurrentdomainofv,LetDwbethecurrentdomainofw,LetPbetheconstraintpredicatethatholdsbetween vand w, thenRevise updatesDvasfollows,:,1/15/2020,34,史忠植,高,高级,人,人工智,能,能,CONSTRAINT PROPAGATION,Mackworth1977,AC-1,AC-2,AC-3,1/15/2020,35,史忠植,高,高级,人,人工智,能,能,约束传,播,播修改,算,算法,REVISE,(,(Vi,Vj,),),1DELETEfalse;,2foreach xDido,3ifthereisnosuch yjDj,4suchthat(x,yj)isconsistent,5then,6deletex fromDi,;,;,7DELETEtrue;,8endif,9endfor,10return DELETE;,11end REVISE,1/15/2020,36,史忠植,高,高级,人,人工智,能,能,AC-1,1Q;,2repeat,3CHANGEfalse;,4for each,(,(Vi,Vj)Q do,5CHANGEREVISE,(,(Vi,Vj)CHANGE,;,;,6endfor;,7untilnot(CHANGE),;,;,8end AC-1,1/15/2020,37,史忠植,高,高级,人,人工智,能,能,AC-3,1Q;,2WhileQnotempty,3Selectanddelete anyarc,(,(Vk,Vm) fromQ;,4If (REVISE,(,(Vk,Vm),Then Q(Vi,Vk) suchthat,(,(Vi,Vk)arcs(G),ik,im;,6endfor;,7endwhile;,8end AC-3,1/15/2020,38,史忠植,高,高级,人,人工智,能,能,Backjumping,Backjumping-Top(P,),),1f,:,:=the nullassignment,2,:,:=Backjumping(f,P),3returnanswer,1/15/2020,39,史忠植,高,高级,人,人工智,能,能,Backjumping,Backjumping(f,P,),),1if fisatotalassignment of thevariablesinP,2answer,:,:=,3else,4v,:,:=somevariableinPthat is notyetassignedavalue,byf,5answer,:,:=Unsat,6conflict-set,:,:=,7foreach value,8f(v),:,:=x,9iffsatisfies theconstraintsinP,10,:,:=Backjumping,(,(f,P),1/15/2020,40,史忠植,高,高级,人,人工智,能,能,Backjumping,11else,12new-conflicts,:,:=the setofvariablesina,violatedconstraint,13ifanswerUnsat,14return,15elseifvnew,-,-conflicts,16return,17else,18conflict-set,:,:=conflict-set(new-conflicts,v,),),19return,1/15/2020,41,史忠植,高,高级,人,人工智,能,能,COPS,Constraint :predicateexpression,P(t1,.,.,tn),where,Pisbuiltinfunction,suchas,sum,times,eq(equal,),),neq(not equal),ge(greatthanorequalto),gt(greatthan),also canbedefined by users,1/15/2020,42,史忠植,高,高级,人,人工智,能,能,COPS,Conditionalconstraint,condition1:constraint1;,.,.,conditionn:constraintn,where,condition1,.,.,conditionnarebooleanexpressions.,constraint1,.,.constraintnareconstraintsorcontraintstable.,1/15/2020,43,史忠植,高,高级,人,人工智,能,能,COPS,RULE,Rule is usedtodefine newfunction,method,predicate, or addnewconstraintinto object.,RULE class:,:,:predicate,(,(varibles) (booleanexpression),constraint_1,;,;,constraint_n,;,;,CASE,booleanexpression_1,:,:constraint_1,;,;,booleanexpression_m,:,:constraint_m,;,;,1/15/2020,44,史忠植,高,高级,人,人工智,能,能,COPS,Forexample:,RULE multiple(INTEGER,:,: *x,INTEGER:y,INTEGER:z),(,(neq(y,0),),),equal(x,divide,(,(z,y),),);,z =x,*,* y,1/15/2020,45,史忠植,高,高级,人,人工智,能,能,COPS,CLASS,class,_,_name,:superclass,_,_name,/attributes definition,date type,:,:attribute,_,_name;,.,/rule definition,rule_name,;,;,.,/function definition,function_name;,.,/methoddefinition,method,_,_name;,.,1/15/2020,46,史忠植,高,高级,人,人工智,能,能,COPS,Implementation,Program writtenbyCOPSconsistsofclasses andrules.COPSconstraint programming language is adeclarativelanguage, providingclasses,methods which areexistinobjectorientedlanguage,.,. It is similarwithC+,.,.COPS hasthefeatures,:,:,constraint,objectoriented,logicprogramming,production system,1/15/2020,47,史忠植,高,高级,人,人工智,能,能,COPS,COPS_Compiler,1,2Callyacctoparsetheprogramand,3togenerateinternalstructures.,4Initializatiion,5CreateCopsConstanttrueNode;,6Allocatememoriesforglobal variables.,1/15/2020,48,史忠植,高,高级,人,人工智,能,能,COPS,7Interprtethe programwiththeinternalstructures.,8Constraint networks arebuiltupforUnsolved,9constraintsandvariables.,10while someconstraintsinthe constraintnetworksare,triggered,11intepretethetriggered constraints.,12,1/15/2020,49,史忠植,高,高级,人,人工智,能,能,COPS,Interpreter:,1,2switch,(,(constrainttype),3caseConstant,:,:,4return Constant:,5caseglobal variable:,6interpreteglobalvariable,:,:,7caselocalvariableorargument,:,:,8interprete local variable or argument:,9caseobject-attributepair;,10interpreteobject,-,-attribute pair,:,:,11casefunctioncall:,1/15/2020,50,史忠植,高,高级,人,人工智,能,能,COPS,12interpretefunctioncall:,13casemethodcall:,14interpretemethod call,:,:,15caseCASE expression,:,:,16interpreteCASEexpression:,17,.,.,.,.,18default:,20report error,21,1/15/2020,51,史忠植,高,高级,人,人工智,能,能,ILOG SOLVER,Combinesobjectorientedprogrammingwithconstraint logic programming,containing logic variables,incrementalconstraintsatisfactionand backtracking.,variables,:,:C+object,integer variableCtIntVar,floatingvariableCtFloatVar,boolean variableCtBoolVar,MemoryManagement,new,:,:,delete,:,:,1/15/2020,52,史忠植,高,高级,人,人工智,能,能,ILOG SOLVER,Constraints,CtTell,(,(x,=,=,(,(y,+,+ z,),);,Basicconstraints:,=,=, , +, -, *, /, subset,superset, union,intersection, member,booleanor,booleanand, booleannot,boolean xor,CtTell,(,(x,=,=0,),) |,|,| (y=0),;,;,CtIfThen,(,(x,chooseValue,(,();,CtOr(Constraint,(,(x,=,=a),CtAnd(Constraint(x,!,!=a),CtInstantiate(x,),),;,;,1/15/2020,54,史忠植,高,高级,人,人工智,能,能,ILOG Schedule 1,.,.0,Schedule,CtSchedule class,Globalobject:time original -,-,-tineMin,time horizon,-,-,-,-timeMax,1/15/2020,55,史忠植,高,高级,人,人工智,能,能,ILOG Schedule 1,.,.0,Resources,CtResource,CtDiscreteResource,CtUnaryResource,CtDiscreteEnergy,CtStateResource,1/15/2020,56,史忠植,高,高级,人,人工智,能,能,ILOG Schedule 1,.,.0,Activities,CtActivityclass,CtIntervalActivity,Anactivityisdefined by itsstarttime,endtimeandduration,Activities require, provide, consumeand produceresources,1/15/2020,57,史忠植,高,高级,人,人工智,能,能,Scheduling Problem,Pricespaidastasksbegin,$,$1000perday,Availability,:,: Day0:$20000,Day 15:,+,+$9000,1/15/2020,58,史忠植,高,高级,人,人工智,能,能,Constraints,/Tocreateaschedulewith origin0 andgivenhorizon.,CtSchedule* schedule =,newCtSchedule(0,horizon),;,;,/Tocreateanactivitywiththegivenduration,.,.,CtIntervalActivity* act,=,=,newCtIntervalActivity(schedule, duration);,/To postaprecedence constraintbetweenact1 andact2.,act2-startsAfterEnd(act1,0);,1/15/2020,59,史忠植,高,高级,人,人工智,能,能,Constraints,/Tocreateatotalbudgetoflimitedcapacity,(,(here29000),.,.,CtDiscreteResource*res=,newCtDiscreteResource(schedule,CtRequiredResource,capacity),;,;,/Tostatethat onlycap (here 20000)isavailablepriortoa,/givendate (here 15).,res-setCapacityMax(0,date,cap),;,;,/Tostatethat an activity actconsumesc units of res.,act,-,-consumes(res, c,),);,1/15/2020,60,史忠植,高,高级,人,人工智,能,能,AlgorithmProgram,CtBooleanIsUnScheduled,(,(CtActivity*act),/Returntrueifactdoesnothavea fixed start time,.,.,if,(,(act-getStartVariable(),-,-isBound,(,(),returnCtFalse;,else,returnCtTrue;,1/15/2020,61,史忠植,高,高级,人,人工智,能,能,AlgorithmProgram,CtBooleanIsMoreUrgent(CtActivity,*,* act1,CtActivity*act2),/Returns trueifact1ismore urgentthan act2,.,.,/Returns trueifact2isunbound (,=,=0,),),if,(,(act2,=,=0),returnCtTrue;,else if (act1-getStartMax(,),) ,getStartMax,(,(),returnCtTrue;,else,returnCtFalse;,1/15/2020,62,史忠植,高,高级,人,人工智,能,能,AlgorithmProgram,CtActivity*SelectActivity(CtSchedule*schedule),/Returns theunscheduledactivitywith thesmallestlatest,/statrttime.Returns0 if allactivities arescheduled,.,.,CtActivity*bestActivity,=,=0;,/Createsaniteratortoiterateonallactivities.,CtActivityIterator,*,* iterator(schedule);,CtActivity*newActivity;,while(iterator.next(newactivity),if(,(,(IsUnScheduled(newActivity),),),&,(,(IsMoreUgent(newActivity,bestActivity,),),bestactivity,=,=newActivity;,returnbestActivity;,1/15/2020,63,史忠植,高,高级,人,人工智,能,能,AlgorithmProgram,void SolveProblem(CtSchedule*schedule),/Solvetheproblemassumingconstraintshave beenposted.,CtActivity*act,=,=SelectActivity(schedule),;,;,while,(,(act !,=,=0),act,-,-setStartTime(act,-,-getStartMin(),),);,act,=,=SelectActivity(schedule),;,;,1/15/2020,64,史忠植,高,高级,人,人工智,能,能,Optimal Solution to theScheduling Problem,1/15/2020,65,史忠植,高,高级,人,人工智,能,能,