人工智能教程（第2版）第2章.ppt

状态空间图2.10与／或树表示法与／或树是不同于状态空间法的另外一种用于表示问题及其求解过程的形式化方法，通常用于表示比较复杂的问题求解。2.10.1问题的分解与等价变换问题的分解是指把一个复杂问题P分解为若干个子问题P1,P2,……,Pn（每个子问题又可以继续分解为若干个更为简单的子问题，直到不需要再分解或者不能再分解为止）。然后对每个子问题求解，并且只有当所有子问题Pi(i=1,2,……,n)都有解时,原问题P才有解,它的解就是所有子问题解的“与”；任何一个子问题Pi无解都会导致原问题P无解。即分解所得到的子问题的与”和原问题P等价。问题的等价变换是指对一个复杂问题P进行同构或同态的等价变换，将其变换为若干个较容易求解的新问题P1,P2,……,Pn，只要这些新问题Pi中有一个有解，则原问题P就有解。只有当变换得到的所有问题Pi(i=1,2,……,n)都无解时,原问题P才无解。也就是说，等价变换所得到的新问题的或”与原问题等价。2.10与／或树表示法2.10.2问题归约的与／或树表示当把一个复杂问题归约为一组本原问题时，其归约过程可以用一个与／或树来表示。下面介绍问题归约过程的与／或树表示方法。1.与树当把一个复杂问题分解为若干个子问题时，可用一个“与树”来表示这种分解。例如，设问题P可以分解为三个子问题Pl、P2、P3，即对它的求解相当于对这三个新问题的同时求解，则P和这三个新问题之间的关系可用如图2.27所示的一个“与树”来表示。在这个“与树”中，用相应的节点表示P、P1、P2、P3，并用三条有向边分别将P和P1、P2、P3连接起来，它表示P1、P2、P3是P的三个子问题。图中连接三条有向边的小弧线表示P1、P2、P3之间是“与”的关系，它们是对节点P的分解，P为“与”节点。图2.27与树2.10与／或树表示法2.或树当把一个复杂问题变换为若干个与之等价的新问题时，可用一个“或树”来表示这种变换。例如，设问题P可以变换为三个新问题Pl、P2、P3中的任何一个，即它与这三个新问题中的任何一个等价，则P与它们之间的关系可用如图2.28所示的一个“或树”来表示。在这个“或”树中，用相应的节点表示P、Pl、P2、P3；并用三条有向边分别将P和Pl、P2、P3连接起来，它表示Pl、P2、P3是与P等价的三个新问题。图中的有向边不用小弧线连接，它表示Pl、P2、P3之间是“或”的关系，即节点P为“或”节点。图2.28或树2.10与／或树表示法3.与/或树如果一个问题既需要通过分解，又需要通过变换才能得到其本原问题，则其求解过程可用一个“与/或树”来表示。与/或树的例子如图2.29所示。事实上，大多数实际问题都需要用与/或树来表示，即在解决大多数问题时，对原问题的分解与变换是相结合的。在与/或树中，其根节点对应着待求解的原始问题。图2.29与／或树2.10与／或树表示法4.端节点与终止节点在与/或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。可见，终止节点一定是端节点，但端节点却不一定是终止节点。5.可解节点与不可解节点在与/或树中，满足以下三个条件之一的节点为可解节点：(1)该节点是一个终止节点。(2)该节点是一个“或”节点，且其子节点中至少有一个为可解节点。(3)该节点是一个“与”节点，且其子节点全部为可解节点。同样，满足下列条件之一的节点为不可解节点：(1)该节点是一个端节点,但却不是终止节点。(2)该节点是一个“或”节点，但其子节点中没有一个是可解节点。(3)该节点是“与”节点，且其子节点中至少有一个为不可解节点。2.10与／或树表示法6.解树解树是一个由可解节点构成，并且可由这些可解节点推出初始节点(它对应着原始问题)也为可解节点的子树。在解树中一定包含初始节点。例如，在图2.30所给出的与/或树中，用粗线表示的子树就是它的一个解树。该图中的节点P为原始问题节点，标有t的节点是终止节点。由可解节点的定义，可以容易推知原始问题P为可解节点。图2.30解树2.10与／或树表示法2.10.3用与／或树表示问题的步骤用与或树表示法表示问题的步骤如下：（1）对所要求解的问题进行分解或等价变换。（2）若所得的子问题不是本原问题，则继续分解或变换，直到分解或变换为本原问题。（3）在分解或变换中，若是不等价的分解，则用“与树”表示，若是等价变换，则用“或树”表示。2.1