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

《实验五、优先队列式分支限界法解装载问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点所相应的载重量与其优先级相同。因此在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解，此时终止算法。上述策略可以用两种

3、不同方式来实现。第一种方式在结点优先队列的每一个活结点中保存从解空间树的根结点到该活结点的路径，在算法确定了达到最优值的叶结点时，就在该叶结点处同时得到相应的最优解。第二种方式在算法的搜索进程中保存当前已构造出的部分解空间树，在算法确定了达到最优值的叶结点时，就可以在解空间树中从该叶结点开始向根结点回溯，构造出相应的最优解。在下面的算法中，采用第二种方式。四、源程序importjava.util.Comparator;importjava.util.Iterator;importjava.util.

4、PriorityQueue;importjava.util.Scanner;publicclasstest5{publicvoidaddLiveNode(PriorityQueueH,bbnodeE,intwt,booleanch,intlev){bbnodeb=newbbnode(E,ch);HeapNodeN=newHeapNode(b,wt,lev);H.add(N);}publicintmaxLoading(intw[],intc,intn,booleanbestx[])

5、{PriorityQueueH=newPriorityQueue(1000,newcomp());/*生成最大堆*/int[]r=newint[n+1];r[n]=0;for(intj=n-1;j>0;j--){r[j]=r[j+1]+w[j+1];}inti=1;bbnodeE=newbbnode(null,false);intEw=0;while(i!=n+1){if(Ew+w[i]<=c){addLiveNode(H,E,Ew+w[i]+r[i],true,i+1);}ad

6、dLiveNode(H,E,Ew+r[i],false,i+1);HeapNodeN;N=H.poll();i=N.level;E=N.ptr;Ew=N.uweight-r[i-1];}//构造最优解for(intj=n;j>0;j--){bestx[j]=E.Lchild;E=E.parent;}returnEw;}publicstaticvoidmain(String[]args){System.out.println("请输入物品总数：");Scannersc1=newScanner(Syst

7、em.in);intn=sc1.nextInt();int[]w=newint[n+1];System.out.println("请输入物品重量：");Scannersc2=newScanner(System.in);for(inti=1;i<=n;i++){w[i]=sc2.nextInt();}System.out.println("请输入箱子重量：");Scannersc3=newScanner(System.in);intc1=sc3.nextInt();intc2=sc3.nextInt(

8、);boolean[]bestx=newboolean[100];test5t=newtest5();//处理第一个箱子System.out.println("first:"+t.maxLoading(w,c1,n,bestx));System.out.print("可装重为：");intcount=0;for(inti=1;i<=n;i++){if(bestx[i]){count++;System.out.print(w[i]+"");/*输出一个可行方案*/}}S