算法分析设计回溯法求解装载问题实验报告

1、算法分析设计回溯法求解装载问题实验报告 算法分析设计回溯法求解装载问题,完善版报告 回溯法求解装载问题 一、方法一般原理 回溯法也称为摸索法，该方法首先临时放弃关于问题规模大小的限制，并将问题的候选解按某种挨次逐一枚举和检验。当发觉当前候选解不行能是解时，就选择下一个候选解；如果当前候选解除了还不满足问题规模要求外，满足全部其他要求时，连续扩大当前候选解的规模，并连续摸索。假如当前候选解满足包括问题规模在内的全部要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，查找下一个候选解的过程称为回溯。扩大当前候选解的规模，以连续摸索的过程称为向前摸索。 可用回溯法求解的问题P，通常要能表达

2、为：对于已知的由n元组（x1，x2，xn）组成的一个状态空间E=（x1，x2，xn）xiSi ，i=1，2，n，给定关于n元组中的一个重量的一个约束集D，要求E中满足D的全部约束条件的全部n元组。其中Si是重量xi的定义域，且 |Si| 有限，i=1，2，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。 解问题P的最俭朴的方法就是枚举法，即对E中的全部n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但明显，其计算量是相当大的。 我们发觉，对于很多问题，所给定的约束集D具有完备性，即i元组（x1，x2，xi）满足D中仅涉及到x1，x2，xi的全部约束意味着j（

3、ji）元组（x1，x2，xj）肯定也满足D中仅涉及到x1，x2，xj的全部约束，i=1，2，n。换句话说，只要存在0jn-1，使得（x1，x2，xj）违反D中仅涉及到x1，x2，xj的约束之一，则以（x1，x2，xj）为前缀的任何n元组（x1，x2，xj，xj+1，xn）肯定也违反D中仅涉及到x1，x2，xi的一个约束，nij。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1，x2，xj）违反D中仅涉及x1，x2，xj的一个约束，就可以确定，以（x1，x2，xj）为前缀的任何n元组（x1，x2，xj，xj+1，xn）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正

4、是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。 回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的全部解转化为在T中搜索问题P的全部解。树T类似于检索树，它可以这样构造： 设Si中的元素可排成xi ，xi ，xi (1)(2)(mi)(1)(2)(mi-1) ，|Si| =mi，i=1，2，n。从根开头，让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边，按从左到右的次序，分别带权xi+1 ，xi+1 ，xi+1 ，i=0，1，2，n-1。照这种构造方式，E中的一个n元组（x1，x2，xn）对应于T中的一个叶子结

5、点，T的根到这个叶子结点的路径上依次的n条边的权分别为x1，x2，xn，反之亦然。另外，对于任意的0in-1，E中n元组（x1，x2，xn）的一个前缀I元组（x1，x2，xi）对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为x1，x2，xi，反之亦然。格外，E中的任意一个n元组的空前缀（），对应于T的根。 因而，在E中查找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该 算法分析设计回溯法求解装载问题,完善版报告 叶子结点的路径上依次的n条边相应带的n个权x1，x2，xn满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根动身，

6、按深度优先的策略逐步深化，即依次搜索满足约束条件的前缀1元组（x1i）、前缀2元组（x1，x2）、，前缀I元组（x1，x2，xi），直到i=n为止。 在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。 二、描述问题 有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为n wi ，且 i 1艘轮船。假如有，请给出该方案。 wi c1 c2 ，要求确定是否有一个合理的装载方案可

