第03章-约束推理优秀PPT.ppt

《第03章-约束推理优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第03章-约束推理优秀PPT.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 约束推理约束推理3.1 概述概述3.2 回溯法回溯法 3.3 约束传播约束传播 3.4 回跳法回跳法 3.5 约束推理系统约束推理系统COPS 3.6 ILOG SOLVER2022/11/51史忠植高级人工智能3.1 3.1 概概 述述最优化问题最优化问题 经济学所推崇的帕累托最优经济学所推崇的帕累托最优:几个人拎着水桶在一个水龙头前面几个人拎着水桶在一个水龙头前面排队打水，水桶有大有小。他们怎样排排队打水，水桶有大有小。他们怎样排队，才能使得总的排队时间最短。这是队，才能使得总的排队时间最短。这是一个寻求一个寻求“最优化最优化”的题目，目标是节的题目，目标是节约总的排队时间，

2、达到最优。约总的排队时间，达到最优。2022/11/52史忠植高级人工智能3.1 3.1 概概 述述 优化问题优化问题 运筹学 遗传算法 神经网络 约束推理2022/11/53史忠植高级人工智能运筹学的工作步骤运筹学的工作步骤v1）提出和形成问题，）提出和形成问题，v2）建立模型，）建立模型，v3）求解，）求解，v4）解的检验，）解的检验，v5）解的限制，）解的限制，v6）解的实施。）解的实施。2022/11/54史忠植高级人工智能线性规划问题线性规划问题l例例1(广告方式的选择广告方式的选择)中华家电公司推销中华家电公司推销一种新型洗衣机，有关数据见下表。销售一种新型洗衣机，有关数据见下表。

3、销售部第一月的广告预算为部第一月的广告预算为20000元，要求至少元，要求至少有有8个电视商业节目，个电视商业节目，15家报纸广告；电视家报纸广告；电视广告费不得超过广告费不得超过12000元，电台广播至少隔元，电台广播至少隔日有一次。现问该公司销售部应当接受怎日有一次。现问该公司销售部应当接受怎样的广告宣扬支配，才能取得最好的效果样的广告宣扬支配，才能取得最好的效果?2022/11/55史忠植高级人工智能线性规划问题线性规划问题广告方式广告方式广告费用广告费用(元元/次次)可用最高可用最高次数次数/月月期望的宣传期望的宣传效果效果/单位单位电视台电视台a(白天白天,1 分钟分钟)500165

4、0电视台电视台b(晚上晚上,30钞钞)10001080每日晨报每日晨报/(半版半版)1002430星期日报星期日报/(半版半版)300440广播电台广播电台/(1分钟分钟)802515表表1 中华家电公司推销新型洗衣机广告方式选择的数据表中华家电公司推销新型洗衣机广告方式选择的数据表2022/11/56史忠植高级人工智能线性规划问题线性规划问题解：设解：设x1,x2,x3,x4,x5分别是第一个月内电视台分别是第一个月内电视台a，电视台电视台b，每日晨报，星期日报，广播电台进行广告，每日晨报，星期日报，广播电台进行广告宣扬的次数，则其数学模型为宣扬的次数，则其数学模型为 max 50 x1+8

5、0 x2+30 x3+40 x4+15x5s.t.50 x1+80 x2+30 x3+40 x4+15x5 20000，x1+x28，x3+x4 15，500 x1+1000 x212000，x116,x210,x324,x44,15x525,x1,x2,x3,x4,x5 0。2022/11/57史忠植高级人工智能线性规划问题线性规划问题线性规划问题线性规划问题(LP)的一般形式为的一般形式为：min(max)z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn(,)b1 a21x1+a22x2+a2nxn(,)b2 am1x1+am2x2+amnxn(,)bmxj0,j

