实验指导书-回溯法

《实验指导书-回溯法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法设计与分析实验指导书（计算机科学与技术系）编写兰州交通大学电子与信息工程学院2018年3月实验5回溯法实验三回溯法一、实验目的(1)回溯法是一种通用的解题法，通过本次实验，掌握回溯法求解问题的一般步骤，掌握如何定义问题的解空间，并将解空间组织为解空间树并掌握如何在解空间树中进行深度优先搜索；利用回溯法解问题时一般按以下三步骤：1)定义问题的解空间；2)确定易于搜索的解空间结构；3)以深度优先策略搜索解空间，并在搜索过程中用剪枝函数避免无效搜索；(2)通过实验掌握回溯法思想和方法；(3)培养学牛的动手能力。二、实验仪器设备(1)计算机；(

2、2)C++编译调试环境。三、实验原理掌握将算法转换为可运行程序的步骤。(1)装载问题。(2)0-1背包问题。(3)TSP问题。(4)八皇后问题。五、实验步骤5.1装载问题(1)问题描述：一批集装箱共n个要装上2艘载重量分别为cl和c2的轮船，其中集装箱i的重量为Wi且W1+W2+……+Wn＜二cl+c2;试确定一个合理的装载方案使这n个集装箱装上这两艘轮船。(2)求解思路：装载问题如果有解，那么相当于将一艘轮船尽可能的装满，那么装载问题转换为一个特殊的(所有物品单位价值均为1)的0・1背包问题，解空间树为子集树。冋溯的过程可以使用约束函数(

3、轮船1是否能装下选定的集装箱)以及限界函数(装入轮船1的集装箱重量之和+待选择的集装箱重量之和与当前最优值的对比)进行剪枝。回溯的方法有递归回溯与迭代回溯。具体代码如下：#include〈iostream>usingnamespacestd;templateTMaxLoading(Tw[],Tc,intn,intbestx[]);//在GNU中，需提前声明intcount二0;//用来记彖递归回溯搜索了多少个节点templateclassLoading{private:intn;//Thenumbersint

4、*x;//当前的搜索的路径x[i]二二1表示在第i层进入了左子树int*bestx;//当前已知的最优解T*w;//TheweightarrayTc;//Thefirstbox'sweightTcw;//currentweightTbestv;//ThebestweightTr;//Therestweightpublic:voidbacktrack(inti);TfriendMaxLoading(Tw[],Tc,intn,intbostx[]);};templatevoidLoading::backtrack(

5、inti)count++;if(i>n)(bestw二cw;//局部最优值for(intj=1；j<二n；j++)bestx[j]=x[j];//局部最优解}else{r-=w[i];//处理第i层的本节点if(cw+w[i]<=c)//进入左子树{x[i]=1;cw+二v[i];backtrack(i+1);cw-=w[i];//左子树搜索完毕，必须准备回溯}if(cw+r＞二bestw)//进入右子树{x[i]=0;backtrack(i+1);}//右子树搜索完毕r+=w[i];//两颗了树都搜索完毕，必须冋溯template

6、assT>TMaxLoading(Tw[],Tc,intn,intbestx[]){/*〃递l丿I回溯容易理解LoadingX;X.x=newint[n+l];//集装箱编号从1开始X.bestx二bestx;//引用X.w=w;X.c=c;X.n=n;X.cw二0;X.bestw二0;X.r=0;//for(inti=l;i<=n;i++)X.r+=w[i];//r初始时为所有集装箱的重量之和X.backtrack(1);delete[]X.x;returnX.bestw;inti=1;int*x=newint[n+1]•9Tbcs

7、tv=0,cw=0,r=o；for(intj=1；j<=n;j++)r+=w[j];while(true){while(i<=n&&cw+w[i]<=c)//深度优先只要能进入左子树，就进入左子树{r-=w[i];cw+=w[i];x[i]=1；}//无法继续进入左子树(1)i>n(2)cv+v[i]>cif(i>n){bestw二cw;//局部最优值for(intj=1;j<=n;j++)bestx[j]=x[j];//局部最优解}else//表示由于约束函数的限制(cw+w[i]>c)而停止上次循环，无法进入下一层的左子树〃右子树

8、肯定可以进入{r-=w[i];x[i]=0;i++；}while(cw+r<=bestw)//如果前述循环己经得到了一个局部最优解和对应的局部最优值〃可以沿着右子树一路回溯剪枝{