人工智能及其应用chapter3_071101课件

1、3.1 搜索系统的组成 搜索系统由以下三大成分构成 ：知识库：描述当前任务的范围以及要求解问题的目标。规则 :用于对数据库的加工处理。控制性知识：决定下一步应如何做？选择什么操作？在何处使用此控制？ 人工智能及其应用1 3.2 问题表示及求解方法 问题表达及其变换问题的直接求解法状态空间图搜索算法 人工智能及其应用2问题表达及其变换 同构同态变换问题分解法与图（树）描述问题分解。或图（树）描述同构同态变换 。人工智能及其应用3问题的直接求解法 状态空间求解法用状态描述与问题相关的事实和事实间的关系。状态常表示为矢量。问题的状态空间可记为三元组(S，F，G)。 问题演绎法 基本思想：分解原问题成

2、若干个子问题。博弈问题求解法 属于对策性课题，表示若干个体开展竞争的过程。 人工智能及其应用4状态空间图搜索算法搜索法求解问题的基本思想： 将初始状态当作当前状态。 选择适当的算符作用于当前状态得到后继状态。检查这组后继状态中是否有目标状态。已扩展节点、未扩展节点的数据结构人工智能及其应用5状态空间图搜索算法状态空间搜索算法流程： 人工智能及其应用6 3.3 基本推理技术 推理的概念及其类型 推理的控制策略人工智能及其应用7推理的概念及其类型定义： 从已有事实和知识中推出结论。 在人工智能系统中，推理机是由程序实现的，它利用知识库中的知识，按一定的控制策略求解问题。 人工智能及其应用8推理的概

3、念及其类型推理方法分类：按途径分： 演绎推理、归纳推理、默认推理。按所用知识的确定性分： 确定性推理、不确定推理。 按结论是否单调增加分： 单调推理、非单调推理。按推理中是否运用启发性知识分： 启发式推理、非启发式推理。 人工智能及其应用9推理的控制策略推理系统构成： 知识库 、数据库 、推理机 。推理方向： (1) 正向推理：由已知事实出发向结论方向的推理，也称事实驱动推理。 (2) 反向推理：以某个假设目标作为出发点的推理，也称为目标驱动推理或逆向推理。 (3) 正反向混合推理: 正向和反向推理相结合的推理。人工智能及其应用10推理的控制策略搜索策略： 状态空间搜索(广度优先搜索、深度优先

4、搜索、有界深度优先搜索等 )、启发式搜索等。冲突解决策略：(1) 专一性排序 (5) 上下文限制 (2) 规则排序 (6) 按匹配度排序 (3) 数据排序 (7) 按条件个数排序 (4) 就近排序人工智能及其应用11 3.4 搜索策略的效率 穿透率 有效分支因素 提高搜索效率的一般原则 人工智能及其应用12穿透率 定义：反映目标搜索时的搜索范围。P还和问题的难度相关，一般是L越大，问题越困难，P值越小；反之P则越大。人工智能及其应用13有效分支因素 定义：有效节点平均生成的子节点总数: 搜索策略的有效分支因素评价: 搜索策略的外显率评价: 人工智能及其应用14提高搜索效率的一般原则 定性策略：

5、 特殊优先策略 新知识优先策略 差异性优先策略 其它策略 人工智能及其应用153.5 基本搜索策略特点:非启发的、解决树状结构问题广度优先搜索 深度优先搜索 有界深度优先搜索代价推进搜索 人工智能及其应用16广度优先搜索搜索原则：深度越小、越早生成结点的优先级越高。当最低层不止一个结点时，它选择最先生成的结点进行搜索。 人工智能及其应用17广度优先搜索例3-4：八数码问题(1)操作规定: 允许空格四周上、下、左、右的数码块移入空格中，不许斜方向移动，不许返回先辈结点。初始布局S和目标状态D如下图所示： 人工智能及其应用18广度优先搜索例3-4的广度优先搜索树：人工智能及其应用19广度优先搜索广

6、度优先算法步骤：(1) 初始结点S加入到队列OPEN的尾部；(2) 若OPEN为空，则搜索失败，问题无解；(3) 取出OPEN队头的结点n，并放入CLOSE队列中；(4) 若n是目标结点D，则搜索成功，问题有解；(5) 若n是叶结点，则转(2)；(6) 扩展n结点(即找出它的所有直接后继)，并把它的诸子结点依次加入OPEN队尾，修改这些子结点的返回指针，使其指向结点n。转(2)。人工智能及其应用20深度优先搜索搜索原则：深度越大、越晚产生结点的优先级越高。深度优先搜索是不完备的，属于非算法的搜索过程。 人工智能及其应用21深度优先搜索例3-5：八数码问题(2)操作规定已在广度优先搜索算法举例中