6、=1,2,n2022/11/58史忠植高级人工智能线性规划问题线性规划问题线性规划问题的标准形式为：线性规划问题的标准形式为：minXCzT=注：任何形式的线性规划问题均可化为标注：任何形式的线性规划问题均可化为标准型。准型。AX=bs.t.X0(假定b为非负)2022/11/59史忠植高级人工智能求解求解-单纯形法单纯形法l将所给问题化为标准形将所给问题化为标准形l找出一个初始可行基，建立初始单纯形表找出一个初始可行基，建立初始单纯形表l检查全部检验数检查全部检验数(若全为非负，则已得到最优若全为非负，则已得到最优解解,计算停止。否则接着下一步计算停止。否则接着下一步)l考察是否无解考察是否

7、无解(若是，计算停止，否则接着下若是，计算停止，否则接着下一步一步)l确定入基变量，出基变量确定入基变量，出基变量l对初始单纯形表进行单纯形变换对初始单纯形表进行单纯形变换2022/11/510史忠植高级人工智能3.1 3.1 概概 述述 一个约束一个约束(Constraint)通常是指一个包含若干通常是指一个包含若干变量的关系表达式，用以表示这些变量所必需满足变量的关系表达式，用以表示这些变量所必需满足的问题。的问题。约束表示广泛地应用于人工智能的各个领域，包约束表示广泛地应用于人工智能的各个领域，包括定性推理、机械与电子设备的设计与分析等。括定性推理、机械与电子设备的设计与分析等。约束满足

8、系统的设计是一项困难而困难的任务，约束满足系统的设计是一项困难而困难的任务，因为约束满足问题在一般状况下是一个因为约束满足问题在一般状况下是一个NP(Nonpolynomia)问题，所以必需运用各种策略与启问题，所以必需运用各种策略与启发式信息。发式信息。2022/11/511史忠植高级人工智能3.1 3.1 概概 述述 一个约束满足问题一个约束满足问题(Constraint Satisfaction Problem,简称简称CSP)包含一组变量与一组变量间的包含一组变量与一组变量间的约束。约束。变量表示领域参数，每个变量都有一个固定的变量表示领域参数，每个变量都有一个固定的值域。值域。一个变

9、量的值域可能是有限的，例如一个布尔一个变量的值域可能是有限的，例如一个布尔变量的值域包含两个值；也可能是离散无限的，如变量的值域包含两个值；也可能是离散无限的，如整数域；也可能是连续的，照实数域。整数域；也可能是连续的，照实数域。x1,x2,xn,D1,D2,Dn,.4,5,6,7 red,green,blue 2022/11/512史忠植高级人工智能3.1 3.1 概概 述述 约束可用于描述领域对象的性质、相互关系、任务要求、约束可用于描述领域对象的性质、相互关系、任务要求、目标等。约束满足问题的目标就是找到全部变量的一个目标等。约束满足问题的目标就是找到全部变量的一个（或多个）赋值，使全部

10、约束都得到满足。（或多个）赋值，使全部约束都得到满足。现有的约束表示可分为几类，按困难性的次序列举如下：现有的约束表示可分为几类，按困难性的次序列举如下：一元谓词。一元谓词。序关系语言，只包含偏序关系或实变量上的大小关系。序关系语言，只包含偏序关系或实变量上的大小关系。形如形如“x-y c”或或“x-y c”的方程。的方程。单位系数的线性方程与不等式，即全部的系数为单位系数的线性方程与不等式，即全部的系数为-1,0,1。随意系数的线性方程与不等式。随意系数的线性方程与不等式。约束的布尔组合。约束的布尔组合。代数与三角方程。代数与三角方程。2022/11/513史忠植高级人工智能3.1 3.1

11、概概 述述 约束表示易于理解、编码及有效实现，具有以下优点约束表示易于理解、编码及有效实现，具有以下优点:约束表示允许以说明性的方式来表达领域学问，表达实力较约束表示允许以说明性的方式来表达领域学问，表达实力较强，应用程序只需指定问题的目标条件及数据间的相互关系。强，应用程序只需指定问题的目标条件及数据间的相互关系。因而具有逻辑表示的类似性质。因而具有逻辑表示的类似性质。约束表示允许变量的域包含随意多个值，而不像命题只取真约束表示允许变量的域包含随意多个值，而不像命题只取真假二值。它保存了问题的一些结构信息，如变量域的大小、变假二值。它保存了问题的一些结构信息，如变量域的大小、变量间的相关性等

