5回溯算法

《5回溯算法》由会员分享，可在线阅读，更多相关《5回溯算法（54页珍藏版）》请在金锄头文库上搜索。

1、第5章 回溯法,有许多问题，当需要找出它的解集或者要求回答什么 解是满足某些约束条件的最佳解时，往往要使用回溯法。 回溯法的基本做法是搜索，或是一种组织得井井有条 的，能避免不必要搜索的穷举式搜索法。这种方法适用于 解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，从根 结点出发搜索解空间树。算法搜索至解空间树的任意一点 时，先判断该结点是否包含问题的解。如果肯定不包含， 则跳过对该结点为根的子树的搜索，逐层向其祖先结点回 溯；否则，进入该子树，继续按深度优先策略搜索。,本章主要知识点： 5.1 回朔法的算法框架 5.2 装载问题 5.3 批处理作业调度 5.4 符号三角形

2、问题 5.5 n后问题 5.6 0-1背包问题 5.7 最大团问题 5.8 图的m着色问题 5.9 旅行售货员问题 5.10 圆排列问题 5.11 电路板排列问题 5.12 连续邮资问题 5.13 回朔法效率分析,5.1 回朔法的算法框架,5.1.1 问题的解空间,问题的解向量：回溯法希望一个问题的解能够表示成一个 n元式(x1,x2,xn)的形式。 显约束：对分量xi的取值限定。 隐约束：为满足问题的解而对不同分量之间施加的约束。 解空间：对于问题的一个实例，解向量满足显式 约束条件的所有多元组，构成了该实例的一个解 空间。,注意：同一个问题可以有多种表示，有些表示方法更 简单，所需表示的状

3、态空间更小（存储量少，搜索方法简 单）。,对于n=3的0-1背包问题，其解空间是一个深度为4的 满二叉数。,当w=16，15，15，p=45，25，25，c=30时，0-1 背包问题的解向量是： （0，1，1）,5.1.2 回朔法的基本思想,扩展结点: 一个正在产生儿 子的结点称为扩展结点。,活结点: 一个自身已生成但其 儿子还没有全部生成的节点称 做活结点。,死结点:一个所有儿子已经产生的结点称做死结点。,深度优先的问题状态生成法： 如果对一个扩展结点R，一旦 产生了它的一个儿子C，就把 C当做新的扩展结点。在完成 对子树C（以C为根的子树） 的穷尽搜索之后，将R重新变 成扩展结点，继续生成

4、R的下 一个儿子（如果存在）。,宽度优先的问题状态生成法：在一个扩展结点变成死结点 之前，它一直是扩展结点。,回溯法：为了避免生成那些 不可能产生最佳解的问题状 态，要不断地利用限界函数 (bounding function)来处死 那些实际上不可能产生所需 解的活结点，以减少问题的 计算量。具有限界函数的深 度优先生成法称为回溯法。,(1) 针对所给问题，定义问题的解空间； (2) 确定易于搜索的解空间结构； (3) 以深度优先方式搜索解空间，并在搜索过程中用剪枝函 数避免无效搜索。,常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。,用回溯法解

