实验六_分支限界法

《实验六_分支限界法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计实验报告　　　　　　　　　　学号姓名班级上课地点教师上课时间实验六分支限界法1.实验目的1.1掌握分支限界法的设计思想；1.2理解分支限界法的剪枝搜索策略；1.3掌握分支限界法的算法框架；1.4学会利用分支限界法解决实际问题。2.实验环境2.1Eclipse2.2WindowXP3.实验内容3.1装载问题3.2旅行售货员问题4.教师批改意见签字：日期：成绩14实验报告细表1装载问题1.1算法设计思想解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载

2、重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。1.2程序源码packagelab06;importjava.util.Comparator;importjava.util.PriorityQueue;importjava.util.Scanner;importlab06.FIFOBB

3、Loading.HeapNode;publicclassFIFOBBLoading{staticintn;//货物数量staticintc1;//第一艘船的载重量staticintc2;//第二艘船的载重量staticint[]w;//货物重量的数组staticintbestw;//当前最优载重量staticboolean[]bestx;//当前最最优解staticScannerscan=newScanner(System.in);publicstaticvoidmain(String[]args){//输入货物数量System.out

4、.print("请输入货物数量：n=");n=inputN();bestx=newboolean[n+1];//输入第一艘船的载重量System.out.print("请输入第一艘船的载重量：c1=");c1=inputC1();//输入第二艘船的载重量System.out.print("请输入第二艘船的载重量：c2=");c2=inputC2();14//输入各个货物的重量System.out.println("请输入各个货物的重量：");w=inputW();System.out.println("第一艘船可载重："+maxLoad

5、ing(w,c1,n,bestx));intcount=0;System.out.print("第一艘船装载的货物为：");for(inti=1;i<=n;i++)if(bestx[i]){System.out.print(w[i]+"");count++;bestx[i]=false;}System.out.println();if(n-count!=0){System.out.println("第二艘船可载重："+maxLoading(w,c2,n-count,bestx));System.out.print("第二艘船装载的货物为

6、：");for(inti=1;i<=n-count;i++)if(bestx[i])System.out.print(w[i]+"");}elseSystem.out.println("只需第一艘船便能装载完所有货物");}//输入货物数量privatestaticintinputN(){n=scan.nextInt();if(n<=0){System.out.println("货物数量有误，请重新输入！");System.out.print("n=");n=scan.nextInt();inputN();}returnn;}//输入第

7、一艘船的载重量privatestaticintinputC1()14{c1=scan.nextInt();if(c1<=0){System.out.println("第一艘船的载重量输入有误，请重新输入！");System.out.print("c1=");c1=scan.nextInt();inputC1();}returnc1;}//输入第二艘船的载重量privatestaticintinputC2(){c2=scan.nextInt();if(c2<=0){System.out.println("第二艘船的载重量输入有误，请重新输

8、入！");System.out.print("c2=");c2=scan.nextInt();inputC2();}returnc2;}//输入第一艘船的载重量privatestaticint[]input