12、，从而为问题求解供应启发式信息。量间的相关性等，从而为问题求解供应启发式信息。易于并行实现。因为约束网络上的信息传播可以认为是同时易于并行实现。因为约束网络上的信息传播可以认为是同时的。的。适合于递增型系统。约束可以递增式地加入到约束网络。适合于递增型系统。约束可以递增式地加入到约束网络。易于与领域相关的问题求解模型相连接。各种数学规划技术，易于与领域相关的问题求解模型相连接。各种数学规划技术，方程求解技术等方程求解技术等,都可以自然地嵌入约束系统。都可以自然地嵌入约束系统。2022/11/514史忠植高级人工智能3.1 3.1 概概 述述 目前，约束推理的探讨主要集中于两个方面：目前，约束推

13、理的探讨主要集中于两个方面：约束搜寻与约束语言。约束搜寻与约束语言。约束搜寻主要探讨有限域上的约束满足。对有约束搜寻主要探讨有限域上的约束满足。对有限域而言，约束满足问题一般状况下是一个限域而言，约束满足问题一般状况下是一个NPNP问题。问题。大体包括下列方法：大体包括下列方法：回溯法；回溯法；约束传播；约束传播；智能回溯与真值维护；智能回溯与真值维护；可变次序例示；可变次序例示；局部修正法；局部修正法；2022/11/515史忠植高级人工智能3.1 3.1 概概 述述约束推理探讨的另一个主要方面是约束语言。约束推理探讨的另一个主要方面是约束语言。以下是几个比较典型的约束语言：以下是几个比较典

14、型的约束语言：CONSTRAINTS：面对电路描述的约束表示语：面对电路描述的约束表示语言。言。Bertrand：Leler开发的一个高级约束语言。开发的一个高级约束语言。CHIP：约束逻辑程序设计语言。：约束逻辑程序设计语言。约束层次与约束层次与HCLP：层次型约束逻辑程序设计：层次型约束逻辑程序设计语言。语言。COPS：面对对象的程序设计语言的基本形式。：面对对象的程序设计语言的基本形式。ILOG：运用建模语言来表示约束问题。：运用建模语言来表示约束问题。2022/11/516史忠植高级人工智能CONSTRAINTSCONSTRAINTS约束语言约束语言 CONSTRAINTS是一个面对电

15、路描述的约束表示语是一个面对电路描述的约束表示语言。作为一个约束表示语言，它运用了符号处理技术来言。作为一个约束表示语言，它运用了符号处理技术来求解数学方程。求解数学方程。在在CONSTRAITS中，物理部件的功能及器件的结中，物理部件的功能及器件的结构都用约束表示。构都用约束表示。这些约束一般是线性方程与不等式这些约束一般是线性方程与不等式,也包括条件表也包括条件表达式。约束变量一般是表示物理量的实变量。也有一些达式。约束变量一般是表示物理量的实变量。也有一些取离散值的变量。如开关的状态、三极管的工作状态等。取离散值的变量。如开关的状态、三极管的工作状态等。系统接受表达式推理与值推理。并实现

16、相关制导的回溯。系统接受表达式推理与值推理。并实现相关制导的回溯。2022/11/517史忠植高级人工智能CONSTRAINTSCONSTRAINTS约束语言约束语言 CONSTRAINTS CONSTRAINTS的一个的一个优点：在类型层次中表示约束，用约束来表优点：在类型层次中表示约束，用约束来表示物理对象的功能与结构。示物理对象的功能与结构。缺点：是该语言缺乏类似于面对对象语言中缺点：是该语言缺乏类似于面对对象语言中的方法那样的成分，不能定义特定于某个类的方法那样的成分，不能定义特定于某个类的概念。的概念。同时，约束传播方法比较单一，既缺乏同时，约束传播方法比较单一，既缺乏实域上的区间传

