高级人工智能第三章约束推理

高级人工智能第三章约束推理史忠植

中国科学院计算技术所1/17/20231第三章约束推理3.1概述3.2回溯法3.3约束传播3.4回跳法3.5约束推理系统COPS3.6ILOGSOLVER1/17/202323.1概述最优化问题经济学所推崇的帕累托最优:几个人拎着水桶在一个水龙头前面排队打水，水桶有大有小。他们怎样排队，才能使得总的排队时间最短。这是一个寻求“最优化”的题目，目标是节省总的排队时间，达到最优。1/17/202333.1概述

优化问题

运筹学

遗传算法

神经网络

约束推理1/17/20234运筹学的工作步骤1）提出和形成问题，2）建立模型，3）求解，4）解的检验，5）解的控制，6）解的实施。1/17/20235线性规划问题例1(广告方式的选择)中华家电公司推销一种新型洗衣机,有关数据见下表.销售部第一月的广告预算为20000元,要求至少有8电视商业节目,15家报纸广告/电视广告费不得超过12000元,电台广播至少隔日有一次.现问该公司销售部应当采用怎样的广告宣传计划,才能取得最好的效果?1/17/20236表1广告方式广告费用(元/次)可用最高次数/月期望的宣传效果/单位电视台a(白天,1分钟)5001650电视台b(晚上,30钞)10001080每日晨报/(半版)1002430星期日报/(半版)300440广播电台/(1分钟)8025151/17/202371/17/20238

1/17/20239

1/17/202310求解解--单单纯纯形形法法将所所给给问问题题化化为为标标准准形形找出出一一个个初初始始可可行行基基,建建立立初初始始单单纯纯形形表表检查查所所有有检检验验数数(若若全全为为非非负负,则则已已得得到到最最优优解解,计计算算停停止止.否否则则继继续续下下一一步步)考察察是是否否无无解解(若若是是,计计算算停停止止,否否则则继继续续下下一一步步)确定定入入基基变变量量,出出基基变变量量对初初始始单单纯纯形形表表进进行行单单纯纯形形变变换换12/31/2022113.1概述一个约束满足足问题(ConstraintSatisfactionProblem,简称CSP)包含一组组变量与一组组变量间的约约束。▪变量表示领领域参数，每每个变量都有有一个固定的的值域。一个变量的值值域可能是有有限的，例如如一个布尔变变量的值域包含两个值值；也可能是是离散无限的的，如整数域域；也可能是连续的，，如实数域。。{x1,x2,…xn},{D1,D2,…Dn},.{4,5,6,7}red,green,blue}12/31/2022123.1概述▪约束可用用于描述领领域对象的的性质、相相互关系、、任务要求、目标标等。约束束满足问问题的目目标就是找找到所有变量的一个个（或多个个）赋值，，使所有约约束都得到到满足。一元谓词。。序关系语言言，只包含含偏序关系系或实变量量上的大小小关系。形如“x-y>c””的方程程。单位系数的的线性方程程与不等式式，即所有有的系数为为-1,0,1。任意系数的的线性方程程与不等式式。约束的布尔尔组合。代数与三角角方程。12/31/2022133.1概述约束表示易易于理解、、编码及有有效实现，，它具有以以下优点:约束表示允允许以说明明性的方式式来表达领领域知识，，表达能力较强，，应用程序序只需指定定问题的目目标条件及及数据间的相互关系系。因而具具有逻辑表表示的类似似性质。约束表示允允许变量的的域包含任任意多个值值，而不像像命题只取真假二二值。所以以它保存了了问题的一一些结构信信息，如变量域的大大小、变量量间的相关关性等，从从而为问题题求解提供供启发式信息息。易于并行实实现。因为为约束网络络上的信息息传播可以以认为是同时的。适合于递增增型系统。。约束可以以递增式地地加入到约约束网络。。易于与领域域相关的问问题求解模模型相衔接接。各种数数学规划技技术，方程求求解技术等等,都可可以自然地地嵌入约束束系统。12/31/2022143.1约束推理约束搜索约束搜索主主要研究有有限域上的的约束满足足。对有限限域而言，，约束满足问问题一般情情况下是一个NP问问题。约束语言12/31/2022153.1约束搜索索回溯法。。约束传播播。智能回溯溯与真值值维护。。可变次序序例示。。局部修正正法。12/31/202216约束语言言CONSTRAINTSCHIPCOPSILOG12/31/202217CONSTRAINTS约束束语言CONSTRAINTS是一一个面向向电路描描述的约约束表示示语言。。作为一个个约束表表示语言言，它它使用了了符号处处理技术术来求解解数学方方程。在CONSTRAITS中，，物理部部件的功功能及器器件的结结构都用用约束表表示。这些约束一般般是线性方程程与不等式,也包括条条件表达式。。约束变量一般是是表示示物理理量的的实变变量。。也有有一些些取离离散值值的变变量。。如开开关的的状态、三三极管管的工工作状状态等等。系系统采采用表表达式式推理理与值值推理理。并并实现现相关制制导的的回溯溯。12/31/202218CONSTRAINTS约约束束语语言言CONSTRAINTS的的一一个个优优点点是是在在类类型型层层次次中中表表示示约约束束，，用用约约束束来表表示示物物理理对对象象的的功功能能与与结结构构。。其其缺缺点点是是该该语语言言缺缺乏乏类类似似于于面面向向对象象语语言言中中的的方方法法那那样样的的成成分分，，不不同时，约束传播方法比较单一，既缺乏实域上的区间传播机制，也缺乏有限域上的域传播机制。

