人工智能课程回顾.ppt

1、第一章 绪论,AI的概念 AI的历史 AI的应用 AI 研究领域 AI 研究方法,第二章 产生式系统,产生系统基本结构 综合数据库、产生式规则、控制系统 产生系统基本过程 匹配、选择、执行,第二章 产生式系统,问题的表示 综合数据库和规则集的描述 状态空间法(S, O, G)、问题归约法(S0, O, P) 控制策略 不可撤回方式 试探方式 回溯方式 图搜索方式,第三章 产生式系统的搜索策略,“状态空间”的图描述 图的节点表示问题的状态 图的弧表示求解问题的步骤（应用的规则） 初始状态对应问题的已知信息，是图的根节点 控制策略 回溯策略 图搜索策略 盲目的图搜索过程 启发式图搜索过程,第三章

2、产生式系统的搜索策略,盲目的图搜索过程 宽度优先搜索 深度优先搜索 启发式图搜索过程 启发式图搜索算法A 最佳图搜索算法A*,第三章 产生式系统的搜索策略,启发式图搜索算法A 对结点n定义评价函数f(n)=g(n)+h(n) g0，f=h爬山法 h0，f=g分支限界法 f=g=d，宽度优先搜索 分支限界法中只考虑f值最小的一条局部路径，动态规划法,第三章 产生式系统的搜索策略,最佳图搜索算法A* 评价函数f(n)=g(n)+h(n)满足条件h(n) h*(n)的启发式图搜索算法A A*算法的改进 针对节点重复扩展问题，改进方法： 定义单调的启发函数h 待扩展节点的选择：已扩展节点的最大f值记为

3、fm，扩展f值小于fm的节点，且选择满足条件的节点中g值最小者进行扩展。,第四章 与或图搜索,“问题归约”对应的与或图 原始问题描述对应根节点 本原问题对应叶节点 图中的弧是1-连接符或k-连接符 与或图搜索 寻找解图 AO*算法,第四章 与或图搜索,博弈树搜索 二人完备博弈 目的是给出最好走步 博弈树的极大极小搜索法 -搜索过程 极大值层的下界值记为，极小值层的上界值记为 -剪枝,在一个分支上进行-剪枝的规则描述如下： 1 剪枝：若任一极小值层节点的值小于或等于它任一先辈极大值层节点的值，即（先辈层）（后继层），则可以终止该极小值层中这个MIN节点以下的搜索，并设置这个MIN节点的最终的倒推

4、值为。(极小值层节点的剪枝) 2 剪枝：若任一极大值层节点的值大于或等于它任一先辈极小值层节点的值，即（后继层）（先辈层），则可以终止该极大值层中这个MAX节点以下的搜索过程，并设置这个MAX节点的最终倒推值为。 (极大值层节点的剪枝),第五章高级搜索,局部搜索算法 遗传算法,第五章高级搜索,局部搜索算法 改进1：针对陷入局部最优，依一定概率选择邻域内的点； 改进2：针对等步长跳过全局最优，改固定步长搜索为变步长搜索； 改进：针对初始点可能距离局部最优点近，随机选择多个初始点。,第五章高级搜索,遗传算法 问题解的编码 定义适应函数 交配规则 变异规则,第六章 基于逻辑的问题求解方法,一阶谓词逻

5、辑 谓词逻辑演算公式 谓词演算的基本等价式及推理规则 谓词公式的规范化 前束范式 SKOLEM范式 谓词公式化为子句集,第六章 基于逻辑的问题求解方法,谓词逻辑公式化为子句集的步骤： 1.消去多余的前束（量词），即在母式中无相应变量的量词。 利用蕴涵等价式消去蕴涵符号（）； 利用摩根律内移否定词的辖区范围，使其仅作用于原子公式。,4.变量标准化。将各约束变量换成不同的名字以免混淆。在一量词的辖区内，受该量词约束的变量名可任意设定（只要没出现过），该过程不影响合式公式的真值。 5.利用量词辖区变换律把量词的辖区范围扩充至整个WFF，得到一个前束范式。即把所有的量词都集中在公式的左边，移动时不要改

6、变其相对顺序。 6. 消去存在量词，把所得的前束范式化为S范式。,7.把母式化成合取范式。反复使用结合律和分配律，将母式表达成合取范式的标准式（即用连接的公式)。 8. 略去全称量词。由于母式的变量均受全称量词的约束，可省略掉全称量词（不显式地受全称量词量化）。 9用子句集表示母式。把母式中每一个合取元称为一个子句，省去合取连接词，这样就可把母式写成集合的形式表示，每个元素就是一个子句。 10子句变量标准化。将子句集合中的变量作分离标准化，即对某些变量重新命名，使任意两个子句不会有相同的变量出现。,第六章 基于逻辑的问题求解方法,归结法 命题逻辑的归结 谓词逻辑的归结 置换 合一 求最一般合一

7、mgu,第六章 基于逻辑的问题求解方法,归结反演产生式系统 基本算法（归结反演树） 搜索策略 宽度优先策略 支持集策略 单元子句优先策略 线性输入策略 祖先过滤形策略,第六章 基于逻辑的问题求解方法,基于归结法的问题解答系统 提取问答的方法 归结反演树：证明目标公式是前提公式集的逻辑推论； 修改证明树：归结反演树中目标公式的否定式用“目标公式的否定与目标公式的析取”替代，找出目标公式中变量的例。,第七章 基本推理技术,基于规则的演绎推理 正向演绎推理 逆向演绎推理 双向演绎推理,表达式化为标准与或形,表达式化为与或图,演绎推理过程,第七章 基本推理技术,双向演绎推理 分别从正反两个方向进行推理

8、，两个与或图分别扩展； 当正反两个方向的与或图对应的叶节点都可合一时，推理结束。,第七章 基本推理技术,不确定性推理 概率方法 条件概率、全概率公式、Bayes公式 概率推理,复习要点及思考题,第二章 产生式系统: 通过八数码游戏，了解产生式系统的问题描述(综合数据库、产生式规则、控制系统)。 思考习题： N=3时梵塔问题的产生式系统的描述 (参考P55页1.1题),第三章 产生式系统的搜索策略,在深刻理解图搜索算法的基础上，通过八数码问题、传教士和野人问题掌握启发式图搜索算法A和A*算法。 思考习题： 1.P55页，1.3：旅行商问题中启发式函数定义及A算法求解过程.（通过列出OPEN、CL

9、OSED表确定扩展顺序） 2.P55页，1.2：滑动积木块游戏的A算法求解：,B,B,W,W,E,B,W,E,W,B,初始状态,目标状态,第四章 与或图搜索,理解能解节点的定义， 通过实例掌握AO*搜索过程；了解博弈问题的产生式描述；掌握博弈树的极大极小、-搜索过程。 思考习题: 1.P75页 2.5题。 2.P75页 2.6题。,第五章 高级搜索,理解组合优化问题的特点，领域的概念。 了解局部搜索算法和遗传算法的原理、过程、和特点。,第六章 基于逻辑的问题求解方法,清楚一阶谓词逻辑的基本定义; 深入理解归结原理, 通过实例掌握谓词逻辑的归结过程(包括置换和合一) ；并能利用归结反演系统证明和求解一些简单的实际问题。 思考习题： 思考习题： 1.P12