人工智能第三章课件.ppt

1、Artificial IntelligenceArtificial Intelligence2023-6-1浙江科技学院浙江科技学院 信息学院信息学院 程志刚程志刚 人工智能人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2第三章第三章 搜索推理技术搜索推理技术3.1 图搜索策略 3.6 产生式系统3.2 盲目搜索3.7 系统组织技术3.3 启发式搜索3.8 不确定性推理3.4 消解原理3.9 非单调推理3.5 规则演绎系统 3.10 小结人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2NOTE 教学内容：教学内容：本章在上一章知识表示的基础上研究问题求解的方

2、法，是人工智能研究的又一核心问题。内容包括早期搜索推理技术，如图搜索策略和消解原理；以及高级搜索推理技术，如规则演绎系统、产生式系统、系统组织技术、不确定性推理和非单调推理。教学重点教学重点：图搜索策略、消解原理、规则演绎系统、产生式系统。教学难点教学难点：启发式搜索、规则双向演绎系统等。教学要求教学要求：重点掌握一般图搜索策略和消解原理，掌握各种搜索方法和产生式系统原理，了解规则演绎系统的基本原理，对系统组织技术、不确定性推理和非单调推理等高级推理技术作一般性了解。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.1 图搜索策略图搜索策略 图搜索控制策略 一种在图中寻找路

3、径的方法。图中每个节点对应一个状态，每条连线代表一个操作符。这些节点与连线（状态与操作符）分别由产生式系统的数据库和规则来标记。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。重要概念 OPEN表与CLOSE表 搜索图与搜索树人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 图搜索过程图GRAPHSEARCH人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.2 盲目搜索盲目搜索 特点：不需重排OPEN表 种类 宽度优先 深度优先 等代价搜索人工智能导论 浙江科技学院

4、信息学院 计算机系 程志刚2006s23.2.1 宽度优先搜索宽度优先搜索 定义 以接近起始节点的程度逐层扩展节点的搜索方法 特点 一种高代价搜索，但如有解存在，则必能找到。算法人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 宽度优先搜索框图人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 例子：八数码难题(8 puzzle problem)2831476512384765初始状态目标状态规则：规则：将数字移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不许移回先辈节点。要扩展26个节点，共生成46个节点后才能求得解人工智能导论 浙江科技学院

5、信息学院 计算机系 程志刚2006s2人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.2.2 深度优先搜索深度优先搜索 定义 首先扩展最新生成的（即最深的）节点，深度相等的节点可以任意排列。特点 搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。算法 为了防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度-深度界限。与宽度优先算法最根本的不同在于：扩展的后继节点放在OPEN表的前端人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.2.3 等代价搜索等代价搜索 定义 是宽度

6、优先搜索的一种推广，不是沿着等长度路径的断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树种每条连接弧线上的有关代价，表示时间、距离 等花费。算法 若所有连接弧具有相同的代价，则简化为宽度优先搜索算法。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 等代价搜索框图人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.3 启发式搜索启发式搜索 特点 重排OPEN表，选择最有希望的节点进行扩展。种类 有序搜索 A*算法人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.3.1 启发式搜索策略和估价函数启发式搜索策略和估价函数 盲目搜索可能带来

7、组合爆炸 定义：搜索过程中，往往存在许多与具体问题领域相关的特征信息，可以用来加速搜索过程，这种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。启发式搜索策略 应用某些准则，利用启发信息，重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有“希望”的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalution function)。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 估价函数 为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最

8、佳路径上。f(n)表示节点n的估价函数值 建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。应用节点“希望”程度，（估价函数值）重排OPEN表。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.3.2 有序搜索有序搜索 实质 选择OPEN表中具有最小f值的节点作为下一个要扩展的节点。有序搜索算法框图人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 例子：八数码难题(8 puzzle problem)2831647512384765初始

9、状态目标状态有序搜索树如下f(n)=d(n)+W(n)人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2八数码难题的有序搜索树02人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.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：在GRAGHSEARCH过程中，如果第8步中重排OPEN表是根据，f(n)=g(n)+h(n)进行的，则称该过程为A算法。定义2：在A

