智能系统与智能软件研究所.ppt

《智能系统与智能软件研究所.ppt》由会员分享，可在线阅读，更多相关《智能系统与智能软件研究所.ppt（45页珍藏版）》请在三一办公上搜索。

1、第三章 搜索推理技术,3.6 产生式系统3.7 系统组织技术3.8 不确定性推理3.9 非单调推理3.10 小结,3.1 图搜索策略3.2 盲目搜索3.3 启发式搜索3.4 消解原理3.5 规则演绎系统,2,3.1 图搜索策略,图搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。图搜索过程图,3,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,n为目标节点吗？,

2、把n的后继节点放入OPEN表的末端，提供返回节点n的指针,修改指针方向,重排OPEN表,失败,成功,图3.1 图搜索过程框图,是,是,否,否,3.1 图搜索策略,4,3.2 盲目搜索,特点：不需重排OPEN表种类：宽度优先、深度优先、等代价搜索等。,5,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,是否有后继节点为目标节点？,扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针,失败,成功,图3.2 宽度优先算法框图,是,否,是,否,3.2 盲目搜索,6,例子八数码难题（8-puzzle problem）,（初始状态）,规定：将牌移

3、入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。,3.2 盲目搜索,7,1,图3.4 八数码难题的宽度优先搜索树,3.2 盲目搜索,8,深度优先搜索,定义,首先扩展最新产生的(即最深的)节点。,算法,防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（算法框图见教材）,3.2 盲目搜索,9,等代价搜索,定义,是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索

4、树中每条连接弧线上的有关代价,表示时间、距离等花费。,算法,若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。,3.2 盲目搜索,10,开始,把S放入OPEN表,OPEN表为空表？,把具有最小g(i)值的节点i从OPEN表移至CLOSED表,是否有后继节点为目标节点？,失败,成功,图3.2 等代价搜索算法框图,是,否,是,否,令g(s)=0,S是否目标节点？,是,成功,扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表,否,3.2 盲目搜索,11,3.3 启发式搜索,特点：重排OPEN表，选择最有希望的节点加以扩展种类：有序搜索、A*算法等,3.3.1 启发式搜索策略和估价函数

5、,盲目搜索可能带来组合爆炸启发式信息 用来加速搜索过程的有关问题领域的特征信息。,12,估价函数 为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)表示节点n的估价函数值 应用节点“希望”程度（估价函数值）重排OPEN表,有序搜索,实质,选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。,3.3 启发式搜索,13,开始,把S放入OPEN表，计算估价函数 f(s),OPEN表为空表？,选取OPEN表中f值最小的节点i放入CLOSED表,i为目标节点吗？,扩展i，得后继节点j，计算f(j)，提供返回节点i的指针，利用f

6、(j)对OPEN表重新排序，调整亲子关系及指针,失败,成功,图3.9 有序搜索算法框图,是,否,是,否,3.3 启发式搜索,算法,14,例子,八数码难题（8-puzzle problem）,八数码难题的有序搜索树见下图：,3.3 启发式搜索,15,5,7,1,4,5,6,3,2,图3.10 八数码难题的有序搜索树,3.3 启发式搜索,16,3.3.3 A*算法,估价函数的定义：对节点n定义f*(n)=g*(n)+h*(n),表示从S开始约束通过节点n的一条最佳路径的代价。希望估价函数f 定义为：f(n)=g(n)+h(n)g是g*的估计，h是h*的估计A*算法的定义：定义1 在GRAPHSEA

7、RCH过程中，如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。定义2 在A算法中，如果对所有的x存在h(x)h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。定义3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。,3.3 启发式搜索,17,3.4 消解原理,回顾：原子公式（atomic formulas）文字一个原子公式及其否定。子句由文字的析取组成的合适公式。消解对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。,18,例子:,将下列谓词演算公式化为一个子句集(x)P

8、(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y),开始：消去蕴涵符号 只应用和符号，以AB替换AB。,(1)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y),3.4 消解原理,19,(2)减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。(3)对变量标准化 对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元。,3.4 消解原理,(2)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y),(3)(x)P(x)(y)P(y)P(f(x,y)(w)Q(x,w)P(w),20,(4)消去存在量词 以Skolem函

9、数代替存在量词内的约束变量，然后消去存在量词化为前束形 把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形=前缀 母式 全称量词串 无量词公式,(4)(x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)）P(g(x)式中，w=g(x)为一Skolem函数。,(5)(x)(y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x),3.4 消解原理,21,把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。(7)消去全称量词 所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。,3.

10、4 消解原理,(6)(x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x),(7)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x),22,(8)消去连词符号 用A,B代替(AB)，消去符号。最后得到一个有限集，其中每个公式是文字的析取。(9)更换变量名称 可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。,3.4 消解原理,(8)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x),(9)P(x1)P(y)Pf(x1,y)P(x2)Qx2,g(x2)P(x3)Pg(x3),23,消解推理规则,消

