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

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

1、第第03章约束推理章约束推理现在学习的是第1页，共68页2023/2/23史忠植 高级人工智能2第三章第三章 约束推理约束推理3.1 概述概述3.2 回溯法回溯法 3.3 约束传播约束传播 3.4 回跳法回跳法 3.5 约束推理系统约束推理系统COPS 3.6 ILOG SOLVER现在学习的是第2页，共68页2023/2/23史忠植 高级人工智能33.1 3.1 概概 述述最优化问题最优化问题 经济学所推崇的经济学所推崇的帕累托帕累托最优最优:几个人拎着水桶在一个水龙头前面排队几个人拎着水桶在一个水龙头前面排队打水，水桶有大有小。他们怎样排队，才能打水，水桶有大有小。他们怎样排队，才能使得总

2、的排队时间最短。这是一个寻求使得总的排队时间最短。这是一个寻求“最最优化优化”的题目，目标是节省总的排队时间，的题目，目标是节省总的排队时间，达到最优。达到最优。现在学习的是第3页，共68页2023/2/23史忠植 高级人工智能43.1 3.1 概概 述述 优化问题优化问题 运筹学 遗传算法 神经网络 约束推理现在学习的是第4页，共68页2023/2/23史忠植 高级人工智能5运筹学的工作步骤运筹学的工作步骤v1）提出和形成问题，）提出和形成问题，v2）建立模型，）建立模型，v3）求解，）求解，v4）解的检验，）解的检验，v5）解的控制，）解的控制，v6）解的实施。）解的实施。现在学习的是第5

3、页，共68页2023/2/23史忠植 高级人工智能6线性规划问题线性规划问题l例例1(广告方式的选择广告方式的选择)中华家电公司推销一中华家电公司推销一种新型洗衣机，有关数据见下表。销售部第种新型洗衣机，有关数据见下表。销售部第一月的广告预算为一月的广告预算为20000元，要求至少有元，要求至少有8个电个电视商业节目，视商业节目，15家报纸广告；电视广告费不得家报纸广告；电视广告费不得超过超过12000元，电台广播至少隔日有一次。现问元，电台广播至少隔日有一次。现问该公司销售部应当采用怎样的广告宣传计划，该公司销售部应当采用怎样的广告宣传计划，才能取得最好的效果才能取得最好的效果?现在学习的是

4、第6页，共68页2023/2/23史忠植 高级人工智能7线性规划问题线性规划问题广告方式广告方式广告费用广告费用(元元/次次)可用最高可用最高次数次数/月月期望的宣传期望的宣传效果效果/单位单位电视台电视台a(白天白天,1分钟分钟)5001650电视台电视台b(晚上晚上,30钞钞)10001080每日晨报每日晨报/(半版半版)1002430星期日报星期日报/(半版半版)300440广播电台广播电台/(1分钟分钟)802515表表1 中华家电公司推销新型洗衣机广告方式选择的数据表中华家电公司推销新型洗衣机广告方式选择的数据表现在学习的是第7页，共68页2023/2/23史忠植 高级人工智能8线性

5、规划问题线性规划问题解：解：设x1,x2,x3,x4,x5分别是第一个月内电视台a，电视台b，每日晨报，星期日报，广播电台进行广告宣传的次数，则其数学模型为 max 50 x1+80 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,x3 24,x44,15x525,x1,x2,x3,x4,x5 0。现在学习的是第8页，共68页2023/2/23史忠植 高级人工智能9线性规划问题线性规划问题线性规划问题线性规划问题(LP)的一般形式为：的

6、一般形式为：min(max)z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn(,)b1 a21x1+a22x2+a2nxn(,)b2 am1x1+am2x2+amnxn(,)bmxj0,j=1,2,n现在学习的是第9页，共68页2023/2/23史忠植 高级人工智能10线性规划问题线性规划问题线性规划问题的标准形式为：线性规划问题的标准形式为：min XCzT=注：任何形式的线性规划问题均可化为标准注：任何形式的线性规划问题均可化为标准型。型。AX=bs.t.X0 (假定b为非负)现在学习的是第10页，共68页2023/2/23史忠植 高级人工智能11求解求解-单纯形

