第03章约束推理精.ppt

第第03章约束推理章约束推理第1页，本讲稿共68页2022/10/15史忠植 高级人工智能2第三章第三章 约束推理约束推理3.1概述概述3.2回溯法回溯法 3.3约束传播约束传播 3.4回跳法回跳法 3.5约束推理系统约束推理系统COPS3.6ILOGSOLVER第2页，本讲稿共68页2022/10/15史忠植 高级人工智能33.1 3.1 概概 述述最优化问题最优化问题 经济学所推崇的经济学所推崇的帕累托帕累托最优最优:几个人拎着水桶在一个水龙头前面排队几个人拎着水桶在一个水龙头前面排队打水，水桶有大有小。他们怎样排队，才能打水，水桶有大有小。他们怎样排队，才能使得总的排队时间最短。这是一个寻求使得总的排队时间最短。这是一个寻求“最最优化优化”的题目，目标是节省总的排队时间，的题目，目标是节省总的排队时间，达到最优。达到最优。第3页，本讲稿共68页2022/10/15史忠植 高级人工智能43.1 3.1 概概 述述 优化问题优化问题 运筹学 遗传算法 神经网络 约束推理第4页，本讲稿共68页2022/10/15史忠植 高级人工智能5运筹学的工作步骤运筹学的工作步骤v1）提出和形成问题，）提出和形成问题，v2）建立模型，）建立模型，v3）求解，）求解，v4）解的检验，）解的检验，v5）解的控制，）解的控制，v6）解的实施。）解的实施。第5页，本讲稿共68页2022/10/15史忠植 高级人工智能6线性规划问题线性规划问题l例例1(广告方式的选择广告方式的选择)中华家电公司推销一中华家电公司推销一种新型洗衣机，有关数据见下表。销售部第一种新型洗衣机，有关数据见下表。销售部第一月的广告预算为月的广告预算为20000元，要求至少有元，要求至少有8个电视个电视商业节目，商业节目，15家报纸广告；电视广告费不得超家报纸广告；电视广告费不得超过过12000元，电台广播至少隔日有一次。现问该元，电台广播至少隔日有一次。现问该公司销售部应当采用怎样的广告宣传计划，才能公司销售部应当采用怎样的广告宣传计划，才能取得最好的效果取得最好的效果?第6页，本讲稿共68页2022/10/15史忠植 高级人工智能7线性规划问题线性规划问题广告方式广告方式广告费用广告费用(元元/次次)可用最高可用最高次数次数/月月期望的宣传期望的宣传效果效果/单位单位电视台电视台a(白天白天,1分钟分钟)5001650电视台电视台b(晚上晚上,30钞钞)10001080每日晨报每日晨报/(半版半版)1002430星期日报星期日报/(半版半版)300440广播电台广播电台/(1分钟分钟)802515表表1中华家电公司推销新型洗衣机广告方式选择的数据表中华家电公司推销新型洗衣机广告方式选择的数据表第7页，本讲稿共68页2022/10/15史忠植 高级人工智能8线性规划问题线性规划问题解：解：设x1,x2,x3,x4,x5分别是第一个月内电视台a，电视台b，每日晨报，星期日报，广播电台进行广告宣传的次数，则其数学模型为 max50 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页2022/10/15史忠植 高级人工智能9线性规划问题线性规划问题线性规划问题线性规划问题(LP)的一般形式为的一般形式为：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页2022/10/15史忠植 高级人工智能10线性规划问题线性规划问题线性规划问题的标准形式为：线性规划问题的标准形式为：minXCzT=注：任何形式的线性规划问题均可化为标准型。注：任何形式的线性规划问题均可化为标准型。AX=bs.t.X0 (假定b为非负)第10页，本讲稿共68页2022/10/15史忠植 高级人工智能11求解求解-单纯形法单纯形法l将所给问题化为标准形将所给问题化为标准形l找出一个初始可行基，建立初始单纯形表找出一个初始可行基，建立初始单纯形表l检查所有检验数检查所有检验数(若全为非负，则已得到最优若全为非负，则已得到最优解解,计算停止。否则继续下一步计算停止。否则继续下一步)l考察是否无解考察是否无解(若是，计算停止，否则继续下一步若是，计算停止，否则继续下一步)l确定入基变量，出基变量确定入基变量，出基变量l对初始单纯形表进行单纯形变换对初始单纯形表进行单纯形变换第11页，本讲稿共68页2022/10/15史忠植 高级人工智能123.1 3.1 概概 述述 一个一个约束约束(Constraint)通常是指一个包含若干变量的关通常是指一个包含若干变量的关系表达式，用以表示这些变量所必须满足的问题。系表达式，用以表示这些变量所必须满足的问题。约束表示广泛地应用于人工智能的各个领域，包括定性约束表示广泛地应用于人工智能的各个领域，包括定性推理、机械与电子设备的设计与分析等。推理、机械与电子设备的设计与分析等。约束满足系统的设计是一项困难而复杂的任务，因约束满足系统的设计是一项困难而复杂的任务，因为约束满足问题在一般情况下是一个为约束满足问题在一般情况下是一个NP(Nonpolynomia)问问题，所以必须使用各种策略与启发式信息。题，所以必须使用各种策略与启发式信息。第12页，本讲稿共68页2022/10/15史忠植 高级人工智能133.1 3.1 概概 述述 一个约束满足问题一个约束满足问题(Constraint Satisfaction Problem,简简称称CSP)包含一组变量与一组变量间的约束。包含一组变量与一组变量间的约束。变量表示领域参数，每个变量都有一个固定的值变量表示领域参数，每个变量都有一个固定的值域。域。一个变量的值域可能是一个变量的值域可能是有限的有限的，例如一个布尔变量，例如一个布尔变量的值域包含两个值；也可能是的值域包含两个值；也可能是离散无限离散无限的，如整数域；也的，如整数域；也可能是连续的，如实数域。可能是连续的，如实数域。x1,x2,xn,D1,D2,Dn,.4,5,6,7 red,green,blue 第13页，本讲稿共68页2022/10/15史忠植 高级人工智能143.1 3.1 概概 述述 约束可用于描述领域对象的性质、相互关系、任务要求、目标等。约束可用于描述领域对象的性质、相互关系、任务要求、目标等。约束满足问题的约束满足问题的目标目标就是就是找找到所有变量的一个（或多个）到所有变量的一个（或多个）赋值赋值，使，使所有约束都得到满足。所有约束都得到满足。现有的约束表示可分为几类，现有的约束表示可分为几类，按复杂性的次序列举如下：按复杂性的次序列举如下：一元谓词。一元谓词。序关系语言，只包含偏序关系或实变量上的大小关系。序关系语言，只包含偏序关系或实变量上的大小关系。形如形如“x-y c”或或“x-y c”的方程。的方程。单位系数的线性方程与不等式，即所有的系数为单位系数的线性方程与不等式，即所有的系数为-1,0,1。任意系数的线性方程与不等式。任意系数的线性方程与不等式。约束的布尔组合。约束的布尔组合。代数与三角方程。代数与三角方程。第14页，本讲稿共68页2022/10/15史忠植 高级人工智能153.1 3.1 概概 述述 约束表示易于理解、编码及有效实现，具有以下约束表示易于理解、编码及有效实现，具有以下优点优点:约束表示允许约束表示允许以说明性的方式以说明性的方式来表达领域知识，表达能力较来表达领域知识，表达能力较强，应用程序只需指定问题的目标条件及数据间的相互关系。强，应用程序只需指定问题的目标条件及数据间的相互关系。因而具有逻辑表示的类似性质。因而具有逻辑表示的类似性质。约束表示允许约束表示允许变量的域包含任意多个值变量的域包含任意多个值，而不像命题只取真，而不像命题只取真假二值。它保存了问题的一些结构信息，如变量域的大小、变假二值。它保存了问题的一些结构信息，如变量域的大小、变量间的相关性等，从而为问题求解提供启发式信息。量间的相关性等，从而为问题求解提供启发式信息。易于并行实现易于并行实现。因为约束网络上的信息传播可以。因为约束网络上的信息传播可以认为是同时的。认为是同时的。适合于适合于递增型系统递增型系统。约束可以递增式地加入到约束网络。约束可以递增式地加入到约束网络。易于易于与领域相关的问题求解模型与领域相关的问题求解模型相衔接。各种数学规划技术，相衔接。各种数学规划技术，方程求解技术等方程求解技术等,都可以自然地嵌入约束系统。都可以自然地嵌入约束系统。第15页，本讲稿共68页2022/10/15史忠植 高级人工智能163.1 3.1 概概 述述 目前，约束推理的研究主要集中于两个方面：目前，约束推理的研究主要集中于两个方面：约束搜约束搜索索与与约束语言约束语言。约束搜索约束搜索主要研究有限域上的约束满足。对有限域主要研究有限域上的约束满足。对有限域而言，约束满足问题一般情况下是一个而言，约束满足问题一般情况下是一个NP问题。大体包问题。大体包括下列方法：括下列方法：回溯法；回溯法；约束传播；约束传播；智能回溯与真值维护；智能回溯与真值维护；可变次序例示；可变次序例示；局部修正法；局部修正法；第16页，本讲稿共68页2022/10/15史忠植 高级人工智能173.1 3.1 概概 述述约束推理研究的另一个主要方面是约束推理研究的另一个主要方面是约束语言约束语言。以下。以下是几个比较典型的约束语言：是几个比较典型的约束语言：CONSTRAINTS：面向电路描述的约束表示语言。面向电路描述的约束表示语言。Bertrand：Leler开发的一个高级约束语言。开发的一个高级约束语言。CHIP：约束逻辑程序设计语言。约束逻辑程序设计语言。约束层次与约束层次与HCLP：层次型层次型约束逻辑程序设计语言。约束逻辑程序设计语言。COPS：面向对象的程序设计语言的基本形式。面向对象的程序设计语言的基本形式。ILOG：使用建模语言来表示约束问题。使用建模语言来表示约束问题。第17页，本讲稿共68页2022/10/15史忠植 高级人工智能18CONSTRAINTSCONSTRAINTS约束语言约束语言 CONSTRAINTS是一个面向电路描述的约束表示语言。作是一个面向电路描述的约束表示语言。作为一个约束表示语言，它使用了符号处理技术来求解数学方程。为一个约束表示语言，它使用了符号处理技术来求解数学方程。在在CONSTRAITS中，物理部件的功能及器件的结构都用约中，物理部件的功能及器件的结构都用约束表示。束表示。这些约束一般是线性方程与不等式这些约束一般是线性方程与不等式,也包括条件表达式。也包括条件表达式。约束变量一般是表示物理量的实变量。也有一些取离散值的约束变量一般是表示物理量的实变量。也有一些取离散值的变量。如开关的状态、三极管的工作状态等。系统采用表达变量。如开关的状态、三极管的工作状态等。系统采用表达式推理与值推理。并实现相关制导的回溯。式推理与值推理。并实现相关制导的回溯。第18页，本讲稿共68页2022/10/15史忠植 高级人工智能19CONSTRAINTSCONSTRAINTS约束语言约束语言 CONSTRAINTSCONSTRAINTS的一个的一个优点：优点：在类型层次中表示约束，用约束来表示物在类型层次中表示约束，用约束来表示物理对象的功能与结构。理对象的功能与结构。缺点：缺点：是该语言缺乏类似于面向对象语言中的方法那是该语言缺乏类似于面向对象语言中的方法那样的成分，不能定义特定于某个类的概念。样的成分，不能定义特定于某个类的概念。同时，约束传播方法比较单一，既缺乏实域同时，约束传播方法比较单一，既缺乏实域上的区间传播机制，也缺乏有限域上的上的区间传播机制，也缺乏有限域上的 域传播域传播机制。机制。第19页，本讲稿共68页2022/10/15史忠植 高级人工智能20约束逻辑程序设计语言约束逻辑程序设计语言CHIPCHIP CHIP(ConstrainthandlinginProlog)就是这样较有影就是这样较有影响一个约束逻辑程序设计语言，其目的是简便、灵活而有响一个约束逻辑程序设计语言，其目的是简便、灵活而有效地解决一大类组合问题。它通过提供几种新的计算域而效地解决一大类组合问题。它通过提供几种新的计算域而增强逻辑程序设计的能力；有限域、布尔项及有理项，对增强逻辑程序设计的能力；有限域、布尔项及有理项，对于每个计算域，都提供有效的约束求解技术，即有限域上于每个计算域，都提供有效的约束求解技术，即有限域上的一致性技术，布尔域的布尔合一技术及有理数域上的单的一致性技术，布尔域的布尔合一技术及有理数域上的单纯型法。除此以外，纯型法。除此以外，CHIP还包含一个一般的延迟计算机制。还包含一个一般的延迟计算机制。CHIP主要应用于两个领域：运筹学与硬件设计。主要应用于两个领域：运筹学与硬件设计。CHIP缺乏类型机制，而这种机制对于表达领域概念是缺乏类型机制，而这种机制对于表达领域概念是极其重要的。极其重要的。第20页，本讲稿共68页2022/10/15史忠植 高级人工智能21面向对象约束语言面向对象约束语言COPSCOPS COPS系统利用面向对象技术，将说明性约系统利用面向对象技术，将说明性约束表达与类型层次结合起来。在形式上吸收了常束表达与类型层次结合起来。在形式上吸收了常规语言，主要是面向对象的程序设计语言的基本规语言，主要是面向对象的程序设计语言的基本形式。内部求解时采用约束推理机制，使说明性形式。内部求解时采用约束推理机制，使说明性约束表达式与类型层次相结合，实现知识的结构约束表达式与类型层次相结合，实现知识的结构化封装，充分发挥两者的优点，力图实现一个具化封装，充分发挥两者的优点，力图实现一个具有较强表达能力和较高求解效率的约束满足系统。有较强表达能力和较高求解效率的约束满足系统。第21页，本讲稿共68页2022/10/15史忠植 高级人工智能22面向对象约束语言面向对象约束语言COPSCOPS COPS的设计考虑了软件工程的应用要求，尽量将一的设计考虑了软件工程的应用要求，尽量将一个不确定问题确定化：它允许条件语句与循环语句，而不个不确定问题确定化：它允许条件语句与循环语句，而不是单纯以递归的形式来实现迭代计算；是单纯以递归的形式来实现迭代计算；通过类方法的重通过类方法的重栽实现同一约束的不同实现，提高了程序的执行效率。栽实现同一约束的不同实现，提高了程序的执行效率。COPS系统同时是一个渐增式的开放系统，用户能通过类型系统同时是一个渐增式的开放系统，用户能通过类型层次定义，实现新的数据类型和新的约束关系。约束语言层次定义，实现新的数据类型和新的约束关系。约束语言COPS具有许多人工智能程序设计语言的特点，如约束传播、面具有许多人工智能程序设计语言的特点，如约束传播、面向目标和数据驱动的问题求解、有限步的回溯、对象分层中的继向目标和数据驱动的问题求解、有限步的回溯、对象分层中的继承等。承等。第22页，本讲稿共68页2022/10/15史忠植 高级人工智能23常用的算法常用的算法 在实际应用中，算法的表现形式千变万化，但是算法的在实际应用中，算法的表现形式千变万化，但是算法的情况也和数据结构类似，许多算法的设计思想具有相似之处，情况也和数据结构类似，许多算法的设计思想具有相似之处，我们可以对它们分类进行学习和研究。我们可以对它们分类进行学习和研究。常用的算法大致有常用的算法大致有如下一些：如下一些：贪心法贪心法 分治法（如二分法检索）分治法（如二分法检索）回溯法回溯法 动态规划法动态规划法 局部搜索法局部搜索法 分支限界法分支限界法第23页，本讲稿共68页2022/10/15史忠植 高级人工智能24算法分析算法分析 评价一个程序优劣的重要依据是看这个程序的执行需要评价一个程序优劣的重要依据是看这个程序的执行需要占用多少机器资源。人们最关心的就是程序所用算法运行时占用多少机器资源。人们最关心的就是程序所用算法运行时所要花费的所要花费的时间代价时间代价和程序中使用的数据结构占有的和程序中使用的数据结构占有的空间代空间代价价。算法的空间代价算法的空间代价(或称或称空间复杂性空间复杂性)：当被解决问题的规：当被解决问题的规模模(以某种单位计算以某种单位计算)由由1增至增至n时，解该问题的算法所需占用时，解该问题的算法所需占用的空间也以某种单位由的空间也以某种单位由f(1)增至增至f(n)，这时我们称该算法的，这时我们称该算法的空空间代价是间代价是f(n)。算法的时间代价算法的时间代价(或称或称时间复杂性时间复杂性)：当问题规模以某种：当问题规模以某种单位由单位由1增至增至n时，对应算法所耗费的时间也以某种单位由时，对应算法所耗费的时间也以某种单位由g(1)增至增至g(n)，这时我们称算法的，这时我们称算法的时间代价是时间代价是g(n)。第24页，本讲稿共68页2022/10/15史忠植 高级人工智能25穷尽搜索方法穷尽搜索方法穷尽搜索方法 即产生所有可能的树，然后根据评价标准选择一棵最优的树。Exhaustive-Search-Top(P)wherePisaCSPoftheform(V,D,C)1.f:=thenullassignment2.returnExhaustive-Search(f,P)第25页，本讲稿共68页2022/10/15史忠植 高级人工智能26穷尽搜索方法穷尽搜索方法Exhaustive-Search(f,P)1.iffisatotalassignmentofthevariablesinP2.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页2022/10/15史忠植 高级人工智能27贪贪心心法法贪心法把构造可行解的工作分阶段来贪心法把构造可行解的工作分阶段来完成。在各个阶段，选择那些在某些意义完成。在各个阶段，选择那些在某些意义下是局部最优的方案，期望各阶段的局部下是局部最优的方案，期望各阶段的局部最优的选择带来整体最优。最优的选择带来整体最优。例：例：Dijkstra的最短路径算法、的最短路径算法、Kruskal的的求最小生成树算法、信号灯问题求最小生成树算法、信号灯问题第27页，本讲稿共68页2022/10/15史忠植 高级人工智能283.2回回溯溯法法有些问题需要彻底的搜索才能解决问题，然而，有些问题需要彻底的搜索才能解决问题，然而，彻底的搜索要以大量的运算时间为代价，对于这彻底的搜索要以大量的运算时间为代价，对于这种情况可以通过回溯法来去掉一些分支，从而大种情况可以通过回溯法来去掉一些分支，从而大大减少搜索的次数。大减少搜索的次数。l八皇后问题八皇后问题l迷宫问题迷宫问题l深度优先周游树或图深度优先周游树或图第28页，本讲稿共68页2022/10/15史忠植 高级人工智能293.2BacktrackingAlgorithmlBasedondepth-firstrecursivesearchlApproach1.Testswhethersolutionhasbeenfound2.Iffoundsolution,returnit3.Elseforeachchoicethatcanbemadea)Makethatchoiceb)Recurc)Ifrecursionreturnsasolution,returnit4.Ifnochoicesremain,returnfailurelSometimescalled“searchtree”第29页，本讲稿共68页2022/10/15史忠植 高级人工智能303.2Solutionto8-QueensPuzzle 八皇后八皇后八皇后八皇后问题，是一个古老而著名的问题，是回问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学溯算法的典型例题。该问题是十九世纪著名的数学家家高斯高斯1850年提出：在年提出：在88格的格的国际象棋国际象棋上摆放八个皇上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。同一行、同一列或同一斜线上，问有多少种摆法。高高斯认为有斯认为有76种种方案。方案。1854年在年在柏林柏林的象棋杂志上不同的的象棋杂志上不同的作者发表了作者发表了40种不同的解，后来有人用图论的方法解种不同的解，后来有人用图论的方法解出出92种种结果。计算机发明后，有多种方法可以解决此结果。计算机发明后，有多种方法可以解决此问题。问题。第30页，本讲稿共68页2022/10/15史忠植 高级人工智能314-QueensPuzzle第31页，本讲稿共68页2022/10/15史忠植 高级人工智能324-QueensTree第32页，本讲稿共68页2022/10/15史忠植 高级人工智能333.2回回溯溯法法Backtracking-Top(P)1f:=thenullassignment2returnBacktracking(f,P)第33页，本讲稿共68页2022/10/15史忠植 高级人工智能343.2回溯法回溯法Backtracking(f,P)1iffisatotalassignmentofthevariablesinP2answer:=f3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6foreachvaluewhileanswer=Umsat7f(v):=x8iffsatisfiestheconstraintsinP9answer:=Backtracking(f,P)10returnanswer第34页，本讲稿共68页2022/10/15史忠植 高级人工智能353.2回溯法回溯法尽尽管管回回溯溯法法好好于于生生成成测测试试法法，但但对对于于非非平平凡凡问问题题仍仍然然是是低低效效的的。其其原原因因在在于于搜搜索索空空间间中中不不同同路路径径的的搜搜索索重重复复相相同同的的失失败败子子路路径径。一一些些研研究究者者认认为为，造造成成这这种种反反复复的的原原因因是是所所谓谓的的局局部部不不一一致致性性。最最简简单单的的情情形形是是所所谓谓的的结结点点不不一一致致性性。对对一一个个变变量量vi的的一一个个一一元元约约束束。存存在在域域中中一一个个值值vi不不满满足足该该约约束束。这这样样，每每当当vi取取到到a时时就就会出现不一致性。会出现不一致性。另一种重复的情形是所谓的弧不一致性。另一种重复的情形是所谓的弧不一致性。第35页，本讲稿共68页2022/10/15史忠植 高级人工智能363.3 3.3 约束传播约束传播 如果对如果对vi的当前域中的所有值的当前域中的所有值x，存在，存在vj的当前域中的某值的当前域中的某值y使得使得 vi=x和和vj=y是是vi与与vj之间的约束所允许的，则弧之间的约束所允许的，则弧(vi,vj)是是弧弧一致的一致的。弧一致性的概念是弧一致性的概念是有向的有向的。即。即(vi,vj)是弧一致的并不自动地意味着是弧一致的并不自动地意味着(vj,vi)是一致是一致的。的。第36页，本讲稿共68页2022/10/15史忠植 高级人工智能373.3 3.3 约束传播约束传播CONSTRAINT PROPAGATIONCONSTRAINT PROPAGATION(red,green)(red,blue)(red,green,blue)弧一致性（弧一致性（Arcconsistency）第37页，本讲稿共68页2022/10/15史忠植 高级人工智能383.33.3 CONSTRAINT PROPAGATION CONSTRAINT PROPAGATIONAlloftheMackworthalgorithmsmakeuseofaReviseprocedure.LetDvbethecurrentdomainofv,LetDwbethecurrentdomainofw,LetPbetheconstraintpredicatethatholdsbetweenvandw,thenReviseupdatesDvasfollows:Dv:=xDv.yDwsuchthatP(x,y)第38页，本讲稿共68页2022/10/15史忠植 高级人工智能393.33.3 CONSTRAINT PROPAGATION CONSTRAINT PROPAGATIONMackworth1977AC-1AC-2AC-3第39页，本讲稿共68页2022/10/15史忠植 高级人工智能40约束传播修改算法约束传播修改算法procedureREVISE(Vi,Vj)1DELETEfalse;2foreachxDido3ifthereisnosuchyjDj4suchthat(x,yj)isconsistent,5then6deletexfromDi;7DELETEtrue;8endif9endfor10returnDELETE;11endREVISE第40页，本讲稿共68页2022/10/15史忠植 高级人工智能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页2022/10/15史忠植 高级人工智能42约束传播约束传播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-3第42页，本讲稿共68页2022/10/15史忠植 高级人工智能43回跳法回跳法BackjumpingBackjumping-Top(P)1f:=thenullassignment2:=Backjumping(f,P)3returnanswer第43页，本讲稿共68页2022/10/15史忠植 高级人工智能44BackjumpingBackjumpingBackjumping(f,P)1iffisatotalassignmentofthevariablesinP2answer:=3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6conflict-set:=7foreachvalue8f(v):=x9iffsatisfiestheconstraintsinP10:=Backjumping(f,P)第44页，本讲稿共68页2022/10/15史忠植 高级人工智能45BackjumpingBackjumping11else12new-conflicts:=thesetofvariablesinaviolatedconstraint13ifanswerUnsat14return15elseifvnew-conflicts16return17else18conflict-set:=conflict-set(new-conflictsv)19return第45页，本讲稿共68页2022/10/15史忠植 高级人工智能463.11 3.11 约束推理系统约束推理系统COPS1.1.约束与规则约束与规则 约束是谓词表达式：约束是谓词表达式：P(t1,.,tn)其其中中，t1,.,tn是是项项，典典型型情情况况时时包包含含变变量量；P是是谓谓词词符符号号，谓词可以是内部函数，如谓词可以是内部函数，如sumtimeseq(equal)neq(notequal)ge(greatthanorequalto)gt(greatthan)也可以由用户定义。也可以由用户定义。第46页，本讲稿共68页2022/10/15史忠植 高级人工智能473.11 3.11 约束推理系统约束推理系统COPS条件约束具有下面的形式：条件约束具有下面的形式：ifcondition1:constraint1;conditionn:constraintnwherecondition1,.,conditionnarebooleanexpressions.constraint1,constraintnareconstraintsorcontraintstable.第47页，本讲稿共68页2022/10/15史忠植 高级人工智能483.11 3.11 约束推理系统约束推理系统COPSRULERuleisusedtodefinenewfunction,method,predicate,oraddnewconstraintintoobject.RULEclass:predicate(variables)(booleanexpression)constraint1;constraintn;CASEbooleanexpression1:constraint1;booleanexpressionm:constraintm;第48页，本讲稿共68页2022/10/15史忠植 高级人工智能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页2022/10/15史忠植 高级人工智能503.11 3.11 约束推理系统约束推理系统COPS2.类定义类定义CLASSclass_name:superclass_name/attributesdefinitiondatetype:attribute_name;./ruledefinitionrule_name;./functiondefinitionfunction_name;./methoddefinitionmethod_name;.第50页，本讲稿共68页2022/10/15史忠植 高级人工智能513.11 3.11 约束推理系统约束推理系统COPSImplementationProgram written by COPS consists of classes and rules.COPS constraint programming language is a declarativelanguage,providing classes,methods which are exist inobjectorientedlanguage.ItissimilarwithC+.COPShasthefeatures:constraintobjectorientedlogicprogrammingproductionsystem第51页，本讲稿共68页2022/10/15史忠植 高级人工智能523.11 3.11 约束推理系统约束推理系统COPS算法算法3.9COPS的核心算法的核心算法main-COPS。proceduremain-COPS1.Callyacctoparsetheprogramandtogenerateinternalstructures.2.InitializatiionCreateCopsConstanttrueNode;Allocatememoriesforglobalvariables.3.Interprtetheprogramwiththeinternalstructures.4.ConstraintnetworksarebuiltupforUnsolvedconstraintsandvariables.5.whilesomeconstraintsintheconstraintnetworksaretriggered,intepretethetriggeredconstraints.3.COPS的约束推理的约束推理第52页，本讲稿共68页2022/10/15史忠植 高级人工智能533.11 3.11 约束推理系统约束推理系统COPS算法中的解释器如下：算法中的解释器如下：Interpreter:12switch(constrainttype)3caseConstant:4returnConstant:5caseglobalvariable:6interpreteglobalvariable:7caselocalvariableorargument:8interpretelocalvariableorargument:9caseobject-attributepair:10interpreteobject-attributepair:第53页，本讲稿共68页2022/10/15史忠植 高级人工智能543.11 3.11 约束推理系统约束推理系统COPS11casefunctioncall:12interpretefunctioncall:13casemethodcall:14interpretemethodcall:15caseCASEexpression:16interpreteCASEexpression:17.18default:20reporterror21第54页，本讲稿共68页2022/10/15史忠植 高级人工智能553.123.12 ILOG Solver约束程序约束程序约束程序约束程序是关于是关于约束的计算系统约束的计算系统，它的，它的 输入输入是是一组约束条件一组约束条件和和需要求解的若干问题需要求解的若干问题，输出输出问题的问题的解决方案解决方案。至于具体解决问题的至于具体解决问题的算法算法等都是约束程序设计语言的等都是约束程序设计语言的基本功能。基本功能。程序员所要面对的，就是程序员所要面对的，就是 如如何何把把问问题题描描述述为为一一组组约约束束构构成成的的模模型型，而而描描述述的的语言可以很接近自然语言。语言可以很接近自然语言。如如果果把把问问题题的的解解决决方方案案也也看看做做是是一一种种约约束束，那那么么问问题的求解题的求解就是就是求求得得一个或若干个约束一个或若干个约束。ILOG公司是法国优化、互动图像界面以及商业规则应用公司是法国优化、互动图像界面以及商业规则应用领域的软件组件供应商，成立于领域的软件组件供应商，成立于1987年。年。第55页，本讲稿共68页2022/10/15史忠植 高级人工智能563.123.12 ILOG SolverILOGSolver是是嵌嵌入入式式过过程程性性语语言言的的约约束束设设计计语语言言，将将面面向向对对象象程程序序设设计计和和约约束束逻逻辑辑程程序序设设计计结结合合起起来来，包包含含逻逻辑辑变变量量，通通过过增增量量式式约约束束满满足足和和回回溯溯实实现现问问题题求求解解。ILOGSolve