数据结构回溯法求装载问题

1、数据结构与算法分析回溯法求解装载问题回溯法求解装载问题一、方法一般原理基本思想：在回溯法中,每次扩大当前部分解时，都面临一个可选的状态集合，新的部分解救通过在该集合中进行选择结构而成的。这样的状态集合，结构上是一颗多叉树，每个树结点代表一个可能的部分解，她的儿子是在他的基础上生成其他部分解。树根为初始状态。这样的状态集合，称为状态空间树。回溯法对任一解的生成，一般都采用逐步扩大解的方式。每前进一部，都试图在当前部分解的基础上扩大该部分解。它在问题的状态空间树中，从开始结点（根结点）出发，一深度优先搜索整个状态空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前扩展结点处，搜索向纵深方

2、向移动一个新的结点。这个新的结点为新的活结点，并成为当前的中结点。如果在当前扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时，应往回移动（回溯）至最近的活结点处，并使这个活结点成为当前扩展结点。回溯法以这种工作方式递归地在状态空间中搜索，直到找到所要求的解或解空间中以无活结点时为止。回溯法与穷举法有某些联系，他们都是基于试探。穷举法要将一个解的各个部分全都生成后，才检查是否满足条件，若不满足，则直接放弃该完整解、然后再尝试另一个可能的完整解，没有沿着一个可能的完整解的各个部分逐步回退生成解的过程。而对于回溯法，一个解的各个部分是逐步生成的，当发现当前生成的某部分不满足约束条件

3、，就放弃该部所做的工作，退到上一步进行新的尝试，而不是放弃整个解重来。一般来说，回溯法要比穷举法效率高一些。可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（1， 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的一个解。但显然，

4、其计算量是相当大的。我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1， x2， xi）满足D中仅涉及到x1， x2， xi的所有约束意味着j（jj。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1， x2， xj）违反D中仅涉及x1， x2， xj的一个约束，就可以肯定，以（x1， x2， xj）为前缀的任何n元组（x1， x2， xj， xj+1， xn）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把

5、在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树，它可以这样构造：设Si中的元素可排成xi (1)， xi (2)， xi (mi-1)， |Si| =mi， i=1， 2， n。从根开始，让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边，按从左到右的次序，分别带权xi+1 (1)， xi+1 (2)， xi+1 (mi)， i=0， 1， 2， n-1。照这种构造方式， E中的一个n元组（x1， x2， xn）对应T中的一个叶子结点， T的根到这个叶子结点的路径上依次的n条边的权分别为x1， x2， xn，反之亦然。另外，对于任意的0in-1， E中

6、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中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组（x1i）、前缀2元组（x1， x2）、，前缀I元组（x1， x2， xi），直到

7、i=n为止。 在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。二、描述问题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为，且，要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，请给出该方案。三、由原理得到的算法、算法的复杂度、改进 1、 可得算法回溯法解装载问题时，用子集树表示解空间最合适。 void Backtrack(int t) if(t

8、n) Output(x); else for(int i=0; in时，搜索至叶节点，若装载量bestw，更新bestw。 当i=n时，扩展节点Z是子集树内部节点。左儿子节点当cw+win) 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 bestw)/搜索右子树 xi=0; Backtrack(i+1); r+=wi; int maxloa

9、ding(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)判断此法

10、是否成功（通过约束函数），不成功则转(2)。(4)试探成功则前进一步再试探。 (5)正确方案还未找到则转(2)。(6)已找到一种方案则记录并打印。 (7)退回一步（回溯），若未退到头则转(2)。(8)已退到头则结束或打印无解。可以看出，回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯法，因为它花费的时间比较长。 附录（源码） #include #include #include typedef int Status; typedef int Type; int n=0; /集装箱数 Ty

11、pe *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; /如果到达叶结点，则判断当前的cw，如果比前面得到的最优解bestw好，则替换原最优解。 if(in) if(cwbestw) f

12、or(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 bestw)/搜索右子树 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=%dn,n,c,cw,bestw,r); for(index=1;index=n;index+) printf(w%d=%d ,index,windex); printf(n); return