分支限界法-最大团问题和旅行背包问题java源程序

额,没什么好说的,自己看吧。

实验报告14

课程 数据结构与算法 实验名称 分支限界法 第 页

班级 11计本 学号 105032011130 姓名 风律澈 实验日期：2013年6月8日 报告退发 (订正 、 重做)

一、实验目的

掌握分支限界法的原理和应用。

二、实验环境

1、微型计算机一台

2、WINDOWS操作系统，Java SDK，Eclipse开发环境

三、实验内容

必做题：

1、编写程序，采用问题。

2、编写程序，采用分支限界法求解旅行售货员问题。

四、实验步骤和结果

(附上代码和程序运行结果截图)

1、分支限界法最大团

package 分支限界最大团;

public class main {

/**

* @param args

*/

public static void // TODO Auto-generated method stub

int [][]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}

};

graph g=new graph(a);

g.find_answer();

g.show();

}

}

----------------------------------------------------------------------------------------------------------------------

额,没什么好说的,自己看吧。

package 分支限界最大团;

import java.util.ArrayList;

import java.util.PriorityQueue;

public class graph {

private ArrayList<point> points;

private ArrayList<point> answer_point;

public graph(int [][]a){

this.points=new ArrayList<>();

this.answer_point=new ArrayList<>();

int n=a.length;

for(int i=0;i<n;i++)

this.points.add(new point());

for(int i=0;i<n;i++)

for(int j=i+1;j<n;j++)

if(a[i][j]==1){

point pi=this.points.get(i);

point pj=this.points.get(j);

pi.add_nearpoint(pj);

pj.add_nearpoint(pi);

}

}

public void find_answer() {

// TODO Auto-generated method stub

int total_points=this.points.size();

PriorityQueue<Node> enode=new PriorityQueue<>();

int node_in=0;

point node_point=this.points.get(0);

ArrayList<point> nowanswer=new ArrayList<>();

int maxnum_point=this.points.size();

Node

Node(node_in,node_point,nowanswer,maxnum_point);

enode.offer(startnode);

Node node=null;

while(true){

if(enode.isEmpty())

break;

node=enode.poll();

if(node.get_node_in()==maxnum_point)

break;

if(node.ifleft()){

int new_node_in=node.get_node_in()+1;

int new_answer=node.get_maxnum_point(); startnode=new

额,没什么好说的,自己看吧。

point newpoint;

if(new_node_in==total_points)

newpoint=null;

else

newpoint=this.points.get(new_node_in);

ArrayList<point> new_answer_point=new ArrayList<point>(node.get_answer_point());

new_answer_point.add(node.get_node_point());

Node new_node=new Node(new_node_in,newpoint,new_answer_point,new_answer);

enode.offer(new_node);

if(new_node.get_answer_point().size()>this.answer_point.size()) this.answer_point=new

ArrayList<>(new_node.get_answer_point());

}

if(node.ifright(this.points.size(),

this.answer_point.size())){

ArrayList<point>

new_node_answer_points=node.get_answer_point();

int new_node_in=node.get_node_in()+1;

int new_node_max=node.get_maxnum_point()-1;

point p=this.points.get(new_node_in);

Node newnode=new Node(new_node_in,p,new_node_answer_points,new_node_max);

enode.add(newnode);

}

}

}

public void show(){

System.out.println(this.answer_point);

}

}

---------------------------------------------------------------------------------------------------------------------- package 分支限界最大团;

import java.util.ArrayList;

public class point {

private static int ids=1;

private int id;

private ArrayList<point> nearpoints;

public point(){

super();

额,没什么好说的,自己看吧。

} this.id=ids++; this.nearpoints=new ArrayList<point>(); } public String toString(){ return "顶点"+this.id; } public void add_nearpoint(point p){ this.nearpoints.add(p); } public boolean check_if_nearpoint(point p){ return this.nearpoints.contains(p); }

---------------------------------------------------------------------------------------------------------------------- package 分支限界最大团;

import java.util.ArrayList;

public class Node implements Comparable<Node> {

private int node_in;

private point node_point;

private ArrayList<point> answer_points;

private int maxnum_point;

public Node(int n,point p,ArrayList<point> a,int m){

super();

this.node_in=n;

this.node_point=p;

this.answer_points=a;

this.maxnum_point=m;

}

public int compareTo(Node o) {

// TODO Auto-generated method stub

if(this.maxnum_point>o.maxnum_point) return -1;

if(this.maxnum_point<o.maxnum_point) return 1;

return 0;

}

public int get_node_in(){return this.node_in;}

public ArrayList<point> get_answer_point(){return this.answer_points;}

public boolean ifleft(){

for(point p:this.answer_points)

if(!p.check_if_nearpoint(this.node_point))

return false;

return true;

额,没什么好说的,自己看吧。

}

public boolean ifright(int total_point,int nowanswer){

int leftpoint=total_point-this.node_in;

if(this.answer_points.size()+leftpoint>nowanswer)

return true;

return false;

}

public int get_maxnum_point(){return this.maxnum_point;}

public point get_node_point(){return this.node_point;}

}

-----------------------------------------------------------------------

2、分支限 …… 此处隐藏：4138字，全部文档内容请下载后查看。喜欢就下载吧 ……