算法实验三——回溯法(2017)

《算法实验三——回溯法(2017)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验三回溯法实验目的学习编程实现深度优先搜索状态空间树求解实际问题的方法，着重体会求解第一个可行解和求解所有可行解之间的差别。加深理解回溯法通过搜索状态空间树、同时用约束函数剪去不含答案状态子树的算法思想，会用蒙特卡罗方法估计算法实际生成的状态空间树的结点数。实验内容一、要求用回溯法求解8-皇后问题，使放置在8*8棋盘上的8个皇后彼此不受攻击，即：任何两个皇后都不在同一行、同一列或同一斜线上。请输出8皇后问题的所有可行解。二、用回溯法编写一个递归程序解决如下装载问题：有n个集装箱要装上2艘载重分别为c1和c?2的轮船，其中集装箱i的重量为wi（1≤i≤n），且∑?=1?

2、?≤?1+?2。问是否有一个合理的装载方案可以将这n个集装箱装上这2艘轮船？如果有，请给出装载方案。提示：参考子集和数问题的求解方法。举例：当n=3，c1=c2=50，且w=[10,40,40]时，可以将集装箱1和2装到第一艘轮船上，集装箱3装到第二艘轮船上；如果w=[20,40,40]时，无法将这3个集装箱都装上轮船。实验步骤一、8皇后问题通过求解n-皇后问题，体会回溯法深度优先遍历状态空间树，并利用约束函数进行剪枝的算法思想。#includeusingnamespacestd;#includeboolPlace(intk,inti

3、,int*x)//判定两个皇后是否在同一列或在同一斜线上{for(intj=0;j

4、

5、(abs(x[j]-i)==abs(j-k)))returnfalse;returntrue;}voidNQueens(intk,intn,int*x)//递归函数（求解n皇后问题）{for(inti=0;i

6、s(intn,int*x){NQueens(0,n,x);}voidmain(){intx[8];for(inti=0;i<8;i++)x[i]=-1;NQueens(8,x);}二、装载问题1、如果给定的装载问题有解，则采用下面的策略可以得到一个最优装载方案：（1）首先将第一艘轮船尽可能装满；（2）然后将剩余的集装箱装到第二艘轮船上。将第一艘轮船尽可能装满，等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近c1。由此可知，装载问题等价于以下特殊的0-1背包问题：?max∑?????=1?∑????≤?1?=1??∈{0,1}，1≤?≤?2、求最优解值时，用

7、变量cw表示当前实际载重量，bestw表示当前最优载重量，r=∑??是剩余集装箱的总重量。?=?+1?该问题解空间可用子集树表示。子集树中可行结点的左儿子结点表示x[i]=1的情形，右儿子结点表示x[i]=0的情形。引入约束函数用于剪去不含可行解和最优解的子树：（约束函数）用来剪去不含可行解的分枝：仅当cw+w[i]≤c时进入可行结点的左子树，否则剪去左子树。而可行结点的右儿子结点总是可行的，故进入右子树时不需检查可行性。（约束函数）用来剪去不含最优解的分枝：由于当前结点的左孩子cw+r值保持不变，因此无需检查。而仅当右孩子cw+r>bestw时才需要进入右子树搜索

8、，否则应对右子树进行剪枝。另外，引入剪去不含最优解分枝的约束函数后，在达到一个叶节点时，就不必再检查该叶结点是否优于当前最优解，因为算法搜索到的每个叶节点都是迄今为止找到的最优解。3、为了在算法中记录与当前最优值相应的当前最优解，需要增加两个数组数据成员x和bestx。x用于记录从根至当前结点的路径；bestx记录当前最优解。算法每搜索到一个叶结点处，就修正bestx的值。4、算法实现主体部分如下，请补充完整，并使用下面三个测试案例调试通过。第一艘船载重60，第二艘船载重40，5个集装箱重量分别为：（1）223524194（2）223524154（3）22352415

9、3templateclassLoading{private:intn,//集装箱数*x,//当前解*bestx;//当前第一艘船的最优解Tc1,//第一艘轮船的核定载重量c2,//第二艘轮船的核定载重量*w,//集装箱重量数组total,//所有集装箱重量之和cw,//当前第一艘船的载重量bestw,//当前第一艘船的最优载重量r;//剩余集装箱总重量public:Loading()//构造函数{……//（请自行补充）}~Loading()//析构函数{……//（请自行补充）}voidBacktrack(inti);//找