与或图.ppt

人工智能 第二章 知识表示方法 NOTE 教学内容：本章讨论知识表示的各种方法，是人工智能课程三大内容（知识表示、知识推理、知识应用）之一，也是学习人工智能其他内容的基础。 教学重点：状态空间法、问题归约法、谓词逻辑法、语义网络法。 教学难点：状态描述与状态空间图示、问题归约机制、置换与合一。 教学要求：重点掌握用状态空间法、问题归约法、谓词演算法、语义网络法来描述问题；解决问题；掌握几种主要方法之间的差别；并对其它几种表示方法有一般了解。 2.1 状态空间法 问题求解的两个方面 问题的表示 求解的方法 状态空间法 基于解空间的问题表示和求解方法就是状态空间法，以状态和算符为基础来表示和求解问题。 多采用试探有哪些信誉好的足球投注网站方法 2.1.1 问题状态描述 1.定义： 状态：为描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合。 算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。 问题的状态空间(state space)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态(S，F，G)。其中所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。 图示 例：三数码难题（3 puzzle problem） 实例：十五数码难题（15 puzzle problem） 状态空间法 从某个初始状态开始，每次增加一个操作符，递增地建立起操作符的试验序列，直到达到目标状态止。 总结 完成问题的状态描述要做三件事： 1）初始状态的描述 2）操作符集合及其对状态改变的作用 3）目标状态的描述 2.1.2 状态图示法 有向图 路径 代价 图的显式说明 图的隐式说明 猴子与香蕉问题 用四元 表列（W,x,Y,z）来表示这个问题的状态 其中， 　　W－猴子的水平位置 　　x－当猴子在箱子顶上时取x=1；否则取x=0 　　Y－箱子的水平位置 　　z－当猴子摘到香蕉时取z=1；否则取z=0 这个问题中的操作（算符）如下： 1、goto（U）猴子走到水平位置U，表示为 goto(U) 　（W，0，Y，z） --------------（U ，0 ，Y ，z ） 即把状态（W，0，Y，z）变换为状态（U，0，Y，z）。 2、pushbox（V）猴子把箱子推到水平位置V，即有 pushbox(V) （W，0，W，z）----------------（V ，0 ，V ，z ） 条件：猴子与箱子必须在同一位置上，并且，猴子不是在箱子顶上。 3、climbbox猴子爬上箱顶，即有 climbbox 　　（W，0，W，z）------------------（W，1，W，z） 条件：猴子和箱子应当在同一位置上，而且猴子不在箱顶上。 4、grasp猴子摘到香蕉，即有 grasp 　 （c，1，c，0） -------------------（c，1，c，1） 条件：猴子和箱子都在位置c上，并且猴子已在箱子顶上。 其中，c是香蕉正下方的地板位置， 该初始状态变换为目标状态的操作序列为： ｛goto(b),pushbox(c),climbbox,grasp｝ 2.2 问题归约法 问题归约法的组成部分 　　（1）一个初始问题描述； 　　（2）一套把问题变换为子问题的操作符； 　　（3）一套本原问题描述。 问题归约的实质：从问题的目标出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。 2.2.1 问题归约描述 梵塔难题 原始问题归约（简化）为三个子问题 1、移动A，B盘至柱子2的双圆盘难题 2、移动圆盘C至柱子3的单圆盘问题 3、移动A，B盘至柱子3的双圆盘难题 归约过程 求解过程（3圆盘难题） 2.2.2 与或图表示 与图、或图、与或图 可解节点：与或图中一个可解节点的一般定义可以归纳如下： 1、 终叶节点是可解节点(因为它们与本原问题相关连)。 2、如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。 3、如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是可解的。 不可解节点 不可解节点的一般定义归纳于下： 1、没有后裔的非终叶节点为不可解节点。 2、如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。 3、如果某个非终