人工智能概述第二章.pptVIP

例：梵塔难题 （1）移动圆盘A和B至柱子2的双圆盘难题 (C B A) （2）移动圆盘C至柱子3的单圆盘难题（本原问题） (C B A) 第二章 知识的表示 2.3 问题归约法 例：梵塔难题 （3）移动圆盘A和B至柱子3的双圆盘难题 (C B A) 第二章 知识的表示 2.3 问题归约法 例：梵塔难题 第二章 知识的表示 2.3 问题归约法 问题归约图（与或图） 用一个类似图的结构来表示把问题归约为后继问题的替换集合 终叶节点：对应于原问题的本原节点 或节点：只要解决某个问题就可解决其父辈问题的节点集合，如（M，N，H） 与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（B,C)和（D,E,F） 第二章 知识的表示 2.3 问题归约法 例：猴子和香蕉问题 算符： f1: f2: f3: f4: 第二章 知识的表示 w－猴子的水平位置 x－当猴子在箱子顶上时取x=1；否则取x=0 y－箱子的水平位置 z－当猴子摘到香蕉时取z=1；否则取z=0 2.3 问题归约法 例：猴子和香蕉问题 初始状态：(a,0,b,0) 目标状态：(w,x,y,1) 用({(a,0,b,0)},G)来表示问题，G为满足目标状态的集合 第二章 知识的表示 2.3 问题归约法 w－猴子的水平位置 x－当猴子在箱子顶上时取x=1；否则取x=0 y－箱子的水平位置 z－当猴子摘到香蕉时取z=1；否则取z=0 例：猴子和香蕉问题 用f4来归约初始问题，得到一对子问题： ({(a,0,b,0)}, Gf4) 其中，Gf4是适用于算符f4的状态集合 ({f4(S1)},G) 其中，S1是Gf4中由求解({(a,0,b,0)}, Gf4)而得到的状态 第二章 知识的表示 2.3 问题归约法 例：猴子和香蕉问题 为了求解({(a,0,b,0)}, Gf4)，由(a,0,b,0)所描述 的状态不在Gf4中，因为： (1)箱子不在c处——f2 pushbox(c) (2)猴子不在c处——f1 goto(c) (3)猴子不在箱子上—— f3 climbbox 第二章 知识的表示 2.3 问题归约法 例：猴子和香蕉问题 把({(a,0,b,0)}, Gf4)归约为一对子问题： ({(a,0,b,0)}, Gf2) (1-1) 其中，Gf2是适用于算符f2的状态集合 ({f2(S11)}, Gf4) (1-2) 其中，S11是Gf2中由求解(1-1)而得到的状态 第二章 知识的表示 2.3 问题归约法 例：猴子和香蕉问题 为了求解({(a,0,b,0)}, Gf2)(1-1)，此时的差别为，猴子不在b处——f1 goto(b) ， 因此把问题({(a,0,b,0)}, Gf2)( 1-1)归约为一对子问题： ({(a,0,b,0)}, Gf1) (1-11) ——本原问题 ({f1(S111)}, Gf2) (1-12) 转变为 ({(b,0,b,0)}, Gf2)（本原问题） 第二章 知识的表示 2.3 问题归约法 例：猴子和香蕉问题 得到算符的解答序列： {goto (b),pushbox(c),climbbox,grasp} 第二章 知识的表示 2.3 问题归约法 本章内容 2.1 知识的基本概念 2.2?状态空间法 2.3 问题归约法 2.4 其它表示法 第二章 知识的表示 比较 状态空间法：是一种基于解答空间的问题表示和求解方法，它是以状态和操作符为基础的。容易出现“组合爆炸”，只适用于表示比较简单的问题。 问题归约法：从目标出发，逆向推理，通过一系列变换把初始问题变换为子问题集合和子-子问题集合，直至最后归约为一个平凡的本原问题集合。 第二章 知识的表示 2.4 其它表示法 陈述式知识表示方法 语义网络、框架、剧本等知识表示方法 是对知识和事实的一种静止的表达方法 是知识的一种显式表达形式 通过控制策略来决定如何使用知识 第二章 知识的表示 2.4 其它表示法 过程式知识表示方法 将有关某一问题领域的知识，连同如何使用这些知识的方法，均隐式地表达为一个求解问题的过程 给出的是事物的一些客观规律，表达的是如何求