第二章 问题归约法.

1、第二章第二章 问题归约法问题归约法 Problem Reduction Representation问题归约法v 问题归约（问题归约（Problem Reduction）是另外一种是另外一种基于状态空间基于状态空间的问题描述与求解方法的问题描述与求解方法已知问题的描述，通过一系列已知问题的描述，通过一系列变换变换把此问题变为一个把此问题变为一个子问题集合子问题集合这些子问题的解可以这些子问题的解可以直接得到（本原问题）直接得到（本原问题），从而解，从而解决了初始问题决了初始问题问题归约法v 问题归约法的组成部分问题归约法的组成部分一个初始问题描述；一个初始问题描述；一套把问题变换为子问题的一套

2、把问题变换为子问题的操作符操作符；一套一套本原问题本原问题描述。描述。( (本原问题本原问题: :不能再分解或变换且不能再分解或变换且直接可解的子问题直接可解的子问题) )v 问题归约的实质：问题归约的实质：从目标（要解决的问题）出发从目标（要解决的问题）出发逆向推理逆向推理，建立子问题，建立子问题以及子问题的子问题，直到最后把初始问题归约为以及子问题的子问题，直到最后把初始问题归约为一一个本原问题集合个本原问题集合。问题归约法v 问题归约法举例：问题归约法举例：汉诺塔问题（汉诺塔问题（ Hanoi ） p 从从1移到移到3p 每次移动一个盘子每次移动一个盘子p 大盘在下小盘在上大盘在下小盘在

3、上123CBA初始状态（初始状态（111111）目标状态（目标状态（333333）CBA汉诺塔问题v 原始问题可以归约为下列原始问题可以归约为下列3 3个子问题：个子问题：子问题子问题1 1：子问题子问题2 2：子问题子问题3 3：汉诺塔问题v 归约过程（归约过程（3 3个圆盘）个圆盘）汉诺塔问题v 汉诺塔问题归约图汉诺塔问题归约图本原问题本原问题本原问题本原问题与或图与或图CBA梵塔问题的答案v一圆盘问题要走几步，两圆盘问题要走几步？三个、四个、六十四个圆盘呢？圆盘个数圆盘个数移动圆盘次数移动圆盘次数11222-1=3323-1=764264-1264-1=18446744073709551

4、615 一年一年=365*24*60*60=31536000秒秒1844674407370955161531536000584942417355年年 问题归约法v 与或图表示：与或图表示：用一个类似于图的结构来表示把问题归约为用一个类似于图的结构来表示把问题归约为后继问题的替换集合。后继问题的替换集合。与图：与图：把一个复杂问题把一个复杂问题分解为若干个较为简单的分解为若干个较为简单的子问题，形成子问题，形成“与与”树。树。或图：或图：把原问题变换为把原问题变换为若干个较为容易求解的新若干个较为容易求解的新问题，形成问题，形成“或或”树。树。问题归约法v 与或图表示：与或图表示：BCDEFGA

5、HMBCDEFGAN子问题替代集合结构图子问题替代集合结构图与或图与或图问题归约法v 一些关于与或图的术语一些关于与或图的术语起始节点起始节点对应于原对应于原始问题描始问题描述述终叶节点对应于本原问题终叶节点对应于本原问题问题归约法v 与或图的构成规则与或图的构成规则 1 1）与或图中的每个节点代表一）与或图中的每个节点代表一个要解决的单一问题或问题集合。个要解决的单一问题或问题集合。图中所含起始节点对应于原始问图中所含起始节点对应于原始问题题A A。 2 2）对应于本原问题的节点称为）对应于本原问题的节点称为终叶节点，它没有后继节点。终叶节点，它没有后继节点。 3 3）对于把算符应用于问题）

6、对于把算符应用于问题A A的每的每种可能情况，都把问题变换为一种可能情况，都把问题变换为一个子问题集合；有向弧线自个子问题集合；有向弧线自A A指指向后继节点表示所求得的子问题向后继节点表示所求得的子问题集合。集合。HMBCDEFGAN问题归约法v 与或图的构成规则与或图的构成规则 4 4）一般对于代表两个或两个以上）一般对于代表两个或两个以上子问题集合的每个节点，有向弧子问题集合的每个节点，有向弧线从此节点指向次子问题集合中线从此节点指向次子问题集合中的各个节点。由于只有当集合中的各个节点。由于只有当集合中所有项都有解时，这个子问题的所有项都有解时，这个子问题的集合才能获得解答，所以这些子集

7、合才能获得解答，所以这些子问题节点叫做与节点。问题节点叫做与节点。 5 5）特殊情况下，当只有一个算符）特殊情况下，当只有一个算符可应用于问题可应用于问题A A，而且这个算符产，而且这个算符产生具有一个以上子问题的某个集生具有一个以上子问题的某个集合时，由上述规则合时，由上述规则3 3）和规则）和规则4 4）所产生的图可以得到简化。所产生的图可以得到简化。MDEFAADEF简化简化问题归约法v与或图的搜索：与或图的搜索：目的在于表明起始节点是有解的。目的在于表明起始节点是有解的。v可解节点可解节点终叶节点是可解节点（对应于本原问题）。终叶节点是可解节点（对应于本原问题）。如果某个非终叶节点含有

8、如果某个非终叶节点含有或后继节点或后继节点，那么只要当其后，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可解继节点至少有一个是可解的时，此非终叶节点才是可解的。的。如果某个非终叶节点含有如果某个非终叶节点含有与后继节点与后继节点，那么只有当其后，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。继节点全部为可解时，此非终叶节点才是可解的。问题归约法v不可解节点不可解节点没有后裔的非终叶节点为不可解节点。没有后裔的非终叶节点为不可解节点。 如果某个非终叶节点含有如果某个非终叶节点含有或后继节点或后继节点，那么只有当其，那么只有当其全全部后裔为不可解时部后裔为不可解时，此非终叶节点才是不可解的。，此非终叶节点才是不可解的。 如果某个非终叶节点含有如果某个非终叶节点含有与后继节点与后继节点，那么只要当其，那么只要当其后后裔至少有一个为不可解时裔至少有一个为不可解时，此非终叶节点才是不可解的。，此非终叶节点才是不可解的。v解树解树由可解节点所构成，并且由这些可解节点可推出初始节由可解节点所构成，并且由这些可解节点可推出初始节点为可解节点的子树称为解树。点为可解节点的子树称为解树。解树中一定包含初始节点，它对应于原始