7、法单纯形法l将所给问题化为标准形将所给问题化为标准形l找出一个初始可行基，建立初始单纯形表找出一个初始可行基，建立初始单纯形表l检查所有检验数检查所有检验数(若全为非负，则已得到最优若全为非负，则已得到最优解解,计算停止。否则继续下一步计算停止。否则继续下一步)l考察是否无解考察是否无解(若是，计算停止，否则继续下一步若是，计算停止，否则继续下一步)l确定入基变量，出基变量确定入基变量，出基变量l对初始单纯形表进行单纯形变换对初始单纯形表进行单纯形变换现在学习的是第11页，共68页2023/2/23史忠植 高级人工智能123.1 3.1 概概 述述 一个一个约束约束(Constraint)通常

8、是指一个包含若干变量的通常是指一个包含若干变量的关系表达式，用以表示这些变量所必须满足的问题。关系表达式，用以表示这些变量所必须满足的问题。约束表示广泛地应用于人工智能的各个领域，包括约束表示广泛地应用于人工智能的各个领域，包括定性推理、机械与电子设备的设计与分析等。定性推理、机械与电子设备的设计与分析等。约束满足系统的设计是一项困难而复杂的任务，因约束满足系统的设计是一项困难而复杂的任务，因为约束满足问题在一般情况下是一个为约束满足问题在一般情况下是一个NP(Nonpolynomia)问题，问题，所以必须使用各种策略与启发式信息。所以必须使用各种策略与启发式信息。现在学习的是第12页，共68

9、页2023/2/23史忠植 高级人工智能133.1 3.1 概概 述述 一个约束满足问题一个约束满足问题(Constraint Satisfaction Problem,简称简称CSP)包含一组变量与一组变量间的约束。包含一组变量与一组变量间的约束。变量表示领域参数，每个变量都有一个固定的值域。变量表示领域参数，每个变量都有一个固定的值域。一个变量的值域可能是一个变量的值域可能是有限的有限的，例如一个布尔变量，例如一个布尔变量的值域包含两个值；也可能是的值域包含两个值；也可能是离散无限离散无限的，如整数域；的，如整数域；也可能是连续的，如实数域。也可能是连续的，如实数域。x1,x2,xn,D1

10、,D2,Dn,.4,5,6,7 red,green,blue 现在学习的是第13页，共68页2023/2/23史忠植 高级人工智能143.1 3.1 概概 述述 约束可用于描述领域对象的性质、相互关系、任务要求、目约束可用于描述领域对象的性质、相互关系、任务要求、目标等。约束满足问题的标等。约束满足问题的目标目标就是就是找找到所有变量的一个（或多个）到所有变量的一个（或多个）赋值赋值，使所有约束都得到满足。，使所有约束都得到满足。现有的约束表示可分为几类，现有的约束表示可分为几类，按复杂性的次序列举如下：按复杂性的次序列举如下：一元谓词。一元谓词。序关系语言，只包含偏序关系或实变量上的大小关系

11、。序关系语言，只包含偏序关系或实变量上的大小关系。形如形如“x-y c”或或“x-y c”的方程。的方程。单位系数的线性方程与不等式，即所有的系数为单位系数的线性方程与不等式，即所有的系数为-1,0,1。任意系数的线性方程与不等式。任意系数的线性方程与不等式。约束的布尔组合。约束的布尔组合。代数与三角方程。代数与三角方程。现在学习的是第14页，共68页2023/2/23史忠植 高级人工智能153.1 3.1 概概 述述 约束表示易于理解、编码及有效实现，具有以下约束表示易于理解、编码及有效实现，具有以下优点优点:约束表示允许约束表示允许以说明性的方式以说明性的方式来表达领域知识，表达能力较强，

