回溯法求装载问题_物联1301班_刘悦_201308080112

算法分析与设计实验报告第X次实验姓名刘悦学号201308080112班级物联1301班时间12.12上午地点工训楼C栋309实验名称回溯算法实验（求装载问题）实验目的通过上机实验，要求掌握回溯算法的问题描述、算法设计思想、程序设计。实验原理使用递归实现回溯，构建一颗子集树。①首先将第一艘轮船尽可能装满。②然后将剩余的集装箱装上第二艘轮船。③若可以将剩余的集装箱全部装上第二艘轮船，则可以将所有集装箱装上船；否则就不可以装上船。实验步骤①先将集装箱装上第一艘轮船。②首先是将第一个集装箱装上，然后第二个集装箱，第三个集装箱……③当到某个集装箱发现无法装入，那就回溯至前面一个集装箱，不将它装上轮船，之后再重复前面的过程。④当到达叶结点的时候，比较当前的解是不是要比之前的最优解更好。⑤若当前的解比之前的最优解要好，就用当前的解更新最优解。⑥搜索完所有的情况结束。⑦需要注意的一点是，若将剩余的集装箱都装上轮船求得的载重量小于当前最优载重量,那就没有必要搜素右子树。发生剪枝。关键代码/*=================================================================定义Loading类来存储集装箱的信息。=================================================================*/classLoading{friendfloatMaxLoading(float[],float,int,int[]);private:voidBacktrack(inti);intn;//集装箱数int*x;//当前解int*bestx;//当前最优解float*w;//集装箱重量数组floatc;//第一艘轮船的载重量floatcw;//当前载重量floatbestw;//当前最优载重量floatr;//剩余集装箱的重量};/*=================================================================Backtrack函数求最优载重量。进行子集树的搜索，首先会判断是否到达叶结点，如果到达叶结点就判断是否更新最优解。之后判断是否进行左子树的搜素,左子树为将当前的集装箱装上轮船。然后判断是否进行右子树的搜索,这里有一个剪枝策略。进入左子树/右子树之后调用本身进行递归。剪枝策略：将剩余的集装箱都装上轮船求得的载重量小于当前最优载重量,那就没有必要搜素右子树。*******************************************************************n表示集装箱数。x数组表示当前解，x[i]表示集装箱i是否装上轮船。bestx数组表示当前最优解。w数组表示集装箱重量,w[i]表示集装箱i的重量。c表示第1艘轮船的载重量。cw表示当前载重量。bestw表示当前最优载重量。r表示剩余集装箱的重量。=================================================================*/voidLoading::Backtrack(inti){//搜索第i层结点if(in){//搜索至叶结点，其相应载重量为cw//若cwbestw,表示当前解优于当前最优解,更新此时的bestw和bestx的值if(cwbestw){for(intj=1;j=n;j++)//更新bestxbestx[j]=x[j];bestw=cw;//更新bestw}return;}//搜索子树r-=w[i];//搜索左子树//当前的集装箱可以装上轮船时,就进入左子树if(cw+w[i]=c){x[i]=1;//x[i]=1,表示第i个集装箱装上了轮船cw+=w[i];//当前载重量加上这个集装箱Backtrack(i+1);cw-=w[i];//递归完成即回到上层结点,此时需要将当前载重量减去这个集装箱}//搜索右子树//如果将剩余的集装箱全部装上轮船求得的载重量都要小于当前最优载重量,那就没有必要搜素右子树if(cw+rbestw){x[i]=0;//x[i]=0,表示第i个集装箱不装上了轮船Backtrack(i+1);}r+=w[i];}/*=================================================================MaxLoading函数进行初始化，并求得最优载重量返回。主要为调用Backtrack函数。*******************************************************************n表示集装箱数。x数组表示当前解，x[i]表示集装箱i是否装上轮船。bestx数组表示当前最优解。w数组表示集装箱重量,w[i]表示集装箱i的重量。c表示第1艘轮船的载重量。cw表示当前载重量。bestw表示当前最优载重量。r表示剩余集装箱的重量。=================================================================*/floatMaxLoading(floatw[],floatc,intn,intbestx[]){//返回最优载重量LoadingX;//动态分配内存X.x=newint[n+1];//初始化XX.w=w;X.c=c;X.n=n;X.bestx=bestx;X.bestw=0;X.cw=0;X.r=0;for(inti=1;i=n;i++)X.r+=w[i];//计算最优载重量X.Backtrack(1);//释放动态分配的内存delete[]X.x;returnX.bestw;}测试结果①可以将集装箱全部装上轮船的情况：②不可以将集装箱全部装上轮船的情况：③可以看到上面的输出结果符合我们的要求，与我们的期望值一样。④还可以看到这个算法的时间比较小，性能比较好。实验心得这个算法解决的问题与之前的最优装载问题不太一样。最优装载问题是要使尽可能多的集装箱装上轮船，而这个装载问题是要看能不能将所有集装箱装上两艘船。其实使用贪心算法也是可以实现装载问题的，但是这里为了巩固回溯法，所以使用回溯法实现。因为要使用递归，所以这个代码自己真的要写起来还是感觉蛮难的，但是书上给了部分实现，对着代码进行理解也不是很困难。比较重要的一点是要自附录：完整代码#includeiostream#includetime.h#includeiomanip#includestdlib.husingnamespacestd;/*============================================================================定义Loading类来存储集装箱的信息。============================================================================*/classLoading{friendfloatMaxLoading(float[],float,int,int[]);private:voidBacktrack(inti);intn;//集装箱数int*x;//当前解int*bestx;//当前最优解float*w;//集装箱重量数组floatc;//第一艘轮船的载重量floatcw;//当前载重量floatbestw;//当前最优载重量floatr;//剩余集装箱的重量};/*============================================================================己心中有一棵子集树，不然理解起来会很难。这棵子集树就是一个二叉树，左子树代表将此集装箱装上轮船，右子树代表不将此集装箱装上轮船。刚开始由于无法理解子集树，所以虽然知道了回溯法的算法思想，但是这个装载问题的实现却总是存在问题。搞清楚子集树之后，整个世界豁然开朗，装载问题的算法实现瞬间就明朗起来了。这个装载问题是NP问题，所以还不能在多项式时间内解决。与贪心算法相比，使用回溯法的时间复杂度要差一些，是指数级的。当然了，装载问题也可以使用动态规划算法实现，但是在某些情况下，回溯法实现要由于动态规划算法。因为动态规划算法的时间复杂度为O(min{c1,2^n})，此回溯法的实现的时间复杂度为O(2^n)。通过这次实验代码的编写，进一步熟悉了回溯法，特别是递归实现回溯。相信通过以后的学习，我一定可以对回溯法有一个更好的认识。实验得分助教签名Backtrack函数求最优载重量。进行子集树的搜索，首先会判断是否到达叶结点，如果到达叶结点就判断是否更新最优解。之后判断是否进行左子树的搜素,左子树为将当前的集装箱装上轮船。然后判断是否进行右子树的搜索,这里有一个剪枝策略。进入左子树/右子树之后调用本身进行递归。剪枝策略：将剩余的集装箱都装上轮船求得的载重量小于当前最优载重量,那就没有必要搜素右子树。******************************************************************************n表示集装箱数。x数组表示当前解，x[i]表示集装箱i是否装上轮船。bestx数组表示当前最优解。w数组表示集装箱重量,w[i]表示集装箱i的重量。c表示第1艘轮船的载重量。cw表示当前载重量。bestw表示当前最优载重量。r表示剩余集装箱的重量。============================================================================*/voidLoading::Backtrack(inti){//搜索第i层结点if(in){//搜索至叶结点，其相应载重量为cw//若cwbestw,表示当前解优于当前最优解,更新此时的bestw和bestx的值if(cwbestw){for(intj=1;j=n;j++)//更新bestxbestx[j]=x[j];bestw=cw;//更新bestw}return;}//搜索子树r-=w[i];//搜索左子树//当前的集装箱可以装上轮船时,就进入左子树if(cw+w[i]=c){x[i]=1;//x[i]=1,表示第i个集装箱装上了轮船cw+=w[i];//当前载重量加上这个集装箱Backtrack(i+1);cw-=w[i];//递归完成即回到上层结点,此时需要将当前载重量减去这个集装箱}//搜索右子树//如果将剩余的集装箱全部装上轮船求得的载重量都要小于当前最优载重量,那就没有必要搜素右子树if(cw+rbestw){x[i]=0;//x[i]=0,表示第i个集装箱不装上了轮船Backtrack(i+1);}r+=w[i];}/*============================================================================MaxLoading函数进行初始化，并求得最优载重量返回。主要为调用Backtrack函数。******************************************************************************n表示集装箱数。x数组表示当前解，x[i]表示集装箱i是否装上轮船。bestx数组表示当前最优解。w数组表示集装箱重量,w[i]表示集装箱i的重量。c表示第1艘轮船的载重量。cw表示当前载重量。bestw表示当前最优载重量。r表示剩余集装箱的重量。============================================================================*/floatMaxLoading(floatw[],floatc,intn,int