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

《分支限界法实验(最优装载问题)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法分析与设计实验报告第八次附加实验姓名学号班级时间12.26上午地点工训楼309实验名称分支限界法实验(最优装载问题)实验目的1.掌握分支限界法求解问题的思想2.学会利用队列求解最优装载问题实验原理问题描述：有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。实验步骤(1)在算法的循环体中，首先检测当前扩展结点的左

2、儿子结点是否为可行结点；(2)如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列屮(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃；(3)活结点队列中的队首元素被取岀作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空；(4)当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。算法分析与设计实验报告第八次附加实验姓名学号班级时间12.26上午地点工训楼309实验名称分支限界法实验(最优装载问题)实验目的1.掌握分支限界法求解问题的

3、思想2.学会利用队列求解最优装载问题实验原理问题描述：有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。实验步骤(1)在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结点；(2)如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列屮(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩

4、展结点被舍弃；(3)活结点队列中的队首元素被取岀作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空；(4)当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。关键代码voidMaxloading(intw[],intc,intn,intbestx[])//K-中w[]为重量数组1{//c为船的总载重量，n为节点数//初始化queueQ;//活节,6:队列Q.PtiSh(O);//将第一个节点加入队列中，并用0表示同层节点的尾部标志inti=l;//当

5、前扩展节点的层数，此时为intEw=O;//扩展节点相应的载重量intbestw=O;//当前最优载重量intr=0;//剩余集装箱的重量for(intj=2;j<=n;j++)//求得最初的剩余载重量r+=w[j];QNode*E=0;//当前扩展节点QNode*bestE;//当前最优扩展节点//搜索子集空间树while(true){//首先检查左儿子节点intwt二Ew+w[i];if(wt<=c)//左儿子节点为可行结点{if(wt>bcstw)bestw=wt;Enqueue(Q,wt,i,n,bestw,E,bestE,bestx,true);//将左节点加入队列}//

6、检査右儿子节点，利用上届函数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_=w[i];//更新剩余集装箱的值}Ew=E->wcight;//新扩展的节点对应的载重量}//构造当前最优解for(intj:n-l;j

7、>0;j—){bestx[j]=bestE->LChiId;bcstE=bcstE->parcnt;}cout〈〈〃最优载重量为：〃〈〈bestw〈〈endl;cout<〈"最优载重方式：〃<〈"("；for(inti=l;i