回溯方法 用来设计货箱装船、背包、最大完备子图、旅行商和电路板排列问题的求解算法。
5星 · 超过95%的资源 需积分: 9 52 浏览量
2008-09-17
20:06:18
上传
评论
收藏 166KB DOC 举报 
第 4 章 回溯
寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完
所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或
部分候选解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用这种方法，
因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也
只能解决规模很小的问题。对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比
较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少
（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以使我们避免对很大的候选解
集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够
用来求解规模很大的问题。
本章集中阐述回溯方法，这种方法被用来设计货箱装船、背包、最大完备子图、旅行商和
电路板排列问题的求解算法。
4.1 算法思想
回溯（b a c k t r a c k i n g）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要
为问题定义一个解空间（ solution space），这个空间必须至少包含问题的一个解（可能是最优
的）。在迷宫老鼠问题中，我们可以定义一个包含从入口到出口的所有路径的解空间；在具有
n 个对象的 0 / 1 背包问题中（见 1 . 4 节和 2 . 2 节），解空间的一个合理选择是 2n 个长度为 n 的
0 / 1 向量的集合，这个集合表示了将 0 或 1 分配给 x 的所有可能方法。当 n= 3 时，解空间为
{ ( 0 , 0 , 0 )，( 0 , 1 , 0 )，( 0 , 0 , 1 )，( 1 , 0 , 0 )，( 0 , 1 , 1 )，( 1 , 0 , 1 )，( 1 , 1 , 0 )，( 1 , 1 ,
1 ) }。
下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。图 1 6 - 1 用图的
形式给出了一个 3×3 迷宫的解空间。从( 1 , 1 )点到( 3 , 3 )点的每一条路径都定义了 3×3 迷宫解
空间中的一个元素，但由于障碍的设置，有些路径是不可行的。
图 1 6 - 2 用树形结构给出了含三个对象的 0 / 1 背包问题的解空间。从 i 层节点到 i+ 1 层节
点的一条边上的数字给出了向量 x 中第 i 个分量的值 xi ，从根节点到叶节点的每一条路径定义了
解空间中的一个元素。从根节点 A 到叶节点 H 的路径定义了解 x= [ 1 , 1 , 1 ]。根据 w 和 c 的值，
从根到叶的路径中的一些解或全部解可能是不可行的。
一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。在
迷宫老鼠问题中，开始节点为入口节点( 1 , 1 )；在 0 / 1 背包问题中，开始节点为根节点 A。开
始节点既是一个活节点又是一个 E-节点（expansion node）。从 E-节点可移动到一个新节点。
如果能从当前的 E-节点移动到一个新节点，那么这个新节点将变成一个活节点和新的 E-节点，
旧的 E-节点仍是一个活节点。如果不能移到一个新节点，当前的 E-节点就“死”了（即不再是一
个活节点），那么便只能返回到最近被考察的活节点（回溯），这个活节点变成了新的 E-节点。
当我们已经找到了答案或者回溯尽了所有的活节点时，搜索过程结束。
例 4-1 [迷宫老鼠] 考察图 16-3a 的矩阵中给出的 3×3 的“迷宫老鼠”问题。我们将利用图 1 6
-1 给出的解空间图来搜索迷宫。
从迷宫的入口到出口的每一条路径都与图 1 6 - 1 中从( 1 , 1 )到( 3 , 3 )的一条路径相对应。
然而，图 1 6 - 1 中有些从( 1 , 1 )到( 3 , 3 )的路径却不是迷宫中从入口到出口的路径。搜索从点
( 1 , 1 )开始，该点是目前唯一的活节点，它也是一个 E-节点。为避免再次走过这个位置，置 m
剩余20页未读，继续阅读
评论3
最新资源