bttsp.java

来自「,《算法设计与分析》王晓东编著」· Java 代码 · 共 72 行

public class Bttsp {
	static int n;		//图G的定点数
	static int[] x;		//当前解
	static int[] bestx;	//当前最优解
	static float bestc;	//当前最优值
	static float cc;	//当前费用
	static float[][] a = {
		{0,0,0,0,0,0},
		{0,32,30,43,43,100},
		{0,10,23,120,23,32},
		{0,100,100,32,30,32},
		{0,23,23,43,54,80},
		{0,32,56,87,45,32},
	};//图G的邻接矩阵
	
	
	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;
	}
	
	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)){
					//搜索子树
					MyMath.swap(x,i,j);
					cc += a[x[i-1]][x[i]];
					backtrack(i+1);
					cc -= a[x[i-1]][x[i]]; 
					MyMath.swap(x,i,j);
				}
			}
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		n = 5;
		int[] v = {0,1,2,3,4,5};
		double bestc = tsp(v);
		System.out.println("The bestc is "+bestc);
		System.out.print("The bestx is ");
		for(int i = 1;i<=n;i++){
			System.out.print(bestx[i]+" ");
		}
		
	}

}