|
一、问题归约描述 本文来自www.eadianqi.com
1.问题归约法的概念
问题归约是将初始问题变为一个本原问题集合。 自动控制网www.eadianqi.com版权所有
2.问题归约法的组成部分
(1) 一个初始问题描述;
(2) 一套把问题变换为子问题的操作符;
(3) 一套本原问题描述。 本文来自www.eadianqi.com
3.示例:梵塔难题
问题
有3个柱子(1,2,3)和3个不同尺寸的圆盘(A,B,C)。在每个圆盘的中心有个孔,所以圆盘可以堆叠在柱子上。最初,全部3个圆盘都堆在柱子1上:最大的圆盘C在底部,最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上,每次只许移动一个,而且只能先搬动柱子顶部的圆盘,还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。
归约过程
(1) 移动圆盘A和B至柱子2的双圆盘难题;
(2) 移动圆盘C至柱子3的单圆盘难题;
(3) 移动圆盘A和B至柱子3的双圆盘难题。 本文来自www.eadianqi.com
二、与或图 自动控制网www.eadianqi.com版权所有
1.与或图的概念
用一个类似图的结构来表示把问题归约为后继问题的替换集合,画出归约问题图。 本文来自www.eadianqi.com
2.与或图的有关术语
父节点
是一个初始问题或是可分解为子问题的问题节点;
子节点
是一个初始问题或是子问题分解的子问题节点;
或节点
只要解决某个问题就可解决其父辈问题的节点集合;
与节点
只有解决所有子问题,才能解决其父辈问题的节点集合;
终叶节点
是对应于原问题的本原节点。 自动控制网www.eadianqi.com版权所有
提问 对于一个与或图,指出图中的父节点、子节点、或节点、与节点、弧线和终叶节点。 本文来自www.eadianqi.com
可解节点
与或图中一个可解节点的一般定义可以归纳如下:
(1) 终叶节点是可解节点(因为它们与本原问题相关连)。
(2) 如果某个非终叶节点含有或后继节点,那么只有当其后继节点至少有一个是可解的时,此非终叶节点才是可解的。
(3) 如果某个非终叶节点含有与后继节点,那么只要当其后继节点全部为可解时,此非终叶节点才是可解的。
不可解节点
不可解节点的一般定义归纳于下:
(1) 没有后裔的非终叶节点为不可解节点。
(2) 如果某个非终叶节点含有或后继节点,那么只有当其全部后裔为不可解时,此非终叶节点才是不可解的。
(3) 如果某个非终叶节点含有与后继节点,那么只要当其后裔至少有一个为不可解时,此非终叶节点才是不可解的。 自动控制网www.eadianqi.com版权所有
3.与或图构图规则
(1) 与或图中的每个节点代表一个要解决的单一问题或问题集合。图中起始节点对应原始问题。
(2) 对应于本原问题的节点,叫做终叶节点。
(3) 有向弧线自A指向后继节点,表示所求得的子问题集合。
(4) 一般对于代表两个或两个以上子问题集合的每个节点,有向弧线从此节点指向集合中的各个节点。
(5) 在特殊情况下,当只有一个算符可应用于问题A,而且这个算符产生具有一个以上子问题的某个集合时,由上述规则(3)和规则(4)所产生的图可以得到简化。 本文来自www.eadianqi.com
|