11、解式的定义令L1，L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1和L2,如果L1和L2具有最一般合一，那么通过消解可以从这两个父辈子句推导出一个新子句()。这个新子句叫做消解式。,消解式求法,取各子句的析取，然后消去互补对。,3.4 消解原理,24,含有变量的消解式,3.4 消解原理,25,消解反演求解过程,消解反演 给出S，L否定L，得L；把L添加到S中去；把新产生的集合L，S化成子句集；应用消解原理，力图推导出一个表示矛盾的空子句,例子储蓄问题 前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱,3.4 消解原理,26,(1）

12、规定原子公式：S(x,y)表示“x储蓄y”M(x)表示“x是钱”I(x)表示“x是利息”E(x，y)表示“x获得y”,(2）用谓词公式表示前提和结论：前提：(x)(y)(S(x,y)M(y)(y)(I(y)E(x,y)结论：(x)I(x)(x)(y)(M(y)S(x,y),(3)化为子句形,证明：,3.4 消解原理,27,把前提化为子句形：1)S(x,y)M(y)I(f(x)2)S(x,y)M(y)E(x,f(x),把结论化为子句形：3)I(z)4)S(a,b)5)M(b),(4)消解反演求NIL,图3.12 储蓄问题反演树,3.4 消解原理,28,反演求解过程从反演树求取答案步骤把由目标公式

13、的否定产生的每个子句添加到目标公式否定之否定的子句中去。按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。用根部的子句作为一个回答语句。实质把一棵根部有NIL的反演树变换为根部带有回 答语句的一棵证明树。,3.4 消解原理,29,3.5 规则演绎系统,定义 基于规则的问题求解系统运用IfThen规则来建立，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统。在这种系统中，通常称每个if部分为前项，称每个then部分为后项。,30,3.5.1 规则正向演绎系统,定义

14、 正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。求解过程事实表达式的与或形变换 在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库。,3.5 规则演绎系统,31,事实表达式的与或图表示,Q(w,A)R(v)P(v)S(A,v),Q(w,A),R(v)P(v)S(A,v),R(v)P(v),S(A,v),R(v),P(v),图3.15 一个事实表达式的与或树表示,3.5 规则演绎系统,32,与或图的F规则变换 这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。我们把允许用作规则的公式类

15、型限制为下列形式：L W 式中：L是单文字；W为与或形的唯一公式。,3.5 规则演绎系统,33,3.5.2 规则逆向演绎系统,定义 逆向规则演绎系统是从then向if进行推理的，即从目标或动作向事实或状况条件进行推理的。求解过程目标表达式的与或形式与或图的B规则变换作为终止条件的事实节点的一致解图,3.5 规则演绎系统,34,正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成。这些与或图结构分别用正向系统的F规则和逆向系统的B规则来修正。,3.5.3 规则双向演绎系统,3.5 规则演绎系统,35,3.6 产生式系统,定义：用来描述若

16、干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念。实质：在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为。由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统。,36,3.6.1 产生式系统的组成,控制策略,图3.22 产生式系统的主要组成,总数据库,产生式规则,3.6 产生式系统,37,选择规则到执行操作的步骤 1 匹配 把当前数据库与规则的条件部分相匹配。2 冲突 当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。3

17、 操作 操作就是执行规则的操作部分。,3.6 产生式系统,38,3.6.2 产生式系统的推理,正向推理：从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。逆向推理：从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。双向推理：双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。,3.6 产生式系统,39,3.7 系统组织技术,3.7.1 议程表,系统组织技术首先将一个大系统或复杂系统中的知识划分为一组相对独立的模块，然后考虑各子模块间在求解

18、时的合作问题。,议程表是一个系统能够执行的任务表列。与每个任务有关的有两件事，即提出该任务的理由和表示对该任务是有用的证据总权的评价。,40,3.7.2 黑板法,黑板法由一组称为知识资源(KS)的独立模块和一块黑板组成求解系统。知识资源含有系统中专门领域的知识，而黑板则是一切KS可以访问的公用数据结构。,3.7 系统组织技术,3.7.3-极小搜索法,提供了一种选择最有希望假设的技术。,41,3.8 不确定性推理,以模糊集理论为基础的方法以概率为基础的方法,关于证据的不确定性,不确定性推理是研究复杂系统不完全性和不确定性的有力工具。有两种不确定性，即关于证据的不确定性和关于结论的不确定性。,42

19、,关于结论的不确定性,关于结论的不确定性也叫做规则的不确定性，它表示当规则的条件被完全满足时，产生某种结论的不确定程度。,多个规则支持同一事实时的不确定性,基于模糊集理论的方法基于概率论的方法,3.8 不确定性推理,43,3.9 非单调推理,定义 非单调推理用来处理那些不适合用谓词逻辑表示的知识。它能够较好地处理不完全信息、不断变化的情况以及求解复杂问题过程中生成的假设，具有较为有效的求解效率。,44,3.9.1 缺省推理,定义1：如果X不知道，那么得结论Y。定义2：如果X不能被证明，那么得结论Y。定义3：如果X不能在某个给定的时间内被证明，那么得结论Y。,3.9 非单调推理,3.9.2 非单调推理系统正确性维持系统用以保持其它程序所产生的命题 之间的相容性。一旦发现某个不相容，它就调出 自己的推理机制，面向从属关系的回溯，并通过 修改最小的信念集来消除不相容。,45,3.10 小结,经典搜索推理技术图搜索技术消解反演 高级搜索推理技术规则演绎系统产生式系统系统组织技术不确定性推理非单调推理,