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

回溯法求解装载问题一、方法一般原理回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si，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（ji）元组（x1，x2，…，xj）一定也满足D中仅涉及到x1，x2，…，xj的所有约束，i=1，2，…，n。换句话说，只要存在0≤j≤n-1，使得（x1，x2，…，xj）违反D中仅涉及到x1，x2，…，xj的约束之一，则以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）一定也违反D中仅涉及到x1，x2，…，xi的一个约束，n≥ij。因此，对于约束集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，把在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，反之亦然。另外，对于任意的0≤i≤n-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中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀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的重量为wi，且211ccwnii，要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，请给出该方案。三、由原理得到的算法、算法的复杂度、改进1、可得算法回溯法解装载问题时，用子集树表示解空间最合适。voidBacktrack(intt){if(tn)Output(x);else{for(inti=0;iz;i++){x[t]=i;if(Constraint(t)&&Bound(t))Backtrack(t+1);}}}Maxloading调用递归函数backtrack实现回溯。Backtrack（i）搜索子集树第i层子树。in时，搜索至叶节点，若装载量bestw，更新bestw。当i=n时，扩展节点Z是子集树内部节点。左儿子节点当cw+w[i]=c时进入左子树，对左子树递归搜索。右儿子节点表示x[i]=0的情形。2、时间复杂度Backtrack动态的生成解空间树。每个节点花费O（1）时间。Backtrack执行时间复杂度为O(2n)。另外Backtrack还需要额外O(n)递归栈空间。3、可能的改进可以再加入一个上界函数来剪去已经不含最优解的子树。设Z是解空间树第i层上的一个当前扩展结点，curw是当前载重量，maxw是已经得到的最优载重量，如果能在当前结点确定curw+剩下的所有载重量≤maxw则可以剪去些子树。所以可以引入一个变量r表示剩余的所有载重量。虽然改进后的算法时间复杂度不变，但是平均情况下改进后算法检查结点数较少。进一步改进：（1）首先运行只计算最优值算法，计算最优装载量，再运行backtrack算法，并在算法中将bestw置为W，在首次到叶节点处终止。（2）在算法中动态更新bestw。每当回溯一层，将x[i]存入bestx[i].从而算法更新bestx所需时间为O(2n)。四、算法实现intBacktrack(inti)//搜索第i层节点{intj_index;//如果到达叶结点，则判断当前的cw，如果比前面得到的最优解bestw好，则替换原最优解。if(in){if(cwbestw){for(j_index=1;j_index=n;j_index++)bestx[j_index]=x[j_index];bestw=cw;}return1;}//搜索子树r-=w[i];if(cw+w[i]=c)//搜索左子树,如果当前剩余空间可以放下当前物品也就是，cw+w[i]=c{x[i]=1;cw+=w[i];//把当前载重cw+=w[i]Backtrack(i+1);//递归访问其左子树，Backtrack(i+1)cw-=w[i];//访问结束，回到调用点，cw-=w[i]}if(cw+rbestw)//搜索右子树{x[i]=0;Backtrack(i+1);}r+=w[i];}intmaxloading(intmu[],intc,intn,int*mx){loadingx;x.w=mu;x.x=mx;x.c=c;x.n=n;x.bestw=0;x.cw=0;x.Backtrack(1);returnx.bestw;}五、总结由此，我们可以总结出回溯法的一般步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。通过DFS思想完成回溯，完整过程如下：(1)设置初始化的方案（给变量赋初值，读入已知数据等）。(2)变换方式去试探，若全部试完则转(7)。(3)判断此法是否成功（通过约束函数），不成功则转(2)。(4)试探成功则前进一步再试探。(5)正确方案还未找到则转(2)。(6)已找到一种方案则记录并打印。(7)退回一步（回溯），若未退到头则转(2)。(8)已退到头则结束或打印无解。可以看出，回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯法，因为它花费的时间比较长。六、附录（源码）#includestdlib.h#includestdio.h#includeiostream.htypedefintStatus;typedefintType;intn=0;//集装箱数Type*x=(Type*)malloc((50)*sizeof(Type));//当前解Type*bestx=(Type*)malloc((50)*sizeof(Type));//当前最优解Typec=0,//第一艘轮船的载重量cw=0,//当前载重量bestw=0,//当前最优载重量r=0,*w=(Type*)malloc((50)*sizeof(Type));//集装箱重量数组intBacktrack(inti)//搜索第i层节点{intj_index;//如果到达叶结点，则判断当前的cw，如果比前面得到的最优解bestw好，则替换原最优解。if(in){if(cwbestw){for(j_index=1;j_index=n;j_index++)bestx[j_index]=x[j_index];bestw=cw;}return1;}//搜索自树r-=w[i];if(cw+w[i]=c)//搜索左子树,如果当前剩余空间可以放下当前物品也就是，cw+w[i]=c{x[i]=1;cw+=w[i];//把当前载重cw+=w[i]Backtrack(i+1);//递归访问其左子树，Backtrack(i+1)cw-=w[i];//访问结束，回到调用点，cw-=w[i]}if(cw+rbestw)//搜索右子树{x[i]=0;Backtrack(i+1);}r+=w[i];}Type*Initiate(){intindex=1;printf(输入集装箱个数：);scanf(%d,&n);printf(输入轮船载重量：);scanf(%d,&c);while(index=n)//数组从1号单元开始存储{printf(输入集装箱%d的重量：,index);scanf(%d,&w[index]);index++;}bestw=0;cw=0;r=0;for(index=1;index=n;index++)r+=w[index];//初始时r为全体物品的重量和printf(n=%dc=%dcw=%dbestw=%dr=%d\n,n,c,cw,bestw,r);for(index=1;index=n;index++){printf(w[%d]=%d,index,w[index]);}printf(\n);returnw;}intmain(){inti;Initiate();//计算最优载重量Backtrack(1);for(i=1;i=n;i++){printf(%d,w[i]);printf(%d\n,bestx[i]);}returnbestw;}