欢迎来到天天文库
浏览记录
ID:20723847
大小:134.05 KB
页数:10页
时间:2018-10-15
《分支限界法-最大团问题与旅行背包问题java源程序》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、实验报告14课程数据结构与算法实验名称分支限界法第页班级11计本学号105032011130姓名风律澈实验日期:2013年6月8日报告退发(订正、重做)一、实验目的掌握分支限界法的原理和应用。二、实验环境1、微型计算机一台2、WINDOWS操作系统,JavaSDK,Eclipse开发环境三、实验内容必做题:1、编写程序,采用问题。2、编写程序,采用分支限界法求解旅行售货员问题。四、实验步骤和结果(附上代码和程序运行结果截图)1、分支限界法最大团package分支限界最大团;publicclassmain{/***@paramargs
2、*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubint[][]a={{1,1,0,1,1},{1,1,1,0,1},{0,1,1,0,1},{1,0,0,1,1},{1,1,1,1,1}};graphg=newgraph(a);g.find_answer();g.show();}}-------------------------------------------------------------------------------------
3、---------------------------------package分支限界最大团;importjava.util.ArrayList;importjava.util.PriorityQueue;publicclassgraph{privateArrayListpoints;privateArrayListanswer_point;publicgraph(int[][]a){this.points=newArrayList<>();this.answer_point=newArrayList<
4、>();intn=a.length;for(inti=0;i5、tubinttotal_points=this.points.size();PriorityQueueenode=newPriorityQueue<>();intnode_in=0;pointnode_point=this.points.get(0);ArrayListnowanswer=newArrayList<>();intmaxnum_point=this.points.size();Nodestartnode=newNode(node_in,node_point,nowanswer,maxnum_p6、oint);enode.offer(startnode);Nodenode=null;while(true){if(enode.isEmpty())break;node=enode.poll();if(node.get_node_in()==maxnum_point)break;if(node.ifleft()){intnew_node_in=node.get_node_in()+1;intnew_answer=node.get_maxnum_point();pointnewpoint;if(new_node_in==total_p7、oints)newpoint=null;elsenewpoint=this.points.get(new_node_in);ArrayListnew_answer_point=newArrayList(node.get_answer_point());new_answer_point.add(node.get_node_point());Nodenew_node=newNode(new_node_in,newpoint,new_answer_point,new_answer);enode.offer(ne8、w_node);if(new_node.get_answer_point().size()>this.answer_point.size())this.answer_point=newArrayList<>(new_node.get_
5、tubinttotal_points=this.points.size();PriorityQueueenode=newPriorityQueue<>();intnode_in=0;pointnode_point=this.points.get(0);ArrayListnowanswer=newArrayList<>();intmaxnum_point=this.points.size();Nodestartnode=newNode(node_in,node_point,nowanswer,maxnum_p
6、oint);enode.offer(startnode);Nodenode=null;while(true){if(enode.isEmpty())break;node=enode.poll();if(node.get_node_in()==maxnum_point)break;if(node.ifleft()){intnew_node_in=node.get_node_in()+1;intnew_answer=node.get_maxnum_point();pointnewpoint;if(new_node_in==total_p
7、oints)newpoint=null;elsenewpoint=this.points.get(new_node_in);ArrayListnew_answer_point=newArrayList(node.get_answer_point());new_answer_point.add(node.get_node_point());Nodenew_node=newNode(new_node_in,newpoint,new_answer_point,new_answer);enode.offer(ne
8、w_node);if(new_node.get_answer_point().size()>this.answer_point.size())this.answer_point=newArrayList<>(new_node.get_
此文档下载收益归作者所有