猴子摘香蕉问题的解 (ab.0初始状态 Goto(b) Goto(b) (b,b,0,0) Pushbox(c) Climbbox Pushbox(c((c, c, 0,0) (b,b,1,0) Climbbox Pushbox (a) Pushbox(c) (c,c,1,0) (a,a,0,0) Pushbox (a Grasp (cc,1,1)目标状态 猴子摘香蕉问题的状态空间图 解序列为:{Goto(b), Pushbox(c), Climbbox, Grasp}16
猴子摘香蕉问题的解 (a,b,0,0) (b,b,0,0) (c,c,0,0) (b ,b,1,0) (c,c,1,0) (a,a,0,0) (c,c,1,1) 初始状态 Goto(b) Goto(b) Pushbox(c) Grasp 目标状态 猴子摘香蕉问题的状态空间图 解序列为： {Goto(b), Pushbox(c), Climbbox, Grasp} Pushbox(c) Climbbox Climbbox Pushbox(c) Pushbox(a) Pushbox(a) 16
51.3问题归约法 1.问题的分解与等价变换 基本思想 当一问题较复杂时,可通过分解或变换,将其转化为一系列较简 单的子问题,然后通过对这些子问题的求解来实现对原问题的求解 分解 如果一个问题P可以归约为一组子问题P1,P2,Pn,并且只有当所有 子问题P都有解时原问题P才有解,任何一个子问题P无解都会导致原 问题P无解,则称此种归约为问题的分解。 即分解所得到的子问题的“与”与原问题P等价。 等价变换 如果一个问题P可以归约为一组子问题P1P2…,Pn,并且子问题P 中只要有一个有解则原问题P就有解,只有当所有子问题P都无解时 原问题P才无解,称此种归约为问题的等价变换,简称变换。 即变换所得到的子问题的“或”与原问题P等价
基本思想 当一问题较复杂时，可通过分解或变换，将其转化为一系列较简 单的子问题，然后通过对这些子问题的求解来实现对原问题的求解。 分解 如果一个问题P可以归约为一组子问题P1 ,P2 ,…,Pn，并且只有当所有 子问题Pi都有解时原问题P才有解，任何一个子问题Pi无解都会导致原 问题P无解，则称此种归约为问题的分解。 即分解所得到的子问题的“与”与原问题P等价。 等价变换 如果一个问题P可以归约为一组子问题P1 ,P2 ,…,Pn，并且子问题Pi 中只要有一个有解则原问题P就有解，只有当所有子问题Pi都无解时 原问题P才无解，称此种归约为问题的等价变换，简称变换。 即变换所得到的子问题的“或”与原问题P等价。 5.1.3 问题归约法 1. 问题的分解与等价变换 17
51.3问题归约法 2.问题的与或树表示 (1)与树分解 (2)或树等价变换 与树 或树 (3)与或树P 12 12 31132133 18 与/或树
P P1 P2 P3 与树 P1 P2 P3 或树 P P P1 P2 P3 P12 P12 P31 P32 P33 与/或树 (1)与树 分解 (2) 或树 等价变换 (3) 与/或树 5.1.3 问题归约法 2. 问题的与/或树表示 18
(4)端节点与终止节点 在与或树中,没有子节点的节点称为端节点;本原问题所对应的节 点称为终止节点。可见,终止节点一定是端节点,但端节点却不一定是 终止节点。 (5)可解节点与不可解节点 在与/或树中,满足以下三个条件之一的节点为可解节点: ①任何终止节点都是可解节点。 ②对“或”节点,当其子节点中至少有一个为可解节点时,则该或节点 就是可解节点。 ③对“与”节点,只有当其子节点全部为可解节点时,该与节点才是可 解节点。 同样,可用类似的方法定义不可解节点: ①不为终止节点的端节点是不可解节点。 ②对“或”节点,若其全部子节点都为不可解节点,则该或节点是不可 解节点。 ③对“与”节点,只要其子节点中有一个为不可解节点,则该与节点是 不可解节点
(4) 端节点与终止节点 在与/或树中，没有子节点的节点称为端节点；本原问题所对应的节 点称为终止节点。可见，终止节点一定是端节点，但端节点却不一定是 终止节点。 (5) 可解节点与不可解节点 在与/或树中，满足以下三个条件之一的节点为可解节点： ①任何终止节点都是可解节点。 ②对“或”节点，当其子节点中至少有一个为可解节点时，则该或节点 就是可解节点。 ③对“与”节点，只有当其子节点全部为可解节点时，该与节点才是可 解节点。 同样，可用类似的方法定义不可解节点： ①不为终止节点的端节点是不可解节点。 ②对“或”节点，若其全部子节点都为不可解节点，则该或节点是不可 解节点。 ③对“与”节点，只要其子节点中有一个为不可解节点，则该与节点是 不可解节点。 19
(6)解树 由可解节点构成,并且由这些可解 节点可以推出初始节点(它对应着原 始问题)为可解节点的子树为解树。 在解树中一定包含初始节点。 例如,右图给出的与或树中,用红 P 线表示的子树是一个解树。在该图中 节点P为原始问题节点,用t标出的节 点是终止节点。根据可解节点的定义 很容易推出原始问题P为可解节点。 问题归约求解过程就实际上就是生 成解树,即证明原始节点是可解节点 的过程。这一过程涉及到搜索的问题 对于与/或树的搜索将在后面详细讨 解树 论。 20
P t t t 解树 (6) 解树 由可解节点构成，并且由这些可解 节点可以推出初始节点（它对应着原 始问题）为可解节点的子树为解树。 在解树中一定包含初始节点。 例如，右图给出的与或树中，用红 线表示的子树是一个解树。在该图中， 节点P为原始问题节点，用t标出的节 点是终止节点。根据可解节点的定义， 很容易推出原始问题P为可解节点。 问题归约求解过程就实际上就是生 成解树，即证明原始节点是可解节点 的过程。这一过程涉及到搜索的问题， 对于与/或树的搜索将在后面详细讨 论。 20