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

point new_point_node=new_node_set.get(new_node_in);

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

int

new_node_nowpath=old_node.get_now_path_long()+this.get_value(old_point_node, new_point_node)+this.get_value(new_point_node, startpoint);

int maybe_the_best=new_node_nowpath;

Node new_node=new Node(new_node_in, new_node_set, new_node_nowpath, maybe_the_best);

if(new_node.get_now_path_long()<this.answerpathlong){

this.answerpathlong=new_node.get_now_path_long();

enode.offer(new_node);

}

continue;

}

for(int i=old_node.get_node_in()+1;i<total_point;i++){//尝试原节点的各个分支

if(old_node.if_in_i(i, this.a, this.answerpathlong)){

int new_node_in=old_node.get_node_in()+1;

ArrayList<point> newnode_nowset=new ArrayList<>(old_node.get_now_sort());

int j=new_node_in;

this.changeij(newnode_nowset, i, j);

point old_node_to_point=old_node.get_node_point();

point new_node_to_point=newnode_nowset.get(new_node_in); int

new_maybe_the_best=old_node.get_node_answer()+this.get_value(old_node_to_point, new_node_to_point)-old_node_to_point.getshortestlong();

int

new_node_path_long=old_node.get_now_path_long()+this.get_value(old_node_to_point, new_node_to_point);

Node new_node=new Node(new_node_in, newnode_nowset, new_node_path_long, new_maybe_the_best);

enode.offer(new_node);

}

}

}

}

private void changeij(ArrayList<point> points,int i, int j) {

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

// TODO Auto-generated method stub

Collections.swap(points, i, j);

}

public void show(){

System.out.println(this.answer_points);

System.out.println("最优路径长度为："+this.answerpathlong);

}

private void set_point_short_long(){

point p;

int[]value;

for(int i=0;i<this.points.size();i++){

p=this.points.get(i);

value=this.a[i];

for(int x:value){

if(x==0)continue;

if(x<p.getshortestlong())p.setshortestlong(x);

}

}

}

}

------------------------------------------------------------------------------- package 旅行售货员问题;

public class point {

private static int ids=0;

private int id;

private int shortestlong;

public point() {

super();

this.id=point.ids++;

this.shortestlong=Integer.MAX_VALUE;

}

public int getid() {

return id;

}

@Override

public String toString() {

return "顶点："+this.id+";"; } public int getshortestlong() { return shortestlong; } public void setshortestlong(int s) { this.shortestlong = s;

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

}

------------------------------------------------------------------------------- package 旅行售货员问题;

import java.util.ArrayList;

public class Node implements Comparable<Node>{

private int node_in;

private point node_point;

private ArrayList<point>now_sort;

private int now_path_long;

private int node_answer;

public Node(int in, ArrayList<point> set, int p_l,int n_a) { super();

this.node_in = in;

this.now_sort = set;

this.now_path_long = p_l;

this.node_answer = n_a;

this.node_point=this.now_sort.get(in);

}

public boolean if_in_i(int i,int[][]a,int now_long){

point now_point=now_sort.get(node_in);

point pointi=now_sort.get(i);

int now_id=now_point.getid();

int pointi_id=pointi.getid();

int value=a[now_id][pointi_id];

if(value==Integer.MAX_VALUE)return false;

int

pointi_answer=this.node_answer+value-now_point.getshortestlong(); if(pointi_answer>now_long)return false;

return true;

}

public boolean if_end(int point_sum){

if(this.node_in==point_sum-1)return true;

return false;

}

public boolean if_end_father(int point_number){

if(this.node_in==point_number-2)return true;

return false;

}

public int get_now_path_long() {

return now_path_long;

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

public ArrayList<point> get_now_sort() {

return now_sort;

}

public int get_node_in() {

return node_in;

}

public int get_node_answer() {

return node_answer;

}

public point get_node_point() {

return node_point;

}

@Override

public int compareTo(Node o) {

if(this.node_answer>o.node_answer)return 1;

if(this.node_answer<o.node_answer)return -1;

return 0;

}

}

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

五、实验总结

(本次实验完成的情况，心得体会)