12、应用来表达领域知识，表达能力较强，应用程序只需指定问题的目标条件及数据间的相互关系。因而具有逻辑表示的程序只需指定问题的目标条件及数据间的相互关系。因而具有逻辑表示的类似性质。类似性质。约束表示允许约束表示允许变量的域包含任意多个值变量的域包含任意多个值，而不像命题只取真假，而不像命题只取真假二值。它保存了问题的一些结构信息，如变量域的大小、变量间二值。它保存了问题的一些结构信息，如变量域的大小、变量间的相关性等，从而为问题求解提供启发式信息。的相关性等，从而为问题求解提供启发式信息。易于并行实现易于并行实现。因为约束网络上的信息传播可以。因为约束网络上的信息传播可以认为是同时的。认为是同时的

13、。适合于适合于递增型系统递增型系统。约束可以递增式地加入到约束网络。约束可以递增式地加入到约束网络。易于易于与领域相关的问题求解模型与领域相关的问题求解模型相衔接。各种数学规划技术，方程相衔接。各种数学规划技术，方程求解技术等求解技术等,都可以自然地嵌入约束系统。都可以自然地嵌入约束系统。现在学习的是第15页，共68页2023/2/23史忠植 高级人工智能163.1 3.1 概概 述述 目前，约束推理的研究主要集中于两个方面：目前，约束推理的研究主要集中于两个方面：约约束搜索束搜索与与约束语言约束语言。约束搜索约束搜索主要研究有限域上的约束满足。对有限主要研究有限域上的约束满足。对有限域而言，

14、约束满足问题一般情况下是一个域而言，约束满足问题一般情况下是一个NP问题。大问题。大体包括下列方法：体包括下列方法：回溯法；回溯法；约束传播；约束传播；智能回溯与真值维护；智能回溯与真值维护；可变次序例示；可变次序例示；局部修正法；局部修正法；现在学习的是第16页，共68页2023/2/23史忠植 高级人工智能173.1 3.1 概概 述述约束推理研究的另一个主要方面是约束推理研究的另一个主要方面是约束语言约束语言。以。以下是几个比较典型的约束语言：下是几个比较典型的约束语言：CONSTRAINTS：面向电路描述的约束表示语言。面向电路描述的约束表示语言。Bertrand：Leler开发的一个

15、高级约束语言。开发的一个高级约束语言。CHIP：约束逻辑程序设计语言。约束逻辑程序设计语言。约束层次与约束层次与HCLP：层次型层次型约束逻辑程序设计语言。约束逻辑程序设计语言。COPS：面向对象的程序设计语言的基本形式。面向对象的程序设计语言的基本形式。ILOG：使用建模语言来表示约束问题。使用建模语言来表示约束问题。现在学习的是第17页，共68页2023/2/23史忠植 高级人工智能18CONSTRAINTSCONSTRAINTS约束语言约束语言 CONSTRAINTS是一个面向电路描述的约束表示语言。是一个面向电路描述的约束表示语言。作为一个约束表示语言，它使用了符号处理技术来求解数学方

16、作为一个约束表示语言，它使用了符号处理技术来求解数学方程。程。在在CONSTRAITS中，物理部件的功能及器件的结构都用中，物理部件的功能及器件的结构都用约束表示。约束表示。这些约束一般是线性方程与不等式这些约束一般是线性方程与不等式,也包括条件表达式。也包括条件表达式。约束变量一般是表示物理量的实变量。也有一些取离散值的变约束变量一般是表示物理量的实变量。也有一些取离散值的变量。如开关的状态、三极管的工作状态等。系统采用表达式推量。如开关的状态、三极管的工作状态等。系统采用表达式推理与值推理。并实现相关制导的回溯。理与值推理。并实现相关制导的回溯。现在学习的是第18页，共68页2023/2/