5、题的一个显著特征是在搜索过程中动态产 生问题的解空间。在任何时刻，算法只保存从根结点到当 前扩展结点的路径。如果解空间树中从根结点到叶结点的 最长路径的长度为h(n)，则回溯法所需的计算空间通常为 O(h(n)。而显式地存储整个解空间则需要O(2h(n)或 O(h(n)!)内存空间。,例如: 对于n=3的0-1背包问题，当w=16，15，15， p=45，25，25，c=30时，该0-1背包问题的最优解向量是 x=（0，1，1）。其解空间是一个深度为4的满二叉数。,各叶子所代表的解向量是,结点H：x=（1，1，1）,结点I： x=（1，1，0）,结点J： x=（1，0，1）,结点K：x=（1，

6、0，0）,结点L： x=（0，1，1）,结点M： x=（0，1，0）,结点N： x=（0，0，1）,结点O： x=（0，0，0）,当扩展结点是E时，活结点有A, B,E; 死结点有D,H,I。,当扩展结点是F时，活结点有A, C,F; 死结点有B,D,H,I,E,J,K。,例如: 对于带权图G，在 图G中求费用最小的周游 路线，其解空间是如右图 所示的树。它的每个叶子 代表了一个解向量。,含有n个顶点的无向完全图有n(n-1)/2条边。由于是完 全图，所以从指定的顶点出发的不同周游路线有(n-1)!条。,回溯法就是在解空间数上一个一个地搜索出每一个解 向量，并在一定的意义下，从这些解向量中通过

7、计算，求 出最优解向量。,对于特定的问题，其解空间树往往特别大，包含的叶 子非常多，因此，剪枝函数对回溯算法的优化非常重要。,5.1.3 递归回朔,回溯法对解空间作深度优先搜索，因此，在一般情况 下用递归方法实现回溯法。,void backtrack (int t) /对于第t层的一个扩展结点 if (tn) output(x); /到达一个叶子，输出该叶子所表示的解向量 else /没有到达一个叶子 for (int i=f(n,t);i=g(n,t);i+) /对于当前扩展结点的第i个孩子 xt=h(i); /求该孩子所表示的部分解向量 if (constraint(t) /生成该孩子，并

8、将其作为新的当前结点 ,5.1.4 迭代回朔,采用树的非递归深度优先遍历算法， 可将回溯法表示为一个非递归迭代过程。,void iterativeBacktrack () int t=1; /对于第t层的一个扩展结点 while (t0) /当该扩展结点存在时 if (f(n,t)=g(n,t) /如果扩展结点有孩子 for (int i=f(n,t);i=g(n,t);i+) /考察其第i个孩子 xt=h(i); /求该孩子所表示的部分解向量 if (constraint(t) /回溯 ,5.1.5 子集树和排列树,遍历子集树需O(2n)计算时间,遍历排列树需要O(n!)计算时间,void

9、backtrack (int t) if (tn) output(x); else for (int i=0;i=1;i+) xt=i; if (legal(t) backtrack(t+1); ,void backtrack (int t) if (tn) output(x); else for (int i=t;i=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); swap(xt, xi); ,5.2 装载问题,1. 问题描述,有一批共n个集装箱要装上2艘载 重量分别为c1和c2的轮船，其中集装 箱i的重量为wi，且,装载问题要求确定是否有一

10、个合理的装载方案 可将这个集装箱装上这2艘轮船。如果有，找出一 种装载方案。 容易证明，如果一个给定装载问题有解，则采 用下面的策略可得到最优装载方案。 (1) 首先将第一艘轮船尽可能装满； (2) 将剩余的集装箱装上第二艘轮船。 将第一艘轮船尽可能装满等价于选取全体集装 箱的一个子集，使该子集中集装箱重量和最接近。 于是，装载问题等价于以下特殊的0-1背包问题。,用回溯法设计解装载问题的O(2n)计算时间算法。在某些情况下该算法优于动态规划算法。,public class Loading static int n; /集装箱个数 static int w; /各个集装箱的重量 static

11、int c; /第1艘船的载重量 static int cw; /当前扩展结点表示的装上船的集装箱重量总和 static int bestw; /当前所求到的所有解中的最优值 public static int maxLoading(int ww, int cc) n=ww.length-1; /初始化 w=ww; c=cc; cw=0; bestw=0; backtrack(1); /从第1个集装箱开始考虑 return bestw; /返回最优值 ,2. 算法设计,cw始终是当前扩展结点的所表示的上第一艘船的集装箱的重量和,本算法所求的bestw是上第一艘船的集装箱的重量和的最优值,pri

12、vate static void backtrack(int i) /对于第i个集装箱 if(in) /如果到达叶子 if(cwbestw) /如果该叶子代表的解优于当前最优解 bestw=cw; /把该叶子代表的解作为当前最优解 return; if(cw+wi=c) /如果第i个集装箱可以上船 cw+=wi; backtrack(i+1); /则生成扩展结点的左孩子 cw-=wi; /子树搜索完毕，回溯 backtrack(i+1); /否则生成扩展结点的右孩子 ,public class Loading static int n; /集装箱个数 static int w; /各个集装箱的

13、重量 static int c; /第1艘船的载重量 static int cw; /当前扩展结点表示的装上船的集装箱重量总和 static int bestw; /当前所求到的所有解中的最优值 static int r; /r是当前码头上剩余集装箱重量和 public static int maxLoading(int ww, int cc) n=ww.length-1; / 初始化 w=ww; c=cc; cw=0; bestw=0; for(int i=1; i=n; i+) /计算当前还没有考虑的集装箱的重量和 r+=wi; backtrack(1); /从第1个集装箱开始考虑 ret

14、urn bestw; /返回最优值 ,3. 上界函数,private static void backtrack(int i) if(in) /如果到达叶子 if(cwbestw) /如果该叶子代表的解优于当前最优解 bestw=cw; /把该叶子代表的解作为当前最优解 return; r=-wi; /第i个集装箱已经被考虑 if(cw+wibestw) /如果扩展结点的右子树中可能有更优的解 backtrack(i+1); /则生成扩展结点的右孩子 r+=wi; /修复r ,public class Loading static int n; static int w; static int

15、 c; static int cw; static int bestw; static int r; static int x; static int bestx; public static int maxLoading(int ww, int cc, int xx) n=ww.length-1; w=ww; c=cc; cw=0; bestw=0; x=new intn+1; bestx=xx; for(int i=1; i=n; i+) r+=wi; backtrack(1); return bestw; ,4. 构造最优解,private static void backtrack(int i) if(in) if(cwbestw) for(int j=1; jbestw) xi=0; backtrack(i+1); r+=wi; ,public static int maxLoading(int w, int c, int bestx) int i=1; n=ww.length-1; int x=new intn+1; int bestx=0; int cw=0; int r=0; for(int j=1; j=n; j+) r+=wj; while(1) while(i=n ,5. 迭代回溯,if(