回溯法 - 山东师范大学

《回溯法 - 山东师范大学》由会员分享，可在线阅读，更多相关《回溯法 - 山东师范大学（64页珍藏版）》请在金锄头文库上搜索。

1、算法设计与分析山东师范大学信息科学与工程学院软件工程研究所 徐连诚 E-Mail： 2006年11月20日第五章 回溯法 学习要点 理解回溯法的深度优先搜索策略 掌握用回溯法解题的算法框架 1）递归回溯最优子结构性质 2）迭代回溯贪心选择性质 3）子集树算法框架 4）排列树算法框架 通过应用范例学习回溯法的设计策略 1）装载问题； 2）批处理作业调度； 3）符号三角形问题 4）n后问题； 5）0-1背包问题； 6）最大团问题； 7）图的m着色问题 8）旅行售货员问题 9）圆排列问题 10）电路板排列问题 11）连续邮资问题2 2引言有许多问题，当需要找出它的解集或者要求回答什 么解是满足某些约

2、束条件的最佳解时，往往要使用 回溯法。 回溯法的基本做法是搜索，或是一种组织得井井有 条的、能避免不必要搜索的穷举式搜索法。这种方 法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，从 根结点出发搜索解空间树。算法搜索至解空间树的 任意一点时，先判断该结点是否包含问题的解：如 果肯定不包含，则跳过对该结点为根的子树的搜索 ，逐层向其祖先结点回溯；否则，进入该子树，继 续按深度优先策略搜索。3 35.1 回溯法的算法框架本节介绍回溯法算法框架的有关问题： 一、问题的解空间 二、回溯法的基本思想 三、递归回溯 四、迭代回溯 五、子集树与排列树4 4一、问题的解空间 应用

3、回溯法解问题时，首先应明确定义问题的解空间。问题 的解空间应至少包含问题的一个(最优)解。 问题的解向量：回溯法希望一个问题的解能够表示成一个n元式 (x1,x2,xn)的形式。 显约束：对分量xi的取值限定。 隐约束：为满足问题的解而对不同分量之间施加的约束。 解空间：对于问题的一个实例，解向量满足显式约束条件的所有多 元组，构成了该实例的一个解空间。 注意：同一个问题可以有多种表示，有些表示方法更简单，所需表 示的状态空间更小（存储量少，搜索方法简单）。 例如，对于有n种可选物品的0-1背包问题，其解空间由长度 为n的0-1向量组成。n=3时的0-1背包问题用完全二叉树表示的解空间5 5二

