tsp

public class TSP {
    double [][] a;//邻接矩阵，给出任意两个点之间的距离
    double min;//所有结点跑且仅跑一遍后最短的路程。
    double total;//当前路程
    int[] bestx;//最优巡回路劲
    int[] x;//排列数组
    int n;
    double[] mine;//第i个结点的所有边中值最小的被记进mine[i]
    
    TSP(double[][] aa){//传无向图的邻接矩阵进去
        a=aa;
        n=a.length;
        mine=new double[n];
        x=new int[n];
        for(int i=0;i<n;i++)
            {
                mine[i]=Double.MAX_VALUE;
                for(int j=0;j<n;j++)
                    if(i!=j&&a[i][j]<mine[i]) mine[i]=a[i][j];
            }

        cacu();//calculate
    }
    
    void swap(int i,int j){//交换，java数组不能用a[i]+=a[j]来换。
        int a=0;
        a=x[i];
        x[i]=x[j];
        x[j]=a;
    }
    
    void cacu(){//因为是巡回一圈，所以可以任选一个结点固定为起点。搜索排列树。
        min=Double.MAX_VALUE;
        total=0;
        bestx=new int[n];
        for(int i=0;i<n;i++)
            x[i]=i;

        backtrack(1);//从第二个结点开始搜索排列树，这样n个结点有(n-1)!条不同的路径。
        

        }
    
        void backtrack(int t){

        if(t>=n) {update();return;}
        for(int i=t;i<n;i++){
            swap(t,i);
            total+=a[x[t-1]][x[t]];//第t个位置轮流由想x[t],x[t+1],x[t+2]..来坐。
            if(bound(t))  backtrack(t+1);
            total-=a[x[t-1]][x[t]];
            swap(t,i);
            }
        
    }   
        
        boolean bound(int t){//限界，看还有多少进步空间。只有加上最理想的进步空间还小于已经找到的min时，才继续搜索。
            double rtotal=total;
            for(int i=t;i<n-1;i++)
                rtotal+=mine[x[i]];
            rtotal+=a[x[n-1]][x[0]];
            return rtotal<min;
        }
        
        void update(){
            min=total+a[x[n-1]][x[0]];
            for(int i=0;i<n;i++)
            bestx[i]=x[i];
        }
        public static void main(String[] args) {
            int n=4;
            double [][] a=new double [n][n];
            a[0][1]=a[1][0]=1;
            a[0][2]=a[2][0]=2;
            a[0][3]=a[3][0]=6;
            a[1][2]=a[2][1]=5;
            a[1][3]=a[3][1]=3;
            a[2][3]=a[3][2]=4;
            TSP tsp=new TSP(a);
            System.out.println(tsp.min);
            for(int i=0;i<n;i++)
                System.out.print(tsp.bestx[i]);
        }
}

旅行商问题 image.png