人工智能第2章(知识表示方法2-问题归约法).ppt

人工智能ArtificialIntelligence AI 许建华xujianhua 南京师范大学计算机科学与技术学院2011年秋季 第2章知识表示方法 2 1状态空间法2 2问题归约法2 3谓词逻辑法 2 2问题归约法 例 求积分 解法1 解法2 解法3 问题 解法1 解法2 解法3 解法4 子问题1 子问题2 子问题3 变换 分解 问题归约法 从已知问题的描述出发 通过一系列变换或分解将问题最终变为一个子问题集合 这些子问题的解可以直接得到 从而解决初始问题 问题归约法由三个部分组成 一个初始问题描述一套将问题变换或分解为子问题的操作符一套本原问题 解可以直接得到的简单问题 描述 2 2 1问题归约描述 1 例子 梵塔问题 三个盘 解决问题的思路 第一 要将所有盘从第一个柱子搬到第三个柱子 根据游戏规则 首先要搬最大的C盘到第三个柱子上 解决问题的思路 第二 要能够搬C盘 条件是 第三个柱子是空的 A B必须在第二个柱子上 这里没有考虑如何搬A B盘 a 初始配置 b 目标配置 图2 6梵塔难题 解决问题的思路 第三 搬C盘到第三个柱子 然后想办法将A B盘搬到第三个柱子上 将问题简化为下列三个子问题 移动园盘A和B到柱子2的双园盘难题移动C盘到柱子3的单园盘难题移动A和B到柱子3的双园盘难题 图2 8梵塔问题的归约 左到右表示盘从大到小 数字表示盘所在柱子号 小盘 1 3中盘 1 2小盘 3 2 小盘 2 1中盘 2 3小盘 1 3 与 中小盘1到2 中小盘2到3 大盘1到3 2 问题归约的描述 问题归约法的基本思路是 应用一系列算符将原始问题的描述变换或分解成为子问题的描述问题的描述可以采用各种数据结构 如表 树 矢量 数组等 对于梵塔问题 问题及子问题描述 113 333 问题归约法可以用一个三元组 S O P 来表示 其中 S 原始问题 即要解决的问题P 本原问题集 其中的每一个问题是不用证明的或自然成立的 例如公理 已知事实等O 操作算子集 用于将问题化为子问题 2 2 2与或图表示 例 有一个问题A 它可以通过三种途径来求解 1 求解问题B和C2 求解问题D E和F3 求解H 引入中间节点 好处 任何一个节点的后继节点要么全是 与节点 要么全是 或节点 与或图的特例 所有节点都是或节点 这时就是一般的图 即状态空间法用到的图除了起始节点外 所有节点只有一个父节点 此时称为与或树 前面的图2 11就是与或树 问题归约法 与或图表示之间的对应关系 问题归约法原始问题本原问题操作符中间问题 与或图表示起始节点终叶节点与 或关系的弧线非终叶节点 在与或图中 问题有解的条件是 起始节点是可解的 一般情况下 分解操作符得到与节点变换操作符得到或节点 在与或图中 一个可解节点的定义是 递归地 1 终叶节点是可解的 因为它们与本原问题相关联的 一般情况 终叶节点用t来表示 2 如果某一个非终叶节点含有 或 后继节点 那么 只要有一个后继节点是可解的 这一个非终叶节点就是可解的 一个节点可解 可解 3 如果某一个非终叶节点含有 与 后继节点 那么 只要所有后继节点是可解的 这一个非终叶节点才是可解的 所有节点可解 可解 与或图中 一个不可解节点的定义 递归地 是 1 没有后裔的非终叶节点是不可解节点 2 如果某一个非终叶节点含有 或 后继节点 那么 只要当所有的后继节点都不可解时 这一个非终叶节点才是不可解的 所有节点不可解 不可解 3 如果某一个非终叶节点含有 与 后继节点 那么 只要有一个后继节点是不可解的 这一个非终叶节点就是不可解的 有一个节点不可解 不可解 与或图的解图