分支限界法实验(最优装载问题).doc

《分支限界法实验(最优装载问题).doc》由会员分享，可在线阅读，更多相关《分支限界法实验(最优装载问题).doc（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date分支限界法实验(最优装载问题)分支限界法实验(最优装载问题)算法分析与设计实验报告第 八 次附加实验姓名学号班级时间12.26上午地点工训楼309 实验名称分支限界法实验(最优装载问题)实验目的1. 掌握分支限界法求解问题的思想2. 学会利用队列求解最优装载问题实验原理问题描述：有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问

2、题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。实验步骤（1）在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结点；（2）如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃；（3）活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空；（

3、4）当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。关键代码void Maxloading(int w,int c,int n,int bestx) /其中w为重量数组 / c为船的总载重量,n为节点数 /初始化queue Q; /活节点队列Q.push(0); /将第一个节点加入队列中，并用0表示同层节点的尾部标志int i=1; /当前扩展节点的层数，此时为int Ew=0; /扩展节点相应的载重量int bestw=0; /当前最优载重量int r=0; /剩余集装箱的重量for(int j=2;j=n;j+) /求

4、得最初的剩余载重量 r+=wj; QNode *E =0; /当前扩展节点QNode *bestE; /当前最优扩展节点/搜索子集空间树while(true)/首先检查左儿子节点int wt=Ew+wi;if(wtbestw) bestw=wt; Enqueue(Q,wt,i,n,bestw,E,bestE,bestx,true);/将左节点加入队列 /检查右儿子节点，利用上届函数if(Ew+r=bestw) Enqueue(Q,Ew,i,n,bestw,E,bestE,bestx,false);/将右节点加入队列 E=Q.front(); /取出当前扩展节点 Q.pop(); if(!E)

5、/到达同层的最末，此时需要更新剩余装箱载重量if(Q.empty() break; /此时队列为空 Q.push(0); /加入0，表示该层结束E=Q.front();Q.pop();i+; /进入下一层r-=wi;/更新剩余集装箱的值 Ew=E-weight; /新扩展的节点对应的载重量 /构造当前最优解for(int j=n-1;j0;j-) bestxj=bestE-LChild; bestE=bestE-parent; cout最优载重量为：bestwendl;cout最优载重方式：(; for(int i=1;in;i+) coutbestxi,;coutbestxn)endl;测试

6、结果 当输入物品数量较少时：当输入物品数量较一般时： 当输入物品数量较大时：实验心得最优装载就是求解载重量最好的载重方案，之前最优装载采用了贪心算法，这里使用的使分支限界法；其实在使用分支限界法进行了单源最短路径的实现之后，在完成这个实验就显得更简单一点。分支限界法的算法思想本身还是很好理解的，但是在这个问题中由于涉及到了剪枝的问题，所以新加入了一个0来判断一层是否结束，因为在一层结束的时候，代表该集装箱的情况已经考虑完了，需要考虑下一个集装箱，这个时候就需要更新剩余集装箱的重量，这会影响到一个右子树是否会被剪掉，因此要特别注意。实验得分助教签名附录：完整代码（分支限界法）/分支限界法求最优装

7、载#include#include#include#includeusing namespace std;class QNodefriend void Enqueue(queue&,int,int,int,int,QNode *,QNode *&,int *,bool);friend void Maxloading(int *,int,int,int *);private:QNode *parent; /指向父节点的指针bool LChild; /左儿子标志，用来表明自己是否为父节点的左儿子int weight; /节点所相应的载重量 ; void Enqueue(queue&Q,int wt

8、,int i,int n,int bestw,QNode *E,QNode *&bestE,int bestx,bool ch)/将活节点加入到队列中if(i=n) /到达叶子节点if(wt=bestw) /确保当前解为最优解bestE=E;bestxn=ch; return;/当不为叶子节点时，加入到队列中，并更新载重、父节点等信息QNode *b;b=new QNode;b-weight=wt;b-parent=E;b-LChild=ch;Q.push(b); void Maxloading(int w,int c,int n,int bestx) /其中w为重量数组 / c为船的总载重量

9、,n为节点数 /初始化queue Q; /活节点队列Q.push(0); /将第一个节点加入队列中，并用0表示同层节点的尾部标志int i=1; /当前扩展节点的层数，此时为int Ew=0; /扩展节点相应的载重量int bestw=0; /当前最优载重量int r=0; /剩余集装箱的重量for(int j=2;j=n;j+) /求得最初的剩余载重量 r+=wj; QNode *E =0; /当前扩展节点QNode *bestE; /当前最优扩展节点/搜索子集空间树while(true)/首先检查左儿子节点int wt=Ew+wi;if(wtbestw) bestw=wt; Enqueue

10、(Q,wt,i,n,bestw,E,bestE,bestx,true);/将左节点加入队列 /检查右儿子节点，利用上届函数if(Ew+r=bestw) Enqueue(Q,Ew,i,n,bestw,E,bestE,bestx,false);/将右节点加入队列 E=Q.front(); /取出当前扩展节点 Q.pop(); if(!E) /到达同层的最末，此时需要更新剩余装箱载重量if(Q.empty() break; /此时队列为空 Q.push(0); /加入0，表示该层结束E=Q.front();Q.pop();i+; /进入下一层r-=wi;/更新剩余集装箱的值 Ew=E-weight;

11、 /新扩展的节点对应的载重量 /构造当前最优解for(int j=n-1;j0;j-) bestxj=bestE-LChild; bestE=bestE-parent; cout最优载重量为：bestwendl;cout最优载重方式：(; for(int i=1;in;i+) coutbestxi,;coutbestxn)endl;int main()int n;coutn;int *w=new intn+1;int *bestx=new intn+1;coutplease input weight:endl;for(int i=1;iwi;int c; coutc;clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();Maxloading(w,c,n,bestx);coutThe time is (double)(end-start-over)/CLK_TCK)endl; system(pause);return 0;-