17、23史忠植 高级人工智能19CONSTRAINTSCONSTRAINTS约束语言约束语言 CONSTRAINTSCONSTRAINTS的一个的一个优点：优点：在类型层次中表示约束，用约束来表示物在类型层次中表示约束，用约束来表示物理对象的功能与结构。理对象的功能与结构。缺点：缺点：是该语言缺乏类似于面向对象语言中的方法那是该语言缺乏类似于面向对象语言中的方法那样的成分，不能定义特定于某个类的概念。样的成分，不能定义特定于某个类的概念。同时，约束传播方法比较单一，既缺乏实同时，约束传播方法比较单一，既缺乏实域上的区间传播机制，也缺乏有限域上的域上的区间传播机制，也缺乏有限域上的 域域传播机制。传

18、播机制。现在学习的是第19页，共68页2023/2/23史忠植 高级人工智能20约束逻辑程序设计语言约束逻辑程序设计语言CHIPCHIP CHIP(Constraint handling in Prolog)就是这样较有影响就是这样较有影响一个约束逻辑程序设计语言，其目的是简便、灵活而有效地解决一个约束逻辑程序设计语言，其目的是简便、灵活而有效地解决一大类组合问题。它通过提供几种新的计算域而增强逻辑程序设一大类组合问题。它通过提供几种新的计算域而增强逻辑程序设计的能力；有限域、布尔项及有理项，对于每个计算域，都提供计的能力；有限域、布尔项及有理项，对于每个计算域，都提供有效的约束求解技术，即有

19、限域上的一致性技术，布尔域的布尔有效的约束求解技术，即有限域上的一致性技术，布尔域的布尔合一技术及有理数域上的单纯型法。除此以外，合一技术及有理数域上的单纯型法。除此以外，CHIP还包含一个还包含一个一般的延迟计算机制。一般的延迟计算机制。CHIP 主要应用于两个领域：运筹学与硬件设计。主要应用于两个领域：运筹学与硬件设计。CHIP 缺乏类型机制，而这种机制对于表达领域概念是缺乏类型机制，而这种机制对于表达领域概念是极其重要的。极其重要的。现在学习的是第20页，共68页2023/2/23史忠植 高级人工智能21面向对象约束语言面向对象约束语言COPSCOPS COPS系统利用面向对象技术，将说

20、明性约系统利用面向对象技术，将说明性约束表达与类型层次结合起来。在形式上吸收了束表达与类型层次结合起来。在形式上吸收了常规语言，主要是面向对象的程序设计语言的常规语言，主要是面向对象的程序设计语言的基本形式。内部求解时采用约束推理机制，使基本形式。内部求解时采用约束推理机制，使说明性约束表达式与类型层次相结合，实现知说明性约束表达式与类型层次相结合，实现知识的结构化封装，充分发挥两者的优点，力图识的结构化封装，充分发挥两者的优点，力图实现一个具有较强表达能力和较高求解效率的实现一个具有较强表达能力和较高求解效率的约束满足系统。约束满足系统。现在学习的是第21页，共68页2023/2/23史忠植

21、 高级人工智能22面向对象约束语言面向对象约束语言COPSCOPS COPS的设计考虑了软件工程的应用要求，尽量将一的设计考虑了软件工程的应用要求，尽量将一个不确定问题确定化：它允许条件语句与循环语句，而个不确定问题确定化：它允许条件语句与循环语句，而不是单纯以递归的形式来实现迭代计算；不是单纯以递归的形式来实现迭代计算；通过类方法的通过类方法的重栽实现同一约束的不同实现，提高了程序的执行效率。重栽实现同一约束的不同实现，提高了程序的执行效率。COPS系统同时是一个渐增式的开放系统，用户能通过类系统同时是一个渐增式的开放系统，用户能通过类型层次定义，实现新的数据类型和新的约束关系。约束型层次定

