约束传播-智能科学与人工智能.ppt

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