算法设计与分析 第8章 回溯法

《算法设计与分析 第8章 回溯法》由会员分享，可在线阅读，更多相关《算法设计与分析 第8章 回溯法（28页珍藏版）》请在金锄头文库上搜索。

1、第八章 回溯法 1 2 3 4 概述 图问题中的回溯法 组合问题中的动态规划法 小结 8.1 概 述 8.1.1 问题的解空间 8.1.2 解空间树的动态搜索（1） 8.1.3 回溯法的求解过程 8.1.4 回溯法的时间性能 用回溯法求解一个具有n个输入的问题，一般 情况下，将其可能解表示为满足某个约束条件 的等长向量X=(x1, x2, , xn)，其中分量xi (1in)的取值范围是某个有限集合Si=ai1, ai2, , airi，所有可能的解向量构成了问题的解空 间。 8.1.1 问题的解空间树 问题的解空间一般用解空间树（也称状 态空间树）的方式组织，树的根结点位于 第1层，表示搜索

2、的初始状态，第2层的结 点表示对解向量的第一个分量做出选择后 到达的状态，第1层到第2层的边上标出对 第一个分量选择的结果，依此类推，从树 的根结点到叶子结点的路径就构成了解空 间的一个可能解。 8.1.1 问题的解空间树 1 1 11 11 0 0 00 0 0 0 1 图8.2 0/1背包问题的解空间树 对物品1的选择 对物品3的选择 对物品2的选择 1 2 3 4 5 7811 121415 310 6 9 对于n=3的0/1背包问题解空间树 对于n=4的TSP问题解空间树 2 434223434131424121233121 34 1313123212142414 34322434 1

3、23124 134 图8.3 n=4的TSP问题的解空间树 5710121517212326283133373942444749525457596264 469111416202225273032363841434648515356586163 3813192429354045505560 2183424 1 1 23 4 34 8.1.2 回溯法的设计思想 回溯法从根结点出发，按照深度优先策略遍历解 空间树，搜索满足约束条件的解。在搜索至树中 任一结点时，先判断该结点对应的部分解是否满 足约束条件，或者是否超出目标函数的界，也就 是判断该结点是否包含问题的（最优）解，如果 肯定不包含，则跳过

4、对以该结点为根的子树的搜 索，即所谓剪枝（Pruning）；否则，进入以该结 点为根的子树，继续按照深度优先策略搜索。 解空间树的动态搜索过程 例如，对于n=3的0/1背包问题，三个物品的重量为 20, 15, 10，价值为20, 30, 25，背包容量为25， 从图8.2所示的解空间树的根结点开始搜索，搜索 过程如下： 重量为20, 15, 10 价值为20, 30, 25 背包容量为25 1 1 11 11 0 0 00 0 0 0 1 1 2 3 4 5 7811 121415 310 6 9 回溯法的搜索过程涉及的结点（称为搜索空间 ）只是整个解空间树的一部分，在搜索过程中 ，通常采用

5、两种策略避免无效搜索：（1）用约 束条件剪去得不到可行解的子树；（2）用目标 函数剪去得不到最优解的子树。这两类函数统 称为剪枝函数。 问题的解空间树是虚拟的，并不需要在算法运 行时构造一棵真正的树结构，只需要存储从根 结点到当前结点的路径。 小结 回溯法的一般框架递归形式 advance(int k) 1. 对每一个xSk循环执行下 列操作 1.1 xk=x; 1.2 将xk加入X; 1.3 if (X是最终解) flag=true; return; 1.4 else if (X是部分解) advance(k+1); 主算法 1X= ; 2. flag=false; 3. advance(1

6、); 4. if (flag) 输出解 X; else输出“无解”; 8.1.3 回溯法的时间性能 在问题的解向量X=(x1, x2, , xn)中，分量xi (1in)的取值 范围为某个有限集合Si=ai1, ai2, , airi，因此，问题的解 空间由笛卡儿积A=S1S2Sn构成。 在用回溯法求解问题时，常常遇到两种典型的解空间树： （1）子集树：当所给问题是从n个元素的集合中找出满足 某种性质的子集时，相应的解空间树称为子集树。在子集 树中，|S1|=|S2|=|Sn|=c，即每个结点有相同数目的子树 ，通常情况下c=2，因此，子集树中共有2n个。 （2）排列树：当所给问题是确定n个元

7、素满足某种性质的 排列时，相应的解空间树称为排列树。在排列树中，通常 情况下，|S1|=n，|S2|=n-1，|Sn|=1，所以，排列树中 共有n!个叶子结点，因此，遍历排列树需要(n!)时间。 8.1.3 回溯法的时间性能 8.1.4 一个简单的例子素数环问题 1 2 3 4 【问题问题 】把整数1, 2, , 20填写到一个环环中， 要求每个整数只填写一次，并且相邻邻的两个整数 之和是一个素数。 8.1.4 一个简单的例子素数环问题 【想法】这这个素数环环有20个位置，每个位置可以 填写的整数有120共20种可能，可以对对每个位置 从1开始进进行试试探，约约束条件是正在试试探的数满满 足如

8、下条件： （1）与已经经填写到素数环环中的整数不重复； （2）与前面相邻邻的整数之和是一个素数； （3）最后一个填写到素数环环中的整数与第一个填 写的整数之和是一个素数。 在填写第k个位置时时，如果满满足上述约约束条件， 则继续则继续 填写第k+1个位置；如果120个数都无法 填写到第k个位置，则则取消对对第k个位置的填写， 回溯到第k-1个位置。 图着色问题描述为：给定无向连通图G=(V, E)和 正整数m，求最小的整数m，使得用m种颜色对G 中的顶点着色，使得任意两个相邻顶点着色不同 。 图问题中的回溯法图着色问题 A C B D E D=1 1 2 34 567 8 9 10 11121

