• 基本概念
• 与或树表示
• 实例：三阶梵塔问题

问题归约法是不同于状态空间方法的另外一种形式化方法，其基本思想是对问题进行分解或变换。当一个问题比较复杂时，如果直接进行求解，往往比较困难，此时可通过分解或变换，将它转化为一系列较简单的问题，然后通过对这些较简单问题的求解来实现对原问题的求解。

基本概念

• 分解：如果一个问题P可以归约为一组子问题P1，P2 ，… ，Pn，并且只有当所有子问题Pi（i = 1，2,…，n)都有解时,原问题P才有解，任何一个子问题Pi（i = 1，2 , … ，n)无解，都会导致原问题P无解 ，则称此种归约为问题的分解，即分解所得到的子问题的“与”与原问题P等价。
• 等价变换：如果一个问题P 可以归约为一组子问题P1，P2 ，… ，Pn，并且这些子问题Pi(i = 1，2，…，n)中只要有一个有解，则原问题P就有解，只有当所有子问题Pi(i=1，2 ,…，n)都无解时，原问题P才无解，则称此种归约为问题的等价变换，简称变换，即变换所得到的子问题的“或”与原问题P等价。

在实际问题的归约过程中，有可能需要同时采用变换和分解的方法。无论是分解还是变换，都是要将原问题归约为一系列本原问题。所谓本原问题是指那种不能（或不需要）再进行分解或变换，且可以直接解答的问题。本原问题可以作为终止归约的限制条件。

与或树表示

把一个原问题归约为一系列本原问题的过程可以很方便地用一个与/或树来表示。

• 与树：把一个原问题分解为若干个子问题可用一个“与树”来 表示。例如，设P可以分解为三个 子问题P1，P2，P3的与，则P和P1 ，P2，P3之间的关系可用如下图所示的一个“与树”来表示。在该树中，我们用相应的节点表示，P2，P3;并用三条有向边分别将P和P1，P2，P3连接起来，它表示P1，P2，P3 是P的三个子问题。图中还有一条连接三条有向边的小弧线，它表 示P1，P2，P3之间是“与”的关系，即节点P为“与”节点。
• 或树：把一个原问题变换为若干个子问题可用一个“或树”来 表示。例如，设P可以变换为三个 子问题P1，P2，P3的或，则P和P1 ，P2，P3之间的关系可用如下图所示的一个“或树”来表示。在该树中，我们用相应的节点表示，P2，P3;并用三条有向边分别将P和P1，P2，P3连接起来，它表示P1，P2，P3 是P的三个子问题。图中的有向边不用小弧线，它表示P1，P2，P3之间是“或”的关系，即节点P为“或”节点。
• 与/或树：如果一个问题既需要通过分解，又需要通过变换才能得到其本原问题，则其归约过程可用一个“与/或树”来表示。与/或树的例子如下图所示。事实上，一般的归约过程多数是需要用与/或树来表示的。在与/或树中，其根节点对应着原始问题。

• 在与/或树中，没有子节点的节点称为端节点，本原问题所对应的节点称为终止节点。可见，终止节点一定是端节点，但端节点却不一定是终止节点。
• 满足以下三个条件之一的节点为可解节点：
  • 任何终止节点都是可解节。
  • 对“或”节点，当其子节点中至少有一个为可解节点时，则该或节点就是可解节点。
  • 对“与”节点，只有当其子节点全部为可解节点时，该与节点才是可解节点。
• 同样，可用类似的方法定义不可解节点：
  • 不为终止节点的端节点是不可解节点。
  • 对“或”节点，若其全部子节点都为不可解节点，则该或节点是不可解节点。
  • 对“与”节点，只要其子节点中有一个为不可解节点，则该与节点是不可解节点。
• 解树：由可解节点构成，并且由这些可解节点可以推出初始节点(它对应着原始问题）为可解节 点的子树为解树。在解树中一定包含初始节点。例如，在下图所给出的与/或树中，用粗线表示的子树是一个解树。在该图中，节点P为 原始问题节点，用t标出的节点是终止节点。根据可解节点的定义，很容易推出原始问题P为可解节点。问题归约求解过程实际上就是生成解树，即证明原始节点是可解节点的过程。这一过程涉及到搜索的问题，对于与/或树的搜索将在后面详细讨论。

实例：三阶梵塔问题

三阶梵塔问题。设有A，B，C三个 金片及1，2，3三根钢针，三个金片按自上而下、从小到大的顺序穿在1号钢针上，要求把它们全部移 到3号钢针上，而且每次只能移动一个金片，任何时刻都不能把大的金片压在小的金片上面，如下图所 示。

解：这个问题也可用状态空间法（详细）来解，不过本例主要用它来说明如何 用归约法来解决问题。

为了能够解决这一问题，首先需要定义该问题的形式化表示方法。设用三元组(S_KA，S_KB，S_KC)表示问题在任一时刻的状态，用“->”表示状态的转换。在上述三元组中，S_KA代表金片A所在的钢针号，S_KB代表金片 B所在的钢针号，S_KC代表金片C所在的钢针号。

利用问题归约方法，原问题可分解为以下三个子问题：

1. 把金片A及B移到2号钢针上的双金片移动问题。即(1，1，1)->(2, 2, 1)
2. 把金片C移到3号钢针上的单金片移动问题。即(2, 2, 1)->(2, 2, 3)
3. 把金片A及B移到3号钢针的双金片移动问题。即(2, 2, 3)—>(3,3, 3)

其中，子问题(1)和(3)都是一个二阶梵塔问题，它们都还可以再继续进行分解;子问题(2)是本原问题，它已不需要再分解。

三阶梵塔问题的分解过程可用如下图所示的与/或树来表示。在该与/或树中，有7个终止节点，它们分别对应着7个本原问题。如果把这些本原问题从左至右排列起来，即得到了原始问题的解：

相关连接：搜索策略