7、将这n个集装箱装上这2 三、由原理得到的算法、算法的简单度、改进 1、 可得算法 回溯法解装载问题时，用子集树表示解空间最合适。 void Backtrack(int t) if(tn) Output(x); else for(int i=0; iz; i+) xt = i; if(Constraint(t) Bound(t) Backtrack(t+1); Maxloading调用递归函数backtrack实现回溯。Backtrack（i）搜索子集树第i层子树。in时，搜索至叶节点，若装载量bestw，更新bestw。 当i=n时，扩展节点Z是子集树内部节点。左儿子节点当cw+wi=c时进入

8、左子树，对左子树递归搜索。右儿子节点表示xi=0的情形。 2、时间简单度 Backtrack动态的生成解空间树。每个节点花费O（1）时间。Backtrack执行时间简单度为nO(2)。另外Backtrack还需要额外O(n)递归栈空间。 3、可能的改进 算法分析设计回溯法求解装载问题,完善版报告 可以再加入一个上界函数来剪去已经不含最优解的子树。设Z是解空间树第i层上的一个当前扩展结点，curw是当前载重量，maxw是已经得到的最优载重量，假如能在当前结点确定curw+剩下的全部载重量 maxw 则可以剪去些子树。所以可以引入一个变量r表示剩余的全部载重量。虽然改进后的算法时间简单度不变，但是

9、平均状况下改进后算法检查 结点数较少。 进一步改进： （1） 首先运行只计算最优值算法，计算最优装载量，再运行backtrack算法，并在算法 中将bestw置为W，在首次到叶节点处终止。 （2） 在算法中动态更新bestw。每当回溯一层，将xi存入bestxi.从而算法更新bestx n所需时间为O(2)。 四、算法实现 int Backtrack(int i)/搜索第i层节点 int j_index; /假如到达叶结点，则推断当前的cw，假如比前面得到的最优解bestw好，则替换原最优解。 if(in) if(cwbestw) for(j_index=1; j_index=n; j_ind

10、ex+) bestxj_index=xj_index; bestw=cw; return 1; /搜索子树 r-=wi; if(cw+wi=c)/搜索左子树,假如当前剩余空间可以放下当前物品也就是， cw + w i = c xi=1; cw+=wi;/把当前载重 cw += w i Backtrack(i+1);/递归访问其左子树，Backtrack( i + 1 ) cw-=wi;/访问结束，回到调用点， cw - = w i if(cw+rbestw)/搜索右子树 算法分析设计回溯法求解装载问题,完善版报告 xi=0; Backtrack(i+1); r+=wi; int maxload

11、ing(int mu,int c,int n,int *mx) loading x; x.w=mu; x.x=mx; x.c=c; x.n=n; x.bestw=0; x.cw=0; x.Backtrack(1); return x.bestw; 五、总结 由此，我们可以总结出回溯法的一般步骤： （1）针对所给问题，定义问题的解空间； （2）确定易于搜索的解空间结构； （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避开无效搜索。 通过DFS思想完成回溯，完整过程如下： (1)设置初始化的方案（给变量赋初值，读入已知数据等）。 (2)变换方式去摸索，若全部试完则转(7)。 (3)推断此

12、法是否胜利（通过约束函数），不胜利则转(2)。 (4)摸索胜利则前进一步再摸索。 (5)正确方案还未找到则转(2)。 (6)已找到一种方案则记录并打印。 (7)退回一步（回溯），若未退到头则转(2)。 (8)已退到头则结束或打印无解。 可以看出，回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯法，由于它花费的时间比较长。 六、附录（源码） #includestdlib.h 算法分析设计回溯法求解装载问题,完善版报告 #includestdio.h #includeiostream.h t

13、ypedef int Status; typedef int Type; int n=0; /集装箱数 Type *x=(Type*)malloc(50)*sizeof(Type);/当前解 Type *bestx=(Type*)malloc(50)*sizeof(Type);/当前最优解 Type c=0, /第一艘轮船的载重量 cw=0, /当前载重量 bestw=0, /当前最优载重量 r=0, *w=(Type*)malloc(50)*sizeof(Type); /集装箱重量数组 int Backtrack(int i)/搜索第i层节点 int j_index; /假如到达叶结点，则推

14、断当前的cw，假如比前面得到的最优解bestw好，则替换原最优解。 if(in) if(cwbestw) for(j_index=1; j_index=n; j_index+) bestxj_index=xj_index; bestw=cw; return 1; /搜索自树 r-=wi; if(cw+wi=c)/搜索左子树,假如当前剩余空间可以放下当前物品也就是， cw + w i = c xi=1; cw+=wi;/把当前载重 cw += w i Backtrack(i+1);/递归访问其左子树，Backtrack( i + 1 ) cw-=wi;/访问结束，回到调用点， cw - = w

15、i if(cw+rbestw)/搜索右子树 xi=0; 算法分析设计回溯法求解装载问题,完善版报告 Backtrack(i+1); r+=wi; Type* Initiate() int index=1; printf(输入集装箱个数：); scanf(%d,n); printf(输入轮船载重量：); scanf(%d,c); while(index=n)/数组从1号单元开头存储 printf(输入集装箱%d的重量：,index); scanf(%d,windex); index+; bestw = 0; cw = 0; r = 0; for(index =1;index = n; index+) r += windex; /初始时r为全体物品的重量和 printf(n=%d c=%d cw=%d bestw=%d r=%