17、播机制，也缺乏有限域上的实域上的区间传播机制，也缺乏有限域上的 域传播机制。域传播机制。2022/11/518史忠植高级人工智能约束逻辑程序设计语言约束逻辑程序设计语言CHIPCHIP CHIP(Constraint handling in Prolog)CHIP(Constraint handling in Prolog)就是这样就是这样较有影响一个约束逻辑程序设计语言，其目的是简便、较有影响一个约束逻辑程序设计语言，其目的是简便、敏捷而有效地解决一大类组合问题。它通过供应几种新敏捷而有效地解决一大类组合问题。它通过供应几种新的计算域而增加逻辑程序设计的实力；有限域、布尔项的计算域而增加逻辑

18、程序设计的实力；有限域、布尔项及有理项，对于每个计算域，都供应有效的约束求解技及有理项，对于每个计算域，都供应有效的约束求解技术，即有限域上的一样性技术，布尔域的布尔合一技术术，即有限域上的一样性技术，布尔域的布尔合一技术及有理数域上的单纯型法。除此以外，及有理数域上的单纯型法。除此以外，CHIPCHIP还包含一个还包含一个一般的延迟计算机制。一般的延迟计算机制。CHIP CHIP 主要应用于两个领域：运筹学与硬件设计。主要应用于两个领域：运筹学与硬件设计。CHIP CHIP 缺乏类型机制，而这种机制对于表达领域缺乏类型机制，而这种机制对于表达领域概念是极其重要的。概念是极其重要的。2022/

19、11/519史忠植高级人工智能面对对象约束语言面对对象约束语言COPSCOPS COPS系统利用面对对象技术，将说明性系统利用面对对象技术，将说明性约束表达与类型层次结合起来。在形式上吸取约束表达与类型层次结合起来。在形式上吸取了常规语言，主要是面对对象的程序设计语言了常规语言，主要是面对对象的程序设计语言的基本形式。内部求解时接受约束推理机制，的基本形式。内部求解时接受约束推理机制，使说明性约束表达式与类型层次相结合，实现使说明性约束表达式与类型层次相结合，实现学问的结构化封装，充分发挥两者的优点，力学问的结构化封装，充分发挥两者的优点，力图实现一个具有较强表达实力和较高求解效率图实现一个具

20、有较强表达实力和较高求解效率的约束满足系统。的约束满足系统。2022/11/520史忠植高级人工智能面对对象约束语言面对对象约束语言COPSCOPS COPS的设计考虑了软件工程的应用要求，尽量将的设计考虑了软件工程的应用要求，尽量将一个不确定问题确定化：它允许条件语句与循环语句，一个不确定问题确定化：它允许条件语句与循环语句，而不是单纯以递归的形式来实现迭代计算；而不是单纯以递归的形式来实现迭代计算；通过类方通过类方法的重栽实现同一约束的不同实现，提高了程序的执行法的重栽实现同一约束的不同实现，提高了程序的执行效率。效率。COPS系统同时是一个渐增式的开放系统，用户系统同时是一个渐增式的开放

21、系统，用户能通过类型层次定义，实现新的数据类型和新的约束关能通过类型层次定义，实现新的数据类型和新的约束关系。约束语言系。约束语言COPS具有很多人工智能程序设计语言的具有很多人工智能程序设计语言的特点，如约束传播、面对目标和数据驱动的问题求解、特点，如约束传播、面对目标和数据驱动的问题求解、有限步的回溯、对象分层中的继承等。有限步的回溯、对象分层中的继承等。2022/11/521史忠植高级人工智能常用的算法常用的算法 在实际应用中，算法的表现形式千变万化，但在实际应用中，算法的表现形式千变万化，但是算法的状况也和数据结构类似，很多算法的设计是算法的状况也和数据结构类似，很多算法的设计思想具有