4、、回溯法的基本思想 回溯法的基本步骤： (1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无 效搜索。 常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。 关于复杂性： 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空 间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如 果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法 所需的计算空间通常为O(h(n)。而显式地存储整个解空间则需要 O(2h(n)或O(h(n)!)内存空间。6 6生

5、成问题状态的基本方法 扩展结点：一个正在产生儿子的结点称为扩展结点 活结点：一个自身已生成但其儿子还没有全部生成的节点称 做活结点 死结点：一个所有儿子已经产生的结点称做死结点 深度优先的问题状态生成法：如果对一个扩展结点R，一旦 产生了它的一个儿子C，就把C当做新的扩展结点。在完成 对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成 扩展结点，继续生成R的下一个儿子（如果存在） 宽度优先的问题状态生成法：在一个扩展结点变成死结点之 前，它一直是扩展结点 回溯法：为了避免生成那些不可能产生最佳解的问题状态， 要不断地利用限界函数(bounding function)来处死那些实际上 不可能

6、产生所需解的活结点，以减少问题的计算量。具有限 界函数的深度优先生成法称为回溯法。7 7示例1 0-1背包问题 n=3, C=30, w=16, 15, 15, v=45, 25, 25 开始时，Cr=C=30，V=0，A为唯一活结点，也是当前扩展结点 扩展A，先到达B结点 Cr=Cr-w1=14，V=V+v1=45 此时A、B为活结点，B成为当前扩展结点 扩展B，先到达D Cr45，皆得到一个可行解x=(0,1,1)，V=50 L不可扩展，成为死结点，返回到F 再扩展F到达M M是叶结点，且2545 x=(0,1,1)Fw2=15，v2=25 Cr=15，V=25 M25n) output(

7、x); else for (int i=f(n,t);i0) if (f(n,t)n) output(x); else for (int i=0;in) output(x); else for (int i=t;i n) / 到达叶结点更新最优解bestx,bestw;return;r -= wi;if (cw + wi bestw) xi = 0; / 搜索右子树backtrack(i + 1); r += wi;17175.3 批处理作业调度一、问题描述 二、实例分析 三、算法描述1818一、问题描述给定n个作业的集合J1,J2,Jn。每个作业 必须先由机器1处理，然后由机器2处理。作 业

8、Ji需要机器j的处理时间为tji。对于一个确 定的作业调度，设Fji是作业i在机器j上完成处 理的时间。所有作业在机器2上完成处理的时 间和称为该作业调度的完成时间和。 批处理作业调度问题要求对于给定的n个作业 ，制定最佳作业调度方案，使其完成时间和 达到最小。1919二、实例分析这3个作业的6种可能的调度方案是1,2,3； 1,3,2；2,1,3；2,3,1；3,1,2；3,2,1； 它们所相应的完成时间和分别是19，18，20 ，21，19，19。 最佳调度方案是1,3,2，其完成时间和为18。tji机器1机器2 作业121 作业231 作业3232020三、算法描述void Flowsh

9、op:Backtrack(int i) if (i n) for (int j = 1; j f1)?f2i-1:f1)+Mxj2;f+=f2i;if (f half)|(t*(t-1)/2-counthalf) return;if (tn) sum+;elsefor (int i=0;in) sum+;elsefor (int i=1;i Typep Knap:Bound(int i) / 计算上界Typew cleft = c - cw; / 剩余容量Typep b = cp;/ 以物品单位重量价值递减序装入物品while (i n) / 到达叶结点for (int j = 1; j be

10、stn) / 进入右子树xi = 0;Backtrack(i+1); 3434四、进一步改进选择合适的搜索顺序，可以使得上界函数更 有效的发挥作用。例如在搜索之前可以将顶 点按度从小到大排序。这在某种意义上相当 于给回溯法加入了启发性。 定义Si=vi,vi+1,.,vn，依次求出Sn,Sn-1,.,S1的 解。从而得到一个更精确的上界函数，若 cn+Sin) sum+;for (int i=1; in) Compute();elsefor (int j = t; j temp) temp=valuex;return temp; void Circle:Compute(void) / 计算当前

11、圆排列的长度float low=0,high=0;for (int i=1;ihigh) high=xi+ri;if (high-lowmin) min=high-low; 4444三、算法改进上述算法尚有许多改进的余地。例如，象 1,2,n-1,n和n,n-1, ,2,1这种互为镜像的排 列具有相同的圆排列长度，只计算一个就够 了，可减少约一半的计算量。 另一方面，如果所给的n个圆中有k个圆有相 同的半径，则这k个圆产生的k!个完全相同的 圆排列，只计算一个就够了。 45455.11 电路板排列问题一、问题描述 二、算法设计 三、算法描述 四、复杂性分析4646一、问题描述设B=1,2,n是

12、n块电路板的集合。集合 L=N1,N2,Nm是这n块电路板的m个连接 块。其中每个连接块Ni是B的一个子集，且Ni 中的电路板用一根导线连接在一起。不同的 连接快可能包含相同的电路板。 设x是n块电路板的一个排列，则电路板的排 列密度Density(x)定义为跨越相邻电路板插槽 的最大连线数。 电路板排列问题要求度与给定的电路板连接 条件(连接块)，确定电路板的最佳排列，使其 具有最小密度。4747二、算法设计问题空间：排列树4848三、算法描述P152-1544949四、复杂性分析每个结点处Backtrack函数的计算时间：O(m) 结点数：O(n!) 总的计算时间：O(mn!)50505.

13、12 连续邮资问题本节要点 回顾回溯法的基本思想 连续邮资问题描述 问题分析 算法设计5151一、回溯法的基本思想1、确定问题的解空间 子集树问题：装载问题、符号三角形问题、0-1背包问题 、最大团问题 排列树问题：批处理作业调度、n后问题、旅行售货员问 题、圆排列问题、电路板排列问题 其他：图的m着色问题 2、找出适当的剪枝函数 约束函数 限界函数 3、以深度优先的方式搜索解空间 递归回溯 迭代回溯5252二、问题描述假设国家发行了n种不同面值的邮票，并且规定每张 信封上最多只允许贴m张邮票。连续邮资问题要求 对于给定的n和m的值，给出邮票面值的最佳设计， 在1张信封上可贴出从邮资1开始，增

14、量为1的最大连 续邮资区间。(NOIP99) 例如，当n=2、m=3时，如果面值分别为1、4，则在 l-6之间的每一个邮资值都能得到(当然还有8、9和 12)；如果面值分别为1、3，则在1-7之间的每一个 邮资值都能得到。可以验证当n=2、m=3时，7就是 可以得到连续的邮资最大值，面值为l、3。 又如，当n=5和m=4时，面值为(1,3,11,15,32)的5种 邮票可以贴出邮资的最大连续邮资区间是1到70。5353三、问题分析 基本思路：搜索所有可行解，找出最大连续邮资区间的方案 解向量：用n元组x1:n表示n种不同的邮票面值，并约定它 们从小到大排列。x1=1是唯一的选择。 可行性约束函

15、数：已选定x1:i-1，最大连续邮资区间是1r ，接下来xi的可取值范围是xi-1+1r+1。 如何确定r的值：计算X1:i的最大连续邮资区间在本算法中 被频繁使用到，因此势必要找到一个高效的方法。考虑到直 接递归的求解复杂度太高，我们不妨尝试计算用不超过m张 面值为x1:i的邮票贴出邮资k所需的最少邮票数yk。通过 yk可以很快推出r的值。事实上，yk可以通过递推在O(n) 时间内解决： for (int j=0; j= xi-2*(m-1);j+) if (yjm) for (int k=1;k=m-yj;k+) if (yj+kyj+xi-1*k) yj+xi-1*k=yj+k; while (yrmaxint) r+;5454四、算法设计P155-15655555.13 回溯法的效率分析本节要点： 一、影响回溯算法效率的因素 二、重排原理 三、回溯法的效率 四、概率方法5656一、影响回溯算法效率的因素通过前面具体实例的讨论容易看出，回溯算法的效 率在很大程度上依赖于