10、算法中，如果对于所有的x都有h(x)h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。定义3：采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.4 消解原理消解原理 基本概念 原子公式（atomic formulas）文字 一个原子公式及其否定 子句-由文字的析取组成的合式公式 谓词公式、推理规则、置换合一等 消解 对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.4.1 子

11、句集的求取子句集的求取标准9步（P68）例子：例子：将下列为此演算公式化为一个子句集 (x)P(x)=(y)P(y)=P(f(x,y)(y)Q(x,y)=P(y)开始：人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2第一步：消去蕴含符号。只应用和符号，以AB替换AB。第二步：减少否定符号的辖域。每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 第三步：对变量标准化。对哑元(虚构变量)改名以保证每个量词有其自己唯一的哑元。第四步：消去存在量词。用Skolem函数代替存在量词内的约束变量，即可消去存在量

12、词 人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 第五步：化为前束形。把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。第六步：把母式化为合取范式。任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 第七步：消去全称量词。消去明显出现的全称量词。第八步：消去连词符号。用A，B代替(AB)，消去符号，最后得到一个有限集，其中每个公式是文字的析取。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 第九步：更换变量名称。可以更换变量符号的

13、名称，使一个变量符号不出现在一个以上的子句中。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.4.2 消解推理规则消解推理规则 消解式的定义 令L1,L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1和L2,如果L1和L2具有最一般合一者，那么通过消解可以从这两个父辈子句推导出一个新子句()。这个新子句叫做消解式。消解式的求法：取各子句的析取，然后消去互补对。假言推理合并 重言式空子句（矛盾）链式（三段论）人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.4.3 含有变量的消解式含有变量的消解式 含有变量的子句之消

14、解式 为了对含有变量的子句使用消解规则，必须找到一个置换，作用于父辈子句使其含有互补文字。例子（P72）消解推理的常用规则人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.4.4 消解反演求解过程消解反演求解过程 1、消解反演给出一个公式集S和目标公式L(1)否定L，得L；(2)把L添加到S中去；(3)把新产生的集合L，S化成子句集；(4)应用消解原理，力图推导出一个表示矛盾的空子句NIL。例子：存储问题 前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2证明 1、规定原子公式 S(x,

15、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)人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 3、化为子句形 前提化为子句形(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)人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 4、消解反演求NIL子句(1)子句(3)子

16、句(4)子句(6)子句(7)子句(5)S(x,y)M(y)M(b)NILf(x)/za/x,b/y储蓄问题反演树储蓄问题反演树人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 反演求解过程 从反演树求取答案步骤 把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。用根部的子句作为一个回答语句。实质 把一棵根部有NIL的 反演树变换为在根部带有可用作答案的某个语句的一颗证明树。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.5 规则演绎系统规则演绎系统 定义 基于规则的问题求解系统

17、运用IfThen规则来建立。每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存。在许多基于规则系统中，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统(rule based deduction system)。在这种系统中，通常称每个if部分为前项(antecedent)，称每个then部分为后项(consequent)。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.5.1 规则正向演绎系统规则正向演绎系统 定义 正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到

18、then的方向进行推理的。求解过程 事实表达式的与或形变换：把事实表示为非蕴涵形式的与或形，作为系统的总数据库。事实表达式的与或图表示（k线分开析取关系）人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 与或图的F规则变换：这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。把允许用作规则的公式类型限制为下列形式：LW 式中：L是单文字；W为与或形的唯一公式。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.5.2 规则逆向演绎系统规则逆向演绎系统 定义 从then到if的推理过

19、程。即从目标到事实或条件进行的推理过程。求解过程 目标表达式的与或形式（k线分开合取关系）与或图的B规则变换 作为终止条件的事实节点的一致解图人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.5.3 规则双向演绎系统规则双向演绎系统 1.正向演绎系统和逆向演绎系统的特点和局限性 正向演绎系统能够处理任意形式的if表达式，但被限制在then表达式为由文字析取组成的一些表达式。逆向演绎系统能够处理任意形式的then表达式，但被限制在if表达式为文字合取组成的一些表达式。双向(正向和逆向)组合演绎系统具有正向和逆向两系统的优点，克服各自的缺点。2.双向(正向和逆向)组合演绎系统的

20、构成 正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成，并分别用F规则和B规则来修正。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 3.终止条件 组合演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。当用F规则和B规则对图进行扩展之后，匹配就可以出现在任何文字节点上。在完成两个图间的所有可能匹配之后，目标图中根节点上的表达式是否已经根据事实图中根节点上的表达式和规则得到证明的问题仍然需要判定。只有当求得这样的一个证明时，证明过程才算成功地终止。若能够断定在给定方法限度内找不到证明时过程

21、则以失败告终。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.6 产生式系统产生式系统 定义定义 在基于规则系统中，每个if可能与某断言(assertion)集中的一个或多个断言匹配，then部分用于规定放入工作内存的新断言。当then部分用于规定动作时，称这种基于规则的系统为反应式系统(reaction system)或产生式系统(production system)。实质实质 在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为，由于这类系统的知识库主要用于存储规则，因此又称此类系统为基于规则的系统。人

22、工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.6.1 产生式系统的组成产生式系统的组成总数据库产生式规则控制策略产生式系统的主要组成产生式系统的主要组成人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2选择规则到执行操作的步骤选择规则到执行操作的步骤 匹配 把当前的数据库与规则的条件部分相匹配 冲突 当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。操作 执行规则的操作部分，经过操作以后，当前数据库将被修改。然后，其他的规则有可能被使用。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.6.2

23、 产生式系统的推理产生式系统的推理 正向推理 从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。逆向推理 从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。双向推理 双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.7 系统组织技术系统组织技术 系统组织技术首先将一个大系统或复杂系统中的知识划分为一组相对独立的模块，然后再考虑各子模块间在求解时的合作问题人工智能导论

24、浙江科技学院 信息学院 计算机系 程志刚2006s23.7.1 议程表议程表 1.1.定义定义 议程表(agenda)是一个系统能够执行的任务表列。与每个任务有关的有两件事，即提出该任务的理由和表示对该任务是有用的证据总权的评价。2.2.模块间的合作模块间的合作 允许几个独立模块进行通讯。其通讯方法是每个模块可将支持(或反对)某 个具体任务的证据，加到一个证明选择该任务是正确的表中。这样就使系统能够选出从各方面都有充分证据的任务。虽然各模块共同使用关于为什么要执行各项任务 的证据，但一个模块并不需要了解其它模块如何工作，以及它们所包含的知识。这样，议程表方法便具有大系统中模块化的一切优点，而无

25、相互隔离的缺点。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.7.2 黑板法黑板法 1.1.定义定义 黑板法(the Blackboard Approach)首先是在HEARSAY-语音理解系统中发展起来的。它的思想比较简单。整个系统由一组称为知识资源(KS)的独立模块和一块黑板组成。这里，知识资源含有系统中专门领域的知识，而黑板则是一切KS可以访问的公用数据结构。2.2.模块间的合作模块间的合作 当一个KS被激发时，它检查当时黑板上的内容，并应用其知识产生一个新的假设写到黑板上，直到完成任务为止。当时间表没有发现未解决的活动记录时，系统便停止执行。人工智能导论 浙江科

26、技学院 信息学院 计算机系 程志刚2006s23.7.3 -极小搜索法极小搜索法 1 1、定义、定义值表示一假设的级别与参加竞争的最佳假设的级别之差，提供了一种选择最有希望假设的技术。2 2、工作过程、工作过程 一次接受一串输入，顺序地处理，使其形成一个关于输入的统一而相容的解释。-极小法是这样来解决这类问题的：在适当的时刻，触发某KS，然后为它生成所有它认为是可能的假设，并赋给某个假设一种级别。由这些级别计算出的值，表示一假设的级别与参加竞争的最佳假设的级别之差。而在该假设最后导致不相容时，再考虑参加竞争的另一假设。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.8 不

27、确定性推理不确定性推理 不确定性推理是研究复杂系统不完全性和不确定性的有力工具。有两种不确定性，即关于证据的不确定性和关于结论的不确定性。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.8.1 关于证据的不确定性关于证据的不确定性 以模糊集理论为基础的方法 把所有条件中最小的可信度作为总条件的可信度。以概率为基础的方法 把所有条件的可信度的乘积作为总的可信度。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.8.2 关于结论的不确定性关于结论的不确定性 不确定性的表示不确定性的表示关于结论的不确定性也叫做规则的不确定性，它表示当规则的条件被完全满足时，

28、产生某种结论的不确定程度。它也是以赋予规则在0和1之间的系数的方法来表示的。不确定性的处理不确定性的处理如果规则的条件部分不完全确定，求得结论的可信度的方法有以下两种：(1)取结论可信度为条件可信度与上述系数的乘积。(2)按照某种概率论的解释，我们假设规则的条件部分的可信度Cin和其结论部分的可信度Cout存在某种关系，这种关系可用来代表规则的不确定性。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.8.3 多个规则支持同一事实时的多个规则支持同一事实时的不确定性不确定性 1.基于模糊集理论的方法基于模糊集理论的方法 取支持这个事实的各规则的可信度的最大值作为事实的可信度

29、。2.基于概率论的方法基于概率论的方法 首先把各个证据的可信度转换成可信性比例r。可信性比例r和可信度c之间的关系可表示为把各证据的可信性比例简单地相乘就可以求得这些证据所支持的事实的可信性比例。然后，再利用上述公式转换回相应的可信度。这样就求得这个事实的可信度。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.9 非单调推理非单调推理 缘由：缘由：基于谓词逻辑的系统，为真的命题数目随时间严格增加，新命题的加入不会导致已知为真或已被证明的命题变成无效。定义定义 非单调推理用来处理那些不适合用谓词逻辑表示的知识 它能够较好得处理不完全信息、不断变化的情况以及求解复杂问题过程中

30、生成的假设，具有较为有效的求解效率。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.9.1 缺省推理缺省推理 定义定义 当缺乏信息时，只要不出现相反的证据，就可以作一些有益的猜想。构造这种猜想称为缺省推理(default reasoning)。缺省推理的定义缺省推理的定义1：如果X不知道，那么得结论Y。缺省推理的定义缺省推理的定义2：如果X不能被证明，那么得结论Y。缺省推理的定义缺省推理的定义3：如果X不能在某个给定的时间内被证明，那么得结论Y。例子例子 一个安排会议程序：程序必须求解一个约束满足问题，即找出每个参加者都有空闲的开会日期与时刻，并有可供开会的房间。人工智能

31、导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.9.2 正确性维持系统（正确性维持系统（TMS）正确性维持系统正确性维持系统(Truth Maintenane System,TMS)这是一个已经实现的非单调推理系统。它用以协助其它推理程序维持系统的正确性，所以它的作用不是生成新的推理，而是在其它程序所产生的命题之间保持相在其它程序所产生的命题之间保持相容性容性。一旦发现某个不相容，它就调出自己的推理机制，面向从属关系的回溯，并通过修改最小的信念集来消除不相容。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 工作原理工作原理 在TMS中，每一命题或规则均称为节点

32、，且对任一节点以下两种状态必居其一：IN 相信为真 OUT 不相信为真，或无理由相信为真，或当前没有可相信的理由。IN节点是指那些至少有一个在当前说来是有效证实的节点。OUT结点则指那些当前无任何有效证实的节点。在系统中，有两种方式可用来证实一个节点的有效性可依赖于其它节点的有效性：(1)支持表(SL(IN-节点)(OUT-节点)(2)条件证明(CP(结论)(IN-假设)(OUT-假设)人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.10 小结小结 经典搜索推理技术经典搜索推理技术 图搜索技术 消解反演 高级推理搜索技术高级推理搜索技术 规则演绎系统 产生式系统 系统组织技术 不确定性推理 非单调推理