22、相像之处，我们可以对它们分类进行学习思想具有相像之处，我们可以对它们分类进行学习和探讨。和探讨。常用的算法大致有如下一些：常用的算法大致有如下一些：贪心法贪心法 分治法（如二分法检索）分治法（如二分法检索）回溯法回溯法 动态规划法动态规划法 局部搜寻法局部搜寻法 分支限界法分支限界法2022/11/522史忠植高级人工智能算法分析算法分析 评价一个程序优劣的重要依据是看这个程序的执行评价一个程序优劣的重要依据是看这个程序的执行须要占用多少机器资源。人们最关切的就是程序所用算须要占用多少机器资源。人们最关切的就是程序所用算法运行时所要花费的时间代价和程序中运用的数据结构法运行时所要花费的时间代价

23、和程序中运用的数据结构占有的空间代价。占有的空间代价。算法的空间代价算法的空间代价(或称空间困难性或称空间困难性)：当被解决问题：当被解决问题的规模的规模(以某种单位计算以某种单位计算)由由1增至增至n时，解该问题的算法时，解该问题的算法所需占用的空间也以某种单位由所需占用的空间也以某种单位由f(1)增至增至f(n)，这时我们，这时我们称该算法的空间代价是称该算法的空间代价是f(n)。算法的时间代价算法的时间代价(或称时间困难性或称时间困难性)：当问题规模以：当问题规模以某种单位由某种单位由1增至增至n时，对应算法所耗费的时间也以某种时，对应算法所耗费的时间也以某种单位由单位由g(1)增至增至

24、g(n)，这时我们称算法的时间代价是，这时我们称算法的时间代价是g(n)。2022/11/523史忠植高级人工智能穷尽搜寻方法穷尽搜寻方法穷尽搜寻方法即产生全部可能的树，然后依据评价标准选择一棵最优的树。Exhaustive-Search-Top(P)wherePisaCSPoftheform(V,D,C)1.f:=thenullassignment2.returnExhaustive-Search(f,P)2022/11/524史忠植高级人工智能穷尽搜寻方法穷尽搜寻方法Exhaustive-Search(f,P)1.iffisatotalassignmentofthevariablesinP

25、2.iffsatisfiestheconstraintsinP3.answer:=f4.else5.answer:=Unsat6.else7.v:=somevariableinPthatisnotyetassignedavaluebyf8.answer:=Unsat9.foreachvaluewhileanswer=Unsat10.f(v):=x11.answer:=Exhaustive-Search(f,P)12.returnanswer2022/11/525史忠植高级人工智能贪贪心心法法贪心法把构造可行解的工作分阶段贪心法把构造可行解的工作分阶段来完成。在各个阶段，选择那些在某些来完成。在

26、各个阶段，选择那些在某些意义下是局部最优的方案，期望各阶段意义下是局部最优的方案，期望各阶段的局部最优的选择带来整体最优。的局部最优的选择带来整体最优。例：例：Dijkstra的最短路径算法、的最短路径算法、Kruskal的求最小生成树算法、信号灯问题的求最小生成树算法、信号灯问题2022/11/526史忠植高级人工智能3.2回回溯溯法法有些问题须要彻底的搜寻才能解决问题，有些问题须要彻底的搜寻才能解决问题，然而，彻底的搜寻要以大量的运算时间为代然而，彻底的搜寻要以大量的运算时间为代价，对于这种状况可以通过回溯法来去掉一价，对于这种状况可以通过回溯法来去掉一些分支，从而大大削减搜寻的次数。些分

27、支，从而大大削减搜寻的次数。八皇后问题八皇后问题迷宫问题迷宫问题深度优先周游树或图深度优先周游树或图2022/11/527史忠植高级人工智能3.2BacktrackingAlgorithmlBasedondepth-firstrecursivesearchlApproach1.Testswhethersolutionhasbeenfound2.Iffoundsolution,returnit3.Elseforeachchoicethatcanbemadea)Makethatchoiceb)Recurc)Ifrecursionreturnsasolution,returnit4.Ifnochoi