22、义，实现新的数据类型和新的约束关系。约束语言语言COPS具有许多人工智能程序设计语言的特点，如约束传具有许多人工智能程序设计语言的特点，如约束传播、面向目标和数据驱动的问题求解、有限步的回溯、对象分播、面向目标和数据驱动的问题求解、有限步的回溯、对象分层中的继承等。层中的继承等。现在学习的是第22页，共68页2023/2/23史忠植 高级人工智能23常用的算法常用的算法 在实际应用中，算法的表现形式千变万化，但是算在实际应用中，算法的表现形式千变万化，但是算法的情况也和数据结构类似，许多算法的设计思想具有法的情况也和数据结构类似，许多算法的设计思想具有相似之处，我们可以对它们分类进行学习和研究

23、。相似之处，我们可以对它们分类进行学习和研究。常常用的算法大致有如下一些：用的算法大致有如下一些：贪心法贪心法 分治法（如二分法检索）分治法（如二分法检索）回溯法回溯法 动态规划法动态规划法 局部搜索法局部搜索法 分支限界法分支限界法现在学习的是第23页，共68页2023/2/23史忠植 高级人工智能24算法分析算法分析 评价一个程序优劣的重要依据是看这个程序的执行需要评价一个程序优劣的重要依据是看这个程序的执行需要占用多少机器资源。人们最关心的就是程序所用算法运行时占用多少机器资源。人们最关心的就是程序所用算法运行时所要花费的所要花费的时间代价时间代价和程序中使用的数据结构占有的和程序中使用

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

25、算法的，这时我们称算法的时间代价是时间代价是g(n)。现在学习的是第24页，共68页2023/2/23史忠植 高级人工智能25穷尽搜索方法穷尽搜索方法穷尽搜索方法 即产生所有可能的树，然后根据评价标准选择一棵最优的树。Exhaustive-Search-Top(P)wherePisaCSPoftheform(V,D,C)1.f:=thenullassignment2.returnExhaustive-Search(f,P)现在学习的是第25页，共68页2023/2/23史忠植 高级人工智能26穷尽搜索方法穷尽搜索方法Exhaustive-Search(f,P)1.iffisatotalassi

26、gnmentofthevariablesinP2.iffsatisfiestheconstraintsinP3.answer:=f4.else5.answer:=Unsat6.else7.v:=somevariableinPthatisnotyetassignedavaluebyf8.answer:=Unsat9.foreachvaluewhileanswer=Unsat10.f(v):=x11.answer:=Exhaustive-Search(f,P)12.returnanswer现在学习的是第26页，共68页2023/2/23史忠植 高级人工智能27贪贪心心法法贪心法把构造可行解的工作分

27、阶段来完贪心法把构造可行解的工作分阶段来完成。在各个阶段，选择那些在某些意义下是成。在各个阶段，选择那些在某些意义下是局部最优的方案，期望各阶段的局部最优的局部最优的方案，期望各阶段的局部最优的选择带来整体最优。选择带来整体最优。例：例：Dijkstra的最短路径算法、的最短路径算法、Kruskal的的求最小生成树算法、信号灯问题求最小生成树算法、信号灯问题现在学习的是第27页，共68页2023/2/23史忠植 高级人工智能283.2回回溯溯法法有些问题需要彻底的搜索才能解决问题，然有些问题需要彻底的搜索才能解决问题，然而，彻底的搜索要以大量的运算时间为代价，对而，彻底的搜索要以大量的运算时间

28、为代价，对于这种情况可以通过回溯法来去掉一些分支，从于这种情况可以通过回溯法来去掉一些分支，从而大大减少搜索的次数。而大大减少搜索的次数。l八皇后问题八皇后问题l迷宫问题迷宫问题l深度优先周游树或图深度优先周游树或图现在学习的是第28页，共68页2023/2/23史忠植 高级人工智能293.2BacktrackingAlgorithmlBasedondepth-firstrecursivesearchlApproach1.Testswhethersolutionhasbeenfound2.Iffoundsolution,returnit3.Elseforeachchoicethatcanbem

