分支限界法实验(最优装载问题).doc
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艘轮船。如果有，找出一种装载方案。 容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。实验步骤（1）在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结点；（2）如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃；（3）活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空；（4）当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。关键代码void Maxloading(int w,int c,int n,int bestx) /其中w为重量数组¦ / c为船的总载重量,n为节点数 /初始化queue <QNode *>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(wt<=c) /左儿子节点为可行结点 if(wt>bestw) 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) /到达同层的最末，此时需要更新剩余装箱载重量if(Q.empty() break; /此时队列为空 Q.push(0); /加入0，表示该层结束E=Q.front();Q.pop();i+; /进入下一层r-=wi;/更新剩余集装箱的值 Ew=E->weight; /新扩展的节点对应的载重量 /构造当前最优解for(int j=n-1;j>0;j-) bestxj=bestE->LChild; bestE=bestE->parent; cout<<"最优载重量为："<<bestw<<endl;cout<<"最优载重方式："<<"(" for(int i=1;i<n;i+) cout<<bestxi<<","cout<<bestxn<<")"<<endl;测试结果 当输入物品数量较少时：当输入物品数量较一般时： 当输入物品数量较大时：实验心得最优装载就是求解载重量最好的载重方案，之前最优装载采用了贪心算法，这里使用的使分支限界法；其实在使用分支限界法进行了单源最短路径的实现之后，在完成这个实验就显得更简单一点。分支限界法的算法思想本身还是很好理解的，但是在这个问题中由于涉及到了剪枝的问题，所以新加入了一个0来判断一层是否结束，因为在一层结束的时候，代表该集装箱的情况已经考虑完了，需要考虑下一个集装箱，这个时候就需要更新剩余集装箱的重量，这会影响到一个右子树是否会被剪掉，因此要特别注意。实验得分助教签名附录：完整代码（分支限界法）/分支限界法求最优装载#include<iostream>#include<time.h>#include<iomanip>#include<queue>using namespace std;class QNodefriend void Enqueue(queue<QNode *>&,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<QNode *>&Q,int wt,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为船的总载重量,n为节点数 /初始化queue <QNode *>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(wt<=c) /左儿子节点为可行结点 if(wt>bestw) 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) /到达同层的最末，此时需要更新剩余装箱载重量if(Q.empty() break; /此时队列为空 Q.push(0); /加入0，表示该层结束E=Q.front();Q.pop();i+; /进入下一层r-=wi;/更新剩余集装箱的值 Ew=E->weight; /新扩展的节点对应的载重量 /构造当前最优解for(int j=n-1;j>0;j-) bestxj=bestE->LChild; bestE=bestE->parent; cout<<"最优载重量为："<<bestw<<endl;cout<<"最优载重方式："<<"(" for(int i=1;i<n;i+) cout<<bestxi<<","cout<<bestxn<<")"<<endl;int main()int n;cout<<"please input number of node:"cin>>n;int *w=new intn+1;int *bestx=new intn+1;cout<<"please input weight:"<<endl;for(int i=1;i<=n;i+) cin>>wi;int c; cout<<"please input limit weight:"cin>>c;clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();Maxloading(w,c,n,bestx);cout<<"The time is "<<(double)(end-start-over)/CLK_TCK)<<endl; system("pause");return 0;-
