TSP

public class TSP {

    private double[][] dArray; // 距离矩阵
    private int length; // 距离矩阵的长度

    public double[][] getdArray() {
        return dArray;
    }

    public int getLength() {
        return length;
    }

    public TSP(double[][] dArray) {
        if (this.check(dArray)) {
            this.dArray = dArray;
            this.length = dArray.length;
        }
    }

    private void dynamic() {
        double[][] D = this.dArray;// 原图的邻接矩阵
        int n = this.length;
        if (this.check(D)) {
            int m = (int) Math.pow(2, n - 1);// 列长度，每行有2的n-1次方列
            double[][] F = new double[n][m];// 存储阶段最优值，指标
            int[][] M = new int[n][m];// 存放阶段最优策略
            // 初始化F[][]和M[][]
            for (int j = 0; j < m; j++) {
                for (int i = 0; i < n; i++) {
                    F[i][j] = -1;
                    M[i][j] = -1;
                }
            }
            // 给F的第0列赋初值
            for (int i = 0; i < n; i++) {
                F[i][0] = D[i][0];
            }
            // 遍历并填表,除最后一列外，i：行，j：列
            double min = 0;
            for (int j = 1; j < m - 1; j++) {
                for (int i = 1; i < n; i++) {
                    if (((int) Math.pow(2, i - 1) & j) == 0) {
                        // 城市i不在j所代表的二进制集合中，可以填表
                        min = 0;
                        for (int k = 1; k < n; k++) {
                            if (((int) Math.pow(2, k - 1) & j) != 0) {
// 对于j集合中所有的k城市，都要存储,j-(int)Math.pow(2, k-1)表示去掉k城市节点后剩下的集合
                                double temp = D[i][k] + F[k][j - (int) Math.pow(2, k - 1)];
                                if (min == 0) {
                                    //第一次循环，直接给最小值赋初值
                                    min = temp;
                                    F[i][j] = min;// 保存阶段最优值
                                    M[i][j] = k;// 保存最优决策
                                }else {
                                    if (temp < min) {
                                        //取小
                                        min = temp;
                                        F[i][j] = min;// 保存阶段最优值
                                        M[i][j] = k;// 保存最优决策
                                    }
                                }
                            }
                        }
                    }
                }
            }
            // 最后一列，即总最优值的计算，且只有第一行有值，且为最优
            min = 0;
            for (int k = 1; k < n; k++) {
                // 二进制全1，表示集合{1,2,3,4,5}，从中去掉k结点即将k对应的二进制位置0
                double temp = D[0][k] + F[k][m-1-(int) Math.pow(2, k - 1)];
                if (min == 0) {
                    //第一次循环，直接给最小值赋初值
                    min = temp;
                    F[0][m-1] = min;// 总最优解
                    M[0][m-1] = k;
                }else {
                    if (temp < min) {
                        //取小
                        min = temp;
                        F[0][m-1] = min;// 总最优解
                        M[0][m-1] = k;
                    }
                }
            }
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(F[j][i]+",");
                }
                System.out.println();
            }
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(M[j][i]+",");
                }
                System.out.println();
            }
            //输出结果，回溯查表M
            System.out.println("最短距离为："+ F[0][m-1]);
            System.out.print("最短路径顺序为："+"0");
            for (int j = m-1,i = 0; j > 0; ) {
                i = M[i][j];//下一步去往哪个城市结点
                j = j-(int)Math.pow(2, i-1);//从j中去掉i节点
                System.out.print("-->"+i);
            }
            System.out.println("-->0");
        }
    }

    private boolean check(double[][] dArray) {
        // 城市少于三个
        if (dArray.length < 3) {
            System.out.println("错误信息：距离矩阵长度过小");
            return false;
        }
        // 不是方阵
        for (int i = 0; i < dArray.length; i++) {
            if (dArray.length != dArray[i].length) {
                System.out.println("错误信息：距离数组长度不合法");
                return false;
            }
        }
        for (int i = 0; i < dArray.length; i++) {
            if (!oneZero(dArray[i], i)) {
                System.out.println("错误信息：城市间距离设置不合法");
                return false;
            }
        }
        return true;
    }

    // 对于一个doulbe类型的数组， 当且仅有对角元素为0
    private boolean oneZero(double[] dArray, int i) {
        int numOfZero = 0;
        for (double d : dArray) {
            if (d == 0.0) {
                numOfZero++;
            }
        }
        if (numOfZero == 1 && (dArray[i] == 0)) {
            return true;
        } else {
            return false;
        }
    }

     //主函数
    public static void main(String[] args) {
        double[][] D = { // 各个节点之间路径长度的二维数组
                { 0, 10, 20, 30, 40, 50 }, 
                { 12, 0, 18, 30, 25, 21 }, 
                { 23, 9, 0, 5, 10, 15 }, 
                { 34, 32, 4, 0, 8, 16 }, 
                { 45, 27, 11, 10, 0, 18 }, 
                { 56, 22, 16, 20, 12, 0 }
        };
        long start = System.currentTimeMillis();
        TSP ff = new TSP(D);
        ff.dynamic();
        long end = System.currentTimeMillis();
        long between = end - start;
        System.out.println("java环境下用动态规划思想求解TSP问题的运行时间为："+between+"ms");
    }
}