第2章产生式系统.ppt

猴子和香蕉问题 解题过程 用一个四元表列（W，x，Y，z）来表示这个问题状态 W：猴子的水平位置； x： 当猴子在箱子顶上时取1；否则取0； Y： 箱子的水平位置； z： 当猴子摘到香蕉时取1；否则取0。 初始状态为(a,0,b,0) ，目标状态为(c,1,c,1) 这个问题的操作（算符）如下： goto（U）表示猴子走到水平位置U pushbox（V）猴子把箱子推到水平位置V climbbox猴子爬上箱顶 grasp猴子摘到香蕉 猴子和香蕉问题 解题过程 该初始状态变换为目标状态的操作序列为： Step1: goto(b) Step2: pushbox(c) Step3: climbbox Step4: grasp 猴子和香蕉问题 状态空间图 (b，1，b，0) （U，0，b，0） （V，0，V，0） （c，1，c，0） （U，0，V，0） （c，1，c，1） （a，0，b，0） 目标状态 goto（U） goto（U） U=b，climbbox goto（U） U=b pushbox（V） goto（U） U=V V=c，climbbox grasp 问题归约法 问题归约（Problem Reduction） 是另外一种基于状态空间的问题描述与求解方法 已知问题的描述，通过一系列变换把此问题变为一个子问题集合 这些子问题的解可以直接得到（本原问题），从而解决了初始问题 问题归约法 问题归约法的组成部分 一个初始问题描述； 一套把问题变换为子问题的操作符； 一套本原问题描述。(本原问题:不能再分解或变换且直接可解的子问题) 问题归约的实质： 从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直到最后把初始问题归约为一个本原问题集合。 问题归约法 问题归约法举例： 汉诺塔问题（ Hanoi ） 从1移到3 每次移动一个盘子 大盘在下小盘在上 1 2 3 C B A 初始状态（111） 目标状态（333） C B A 汉诺塔问题 原始问题可以归约为下列3个子问题： 子问题1：移动圆盘A和 B至柱子2（借助柱子3） 子问题2：移动圆盘C至柱子3 子问题3：把圆盘A和B移至柱子3（借助柱子1） 汉诺塔问题 归约过程（3个圆盘） 汉诺塔问题 汉诺塔问题归约图 本原问题 本原问题 与或图 C B A 问题归约法 与或图表示：用一个类似于图的结构来表示把问题归约为后继问题的替换集合。 与图：把一个复杂问题分解为若干个较为简单的子问题，形成“与”树。 或图：把原问题变换为若干个较为容易求解的新问题，形成“或”树。 问题归约法 与或图表示： B C D E F G A H M B C D E F G A N 子问题替代集合结构图 与或图 问题归约法 一些关于与或图的术语 起始节点对应于原始问题描述 终叶节点对应于本原问题 问题归约法 与或图的构成规则 1）与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题A。 2）对应于本原问题的节点称为终叶节点，它没有后继节点。 3）对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点表示所求得的子问题集合。 H M B C D E F G A N 问题归约法 与或图的构成规则 4）一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向次子问题集合中的各个节点。由于只有当集合中所有项都有解时，这个子问题的集合才能获得解答，所以这些子问题节点叫做与节点。 5）特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3）和规则4）所产生的图可以得到简化。 M D E F A A D E F 简化 问题归约法 与或图的有哪些信誉好的足球投注网站：目的在于表明起始节点是有解的。 可解节点 终叶节点是可解节点（对应于本原问题）。 如果某个非终叶节点含有或后继节点，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。 如果某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。 问题归约法 不可解节点 没有后裔的非终叶节点为不可解节点。 如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。 如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。 解树 由可解节点所构成，并且由这些可解节点可推出初始节点为可解节点的子树称为解树。 解树中一定包含初始节点，它对应于原始问题。 问题归约法 t t t t t t t t t 有解节点 无解节点 终叶节点 与或图例子 原始问题有一个以上的解 原始问题有解 * * * * * * * * * *