２．１０ 与／或树表示法 ７５  图２．２９ 与／或树 用与／或树 来 表示，即 在解 决 大多 数 问题 时，对原 问 题的 分 解与变换是相结合的。氮吹仪价格 在与／或树 中，其根 节点 对 应着 待求 解的原始问题。 ４． 端节点与终止节点 在与／或树中，没有子节点的节点称为端节点；本原问题 所对应的节 点称 为 终 止 节 点。可 见，终止 节 点 一 定 是端 节 点，但端节点却不一定是终止节点。 ５． 可解节点与不可解节点 在与／或树中，满足以下三个条件之一的节点为可解节点： （１） 该节点是一个终止节点。 （２） 该节点是一个“或”节点，且其子节点中至少有一个为可解节点。 （３） 该节点是一个“与”节点，且其子节点全部为可解节点。 同样，满足下列条件之一的节点为不可解节点： （１） 该节点是一个端节点，但却不是终止节点。 图２．３０ 解树 （２） 该节 点 是一 个“或”节点，但其 子 节 点中 没有一个是可解节点。 （３） 该节点是“与”节点，且其子节点 中至少有 一个为不可解节点。

 ６． 解树 解树是一 个 由 可 解 节 点 构 成，并 且 可 由 这 些 可解节点推出初始 节点（它 对应 着原始 问题）也为 可解节 点 的 子 树。在 解 树 中 一 定 包 含 初 始 节 点。 例如，在图２．３０ 所 给出 的与／或树 中，用 粗线 表示 的子树就是它的一个解树。该图中 的节点 Ｐ 为原 始问题节 点，标 有 ｔ的 节 点 是 终 止 节 点。由 可 解 节点的定义，可以容易推知原始问题 Ｐ 为可解节点。 ２．１０．３ 用与／或树表示问题的步骤 用与或树表示法表示问题的步骤如下： （１） 对所要求解的问题进行分解或等价变换。 （２） 若所得的子问题不是本原问题，则继续分解或变换，直到分解或变换为本原问题。 ７６ 第二章 知识表示方法  （３） 在分解或变换中，若是不等价的分解，则用“与树”表示，若是等价 变换，则用“或树” 表示。 ２．１０．４ 与／或树表示举例 例２．１４ 三阶 Ｈａｎｏｉ塔问 题。设有 Ａ、Ｂ、Ｃ 三 个盘子（Ａ 比 Ｂ小，Ｂ比 Ｃ 小）及三 根柱 子，三 个盘子 按自 上而 下从

小 到大 的顺序 穿在 １号 柱子 上，要求 把它们 全部 移到 ３号 柱子 上，而且每次只能移动一个盘子，任何时刻都不能把大的盘 子压在小 的盘子 上面，如图２．３１ 所示。 图２．３１ 三阶 Ｈａｎｏｉ塔问题 解 这个问题我们在前面已经用一阶谓词逻辑法表示过了，上一节，我们又用状态空间 表示法对二阶 Ｈａｎｏｉ塔问题作过 表示 和求解。 现在 在尝试 着用 与／或 树表示 法对 它进 行表 示。 第一步，设用三元组 （ｉ，ｊ，ｋ） 表示问题在任一时刻的状态，用“→”表示状态的转换。在上述三元组中，ｉ代 表盘子 Ｃ 所在 的柱子号，ｊ代表盘子 Ｂ所在的柱子号，ｋ代表盘子 Ａ 所在的柱子号。则原问题可以表示为 （１，１，１）→（３，３，３） 第二步，利用归约方法，原问题可分解为以下三个子问题： （１） 把盘子 Ａ 和 Ｂ 移到２号柱子上的双盘子移动问题。即 （１，１，１）→（１，２，２） （２） 把盘子 Ｃ移到３号柱子上的单盘子移动问题。即 （１，２，２）→（３，２，２） （３） 把盘子 Ａ 和 Ｂ 移到３号柱子的双盘子移动问题。即 （３，２，２）→（３，３，３） 其中，子问题（１）和（３）都是一个二阶 Ｈａｎｏｉ塔 问题，它们 都还 可以 再继续 进行 分解；子 问题 （２）是本原问题，它已不需要再分解。 （１，１，１）→（１，２，２）又可分解为（１，１，１）→（１，１，３）、（１，１，

３）→（１，２，３）和（１，２，３）→（１， ２，２）三个本原问题；（３，２，２）→（３，３，３）又可分解为（３，２，２）→（３，２，１）、（３，２，１）→（３，３，１）和 ２．１０ 与／或树表示法 ７７  （３，３，１）→（３，３，３）三个本原问题。 第三步：根据分解与变换情况画出与／或树。如图２．３２所示。 图２．３２ 三阶 Ｈａｎｏｉ塔的与／或树 图２．３２所示的与／或树是对三阶 Ｈａｎｏｉ塔问题分解过程的图示说明。在该与／或树中， 有７个终止节点，它们分别对应着７个本原问题。如果把这些本原问题从左至右排列起来， 即得到了原始问题的解： （１，１，１）→（１，１，３） （１，１，３）→（１，２，３） （１，２，３）→（１，２，２） （１，２，２）→（３，２，２） （３，２，２）→（３，２，１） （３，２，１）→（３，３，１） （３，３，１）→（３，３，３） 知识表示是人工智能研究的主要问题之一，也是 利用 人工智 能求 解实际 问题 的必 经之 路。本章讨论了知识表示常用的９种方法，针对每一 种方法，都讨论了它适于表示的知识种 类，特别是讨论了表示知识的步骤和方法，并通过举例对这些步骤和方法进行了说明，使得知 识表示的可操作性更强、更实用。学习者通过本章，可以克服在表示知识时所遇到的困难。 习 题 二 ２．１ 什么是知识？它有哪些特性？有哪几种分类方法？