您的当前位置是：第二章 知识表示方法>>学习内容>>知识点二

观看视频讲解，学习问题归约法

一、问题归约描述

1．问题归约法的概念

已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。

该方法也就是从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。

2．问题归约法的组成部分

① 一个初始问题描述；

② 一套把问题变换为子问题的操作符；

③ 一套本原问题描述。

3．示例：梵塔难题

问题 有3个柱子（1，2，3）和3个不同尺寸的圆盘（A，B，C）。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。

归约过程

① 移动圆盘A和B至柱子2的双圆盘难题；

② 移动圆盘C至柱子3的单圆盘难题；

③ 移动圆盘A和B至柱子3的双圆盘难题。

由上可以看出简化了难题每一个都比原始难题容易，所以问题都会变成易解的本原问题。

4．归约描述

问题归约方法是应用算符来把问题描述变换为子问题描述。

可以用状态空间表示的三元组合（S、F、G）来规定与描述问题；对于梵塔问题，子问题［（111）→（122）］，［（122）→（322）］以及［（322）→（333）］规定了最后解答路径将要通过的脚踏石状态（122）和（322）。

问题归约方法可以应用状态、算符和目标这些表示法来描述问题，这并不意味着问题归约法和状态空间法是一样的。

二、与或图表示

1．与或图的概念

用一个类似图的结构来表示把问题归约为后继问题的替换集合，画出归约问题图。

例如，设想问题A需要由求解问题B、C和D来决定，那么可以用一个与图来表示；同样，一个问题A或者由求解问题B、或者由求解问题C来决定，则可以用一个或图来表示。

2．与或图的有关术语

父节点 是一个初始问题或是可分解为子问题的问题节点；

子节点 是一个初始问题或是子问题分解的子问题节点；

或节点 只要解决某个问题就可解决其父辈问题的节点集合；

与节点 只有解决所有子问题，才能解决其父辈问题的节点集合；

弧线 是父辈节点指向子节点的圆弧连线；

终叶节点 是对应于原问题的本原节点。

3．与或图的有关定义

可解节点 与或图中一个可解节点的一般定义可以归纳如下：

① 终叶节点是可解节点（因为它们与本原问题相关连）。

② 如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。

③ 如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是可解的。

不可解节点 不可解节点的一般定义归纳于下：

① 没有后裔的非终叶节点为不可解节点。

② 如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。

③ 如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。

4．与或图构图规则

① 与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。

② 对应于本原问题的节点，叫做终叶节点，它没有后裔。

③ 对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点，表示所求得的子问题集合。

④ 一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。

⑤ 在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。