文档介绍：Artificial Intelligence 2017-1-2 浙江科技学院信息学院程志刚人工智能《人工智能导论》浙江科技学院信息学院计算机系程志刚 2006s2 第三章搜索推理技术 小结 规则演绎系统 非单调推理 消解原理 不确定性推理 启发式搜索 系统组织技术 盲目搜索 产生式系统 图搜索策略《人工智能导论》浙江科技学院信息学院计算机系程志刚 2006s2 NOTE ?教学内容: 本章在上一章知识表示的基础上研究问题求解的方法,是人工智能研究的又一核心问题。内容包括早期搜索推理技术,如图搜索策略和消解原理;以及高级搜索推理技术,如规则演绎系统、产生式系统、系统组织技术、不确定性推理和非单调推理。?教学重点:图搜索策略、消解原理、规则演绎系统、产生式系统。?教学难点:启发式搜索、规则双向演绎系统等。?教学要求:重点掌握一般图搜索策略和消解原理,掌握各种搜索方法和产生式系统原理,了解规则演绎系统的基本原理,对系统组织技术、不确定性推理和非单调推理等高级推理技术作一般性了解。《人工智能导论》浙江科技学院信息学院计算机系程志刚 2006s2 图搜索策略?图搜索控制策略?一种在图中寻找路径的方法。?图中每个节点对应一个状态,每条连线代表一个操作符。这些节点与连线(状态与操作符)分别由产生式系统的数据库和规则来标记。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。?重要概念? OPEN 表与 CLOSE 表?搜索图与搜索树《人工智能导论》浙江科技学院信息学院计算机系程志刚 2006s2 ?图搜索过程图 GRAPHSEARCH 《人工智能导论》浙江科技学院信息学院计算机系程志刚 2006s2 盲目搜索?特点: ?不需重排 OPEN 表?种类?宽度优先?深度优先?等代价搜索《人工智能导论》浙江科技学院信息学院计算机系程志刚 2006s2 宽度优先搜索?定义?以接近起始节点的程度逐层扩展节点的搜索方法?特点?一种高代价搜索,但如有解存在,则必能找到。?算法《人工智能导论》浙江科技学院信息学院计算机系程志刚 2006s2 ?宽度优先搜索框图《人工智能导论》浙江科技学院信息学院计算机系程志刚 2006s2 ?例子:八数码难题(8 puzzle problem) 567 41 382567 48 321 初始状态目标状态规则: 将数字移入空格的顺序为:从空格左边开始顺时针旋转。不许斜向移动,也不许移回先辈节点。要扩展 26 个节点,共生成 46 个节点后才能求得解《人工智能导论》浙江科技学院信息学院计算机系程志刚 2006s2