第三章约束推理()PPT课件

-,1,约束推理,史忠植中国科学院计算技术研究所,高级人工智能第三章,2020/5/15,-,2,第三章约束推理,3.1概述3.2回溯法3.3约束传播3.4回跳法3.5约束推理系统COPS3.6ILOGSOLVER3.7约束逻辑程序设计,-,3,在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合法布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树。,八皇后问题,-,4,采用DFS/BFS搜索策略,TheDFS/BFStreewillenumerateupto648combinations(assumelimitdepthto8).648=248=2.8x1014Noteredundancy:Q1in(1,3),Q2in(2,7)vs.Q1in(2,7),Q2in(1,3),2020/5/15,-,5,概述,一个约束满足问题(ConstraintSatisfactionProblem,简称CSP)包含一组变量与一组变量间的约束。变量表示领域参数，每个变量都有一个固定的值域。一个变量的值域可能是有限的，例如一个布尔变量的值域包含两个值；也可能是离散无限的，如整数域；也可能是连续的，如实数域。x1,x2,xn,D1,D2,Dn,.4,5,6,7red,green,blue,2020/5/15,-,6,约束满足问题CSP,Given:(1)setofvariables,(2)domainsofthevariables(3)constraintsthatthevariableshavetosatisfyFind:Anassignmentofvaluestothevariables,sothatthesevaluessatisfyallthegivenconstraints.Inoptimisationproblems,alsospecifyoptimisationcriterion,2020/5/15,-,7,概述,约束可用于描述领域对象的性质、相互关系、任务要求、目标等。约束满足问题的目标就是找到所有变量的一个（或多个）赋值，使所有约束都得到满足。一元谓词。序关系语言，只包含偏序关系或实变量上的大小关系。形如“x-yc”的方程。单位系数的线性方程与不等式，即所有的系数为-1,0,1。任意系数的线性方程与不等式。约束的布尔组合。代数与三角方程。,2020/5/15,-,8,概述,约束表示易于理解、编码及有效实现，它具有以下优点:约束表示允许以说明性的方式来表达领域知识，表达能力较强，应用程序只需指定问题的目标条件及数据间的相互关系。因而具有逻辑表示的类似性质。约束表示允许变量的域包含任意多个值，而不像命题只取真假二值。所以它保存了问题的一些结构信息，如变量域的大小、变量间的相关性等，从而为问题求解提供启发式信息。易于并行实现。因为约束网络上的信息传播可以认为是同时的。适合于递增型系统。约束可以递增式地加入到约束网络。易于与领域相关的问题求解模型相衔接。各种数学规划技术，方程求解技术等,都可以自然地嵌入约束系统。,2020/5/15,-,9,约束推理,约束搜索约束搜索主要研究有限域上的约束满足。对有限域而言，约束满足问题一般情况下是一个NP问题。约束语言,2020/5/15,-,10,约束搜索,回溯法。约束传播。智能回溯与真值维护。可变次序例示。局部修正法。,2020/5/15,-,11,约束语言,CONSTRAINTSCHIPCOPSILOG,2020/5/15,-,12,CONSTRAINTS约束语言,CONSTRAINTS是一个面向电路描述的约束表示语言。作为一个约束表示语言，它使用了符号处理技术来求解数学方程。在CONSTRAITS中，物理部件的功能及器件的结构都用约束表示。这些约束一般是线性方程与不等式,也包括条件表达式。约束变量一般是表示物理量的实变量。也有一些取离散值的变量。如开关的状态、三极管的工作状态等。系统采用表达式推理与值推理。并实现相关制导的回溯。,2020/5/15,-,13,CONSTRAINTS约束语言,CONSTRAINTS的一个优点是在类型层次中表示约束，用约束来表示物理对象的功能与结构。其缺点是该语言缺乏类似于面向对象语言中的方法那样的成分，不能定义特定于某个类的概念。同时，约束传播方法比较单一，既缺乏实域上的区间传播机制，也缺乏有限域上的域传播机制。,2020/5/15,-,14,约束逻辑程序设计语言CHIP,CHIP(ConstrainthandlinginProlog)就是这样较有影响一个约束逻辑程序设计语言，其目的是简便、灵活而有效地解决一大类组合问题。它通过提供几种新的计算域而增强逻辑程序设计的能力；有限域、布尔项及有理项，对于每个计算域，都提供有效的约束求解技术，即有限域上的一致性技术，布尔域的布尔合一技术及有理数域上的单纯型法。除此以外，CHIP还包含一个一般的延迟计算机制。CHIP主要应用于两个领域:运筹学与硬件设计。CHIP缺乏类型机制，而这种机制对于表达领域概念是极其重要的。,2020/5/15,-,15,面向对象约束语言COPS,COPS系统利用面向对象技术，将说明性约束表达与类型层次结合起来。在形式上吸收了常规语言，主要是面向对象的程序设计语言的基本形式。内部求解时采用约束推理机制，使说明性约束表达式与类型层次相结合，实现知识的结构化封装，充分发挥两者的优点，力图实现一个具有较强表达能力和较高求解效率的约束满足系统。,2020/5/15,-,16,面向对象约束语言COPS,COPS的设计考虑了软件工程的应用要求，尽量将一个不确定问题确定化：它允许条件语句与循环语句，而不是单纯以递归的形式来实现迭代计算；通过类方法的重栽实现同一约束的不同实现，提高了程序的执行效率。COPS系统同时是一个渐增式的开放系统，用户能通过类型层次定义，实现新的数据类型和新的约束关系。约束语言COPS具有许多人工智能程序设计语言的特点，如约束传播、面向目标和数据驱动的问题求解、有限步的回溯、对象分层中的继承等。,2020/5/15,-,17,在实际应用中，算法的表现形式千变万化，但是算法的情况也和数据结构类似，许多算法的设计思想具有相似之处，我们可以对它们分类进行学习和研究。常用的算法大致有如下一些：贪心法分治法：如二分法检索回溯法动态规划法局部搜索法分支限界法,常用的算法,2020/5/15,-,18,评价一个程序优劣的重要依据是看这个程序的执行需要占用多少机器资源。人们最关心的就是程序所用算法运行时所要花费的时间代价和程序中使用的数据结构占有的空间代价。算法的空间代价(或称空间复杂性)：当被解决问题的规模(以某种单位计算)由1增至n时，解该问题的算法所需占用的空间也以某种单位由f(1)增至f(n)，这时我们称该算法的空间代价是f(n)。算法的时间代价(或称时间复杂性)：当问题规模以某种单位由1增至n时，对应算法所耗费的时间也以某种单位由g(1)增至g(n)，这时我们称算法的时间代价是g(n)。,算法分析,2020/5/15,-,19,穷尽搜索方法,穷尽搜索方法即产生所有可能的树，然后根据评价标准选择一棵最优的树。Exhaustive-Search-Top(P)wherePisaCSPoftheform(V,D,C)1.f:=thenullassignment2.returnExhaustive-Search(f,P),2020/5/15,-,20,穷尽搜索方法,Exhaustive-Search(f,P)1.iffisatotalassignmentofthevariablesinP2.iffsatisfiestheconstraintsinP3.answer:=f4.else5.answer:=Unsat6.else7.v:=somevariableinPthatisnotyetassignedavaluebyf8.answer:=Unsat9.foreachvaluewhileanswer=Unsat10.f(v):=11.answer:=Exhaustive-Search(f,P)12.returnanswer,2020/5/15,-,21,贪心法,贪心法把构造可行解的工作分阶段来完成。在各个阶段，选择那些在某些意义下是局部最优的方案，期望各阶段的局部最优的选择带来整体最优。例：Dijkstra的最短路径算法、Kruskal的求最小生成树算法、信号灯问题,2020/5/15,-,22,回溯算法,有些问题需要彻底的搜索才能解决问题，然而，彻底的搜索要以大量的运算时间为代价，对于这种情况可以通过回溯法来去掉一些分支，从而大大减少搜索的次数。八皇后问题迷宫问题深度优先周游树或图,约束推理ppt,-,23,四皇后问题中隐含的状态树,四皇后问题,2020/5/15,-,24,4-QueensPuzzle,2020/5/15,-,25,4-QueensTree,-,26,回溯算法BacktrackSearch,-,27,回溯算法BacktrackSearch,Assignment=(var1=v11),-,28,回溯算法BacktrackSearch,Assignment=(var1=v11),(var2=v21),-,29,回溯算法BacktrackSearch,Assignment=(var1=v11),(var2=v21),(var3=v31),-,30,回溯算法BacktrackSearch,Assignment=(var1=v11),(var2=v21),(var3=v32),-,31,回溯算法BacktrackSearch,Assignment=(var1=v11),(var2=v22),-,32,回溯算法BacktrackSearch,Assignment=(var1=v11),(var2=v22),(var3=v31),2020/5/15,-,33,回溯算法,Backtracking-Top(P)1f:=thenullassignment2returnBacktracking(f,P),2020/5/15,-,34,回溯算法,Backtracking(f,P)1iffisatotalassignmentofthevariablesinP2answer:=f3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6foreachvaluewhileanswer=Umsat7f(v):=x8iffsatisfiestheconstraintsinP9answer:=Backtracking(f,P)10returnanswer,2020/5/15,-,35,BacktrackingAlgorithm,Basedondepth-firstrecursivesearchApproachTestswhethersolutionhasbeenfoundIffoundsolution,returnitElseforeachchoicethatcanbemadeMakethatchoiceRecurIfrecursionreturnsasolution,returnitIfnochoicesremain,returnfailureSometimescalled“searchtree”,2020/5/15,-,36,回溯算法,尽管回溯法好于生成测试法，但对于非平凡问题仍然是低效的。其原因在于搜索空间中不同路径的搜索重复相同的失败子路径。一些研究者认为，造成这种反复的原因是所谓的局部不一致性。最简单的情形是所谓的结点不一致性。对一个变量vi的一个一元约束。存在域中一个值vi不满足该约束。这样，每当vi取到a时就会出现不一致性。另一种重复的情形是所谓的弧不一致性。,2020/5/15,-,37,约束传播CONSTRAINTPROPAGATION,弧一致性Arcconsistency,2020/5/15,-,38,弧一致性,Arcconsistency如果对vi的当前域中的所有值x，存在vj的当前域中的某值y使得vi=x和vj=y是vi与vj之间的约束所允许的，则弧(vi,vj)是弧一致的。弧一致性的概念是有向的。即(vi,vj)是弧一致的并不自动地意味着(vj,vi)是一致的。,2020/5/15,-,39,CONSTRAINTPROPAGATION,AlloftheMackworthalgorithmsmakeuseofaReviseprocedure.LetDvbethecurrentdomainofv,LetDwbethecurrentdomainofw,LetPbetheconstraintpredicatethatholdsbetweenvandw,thenReviseupdatesDvasfollows:,2020/5/15,-,40,CONSTRAINTPROPAGATION,Mackworth1977AC-1AC-2AC-3,2020/5/15,-,41,约束传播修改算法,REVISE(Vi,Vj)1DELETEfalse;2foreachxDido3ifthereisnosuchyjDj4suchthat(x,yj)isconsistent,5then6deletexfromDi;7DELETEtrue;8endif9endfor10returnDELETE;11endREVISE,2020/5/15,-,42,弧一致性算法AC-1,1Q;2repeat3CHANGEfalse;4foreach(Vi,Vj)Qdo5CHANGEREVISE(Vi,Vj)CHANGE;6endfor;7untilnot(CHANGE);8endAC-1,2020/5/15,-,43,弧一致性算法AC-3,1Q;2WhileQnotempty3Selectanddeleteanyarc(Vk,Vm)fromQ;4If(REVISE(Vk,Vm)ThenQ(Vi,Vk)suchthat(Vi,Vk)arcs(G),ik,im;6endfor;7endwhile;8endAC-3,-,44,弧一致性算法AC-3,-,45,弧一致性算法AC-3,时间复杂性:,n2=numberofconstraints(edges;nisthe#ofvariables)d=numberofvaluespervariable,REMOVE-ARC-INCONSISTENCYtakesO(d2)timeEachvariableisinsertedinQueueuptodtimes,sinceatmostdvaluescanbedeleted,AC3takesO(n2d3)timetorun,2020/5/15,-,46,Backjumping,Backjumping-Top(P)1f:=thenullassignment2:=Backjumping(f,P)3returnanswer,2020/5/15,-,47,Backjumping,Backjumping(f,P)1iffisatotalassignmentofthevariablesinP2answer:=3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6conflict-set:=7foreachvalue8f(v):=x9iffsatisfiestheconstraintsinP10:=Backjumping(f,P),2020/5/15,-,48,Backjumping,11else12new-conflicts:=thesetofvariablesinaviolatedconstraint13ifanswerUnsat14return15elseifvnew-conflicts16return17else18conflict-set:=conflict-set(new-conflictsv)19return,2020/5/15,-,49,COPS,Constraint:predicateexpressionP(t1,.,tn)wherePisbuiltinfunction,suchassumtimeseq(equal)neq(notequal)ge(greatthanorequalto)gt(greatthan)alsocanbedefinedbyusers,2020/5/15,-,50,COPS,Conditionalconstraintcondition1:constraint1;.conditionn:constraintnwherecondition1,.,conditionnarebooleanexpressions.constraint1,.constraintnareconstraintsorcontraintstable.,2020/5/15,-,51,COPS,RULERuleisusedtodefinenewfunction,method,predicate,oraddnewconstraintintoobject.RULEclass:predicate(varibles)(booleanexpression)constraint_1;constraint_n;CASEbooleanexpression_1:constraint_1;booleanexpression_m:constraint_m;,2020/5/15,-,52,COPS,Forexample:RULEmultiple(INTEGER:*x,INTEGER:y,INTEGER:z)(neq(y,0)equal(x,divide(z,y);z=x*y,2020/5/15,-,53,COPS,CLASSclass_name:superclass_name/attributesdefinitiondatetype:attribute_name;./ruledefinitionrule_name;./functiondefinitionfunction_name;./methoddefinitionmethod_name;.,2020/5/15,-,54,COPS,ImplementationProgramwrittenbyCOPSconsistsofclassesandrules.COPSconstraintprogramminglanguageisadeclarativelanguage,providingclasses,methodswhichareexistinobjectorientedlanguage.ItissimilarwithC+.COPShasthefeatures:constraintobjectorientedlogicprogrammingproductionsystem,2020/5/15,-,55,COPS,COPS_Compiler12Callyacctoparsetheprogramand3togenerateinternalstructures.4Initializatiion5CreateCopsConstanttrueNode;6Allocatememoriesforglobalvariables.,2020/5/15,-,56,COPS,7Interprtetheprogramwiththeinternalstructures.8ConstraintnetworksarebuiltupforUnsolved9constraintsandvariables.10whilesomeconstraintsintheconstraintnetworksaretriggered,11intepretethetriggeredconstraints.12,2020/5/15,-,57,COPS,Interpreter:12switch(constrainttype)3caseConstant:4returnConstant:5caseglobalvariable:6interpreteglobalvariable:7caselocalvariableorargument:8interpretelocalvariableorargument:9caseobject-attributepair;10interpreteobject-attributepair:11casefunctioncall:,2020/5/15,-,58,COPS,12interpretefunctioncall:13casemethodcall:14interpretemethodcall:15caseCASEexpression:16interpreteCASEexpression:17.18default:20reporterror21,2020/5/15,-,59,ILOGSOLVER,Combinesobjectorientedprogrammingwithconstraintlogicprogramming,containinglogicvariables,incrementalconstraintsatisfactionandbacktracking.variables:C+objectintegervariableCtIntVarfloatingvariableCtFloatVarbooleanvariableCtBoolVarMemoryManagementnew:delete:,2020/5/15,-,60,ILOGSOLVER,ConstraintsCtTell(x=(y+z);Basicconstraints:=,+,-,*,/,subset,superset,union,intersection,member,booleanor,booleanand,booleannot,booleanxor,CtTell(x=0)|(y=0);CtIfThen(xchooseValue();CtOr(Constraint(x=a),CtAnd(Constraint(x!=a),CtInstantiate(x);,2020/5/15,-,62,ILOGSchedule1.0,ScheduleCtScheduleclassGlobalobject:timeoriginal-tineMintimehorizon-timeMax,2020/5/15,-,63,ILOGSchedule1.0,ResourcesCtResourceCtDiscreteResourceCtUnaryResourceCtDiscreteEnergyCtStateResource,2020/5/15,-,64,ILOGSchedule1.0,ActivitiesCtActivityclassCtIntervalActivityAnactivityisdefinedbyitsstarttime,endtimeanddurationActivitiesrequire,provide,consumeandproduceresources,2020/5/15,-,65,SchedulingProblem,Pricespaidastasksbegin$1000perdayAvailability:Day0:$20000,Day15:+$9000,2020/5/15,-,66,Constraints,/Tocreateaschedulewithorigin0andgivenhorizon.CtSchedule*schedule=newCtSchedule(0,horizon);/Tocreateanactivitywiththegivenduration.CtIntervalActivity*act=newCtIntervalActivity(schedule,duration);/Topostaprecedenceconstraintbetweenact1andact2.act2-startsAfterEnd(act1,0);,2020/5/15,-,67,Constraints,/Tocreateatotalbudgetoflimitedcapacity(here29000).CtDiscreteResource*res=newCtDiscreteResource(schedule,CtRequiredResource,capacity);/Tostatethatonlycap(here20000)isavailablepriortoa/givendate(here15).res-setCapacityMax(0,date,cap);/Tostatethatanactivityactconsumescunitsofres.act-consumes(res,c);,2020/5/15,-,68,AlgorithmProgram,CtBooleanIsUnScheduled(CtActivity*act)/Returntrueifactdoesnothaveafixedstarttime.if(act-getStartVariable()-isBound()returnCtFalse;elsereturnCtTrue;,2020/5/15,-,69,AlgorithmProgram,CtBooleanIsMoreUrgent(CtActivity*act1,CtActivity*act2)/Returnstrueifact1ismoreurgentthanact2./Returnstrueifact2isunbound(=0)if(act2=0)returnCtTrue;elseif(act1-getStartMax()getStartMax()returnCtTrue;elsereturnCtFalse;,2020/5/15,-,70,AlgorithmProgram,CtActivity*SelectActivity(CtSchedule*schedule)/Returnstheunscheduledactivitywiththesmallestlatest/statrttime.Returns0ifallactivitiesarescheduled.CtActivity*bestActivity=0;/Createsaniteratortoiterateonallactivities.CtActivityIterator*iterator(schedule);CtActivity*newActivity;while(iterator.next(newactivity)if(IsUnScheduled(newActivity),2020/5/15,-,71,AlgorithmProgram,voidSolveProblem(CtSchedule*schedule)/Solvetheproblemassumingconstraintshavebeenposted.CtActivity*act=SelectActivity(schedule);while(act!=0)act-setStartTime(act-getStartMin();act=SelectActivity(schedule);,2020/5/15,-,72,OptimalSolutiontotheSchedulingProblem,2020/5/15