智能系统与智能软件研究所.ppt

第三章 搜索推理技术 3.6 产生式系统 3.7 系统组织技术 3.8 不确定性推理 3.9 非单调推理 3.10 小结 3.1 图搜索策略 3.2 盲目搜索 3.3 启发式搜索 3.4 消解原理 3.5 规则演绎系统 智能系统与智能软件研究所 2 3.1 图搜索策略 图搜索控制策略 一种在图中寻找路径的方法。 图中每个节点对应一个状态，每条连线对应 一个操作符。这些节点和连线 (即状态与操 作符 )又分别由产生式系统的数据库和规则 来标记。求得把一个数据库变换为另一数据 库的规则序列问题就等价于求得图中的一条 路径问题。 图搜索过程图 智能系统与智能软件研究所 3 开始 把 S放入 OPEN表 OPEN表为空表？ 把第一个节点 (n)从 OPEN表移至 CLOSED表 n为目标节点吗？ 把 n的后继节点放入 OPEN表的 末端，提供返回节点 n的指针 修改指针方向 重排 OPEN表 失败 成功 图 3.1 图搜索过程框图 是 是 否 否 3.1 图搜索策略 智能系统与智能软件研究所 4 3.2 盲目搜索 特点：不需重排 OPEN表 种类：宽度优先、深度优先、等代价搜索等。 3.2.1 宽度优先搜索 定义 以接近起始节点的程度逐层扩展节点的搜索方法 。 特点： 一种高代价搜索，但若有解存在，则必能找到它 。 算法 智能系统与智能软件研究所 5 开始 把 S放入 OPEN表 OPEN表为空表？ 把第一个节点 (n)从 OPEN表移至 CLOSED表 是否有后继节点 为目标节点？ 扩展 n，把 n的后继节点放入 OPEN 表的末端，提供返回节点 n的指针 失败 成功 图 3.2 宽度优先算法框图 是 否 是 否 3.2 盲目搜索 智能系统与智能软件研究所 6 例子 八数码难题（ 8-puzzle problem） 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 （目标状态） （初始状态 ） 规定： 将牌移入空格的顺序为：从空格左边开始 顺时针旋转。不许斜向移动，也不返回先辈节点。 从图可见，要扩展 26个节点，共生成 46个节点 之后才求得解（目标节点） 。 3.2 盲目搜索 智能系统与智能软件研究所 7 1 2 3 8 4 5 6 7 1 2 3 8 4 1 2 3 8 4 5 6 7 4 1 2 3 8 5 6 7 1 2 3 8 4 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 6 7 8 9 10 11 12 13 1 2 3 8 4 5 6 7 5 6 7 5 6 7 1 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 2 3 4 5 图 3.4 八数码难题的宽度优先搜索树 1 3 4 5 6 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 23 24 25 26 27 2 7 8 22 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 14 15 16 17 18 19 20 21 1 2 3 8 4 5 6 7 3.2 盲目搜索 智能系统与智能软件研究所 8 3.2.2 深度优先搜索 定义 首先扩展最新产生的 (即最深的 )节点 。 算法 防止搜索过程沿着无益的路径扩展下去 ， 往往给出一个节点扩展的最大深度 深度界 限 。 与宽度优先搜索算法最根本的不同在于： 将扩展的后继节点放在 OPEN表的前端 。 （ 算 法框图见教材 ） 3.2 盲目搜索 智能系统与智能软件研究所 9 3.2.3 等代价搜索 定义 是宽度优先搜索的一种推广，不是沿着等长 度路径断层进行扩展，而是沿着等代价路径断层 进行扩展。 搜索树中每条连接弧线上的有关代价 ,表示时 间、距离等花费。 算法 若所有连接弧线具有相等代价，则简化为宽 度优先搜索算法。 3.2 盲目搜索 智能系统与智能软件研究所 10 开始 把 S放入 OPEN表 OPEN表为空表？ 把具有最小 g(i)值的节点 i从 OPEN表移 至 CLOSED表 是否有后继节点 为目标节点？ 失败 成功 图 3.2 等代价搜索算法框图 是 否 是 否 令 g(s)=0 S是否目标节点 ？ 是 成功 扩展 i，计算其后继节点 j的 g(j)， 并把后继节点放入 OPEN表 否 3.2 盲目搜索 智能系统与智能软件研究所 11 3.3 启发式搜索 特点： 重排 OPEN表，选择最有希望的节点 加以扩展 种类：有序搜索、 A*算法等 3.3.1 启发式搜索策略和估价函数 盲目搜索可能带来组合爆炸 启发式信息 用来加速搜索过程的有关问题领域的特征信息。 智能系统与智能软件研究所 12 估价函数 为获得某些节点 “ 希望 ” 的启发信息，提供一 个评定侯选扩展节点的方法，以便确定哪个节点最 有可能在通向目标的最佳路径上 。 f(n) 表示节点 n的估价函数值 应用节点 “ 希望 ” 程度（估价函数值）重排 OPEN 表 3.3.2 有序搜索 实质 选择 OPEN表上具有最小 f值的节点作为下一 个要扩展的节点 。 3.3 启发式搜索 智能系统与智能软件研究所 13 开始 把 S放入 OPEN表， 计算估价函数 f (s) OPEN表为空表？ 选取 OPEN表中 f值最小的节点 i放入 CLOSED表 i为目标节点吗？ 扩展 i，得后继节点 j，计算 f(j)，提供返回 节点 i的指针，利用 f(j)对 OPEN表重新排 序，调整亲子关系及指针 失败 成功 图 3.9 有序搜索算法框图 是 否 是 否 3.3 启发式搜索 算法 智能系统与智能软件研究所 14 例子 八数码难题（ 8-puzzle problem） 1 2 3 8 4 5 6 7 （目标状态） 1 2 3 8 4 5 6 7 （初始状态） 八数码难题的有序搜索树见下图 ： 3.3 启发式搜索 智能系统与智能软件研究所 15 5 7 1 4 5 6 3 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 （ 4） （ 6） （ 6） 2 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 （ 6） （ 5） （ 5） 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 （ 5） （ 7） 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 （ 6） （ 7） 1 2 3 8 4 5 6 7 （ 5） 8 1 3 2 4 5 6 7 1 2 3 8 4 5 6 7 （ 5） （ 7） 图 3.10 八数码难题的 有序搜索树 1 2 3 8 4 6 （ 4） 3.3 启发式搜索 智能系统与智能软件研究所 16 3.3.3 A*算法 估价函数的定义： 对节点 n定义 f*(n)=g*(n)+h*(n) ,表示从 S开始约束通 过节点 n的一条最佳路径的代价。 希望估价函数 f 定义为： f(n)=g(n)+h(n) g是 g*的估计 ， h是 h*的估计 A*算法的定义： 定义 1 在 GRAPHSEARCH过程中，如果第 8步的重排 OPEN表 是依据 f(x)=g(x)+h(x)进行的，则称该过程为 A算法。 定义 2 在 A算法中 ， 如果对所有的 x存在 h(x)h*(x), 则称 h(x) 为 h*(x)的下界 ， 它表示某种偏于保守的估计 。 定义 3 采用 h*(x)的下界 h(x)为启发函数的 A算法 ， 称为 A*算法 。 当 h=0时 ， A*算法就变为有序搜索算法 。 3.3 启发式搜索 智能系统与智能软件研究所 17 3.4 消解原理 回顾 ： 原子公式 （ atomic formulas） 文字 一个原子公式及其否定 。 子句 由文字的析取组成的合适公式 。 消解 对谓词演算公式进行分解和化简，消 去一些符号，以求得导出子句。 3.4.1 子句集的求取 步骤：共 9步。 智能系统与智能软件研究所 18 例子 : 将下列谓词演算公式化为一个子句集 (x) P(x) (y) P(y)P(f(x,y) (y) Q(x,y)P(y) 开始： (1)消去蕴涵符号 只应用 和符号，以 AB 替换 AB。 (1) (x) P(x) (y) P(y) P(f(x,y) (y) Q(x,y) P(y) 3.4 消解原理 智能系统与智能软件研究所 19 (2) 减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上， 并反复应用狄 摩根定律。 (3) 对变量标准化 对哑元（虚构变量）改名，以保证每个量词 有其自己唯一的哑元。 3.4 消解原理 (2) (x) P(x) (y) P(y) P(f(x,y) (y) Q(x,y) P(y) (3) (x) P(x) (y) P(y) P(f(x,y) (w) Q(x,w) P(w) 智能系统与智能软件研究所 20 (4) 消去存在量词 以 Skolem函数代替存在量词内的约束变量， 然后消去存在量词 (5) 化为前束形 把所有全称量词移到公式的左边，并使每个量词的 辖域包括这个量词后面公式的整个部分。 前束形 = 前缀 母式 全称量词串 无量词公式 (4) (x) P(x) (y)P(y) P(f(x,y) Q(x,g(x)） P(g(x) 式中， w=g(x)为一 Skolem函数。 (5) (x)(y) P(x) P(y) P(f(x,y) Q(x,g(x) P(g(x) 3.4 消解原理 智能系统与智能软件研究所 21 (6) 把母式化为合取范式 任何母式都可写成由一些谓词公式和 (或 )谓词公 式的否定的析取的有限集组成的合取 。 (7) 消去全称量词 所有余下的量词均被全称量词量化了。 消去前缀， 即消去明显出现的全称量词。 3.4 消解原理 (6) (x)(y) P(x) P(y) P(f(x,y) P(x) Q(x,g(x) P(x) P(g(x) (7) P(x) P(y) P(f(x,y) P(x) Q(x,g(x) P(x) P(g(x) 智能系统与智能软件研究所 22 (8) 消去连词符号 用 A,B代替 (AB) ，消去符号 。最后得到一 个有限集，其中每个公式是文字的析取。 (9) 更换变量名称 可以更换变量符号的名称，使一个变量符号不 出现在一个以上的子句中。 3.4 消解原理 (8) P(x) P(y) P(f(x,y) P(x) Q(x,g(x) P(x) P(g(x) (9) P(x1) P(y) P f(x1,y) P(x2) Q x2,g(x2) P(x3) P g(x3) 智能系统与智能软件研究所 23 3.4.2 消解推理规则 消解式的定义 令 L1， L2为两任意原子公式； L1和 L2具有相同 的谓词符号，但一般具有不同的变量。已知 两子句 L1 和 L2, 如果 L1和 L2具有最一 般合一 ，那么通过消解可以从这两个父辈 子句推导出一个新子句 () 。这个新子 句叫做消解式。 消解式求法 取各子句的析取，然后消去互补对。 3.4 消解原理 智能系统与智能软件研究所 24 3.4.3 含有变量的消解式 要把消解推理规则推广到含有变量的子句 ， 必须找到一 个作用于父辈子句的臵换 ， 使父辈子句含有互补文字 。 含有变量的子句之消解式 例子 Px,f(y) Q(x) Rf(a),y Pf (f(a),z R(z， w) Q f (f(a) R(f(a)， y) R(f(y)， w) =f(f(a)/x,f(y)/z 3.4 消解原理 智能系统与智能软件研究所 25 3.4.4 消解反演求解过程 消解反演 给出 S， L 否定 L，得 L； 把 L添加到 S中去； 把新产生的集合 L， S化成子句集； 应用消解原理，力图推导出一个表示矛盾的空子句 例子 储蓄问题 前提：每个储蓄钱的人都获得利息。 结论：如果没有利息，那么就没有人去储蓄钱 3.4 消解原理 智能系统与智能软件研究所 26 (1） 规定原子公式 ： S(x,y) 表示 “ x储蓄 y” M(x) 表示 “ x是钱 ” I(x) 表示 “ x是利息 ” E(x， y) 表示 “ x获得 y” (2） 用谓词公式表示前提和结论： 前提： (x)(y)(S(x,y)M(y) (y)(I(y)E(x,y) 结论： (x)I(x) (x)(y)(M(y) S(x,y) (3) 化为子句形 证明 ： 3.4 消解原理 智能系统与智能软件研究所 27 把前提化为子句形 ： 1) S(x,y) M(y)I(f(x) 2) S(x,y) M(y)E(x,f(x) 把结论化为子句形： 3) I(z) 4) S(a,b) 5) M(b) (4) 消解反演求 NIL 图 3.12 储蓄问题反演树 子句 （ 1） 子句 （ 3） f (x)/z M(b) NIL 子句 （ 5） 子句 （ 7） 子句 （ 4） a/x,b/y S(x,y) M(y) 子句 （ 6） 3.4 消解原理 智能系统与智能软件研究所 28 反演求解过程 从反演树求取答案步骤 把由目标公式的否定产生的每个子句添加到目 标公式否定之否定的子句中去。 按照反演树，执行和以前相同的消解，直至在 根部得到某个子句止。 用根部的子句作为一个回答语句。 实质 把一棵根部有 NIL的反演树变换为根部带有回 答 语句的一棵证明树 。 3.4 消解原理 智能系统与智能软件研究所 29 3.5 规则演绎系统 定义 基于规则的问题求解系统运用 IfThen 规则来建立 ， 每个 if可能与某断言 (assertion)集 中的一个或多个断言匹配 。 有时把该断言集称 为工作内存 ， then部分用于规定放入工作内存 的新断言 。 这种基于规则的系统叫做规则演绎 系统 。 在这种系统中 ， 通常称每个 if部分为前 项 ， 称每个 then部分为后项 。 智能系统与智能软件研究所 30 3.5.1 规则正向演绎系统 定义 正向规则演绎系统是从事实到目标进行操作的， 即从状况条件到动作进行推理的，也就是从 if到 then的方向进行推理的。 求解过程 事实表达式的与或形变换 在基于规则的正向演绎系统中 ， 我们把事实 表示为非蕴涵形式的与或形，作为系统的总数 据库 。 3.5 规则演绎系统 智能系统与智能软件研究所 31 事实表达式的与或图表示 Q(w,A) R(v) P(v) S(A,v) Q(w,A) R(v) P(v) S(A,v) R(v) P(v) S(A,v) R(v) P(v) 图 3.15 一个事实表达式的与或树表示 3.5 规则演绎系统 智能系统与智能软件研究所 32 与或图的 F规则变换 这些规则是建立在某个问题辖域中普通陈 述性知识的蕴涵公式基础上的。我们把允许用 作规则的公式类型限制为下列形式： L W 式中： L是单文字； W为与或形的唯一公式 。 3.5 规则演绎系统 智能系统与智能软件研究所 33 3.5.2 规则逆向演绎系统 定义 逆向规则演绎系统是从 then向 if进行推理的， 即从目标或动作向事实或状况条件进行推理的。 求解过程 目标表达式的与或形式 与或图的 B规则变换 作为终止条件的事实节点的一致解图 3.5 规则演绎系统 智能系统与智能软件研究所 34 正向和逆向组合系统是建立在两个系统相结 合的基础上的。此组合系统的总数据库由表示目 标和表示事实的两个与或图结构组成。这些与或 图结构分别用正向系统的 F规则和逆向系统的 B规 则来修正。 3.5.3 规则双向演绎系统 3.5 规则演绎系统 智能系统与智能软件研究所 35 3.6 产生式系统 定义 ： 用来描述若干个不同的以一个基本概念为 基础的系统。这个基本概念就是产生式规则或产 生式条件和操作对的概念 。 实质： 在产生式系统中，论域的知识分为两部分： 用事实表示静态知识，如事物、事件和它们之间 的关系；用产生式规则表示推理过程和行为。由 于这类系统的知识库主要用于存储规则，因此又 把此类系统称为基于规则的系统。 智能系统与智能软件研究所 36 3.6.1 产生式系统的组成 控制策略 图 3.22 产生式系统的主要组成 总数据库 产生式规则 3.6 产生式系统 智能系统与智能软件研究所 37 选择规则到 执行操作的步骤 1 匹配 把当前数据库与规则的条件部分相匹配。 2 冲突 当有一条以上规则的条件部分和当前数据库 相匹配时，就需要决定首先使用哪一条规则，这 称为冲突解决。 3 操作 操作就是执行规则的操作部分。 3.6 产生式系统 智能系统与智能软件研究所 38 3.6.2 产生式系统的推理 正向推理 ： 从一组表示事实的谓词或命题出发， 使用一组产生式规则，用以证明该谓词公式或命题 是否成立。 逆向推理 ： 从表示目标的谓词或命题出发，使用 一组产生式规则证明事实谓词或命题成立，即首先 提出一批假设目标，然后逐一验证这些假设。 双向推理 ： 双向推理的推理策略是同时从目标向 事实推理和从事实向目标推理，并在推理过程中的 某个步骤，实现事实与目标的匹配。 3.6 产生式系统 智能系统与智能软件研究所 39 3.7 系统组织技术 3.7.1 议程表 系统组织技术首先将一个大系统或复杂系统中 的知识划分为一组相对独立的模块 ， 然后考虑 各子模块间在求解时的合作问题 。 议程表是一个系统能够执行的任务表列 。 与每 个任务有关的有两件事 ， 即提出该任务的理由 和表示对该任务是有用的证据总权的评价 。 智能系统与智能软件研究所 40 3.7.2 黑板法 黑板法由一组称为 知识资源 (KS)的独立模块和 一块 黑板 组成求解系统。知识资源含有系统中 专门领域的知识，而黑板则是一切 KS可以访问 的公用数据结构。 3.7 系统组织技术 3.7.3 -极小搜索法 提供了一种选择最有希望假设的技术。 智能系统与智能软件研究所 41 3.8 不确定性推理 以模糊集理论为基础的方法 以概率为基础的方法 3.8.1 关于证据的不确定性 不确定性推理是研究复杂系统不完全性和不确 定性的有力工具。有两种不确定性，即关于证 据的不确定性和关于结论的不确定性。 智能系统与智能软件研究所 42 3.8.2 关于结论的不确定性 关于结论的不确定性也叫做 规则的不确定性 ， 它表示当规则的条件被完全满足时，产生某 种 结论的不确定程度 。 3.8.3 多个规则支持同一事实时的不确定性 基于模糊集理论的方法 基于概率论的方法 3.8 不确定性推理 智能系统与智能软件研究所 43 3.9 非单调推理 定义 非单调推理用来处理那些不适合用 谓词逻辑表示的知识。 它能够较好地处理不完全信息、不 断变化的情况以及求解复杂问题过程中 生成的假设，具有较为有效的求解效率。 智能系统与智能软件研究所 44 3.9.1 缺省推理 定义 1： 如果 X不知道，那么得结论 Y。 定义 2： 如果 X不能被证明，那么得结论 Y。 定义 3： 如果 X不能在某个给定的时间内被证明， 那么得结论 Y。 3.9 非单调推理 3.9.2 非单调推理系统 正确性维持系统 用以保持其它程序所产生的命题 之间的相容性。一旦发现某个不相容，它就调出 自己的推理机制，面向从属关系的回溯，并通过 修改最小的信念集来消除不相容。 智能系统与智能软件研究所 45 3.10 小结 经典搜索推理技术 图搜索技术 消解反演 高级搜索推理技术 规则演绎系统 产生式系统 系统组织技术 不确定性推理 非单调推理