28、cesremain,returnfailurelSometimescalled“searchtree”2022/11/528史忠植高级人工智能3.2Solutionto8-QueensPuzzle 八皇后问题，是一个古老而著名的问题，是八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的回溯算法的典型例题。该问题是十九世纪著名的数学家高斯数学家高斯1850年提出：在年提出：在88格的国际象棋上摆格的国际象棋上摆放八个皇后，使其不能相互攻击，即随意两个皇放八个皇后，使其不能相互攻击，即随意两个皇后都不能处于同一行、同一列或同一斜线上，问后都不能处于同一行、同一列或同一

29、斜线上，问有多少种摆法。有多少种摆法。高斯认为有高斯认为有76种方案。种方案。1854年在年在柏林的象棋杂志上不同的作者发表了柏林的象棋杂志上不同的作者发表了40种不同的种不同的解，后来有人用图论的方法解出解，后来有人用图论的方法解出92种结果。计算种结果。计算机独创后，有多种方法可以解决此问题。机独创后，有多种方法可以解决此问题。2022/11/529史忠植高级人工智能4-QueensPuzzle2022/11/530史忠植高级人工智能4-QueensTree2022/11/531史忠植高级人工智能3.2回回溯溯法法Backtracking-Top(P)1f:=thenullassignme

30、nt2returnBacktracking(f,P)2022/11/532史忠植高级人工智能3.2回溯法回溯法Backtracking(f,P)1iffisatotalassignmentofthevariablesinP2answer:=f3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6foreachvaluewhileanswer=Umsat7f(v):=x8iffsatisfiestheconstraintsinP9answer:=Backtracking(f,P)10returnanswer2022

31、/11/533史忠植高级人工智能3.2回溯法回溯法尽尽管管回回溯溯法法好好于于生生成成测测试试法法，但但对对于于非非平平凡凡问问题题仍仍旧旧是是低低效效的的。其其缘缘由由在在于于搜搜寻寻空空间间中中不不同同路路径径的的搜搜寻寻重重复复相相同同的的失失败败子子路路径径。一一些些探探讨讨者者认认为为，造造成成这这种种反反复复的的缘缘由由是是所所谓谓的的局局部部不不一一样样性性。最最简简洁洁的的情情形形是是所所谓谓的的结结点点不不一一样样性性。对对一一个个变变量量vi的的一一个个一一元元约约束束。存存在在域域中中一一个个值值vi不不满满足足该该约约束束。这这样样，每当每当vi取到取到a时就会出现不一

32、样性。时就会出现不一样性。另一种重复的情形是所谓的弧不一样性。另一种重复的情形是所谓的弧不一样性。2022/11/534史忠植高级人工智能3.3 3.3 约束传播约束传播 假如对假如对vi 的当前域中的全部值的当前域中的全部值x，存，存在在vj的当前域中的某值的当前域中的某值y使得使得 vi=x和和vj=y是是vi与与vj之间的约束所允许的，则弧之间的约束所允许的，则弧(vi,vj)是弧一样的。是弧一样的。弧一样性的概念是有向的。即弧一样性的概念是有向的。即(vi,vj)是弧一样的并不自动地意味着是弧一样的并不自动地意味着(vj,vi)是是一样的。一样的。2022/11/535史忠植高级人工智

33、能3.3 3.3 约束传播约束传播CONSTRAINT PROPAGATIONCONSTRAINT PROPAGATION(red,green)(red,blue)(red,green,blue)弧一样性（弧一样性（Arc Arc consistencyconsistency）2022/11/536史忠植高级人工智能3.33.3 CONSTRAINT PROPAGATION CONSTRAINT PROPAGATIONAlloftheMackworthalgorithmsmakeuseofaReviseprocedure.LetDvbethecurrentdomainofv,LetDwbeth

