人工智能第三章节

《人工智能第三章节》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、人工智能9/4/2021浙江科技学院信息学院程志刚第三章搜索推理技术3.1图搜索策略3.6产生式系统3.2盲目搜索3.7系统组织技术3.3启发式搜索3.8不确定性推理3.4消解原理3.9非单调推理3.5规则演绎系统3.10小结NOTE教学内容：本章在上一章知识表示的基础上研究问题求解的方法，是人工智能研究的又一核心问题。内容包括早期搜索推理技术，如图搜索策略和消解原理；以及高级搜索推理技术，如规则演绎系统、产生式系统、系统组织技术、不确定性推理和非单调推理。教学重点：图搜索策略、消解原理、规则演绎系统、产生式系统。教学难点：启发式搜索、规则双向演绎系统等。教学要求：重

2、点掌握一般图搜索策略和消解原理，掌握各种搜索方法和产生式系统原理，了解规则演绎系统的基本原理，对系统组织技术、不确定性推理和非单调推理等高级推理技术作一般性了解。3.1图搜索策略图搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线代表一个操作符。这些节点与连线（状态与操作符）分别由产生式系统的数据库和规则来标记。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。重要概念OPEN表与CLOSE表搜索图与搜索树图搜索过程图GRAPHSEARCH3.2盲目搜索特点：

3、不需重排OPEN表种类宽度优先深度优先等代价搜索3.2.1宽度优先搜索定义以接近起始节点的程度逐层扩展节点的搜索方法特点一种高代价搜索，但如有解存在，则必能找到。算法宽度优先搜索框图例子：八数码难题(8puzzleproblem)2831476512384765初始状态目标状态规则：将数字移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不许移回先辈节点。要扩展26个节点，共生成46个节点后才能求得解3.2.2深度优先搜索定义首先扩展最新生成的（即最深的）节点，深度相等的节点可以任意排列。特点搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到

4、达一个没有后裔的状态时，它才考虑另一条替代的路径。算法为了防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度--深度界限。与宽度优先算法最根本的不同在于：扩展的后继节点放在OPEN表的前端3.2.3等代价搜索定义是宽度优先搜索的一种推广，不是沿着等长度路径的断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树种每条连接弧线上的有关代价，表示时间、距离等花费。算法若所有连接弧具有相同的代价，则简化为宽度优先搜索算法。等代价搜索框图3.3启发式搜索特点重排OPEN表，选择最有希望的节点进行扩展。种类有序搜索A*算法3.3.1启发式搜索策略和估价函数盲目搜索

5、可能带来组合爆炸定义：搜索过程中，往往存在许多与具体问题领域相关的特征信息，可以用来加速搜索过程，这种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。启发式搜索策略应用某些准则，利用启发信息，重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有“希望”的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalutionfunction)。估价函数为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)——表示节点n的估价函数

6、值建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。应用节点“希望”程度，（估价函数值）重排OPEN表。3.3.2有序搜索实质选择OPEN表中具有最小f值的节点作为下一个要扩展的节点。有序搜索算法框图例子：八数码难题(8puzzleproblem)2831647512384765初始状态目标状态有序搜索树如下f(n)=d(n)+W(n)八数码难题的有序搜索树023.3.3A*算法估价函数的定义对节点n定义f*(n)=g*(n)+h*(n)，表示从

7、节点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),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。定义3：采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。3.4消解原理基本概念原子公式（atomicfo