29、adea)Makethatchoiceb)Recurc)Ifrecursionreturnsasolution,returnit4.Ifnochoicesremain,returnfailurelSometimescalled“searchtree”现在学习的是第29页，共68页2023/2/23史忠植 高级人工智能303.2Solutionto8-QueensPuzzle 八皇后八皇后问题，是一个古老而著名的问题，是回问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学溯算法的典型例题。该问题是十九世纪著名的数学家家高斯高斯1850年提出：在年提出：在88格的格的国

30、际象棋国际象棋上摆放八个皇上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。一行、同一列或同一斜线上，问有多少种摆法。高斯认高斯认为有为有76种种方案。方案。1854年在年在柏林柏林的象棋杂志上不同的作者的象棋杂志上不同的作者发表了发表了40种不同的解，后来有人用图论的方法解出种不同的解，后来有人用图论的方法解出92种种结果。计算机发明后，有多种方法可以解决此问结果。计算机发明后，有多种方法可以解决此问题。题。现在学习的是第30页，共68页2023/2/23史忠植 高级人工智能314-Queen

31、sPuzzle现在学习的是第31页，共68页2023/2/23史忠植 高级人工智能324-QueensTree现在学习的是第32页，共68页2023/2/23史忠植 高级人工智能333.2回回溯溯法法Backtracking-Top(P)1f:=thenullassignment2returnBacktracking(f,P)现在学习的是第33页，共68页2023/2/23史忠植 高级人工智能343.2回溯法回溯法Backtracking(f,P)1iffisatotalassignmentofthevariablesinP2answer:=f3else4v:=somevariableinPt

32、hatisnotyetassignedavaluebyf5answer:=Unsat6foreachvaluewhileanswer=Umsat7f(v):=x8iffsatisfiestheconstraintsinP9answer:=Backtracking(f,P)10returnanswer现在学习的是第34页，共68页2023/2/23史忠植 高级人工智能353.2回溯法回溯法尽尽管管回回溯溯法法好好于于生生成成测测试试法法，但但对对于于非非平平凡凡问问题题仍仍然然是是低低效效的的。其其原原因因在在于于搜搜索索空空间间中中不不同同路路径径的的搜搜索索重重复复相相同同的的失失败败子子路

33、路径径。一一些些研研究究者者认认为为，造造成成这这种种反反复复的的原原因因是是所所谓谓的的局局部部不不一一致致性性。最最简简单单的的情情形形是是所所谓谓的的结结点点不不一一致致性性。对对一一个个变变量量vi的的一一个个一一元元约约束束。存存在在域域中中一一个个值值vi不不满满足足该该约约束束。这样，每当这样，每当vi取到取到a时就会出现不一致性。时就会出现不一致性。另一种重复的情形是所谓的弧不一致性。另一种重复的情形是所谓的弧不一致性。现在学习的是第35页，共68页2023/2/23史忠植 高级人工智能363.3 3.3 约束传播约束传播 如果对如果对vi 的当前域中的所有值的当前域中的所有值

34、x，存在，存在vj的当前域中的某值的当前域中的某值y使得使得 vi=x和和vj=y是是vi与与vj之间的约束所允许的，则弧之间的约束所允许的，则弧(vi,vj)是是弧一致弧一致的的。弧一致性的概念是弧一致性的概念是有向的有向的。即。即(vi,vj)是弧一致的并不自动地意味着是弧一致的并不自动地意味着(vj,vi)是一是一致的。致的。现在学习的是第36页，共68页2023/2/23史忠植 高级人工智能373.3 3.3 约束传播约束传播CONSTRAINT PROPAGATIONCONSTRAINT PROPAGATION(red,green)(red,blue)(red,green,blue)

