bttsp.java

旅行售货员算法分析与设计第六章例题实现与大家共享

/**
 *@author wangwei
 *@since 2007-12-5
 */
 public class Bttsp{
 	static int n = 4;   //the quantity of the V of the graphics G
 	static int[] x;  //the current result
 	static int[] bestx; //the current best result
 	static float bestc;  //the current best value
 	static float cc;      //the current expensive
 	//denote the Graphics G with matrix
 	static float[][] a = {
 		{Float.MAX_VALUE,Float.MAX_VALUE,Float.MAX_VALUE,Float.MAX_VALUE,Float.MAX_VALUE},
 		{Float.MAX_VALUE,Float.MAX_VALUE,30,6,4},
 		{Float.MAX_VALUE,30,Float.MAX_VALUE,5,10},
 		{Float.MAX_VALUE,6,5,Float.MAX_VALUE,20},
 		{Float.MAX_VALUE,4,10,20,Float.MAX_VALUE}
 		}; 
 		 
 	
 	/**
 	 *
 	 *the main function
 	 */
 	 
 	 public static void main(String[] args){
 	 	int[] v = {0,1,2,3,4};
 	 	float result = 0;
 	 	result = tsp(v);
 	 	System.out.print("最优路径是：");
        for(int element:bestx)
        	if(element != 0)
        		System.out.print(element + "---");
        System.out.println('1');
 	 	System.out.print("最优值是：");
 	 	System.out.print(result);

 	 }
 	
 	/**
 	 *the best result = 25.
 	 *the littlest road is 1->3->2->4->1
 	 */
 	 public static float tsp(int[] v){
 	 	//x 的单位排列
 	 	x = new int[n+1];
 	 	for(int i = 1;i <= n;i++)
 	 	  x[i] = i;
 	 	bestc = Float.MAX_VALUE;
 	 	bestx = v;
 	 	cc = 0;
 	 	//搜索x[2:n]的全排列
 	 	backtrack(2);
 	 	return bestc;
 	 }
 	 
 	 /**
 	  *the arithmetic of the back
 	  */
 	  private static void backtrack(int i){
 	  	if(i == n){
 	  		if(a[x[n-1]][x[n]] < Float.MAX_VALUE &&
 	  		   a[x[n]][1] < Float.MAX_VALUE &&
 	  		   (bestc == Float.MAX_VALUE || 
 	  		    cc + a[x[n-1]][x[n]] + a[x[n]][1] < bestc
 	  		   )
 	  		){
 	  			for(int j = 1;j <= n;j++)
 	  			  bestx[j] = x[j];
 	  			  bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];
 	  		}
 	  	}
 	  	else{
 	  		for(int j = i;j <= n;j++)
 	  		  //是否可以进入x[j]子树？
 	  		  if(a[x[i-1]][x[j]] < Float.MAX_VALUE &&
 	  		     (bestc == Float.MAX_VALUE ||
 	  		     cc + a[x[i-1]][x[j]] < bestc
 	  		     )
 	  		  ){
 	  		  	//搜索子树
 	  		  	Bttsp.swap(x,i,j);
 	  		  	cc += a[x[i-1]][x[i]];
 	  		  	backtrack(i+1);
 	  		  	cc -= a[x[i-1]][x[i]];
 	  		  	Bttsp.swap(x,i,j);
 	  		  }
 	  	}
 	  }
 	  /**
 	   *this method is used to swap the two elements in a array
 	   *@param int[]x:the name of the array
 	   *@param i,j;the suffix of the tow element in the array
 	   */
 		public static void swap(int[] x,int i,int j){
 			int temp;
 			temp = x[i];
 			x[i] = x[j];
 			x[j] = temp;
 		}
 }