12/31/202219约束束逻逻辑辑程程序序设设计计语语言言CHIPCHIP(ConstrainthandlinginPr一个约束逻辑程序设计语言，其目的是简便、灵活而有效地解决一大类组合问题。它通过提供几种新的计算域而增强逻辑程序设计的能力；有限域、布尔项及有理项，对于每个计算域，都提供有效的约束求解技术，即有限域上的一致性技术，布尔域的布尔合一技术及有理数域上的单纯型法。除此以外，CHIP还包含一个一般的延迟计算机制。CHIP主要应用于两个领域:运筹学与硬件设计。CHIP缺乏类型机制，而这种机制对于表达领域概念是极其重要的。12/31/202220面向向对对象象约约束束语语言言COPSCOPS系系统统利利用用面面向向对对象象技技术术，，将将说说明明性性约约束束表表达达与与类类型型层层次次结合起起来。。在形形式上上吸收收了常常规语语言，，主要要是面面向对对象的的程序序设计语言言的基基本形形式。。内部部求解解时采采用约约束推推理机机制，，使说说明性性约束表达达式与与类型型层次次相结结合，，实现现知识识的结结构化化封装装，充充分发发挥两者的的优点点，力力图实实现一一个具具有较较强表表达能能力和和较高高求解解效率率的约束满满足系系统。。12/31/202221面向对象象约束语语言COPSCOPS的设计计考虑了了软件工工程的应应用要求求，尽量量将一个个不确定定问题确定化化：它允允许条件件语句与与循环语语句，而而不是单单纯以递归归的形式式来实现现迭代计计算；通通过类类方法的的重栽实实现同一一约束的不不同实现现，提高高了程序序的执行行效率。。COPS系统统同时是是一个渐增式的的开放系系统，用用户能通通过类型型层次定定义，实实现新的的数据类类型和新的的约束关关系。约约束语言言COPS具有有许多人人工智能能程序设设计语言的特点点，如约约束传播播、面向向目标和和数据驱驱动的问问题求解解、有限限步的回溯溯、对象象分层中中的继承承等。12/31/202222在实际应应用中，，算法的的表现形形式千变变万化，，但是算算法的情情况也和和数据结结构类似似，许多多算法的的设计思思想具有有相似之之处，我我们可以以对它们们分类进进行学习习和研究究。常用的算算法大致致有如下下一些：：贪心法分治法：：如二分分法检索索回溯法动态规划划法局部搜索索法分支限界界法12/31/202223算法分析析评价一个个程序优优劣的重重要依据据是看这这个程序序的执行行需要占占用多少少机器资资源。人人们最关关心的就就是程序序所用算算法运行行时所要要花费的的时间代价价和程序中中使用的的数据结结构占有有的空间代价价。算法的空空间代价价(或称空间复杂杂性)：当被被解决问问题的规规模(以以某种单单位计算算)由1增至n时，解该该问题的的算法所所需占用用的空间间也以某某种单位位由f(1)增增至f(n)，这时时我们称称该算法法的空间间代价是是f(n)。算法的时时间代价价(或称时间复杂杂性)：当问问题规模模以某种种单位由由1增至至n时，对应应算法所所耗费的的时间也也以某种种单位由由g(1)增增至g(n)，这时时我们称称算法的的时间代代价是g(n)。12/31/202224穷尽搜索方法法穷尽搜索方法法即产生所有可可能的树，然然后根据评价价标准选择一一棵最优的树树。Exhaustive-Search-Top(P){wherePisaCSPoftheform(V,D,C)}1.f:=thenullassignment2.returnExhaustive-Search(f,P)12/31/202225穷尽搜索方法法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.returnanswer12/31/202226贪心法贪心法把构造造可行解的工工作分阶段来来完成。在各各个阶段，选选择那些在某某些意义下是是局部最优的的方案，期望望各阶段的局局部最优的选选择带来整体体最优。例：Dijkstra的最短短路径算法、、Kruskal的求最最小生成树算算法、信号灯灯问题12/31/202227回溯算法有些问题需需要彻底的的搜索才能能解决问题题，然而，，彻底的搜搜索要以大大量的运算算时间为代代价，对于于这种情况况可以通过过回溯法来来去掉一些些分支，从从而大大减减少搜索的的次数。八皇后问题题迷宫问题深度优先周周游树或图图12/31/202228回溯算法Backtracking-Top(P)1f:=thenullassignment2returnBacktracking(f,P)12/31/202229回溯算法法Backtracking(f,P)1iffisatotalassignmentofthevariablesinP2answer:=f3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6foreachvaluewhileanswer=Umsat7f(v):=x8iffsatisfiestheconstraintsinP9answer:=Backtracking(f,P)10returnanswer12/31/202230回溯算算法尽管回回溯法法好于于生成成测试试法，，但对对于非非平凡凡问题题仍然然是低低效的的。其其原因因在于于搜索索空间间中不不同路路径的的搜索索重复复相同同的失失败子子路径径。一一些研研究者者认为为，造造成这这种反反复的的原因因是所所谓的的局部部不一一致性性。最最简单单的情情形是是所谓谓的结结点不不一致致性。。对一一个变变量vi的的一个个一元元约束束。存存在域域中一一个值值vi不满满足该该约束束。这这样，，每当当vi取到到a时时就会会出现现不一致致性。。另一种种重复复的情情形是是所所谓的的弧不不一致致性。。12/31/2022313.3约约束束传播播CONSTRAINTPROPAGATION弧一致致性Arcconsistency12/31/202232弧一致致性Arcconsistency如果对对vi的的当前前域中中的所所有值值x，，存在在vj的当当前域域中的的某值值y使使得vi=x和vj=y是是vi与vj之之间的的约束束所允允许的的，则则弧(vi,vj)是是弧一一致的的。弧一致性的的概念是有有向的。即即(vi,vj)是弧一致的的并不自动动地意味着着(vj,vi)是一致的的。12/31/2022333.3CONSTRAINTPROPAGATIONAlloftheMackworthalgorithmsmakeuseofaReviseprocedure.LetDvbethecurrentdomainofv,LetDwbethecurrentdomainofw,LetPbetheconstraintpredicatethatholdsbetweenvandw,thenReviseupdatesDvasfollows:12/31/202234CONSTRAINTPROPAGATIONMackworth1977AC-1AC-2AC-312/31/202235约束传播播修改算算法REVISE(Vi,Vj)1DELETEfalse;2foreachxDido3ifthereisnosuchyjDj4 suchthat(x,yj)isconsistent,5then6deletexfromDi;7DELETEtrue;8endif9endfor10returnDELETE;11endREVISE12/31/202236AC-11Q;2repeat3CHANGEfalse;4foreach(Vi,Vj)Qdo5CHANGEREVISE(Vi,Vj)CHANGE;6endfor;7untilnot(CHANGE);8endAC-112/31/202237AC-31Q;2WhileQnotempty3Selectanddeleteanyarc(Vk,Vm)fromQ;4If(REVISE(Vk,Vm))ThenQ{(Vi,Vk)suchthat(Vi,Vk)arcs(G),ik,im};6endfor;7endwhile;8endAC-312/31/202238BackjumpingBackjumping-Top(P)1f:=thenullassignment2<answer,conflict-set>:=Backjumping(f,P)3returnanswer12/31/202239BackjumpingBackjumping(f,P)1iffisatotalassignmentofthevariablesinP2answer:=<f,>3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6conflict-set:=7foreachvalue8f(v):=x9iffsatisfiestheconstraintsinP10<answer,new-conflicts>:=Backjumping(f,P)12/31/202240Backjumping11else12new-conflicts:=thesetofvariablesinaviolatedconstraint13ifanswerUnsat14return<answer,>15elseifvnew-conflicts16return<Unsat,new-conflicts>17else18conflict-set:=conflict-set(new-conflicts{v})19return<Unsat,conflict-set>12/31/202241COPS

P(t1,...,tn)wherePisbuiltinfunction,suchas

sumtimeseq(equal)neq(notequal)ge(greatthanorequalto)gt(greatthan)alsocanbedefinedbyusers12/31/202242COPSConditionalconstraintcondition1:constraint1;..conditionn:constraintnwherecondition1,...,conditionnarebooleanexpressions.constraint1,...constraintnareconstraintsorcontraintstable.12/31/202243COPSRULERuleisusedtodefinenewfunction,method,predicate,oraddnewconstraintintoobject.RULE[class::]predicate(varibles)(booleanexpression){constraint_1;­constraint_n;CASEbooleanexpression_1:constraint_1;­booleanexpression_m:constraint_m;}12/31/202244COPSForexample:RULEmultiple(INTEGER:*x,INTEGER:y,INTEGER:z)(neq(y,0)){equal(x,divide(z,y));}z=x*y12/31/202245COPSCLASS[class_name][:superclass_name]{//attributesdefinitiondatetype:attribute_name;...//ruledefinitionrule_name;...//functiondefinitionfunction_name;...//methoddefinitionmethod_name;...}12/31/202246COPSImplementationProgramwrittenbyCOPSconsistsofclassesandrules.COPSconstraintprogramminglanguageisadeclarativelanguage,providingclasses,methodswhichareexistinobjectorientedlanguage.ItissimilarwithC++.COPShasthefeatures:constraintobjectorientedlogicprogrammingproductionsystem12/31/202247COPSCOPS_Compiler1{2Callyacctoparsetheprogramand3togenerateinternalstructures.4Initializatiion5CreateCopsConstanttrueNode;6Allocatememoriesforglobalvariables.12/31/202248COPS7Interprtetheprogramwiththeinternalstructures.8ConstraintnetworksarebuiltupforUnsolved9constraintsandvariables.10whilesomeconstraintsintheconstraintnetworksaretriggered,11intepretethetriggeredconstraints.12}12/31/202249COPSInterpreter:1{2switch(constrainttype)3caseConstant:4returnConstant:5caseglobalvariable:6interpreteglobalvariable:7caselocalvariableorargument:8interpretelocalvariableorargument:9caseobject-attributepair;10interpreteobject-attributepair:11casefunctioncall:12/31/202250COPS12interpretefunctioncall:13casemethodcall:14interpretemethodcall:15caseCASEexpression:16interpreteCASEexpression:17...18default:20reporterror21}12/31/202251ILOGSOLVERCombinesobjectorientedprogrammingwithconstraintlogicprogramming,containinglogicvariables,incrementalconstraintsatisfactionandbacktracking.variables:C++objectintegervariableCtIntVarfloatingvariableCtFloatVarbooleanvariableCtBoolVarMemoryManagementnew:delete:12/31/202252ILOGSOLVERConstraintsCtTell(x==(y+z));Basicconstraints:=,,,<,>,+,-,*,/,subset,superset,union,intersection,member,booleanor,booleanand,booleannot,booleanxor,CtTell((x==0)||(y==0));CtIfThen(x<100,x=x+1);Search12/31/202253ILOGSOLVERCTGOALn:howtoexecuteCTGOAL1(CtInstantiate,CtIntVar*x){CtInta=x->chooseValue();CtOr(Constraint(x==a),CtAnd(Constraint(x!=a),CtInstantiate(x)));}12/31/202254ILOGSchedule1.0ScheduleCtScheduleclassGlobalobject:timeoriginal---tineMintimehorizon---timeMax12/31/202255ILOGSchedule1.0ResourcesCtResourceCtDiscreteResourceCtUnaryResourceCtDiscreteEnergyCtStateResource12/31/202256ILOGSchedule1.0ActivitiesCtActivityclassCtIntervalActivityAnactivityisdefinedbyitsstarttime,endtimeanddurationActivitiesrequire,provide,consumeandproduceresources12/31/202257SchedulingProblemPricespaidastasksbegin$1000perdayAvailability:Day0:$20000,Day15:+$900012/31/202258Constraints//Tocreateaschedulewithorigin0andgivenhorizon.CtSchedule*schedule=newCtSchedule(0,horizon);//Tocreateanactivitywiththegivenduration.CtIntervalActivity*act=newCtIntervalActivity(schedule,duration);//Topostaprecedenceconstraintbetweenact1andact2.act2->startsAfterEnd(act1,0);12/31/202259Constraints//Tocreateatotalbudgetoflimitedcapacity(here29000).CtDiscreteResource*res=newCtDiscreteResource(schedule,CtRequiredResource,capacity);//Tostatethatonlycap(here20000)isavailablepri