7、介绍过。初始布局S和目标状态D如下图所示： 人工智能及其应用22深度优先搜索例3-5的深度优先搜索树：人工智能及其应用23深度优先搜索深度优先算法步骤：(1) 初始结点S放入堆栈OPEN中； (2) 若OPEN为空，则搜索失败，问题无解； (3) 弹出OPEN表中最顶端结点放到CLOSE表中，并给出顺序编号n； (4) 若n为目标结点D，则搜索成功，问题有解； (5) 若n无子结点，转(2)；(6) 扩展n结点，将其所有子结点配上返回n的指针，并按次序压入OPEN堆栈，转(2) 。人工智能及其应用24有界深度优先搜索特点： 引入搜索深度限制值d，使深度优先搜索过程具有完备性 。例3-6：八数码

8、问题(2) 设定搜索深度限制d=5，问题同深度优先算法中的八数码问题(2)。人工智能及其应用25有界深度优先搜索例3-6的有界深度优先搜索树：人工智能及其应用26有界深度优先搜索有界深度优先算法步骤：(1)初始结点S放入堆栈OPEN中；(2)若OPEN为空，则搜索失败，问题无解；(3)弹出OPEN中栈顶结点n，放入CLOSE表中，并给出顺序编号n；(4)若n为目标结点D，则搜索成功，问题有解；(5)若n的深度d(n)=d，则转(2) ；(6)若n无子结点，即不可扩展，转(2) ；(7)扩展结点n，将其所有子结点配上返回n的指针，并压入OPEN堆栈，转(2) 。人工智能及其应用27代价推进搜索特

9、点： 节点间有向边的代价不同算法修改：(1)广度优先搜索法：每次从OPEN表中取出具有最小代价的节点进行扩展 。(2)有界深度优先搜索法：用代价限制g代替深度限制d，用代价g(n)代替节点深度d(n)。 人工智能及其应用28代价推进搜索例3-7 ： 求下图所示的旅行问题中，费用最小的路线，设出发地是A城，目的地是E城，图中各边上的数字代表交通费用。 人工智能及其应用29代价推进搜索例3-7的代价推进搜索树：人工智能及其应用303.6 启发式搜索策略启发信息和估价函数 局部择优搜索 全局择优搜索 A*算法 人工智能及其应用31启发信息和估价函数启发信息： 与具体问题解相关的控制性知识 。估价函数

10、： 估计OPEN表中各扩展节点的重要程度，给它们排定扩展次序。 人工智能及其应用32局部择优搜索基本思想 ： 选择一个节点的后继节点，是在它的所有子节点中，选估价函数f(n)最优者。因此，亦称“瞎子爬山法”。特点：可以取消OPEN表，每次扩展后只保留一个最优子节点，直接放入CLOSE表中，丢掉其它子节点。主要在单因素、单极值情况下使用；在多因素，多极值情况下，找不到最佳解。 人工智能及其应用33局部择优搜索例3-8 ： 在深度优先搜索算法的八数码问题(2)中，如果把估价函数定义为f(n)=w(n)，其中，w(n)表示结点n的格局与目标结点D格局相比位置不符的数码个数。用局部择优搜索策略求解该问

11、题 。其搜索树如下页图所示：人工智能及其应用34例3-8的局部择优搜索树：人工智能及其应用35全局择优搜索特点：在OPEN表中保留所有已生成而未扩展的节点，并用估价函数f(n)对它们全部进行估计，从中选出最优的节点进行扩展，因此，亦称“最好优先搜索法” 。得到的不一定是实际上的最佳解。 人工智能及其应用36全局择优搜索例3-9：八数码问题(2)如果将广度优先搜索算法中的估计函数定义为：f(n) = d(n) + w(n)，其中，d(n)代表结点n的扩展深度，w(n)含义同例3-8。用全局择优搜索法求解此问题。其搜索树如下页图所示。图中，状态结点右边圆圈中的数字表示估价函数值。 人工智能及其应用37全局择优搜索例3-9的全局择优搜索树：人工智能及其应用38A*算法特点：对状态空间搜索算法中的扩展节点选择原则进行了限制。选用了一个比较特殊的估价函数。定义:A*算法A 算法 性质:采纳性单调性信息性人工智能及其应用393.7 基于规划的启发式搜索原理 基本规划 多层规划 人工智能及其应用40基本规划 规划解决问题的方法:引入一系列子目标 把问题分解成若干子问题 解决子问题产生规划的基本方法:差异减小法 人工智能及其应用41多层规划 多层规划解决问题的方法:给出一个总的粗略设想 逐步细化设想产生详尽规划为止 人工智能及其应用42多层规划 例3-12: 假设有A、B