35、弧一致性（弧一致性（Arc consistency）现在学习的是第37页，共68页2023/2/23史忠植 高级人工智能383.33.3 CONSTRAINT PROPAGATION CONSTRAINT PROPAGATIONAlloftheMackworthalgorithmsmakeuseofaReviseprocedure.LetDvbethecurrentdomainofv,LetDwbethecurrentdomainofw,LetPbetheconstraintpredicatethatholdsbetweenvandw,thenReviseupdatesDvasfollows:

36、Dv:=xDv.yDwsuchthatP(x,y)现在学习的是第38页，共68页2023/2/23史忠植 高级人工智能393.33.3 CONSTRAINT PROPAGATION CONSTRAINT PROPAGATIONMackworth1977AC-1AC-2AC-3现在学习的是第39页，共68页2023/2/23史忠植 高级人工智能40约束传播修改算法约束传播修改算法procedureREVISE(Vi,Vj)1DELETEfalse;2foreachxDido 3ifthereisnosuchyjDj4suchthat(x,yj)isconsistent,5then6deletex

37、fromDi;7DELETEtrue;8endif9endfor10returnDELETE;11endREVISE现在学习的是第40页，共68页2023/2/23史忠植 高级人工智能41约束传播约束传播AC-1算法算法procedureAC-11Q(Vi,Vj)arcs(G),ij;2repeat3CHANGEfalse;4foreach(Vi,Vj)Qdo5CHANGEREVISE(Vi,Vj)CHANGE;6endfor;7untilnot(CHANGE);8endAC-1现在学习的是第41页，共68页2023/2/23史忠植 高级人工智能42约束传播约束传播AC-3算法算法proced

38、ureAC-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-3现在学习的是第42页，共68页2023/2/23史忠植 高级人工智能43回跳法回跳法BackjumpingBackjumping-Top(P)1f:=thenullassignment2:=Backjumping(f,P)3returnanswer现在学习的是第43页，共68

39、页2023/2/23史忠植 高级人工智能44BackjumpingBackjumpingBackjumping(f,P)1iffisatotalassignmentofthevariablesinP2answer:=3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6conflict-set:=7foreachvalue8f(v):=x9iffsatisfiestheconstraintsinP10:=Backjumping(f,P)现在学习的是第44页，共68页2023/2/23史忠植 高级人工智能45Bac

40、kjumpingBackjumping11else12new-conflicts:=thesetofvariablesinaviolatedconstraint13ifanswerUnsat14return15elseifvnew-conflicts16return17else18conflict-set:=conflict-set(new-conflictsv)19return现在学习的是第45页，共68页2023/2/23史忠植 高级人工智能463.11 3.11 约束推理系统约束推理系统COPS1.1.约束与规则约束与规则 约束是谓词表达式：约束是谓词表达式：P(t1,.,tn)其其中中

41、，t1,.,tn是是项项，典典型型情情况况时时包包含含变变量量；P是是谓谓词词符符号号，谓谓词词可可以是内部函数，如以是内部函数，如sumtimeseq(equal)neq(notequal)ge(greatthanorequalto)gt(greatthan)也可以由用户定义。也可以由用户定义。现在学习的是第46页，共68页2023/2/23史忠植 高级人工智能473.11 3.11 约束推理系统约束推理系统COPS条件约束具有下面的形式：条件约束具有下面的形式：ifcondition1:constraint1;conditionn:constraintnwherecondition1,.,

42、conditionnarebooleanexpressions.constraint1,constraintnareconstraintsorcontraintstable.现在学习的是第47页，共68页2023/2/23史忠植 高级人工智能483.11 3.11 约束推理系统约束推理系统COPSRULERuleisusedtodefinenewfunction,method,predicate,oraddnewconstraintintoobject.RULEclass:predicate(variables)(booleanexpression)constraint1;constraint

