分支限界法实验最优装载问题

算法分析与设计实验报告 第 八 次附加实验 姓名 学号 班级 时间 12.26上午 地点 工训楼309 实验名称 分支限界法实验最优装载问题 实验目的 1. 掌握分支限界法求解问题的思想 学会利用队列求解最优装载问题 2. 实验原理 问题描述 有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 则采用下面的策略可得到最优装载方如果一个给定装载问题有解，容易证明 案。 1首先将第一艘轮船尽可能装满； 2将剩余的集装箱装上第二艘轮船。 实验步骤 ）在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结（1 点；）如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点（2个儿子结点都产生后，当前扩展结点。2队列中右儿子结点一定是可行结点被舍弃； ）活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层（3 结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空；时，再判断当前队列是否为空。如果队列非空，则将-14）当取出的元素是（ -1尾部标记加入活结点队列，算法开始处理下一层的活结点。 关键代码 void Maxloadingint w[],int c,int n,int bestx[] //其中w[]为重量数组| { // c为船的总载重量,n为节点数 //初始化 queue QNode *Q; //活节点队列 Q.push0; //将第一个节点加入队列中，并用0表示同层节点的尾部标志 当前扩展节点的层数，此时为// i1; int int Ew0; //扩展节点相应的载重量 int bestw0; //当前最优载重量 int r0; //剩余集装箱的重量 forint j2;jn;j //求得最初的剩余载重量 rw[j]; QNode *E 0; //当前扩展节点 QNode *bestE; //当前最优扩展节点 //搜索子集空间树 whiletrue { //首先检查左儿子节点 int wtEww[i]; ifwtc //左儿子节点为可行结点 { ifwtbestw bestwwt; EnqueueQ,wt,i,n,bestw,E,bestE,bestx,true;//将左节点加入队列 } //检查右儿子节点，利用上届函数 ifEwrbestw EnqueueQ,Ew,i,n,bestw,E,bestE,bestx,false;//将右节点加入队列 EQ.front; //取出当前扩展节点 Q.pop; ifE //到达同层的最末，此时需要更新剩余装箱载重量 { ifQ.empty break; //此时队列为空 Q.push0; //加入0，表示该层结束 EQ.front; Q.pop; i; //进入下一层 r-w[i];//更新剩余集装箱的值 } EwE-weight; //新扩展的节点对应的载重量 } //构造当前最优解 forint jn-1;j0;j-- { bestx[j]bestE-LChild; bestEbestE-parent; } cout最优载重量为bestwendl; ; 最优载重方式cout forint i1;in;i coutbestx[i]; coutbestx[n]endl; } 当输入物品数量较少时 当输入物品数量较一般时 测试结果 当输入物品数量较大时 最优装载就是求解载重量最好的载重方案，之前最优装载采用了贪心算法，这里使用的使分支限界法；其实在使用分支限界法进行了单源最短路径的实现之后，在完成这个实验就显得更简单一点。分支限界法的算法思想本身还是很好理解的，但是在这个问题中由于涉及到了剪枝的问题，所以新加入了一实验心得 代表该集装箱的情况已经因为在一层结束的时候，来判断一层是否结束，个0考虑完了，需要考虑下一个集装箱，这个时候就需要更新剩余集装箱的重量， 这会影响到一个右子树是否会被剪掉，因此要特别注意。实验得助教签 附录 完整代码（分支限界法） //分支限界法求最优装载 includeiostream includetime.h includeiomanip includequeue using namespace std; class QNode { friend void EnqueuequeueQNode *,int,int,int,int,QNode *,QNode *,int *,bool; friend void Maxloadingint *,int,int,int *; private QNode *parent; //指向父节点的指针 bool LChild; //左儿子标志，用来表明自己是否为父节点的左儿子 int weight; //节点所相应的载重量 }; void EnqueuequeueQNode *Q,int wt,int i,int n,int bestw,QNode *E,QNode *bestE,int bestx[],bool ch { //将活节点加入到队列中 ifin //到达叶子节点 { ifwtbestw //确保当前解为最优解 { bestEE; bestx[n]ch; } return; } //当不为叶子节点时，加入到队列中，并更新载重、父节点等信息 QNode *b; bnew QNode; b-weightwt; b-parentE; b-LChildch; Q.pushb; } void Maxloadingint w[],int c,int n,int bestx[] //其中w[]为重量