9、3 14 A=1 B=2 C=3 D=3 E=1 图问题中的回溯法图着色问题 问题描述：著名的爱尔兰数学家哈密顿提出了著 名的周游世界问题。正十二面体的20个顶点代表 20个城市，要求从一个城市出发，经过每个城市 恰好一次，然后回到出发城市。 19 8 3 14 1 20 2 13 15 4 5 67 9 10 11 12 16 17 18 图问题中的回溯法哈密顿回路问题 假定图G=(V, E)的顶点集为V=1, 2, , n，则哈密 顿回路的可能解表示为n元组X=(x1, x2, , xn)，其 中，xi1, 2, , n。根据题意，有如下约束条件 ： (xi, xi+1)E (1in1)

10、(xn, x1)E xixj (1i, jn，ij) 哈密顿回路问题数学模型 在哈密顿回路的可能解中，考虑到约束条件xixj (1i, jn，ij)，则可能解应该是(1, 2, , n)的一个 排列，对应的解空间树中有n!个叶子结点。 1 2 4 3 5 x4=4 x3=3 x2=2 2 1 x1=1 4 7 11 17 16 x5=5 x4=5 3 5 10 89 6 121314 15 21201819 x5=4 图问题中的回溯法哈密顿回路问题 设数组xn存储哈密顿回路上的顶点，数组visitedn存 储顶点的访问标志，visitedi=1表示哈密顿回路经过顶 点i，算法如下： 1将顶点数

11、组xn初始化为0，标志数组visitedn初始化为0； 2k=1; visited1=1; x1=1; 从顶点1出发构造哈密顿回路； 3while (k=1) 3.1 xk=xk+1，搜索下一个顶点; 3.2 若(n个顶点没有被穷举) 执行下列操作 3.2.1 若(顶点xk不在哈密顿回路上 3.2.2 否则，xk=xk+1，搜索下一个顶点； 3.3 若数组xn已形成哈密顿路径，则输出xn，算法结束； 3.4 否则， 3.4.1 若xn构成部分解，则k=k+1，转步骤3； 3.4.2 否则，重置xk，k=k-1，取消顶点xk的访问标志， 转步骤3； 图问题中的回溯法哈密顿回路问题 8.3 组合问

12、题中的回溯法 8.3.1 八皇后问题 8.3.2 批处理作业调度问题 组合问题中的回溯法八皇后问题 问题描述：八皇后问题是十九世纪著名的数学家高斯于 1850年提出的。问题是：在88的棋盘上摆放八个皇后 ，使其不能互相攻击，即任意两个皇后都不能处于同一 行、同一列或同一斜线上。可以把八皇后问题扩展到n 皇后问题，即在nn的棋盘上摆放n个皇后，使任意两 个皇后都不能处于同一行、同一列或同一斜线上。 显然，棋盘的每一行上可以而且必须摆放一个皇后，所 以，n皇后问题的可能解用一个n元向量X=(x1, x2, , xn) 表示，其中，1in并且1xin，即第i个皇后放在第i行 第xi列上。 由于两个皇

13、后不能位于同一列上，所以，解向量X必须 满足约束条件： xixj （式8.1） 若两个皇后摆放的位置分别是(i, xi)和(j, xj)，在棋盘上 斜率为-1的斜线上，满足条件ij= xixj，在棋盘上斜 率为1的斜线上，满足条件ij= xixj，综合两种情况 ，由于两个皇后不能位于同一斜线上，所以，解向量X 必须满足约束条件： |ixi|jxj| （式8.2） 为了简化问题，下面讨论四皇后问题。四皇后问 题的解空间树是一个完全4叉树，树的根结点表示搜索 的初始状态，从根结点到第2层结点对应皇后1在棋盘 中第1行的可能摆放位置，从第2层结点到第3层结点对 应皇后2在棋盘中第2行的可能摆放位置，

14、依此类推。 组合问题中的回溯法八皇后问题 QQ Q Q Q Q Q Q Q Q QQ Q Q Q Q Q Q Q Q (a) (b) (c) (d) (e) (f) (g) (h) (i) (j) Q Q Q 组合问题中的回溯法八皇后问题 批处理作业调度问题 问题描述：n个作业1, 2, , n要在两台机器上处理， 每个作业必须先由机器1处理，然后再由机器2处理， 机器1处理作业i所需时间为ai，机器2处理作业i所需时 间为bi（1in），批处理作业调度问题要求确定这 n个作业的最优处理顺序，使得从第1个作业在机器1上 处理开始，到最后一个作业在机器2上处理结束所需时 间最少。 批处理作业调度问题 显然，批处理作业的一个最优调度应使机器1没有空闲 时间，且机器2的空闲时间最小。可以证明，存在一个 最优作业调度使得在机器1和机器2上作业以相同次序 完成。 例如，有三个作业1, 2, 3，这三个作业在机器1上所 需的处理时间为(2, 3, 2)，在机器2上所需的处理时间 为(1, 1, 3)，则这三个作业存在6种可能的调度方案： (1, 2, 3)、(1, 3, 2)、(2, 1, 3)、(2, 3, 1)、(3, 1, 2)、(3, 2, 1)，相应的完成时间为10, 8, 10, 9, 8, 8。 批处理作业调度问题 批处理作业调度问题