43、n;CASEbooleanexpression1:constraint1;booleanexpressionm:constraintm;现在学习的是第48页，共68页2023/2/23史忠植 高级人工智能493.11 3.11 约束推理系统约束推理系统COPSForexample:RULEmultiple(INTEGER:*x,INTEGER:y,INTEGER:z)(neq(y,0)equal(x,divide(z,y);这段程序定义了三个变量这段程序定义了三个变量x、y、z之间的约束关系：之间的约束关系：x=z/y。现在学习的是第49页，共68页2023/2/23史忠植 高级人工智能503

44、.11 3.11 约束推理系统约束推理系统COPS2.类定义类定义CLASSclass_name:superclass_name/attributesdefinitiondatetype:attribute_name;./ruledefinitionrule_name;./functiondefinitionfunction_name;./methoddefinitionmethod_name;.现在学习的是第50页，共68页2023/2/23史忠植 高级人工智能513.11 3.11 约束推理系统约束推理系统COPSImplementationProgram written by COPS

45、consists of classes and rules.COPS constraint programming language is a declarativelanguage,providingclasses,methodswhichareexistinobjectoriented language.It is similar with C+.COPS has thefeatures:constraintobjectorientedlogicprogrammingproductionsystem现在学习的是第51页，共68页2023/2/23史忠植 高级人工智能523.11 3.11

46、约束推理系统约束推理系统COPS算法算法3.9COPS的核心算法的核心算法main-COPS。proceduremain-COPS1.Callyacctoparsetheprogramandtogenerateinternalstructures.2.InitializatiionCreateCopsConstanttrueNode;Allocatememoriesforglobalvariables.3.Interprtetheprogramwiththeinternalstructures.4.ConstraintnetworksarebuiltupforUnsolvedconstrain

47、tsandvariables.5.whilesomeconstraintsintheconstraintnetworksaretriggered,intepretethetriggeredconstraints.3.COPS的约束推理的约束推理现在学习的是第52页，共68页2023/2/23史忠植 高级人工智能533.11 3.11 约束推理系统约束推理系统COPS算法中的解释器如下：算法中的解释器如下：Interpreter:12switch(constrainttype)3caseConstant:4returnConstant:5caseglobalvariable:6interpret

48、eglobalvariable:7caselocalvariableorargument:8interpretelocalvariableorargument:9caseobject-attributepair:10interpreteobject-attributepair:现在学习的是第53页，共68页2023/2/23史忠植 高级人工智能543.11 3.11 约束推理系统约束推理系统COPS11casefunctioncall:12interpretefunctioncall:13casemethodcall:14interpretemethodcall:15caseCASEexpre

49、ssion:16interpreteCASEexpression:17.18default:20reporterror21现在学习的是第54页，共68页2023/2/23史忠植 高级人工智能553.123.12 ILOG Solver约束程序约束程序约束程序约束程序是关于是关于约束的计算系统约束的计算系统，它的，它的 输入输入是是一组约束条件一组约束条件和和需要求解的若干问题需要求解的若干问题，输出输出问题的问题的解决方案解决方案。至于具体解决问题的至于具体解决问题的算法算法等都是约束程序设计语言的等都是约束程序设计语言的基本功能。基本功能。程序员所要面对的，就是程序员所要面对的，就是 如如何

50、何把把问问题题描描述述为为一一组组约约束束构构成成的的模模型型，而而描描述述的的语语言言可可以很接近自然语言。以很接近自然语言。如如果果把把问问题题的的解解决决方方案案也也看看做做是是一一种种约约束束，那那么么问问题题的的求求解解就是就是求求得得一个或若干个约束一个或若干个约束。ILOG公司是法国优化、互动图像界面以及商业规则应用领公司是法国优化、互动图像界面以及商业规则应用领域的软件组件供应商，成立于域的软件组件供应商，成立于1987年。年。现在学习的是第55页，共68页2023/2/23史忠植 高级人工智能563.123.12 ILOG SolverILOGSolver是是嵌嵌入入式式过过