实验五优先队列式分支限界法解装载问题

1、实验五优先队列式分支限界法解装载问题09电信实验班I09660118徐振飞一、实验题目实现书本P201所描述的优先队列式分支限界法解装载问题二、实验目的1）掌握并运用分支限界法基本思想2）运用优先队列式分支限界法实现装载问题3）比较队列式分支限界法和优先队列式分支限界法的优缺点三、实验内容和原理（1）实验内容有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，nwic1c2其中集装箱i的重量为Wi，且i1，要求确定可否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。若是有，请给出方案。（2）实验原理解装载问题的优先队列式分支限界法用最大优先队列储藏活结点表。活结点x在优先队列中的优先

2、级定义为从根结点到结点x的路径所相应的载重量再加上节余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点所相应的载重量与其优先级相同。因此在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结1点，则可以断言该叶结点所相应的解即为最优解，此时停止算法。上述策略可以用两种不相同方式来实现。第一种方式在结点优先队列的每一个活结点中保存从解空间树的根结点到该活结点的路径，在算法确定了达到最优值的叶结点时，就在该叶结点处同时获取相应的最优解。第二种方式

3、在算法的搜寻进度中保存当前已构造出的部分解空间树，在算法确定了达到最优值的叶结点时，就可以在解空间树中从该叶结点开始向根结点回溯，构造出相应的最优解。在下面的算法中，采用第二种方式。四、源程序importjava.util.Comparator;importjava.util.Iterator;importjava.util.PriorityQueue;importjava.util.Scanner;publicclasstest5publicvoidaddLiveNode(PriorityQueueH,bbnodeE,intwt,booleanch,intlev)bbnodeb=newbbn

4、ode(E,ch);HeapNodeN=newHeapNode(b,wt,lev);H.add(N);publicintmaxLoading(intw,intc,intn,booleanbestx)PriorityQueueH=newPriorityQueue(1000,newcomp();/*生成最大堆*/intr=newintn+1;rn=0;for(intj=n-1;j0;j-)rj=rj+1+wj+1;inti=1;bbnodeE=newbbnode(null,false);intEw=0;while(i!=n+1)if(Ew+wi0;j-)bestxj=E.Lchild;E=E.pa

5、rent;returnEw;publicstaticvoidmain(Stringargs)System.out.println(请输入物品总数：);Scannersc1=newScanner(System.in);intn=sc1.nextInt();intw=newintn+1;System.out.println(请输入物品重量：);Scannersc2=newScanner(System.in);for(inti=1;i=n;i+)wi=sc2.nextInt();System.out.println(请输入箱子重量：);Scannersc3=newScanner(System.in)

6、;intc1=sc3.nextInt();intc2=sc3.nextInt();booleanbestx=newboolean100;test5t=newtest5();/办理第一个箱子System.out.println(first:+t.maxLoading(w,c1,n,bestx);System.out.print(可装重为：);intcount=0;for(inti=1;i=n;i+)if(bestxi)count+;System.out.print(wi+);/*输出一个可行方案*/System.out.println();/*办理第二个箱子*/intm=n-count;3int

7、ww=newintm+1;intk=1;for(inti=1;i=n;i+)if(!bestxi)wwk=wi;k+;bestxi=false;System.out.println();System.out.println(second:+t.maxLoading(ww,c2,m,bestx);System.out.print(可装重为：);for(inti=1;i=m;i+)if(bestxi)System.out.print(wwi+);/*输出一个可行方案*/*堆结点类*/classHeapNodebbnodeptr;intuweight;intlevel;publicHeapNode(

8、)publicHeapNode(bbnodeptr,intuweight,intlevel)this.ptr=ptr;this.uweight=uweight;this.level=level;publicStringtoString()return+this.uweight;classbbnodebbnodeparent;booleanLchild;publicbbnode(bbnodenode,booleanch)this.parent=node;this.Lchild=ch;/定义比较器类4classcompimplementsComparatorOverridepublicintcom

9、pare(HeapNodeo1,HeapNodeo2)intdif=o1.uweight-o2.uweight;if(dif0)return-1;elseif(dif=0)return0;elsereturn1;五、实验结果和解析a.输入格式说明：1）第一输入物品总数量2）第二栏输入所有物品重量3）第三栏输入2个箱子的重量b.输出格式说明：1）第一输出first的字样，后边的数字表示第一个箱子所能装载的最大重量，紧接着的一行输出一种可以选择装载的方案2）Second字样后边的数字表示第二个箱子所能装载的最大重量，紧接着的一行输出一种可行方案5经过解析，上述结果正确。六、实验心得和领悟经过实验，

10、认识了分支限界法的基本思想。掌握了利用优先队列式分支限界法实现详尽的装载问题。由于本次实验利用java.util包下的PriorityQueue代替算法中的最大堆，免去了编写实现最大堆的程序代码（但这其实不表示我不会编写最大堆程序，在此次实验中，最大堆的实现其实不是主要部分），因此本次实验实现的相对顺利。存在的问题及解析：在此例中最合理的装载方法是第一个箱子装载重量为：1050的6物品，第二个箱子装载重量为2020的物品。解析：由于程序中先装载第一个箱子，尔后再装载第二个箱子；而分支限界法一旦扩展结点到达叶子结点时，程序便停止退出。因此在此例中当第一个箱子装满后（此时重量为102030的物品已被装走），余下的