人工智能第三章

《人工智能第三章》由会员分享，可在线阅读，更多相关《人工智能第三章（58页珍藏版）》请在金锄头文库上搜索。

1、Artificial Intelligence人工智能*浙江科技学院 信息学院 程志刚 *人工智能导论 浙江科技学院 信息学院 计算机系 程志刚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表 种类 宽度优先 深度优先 等代价搜索*人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.2.1 宽度优先搜索 定义 以接近起始节点的程度逐层扩展节点的

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

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

6、每条连接弧线上的有关代价，表示时间 、距离 等花费。 算法 若所有连接弧具有相同的代价，则简化为 宽度优先搜索算法。*人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 等代价搜索框图*人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.3 启发式搜索 特点 重排OPEN表，选择最有希望的节点进行 扩展。 种类 有序搜索 A*算法*人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.3.1 启发式搜索策略和估价函数 盲目搜索可能带来组合爆炸 定义： 搜索过程中，往往存在许多与具体问题领域相关 的特征信息，可以用来加速搜索过程，这种信息叫做启

7、发信息。利用启发信息的搜索方法叫做启发式搜索方法 。 启发式搜索策略 应用某些准则，利用启发信息，重新排列每一步 OPEN表中所有节点的顺序。然后，搜索就可能沿着某 个被认为是最有“希望”的边缘区段向外扩展。 应用这种排序过程，需要某些估算节点“希望”的量 度，这种量度叫做估价函数(evalution function)。*人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 估价函数 为获得某些节点“希望”的启发信息，提供一个评定 侯选扩展节点的方法，以便确定哪个节点最有可能在通 向目标的最佳路径上 。f(n)表示节点n的估价函数值 建立估价函数的一般方法： 试图确定一个处在最

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

9、能导论 浙江科技学院 信息学院 计算机系 程志刚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算法中，如果对于所有的x都有 h(x)h*(x

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

11、例子：将下列为此演算公式化为一个子句集(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)子句(4)子句(6)子句(7)子句(5)S(x,y)M(y)M(b)NILf(x)/za/x,b/y储蓄问题反演树*人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2 反演求解过程 从反演树求取答案步骤 把由目标公式的否定产生的每个子句添加到目 标公式否定之否定的子句中去。 按照反演树，执行和以前相