34、ecurrentdomainofw,LetPbetheconstraintpredicatethatholdsbetweenvandw,thenReviseupdatesDvasfollows:Dv:=xDv.yDwsuchthatP(x,y)2022/11/537史忠植高级人工智能3.33.3 CONSTRAINT PROPAGATION CONSTRAINT PROPAGATIONMackworth1977AC-1AC-2AC-32022/11/538史忠植高级人工智能约束传播修改算法约束传播修改算法procedureREVISE(Vi,Vj)1DELETEfalse;2foreachxD

35、ido3ifthereisnosuchyjDj4suchthat(x,yj)isconsistent,5then6deletexfromDi;7DELETEtrue;8endif9endfor10returnDELETE;11endREVISE2022/11/539史忠植高级人工智能约束传播约束传播AC-1算法算法procedureAC-11Q(Vi,Vj)arcs(G),ij;2repeat3CHANGEfalse;4foreach(Vi,Vj)Qdo5CHANGEREVISE(Vi,Vj)CHANGE;6endfor;7untilnot(CHANGE);8endAC-12022/11/54

36、0史忠植高级人工智能约束传播约束传播AC-3算法算法procedureAC-31Q(Vi,Vj)arcs(G),ij;2whileQnotempty3selectanddeleteanyarc(Vk,Vm)fromQ;4if(REVISE(Vk,Vm)5thenQ(Vi,Vk)suchthat(Vi,Vk)arcs(G),6ik,im;6endif;7endwhile;8endAC-32022/11/541史忠植高级人工智能回跳法回跳法BackjumpingBackjumping-Top(P)1f:=thenullassignment2:=Backjumping(f,P)3returnansw

37、er2022/11/542史忠植高级人工智能BackjumpingBackjumpingBackjumping(f,P)1iffisatotalassignmentofthevariablesinP2answer:=3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6conflict-set:=7foreachvalue8f(v):=x9iffsatisfiestheconstraintsinP10:=Backjumping(f,P)2022/11/543史忠植高级人工智能BackjumpingBackjump

38、ing11else12new-conflicts:=thesetofvariablesinaviolatedconstraint13ifanswerUnsat14return15elseifvnew-conflicts16return17else18conflict-set:=conflict-set(new-conflictsv)19return2022/11/544史忠植高级人工智能3.11 3.11 约束推理系统约束推理系统COPS1.1.约束与规则约束与规则 约束是谓词表达式：约束是谓词表达式：P(t1,.,tn)P(t1,.,tn)其其中中，t1,t1,.,.,tntn是是项项，典典

39、型型状状况况时时包包含含变变量量；P P是是谓谓词词符符号，谓词可以是内部函数，如号，谓词可以是内部函数，如 sum sum times times eq(equal)eq(equal)neq(not equal)neq(not equal)ge(great than or equal to)ge(great than or equal to)gt(great than)gt(great than)也可以由用户定义。也可以由用户定义。2022/11/545史忠植高级人工智能3.11 3.11 约束推理系统约束推理系统COPS条件约束具有下面的形式：条件约束具有下面的形式：ifcondition

40、1:constraint1;conditionn:constraintnwherecondition1,.,conditionnarebooleanexpressions.constraint1,constraintnareconstraintsorcontraintstable.2022/11/546史忠植高级人工智能3.11 3.11 约束推理系统约束推理系统COPSRULERuleisusedtodefinenewfunction,method,predicate,oraddnewconstraintintoobject.RULEclass:predicate(variables)(bo

41、oleanexpression)constraint1;constraintn;CASEbooleanexpression1:constraint1;booleanexpressionm:constraintm;2022/11/547史忠植高级人工智能3.11 3.11 约束推理系统约束推理系统COPSForexample:RULE multiple(INTEGER:*x,INTEGER:y,INTEGER:z)(neq(y,0)equal(x,divide(z,y);这段程序定义了三个变量这段程序定义了三个变量x、y、z之间的约束关系：之间的约束关系：x=z/y。2022/11/548史忠植

42、高级人工智能3.11 3.11 约束推理系统约束推理系统COPS2.类定义类定义CLASSclass_name:superclass_name/attributesdefinitiondatetype:attribute_name;./ruledefinitionrule_name;./functiondefinitionfunction_name;./methoddefinitionmethod_name;.2022/11/549史忠植高级人工智能3.11 3.11 约束推理系统约束推理系统COPSImplementationProgram written by COPS consists

43、of classes and rules.COPS constraint programming language is a declarativelanguage,providing classes,methods which are exist inobjectorientedlanguage.ItissimilarwithC+.COPShasthefeatures:constraintobjectorientedlogicprogrammingproductionsystem2022/11/550史忠植高级人工智能3.11 3.11 约束推理系统约束推理系统COPS算法算法3.9COPS

44、的核心算法的核心算法main-COPS。proceduremain-COPS1.Callyacctoparsetheprogramandtogenerateinternalstructures.2.InitializatiionCreateCopsConstanttrueNode;Allocatememoriesforglobalvariables.3.Interprtetheprogramwiththeinternalstructures.4.ConstraintnetworksarebuiltupforUnsolvedconstraintsandvariables.5.while some

45、 constraints in the constraint networks aretriggered,intepretethetriggeredconstraints.3.COPS的约束推理的约束推理2022/11/551史忠植高级人工智能3.11 3.11 约束推理系统约束推理系统COPS算法中的说明器如下：算法中的说明器如下：Interpreter:12switch(constrainttype)3caseConstant:4returnConstant:5caseglobalvariable:6interpreteglobalvariable:7caselocalvariableor

46、argument:8interpretelocalvariableorargument:9caseobject-attributepair:10interpreteobject-attributepair:2022/11/552史忠植高级人工智能3.11 3.11 约束推理系统约束推理系统COPS11casefunctioncall:12interpretefunctioncall:13casemethodcall:14interpretemethodcall:15caseCASEexpression:16interpreteCASEexpression:17.18default:20repo

47、rterror212022/11/553史忠植高级人工智能3.123.12 ILOG Solver约束程序是关于约束的计算系统，它的约束程序是关于约束的计算系统，它的输入是一组约束条件和须要求解的若干问题，输入是一组约束条件和须要求解的若干问题，输出问题的解决方案。输出问题的解决方案。至至于于具具体体解解决决问问题题的的算算法法等等都都是是约约束束程程序序设设计计语语言言的基本功能。的基本功能。程序员所要面对的，就是程序员所要面对的，就是如如何何把把问问题题描描述述为为一一组组约约束束构构成成的的模模型型，而而描描述的语言可以很接近自然语言。述的语言可以很接近自然语言。假假如如把把问问题题的的

48、解解决决方方案案也也看看做做是是一一种种约约束束，那那么问题的求解就是求得一个或若干个约束。么问题的求解就是求得一个或若干个约束。ILOG公公司司是是法法国国优优化化、互互动动图图像像界界面面以以及及商商业业规则应用领域的软件组件供应商，成立于规则应用领域的软件组件供应商，成立于1987年。年。2022/11/554史忠植高级人工智能3.123.12 ILOG SolverILOGSolver是是嵌嵌入入式式过过程程性性语语言言的的约约束束设设计计语语言言，将将面面对对对对象象程程序序设设计计和和约约束束逻逻辑辑程程序序设设计计结结合合起起来来，包包含含逻逻辑辑变变量量，通通过过增增量量式式约

49、约束束满满足足和和回回溯溯实实现现问问题题求求解解。ILOGSolver中中主主要要语语言言成成分分如如下下：variables:C+object/*变量变量*/integervariableCtIntVarfloatingvariableCtFloatVarbooleanvariableCtBoolVarMemoryManagement/*存储管理存储管理*/new:delete:2022/11/555史忠植高级人工智能3.123.12 ILOG SOLVERConstraints/*/*约束约束*/CtTell(x=(y+z);Basicconstraints:=,+,-,*,/,subs

50、et,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);2022/11/557史忠植高级人工智能ILOG Schedule 1.0Schedule/*/*调度调度*/CtScheduleclassGlobalobject:timeoriginaltineMintimehorizontim