一、动态规划

import java.util.ArrayList;

/**
 * @author xifeng.yang
 */
public class TSPEngine {
    private ArrayList<Integer> outputArray = new ArrayList<>();
    private int dp[][]; //重叠子问题的记忆, 表示由i出发、途径集合j中的元素、再回到起始点0的最短长度;
    private int path[][]; //表示在所选路径最优的情况下, 下一步要到达的点;
    private int distance[][];
    private int nPow, N;
    public static long time;

    public ArrayList<Integer> computeTSP(int[][] inputArray, int n) {
        long start = System.nanoTime();
        N = n;
        nPow = (int) Math.pow(2, n);
        dp = new int[n][nPow];
        path = new int[n][nPow];
        distance = inputArray;
        int i, j;
        for (i = 0; i < n; i++) {
            for (j = 0; j < nPow; j++) {
                dp[i][j] = -1;
                path[i][j] = -1;
            }
        }

        /* 从i出发, 直接到达起始点0的长度. */
        for (i = 0; i < n; i++) {
            dp[i][0] = inputArray[i][0];
        }

        outputArray.add(0);
        int result = tsp(0, nPow - 2);
        getPath(0, nPow - 2);
        outputArray.add(result);
        long end = System.nanoTime();
        time = (end - start) / 1000;
        return outputArray;
    }

    /**
     * 从start出发, 途径集合set中的元素(由二进制中的非0位来表示), 再回到起始点时的最短长度, 即:
     * tsp(start, set) = min{start-> {set} -> 0)}.
     *
     * @param start
     * @param set
     * @return
     */
    private int tsp(int start, int set) {
        int masked, mask, result = -1, temp;
        if (dp[start][set] != -1) {
            return dp[start][set];
        } else {
            for (int x = 0; x < N; x++) {
                mask = nPow - 1 - (int) Math.pow(2, x);
                masked = set & mask;

                //过滤掉set中未置1的元素.
                if (masked != set) {
                    temp = distance[start][x] + tsp(x, masked);
                    if (result == -1 || result > temp) {
                        //更新result的同时, 也更新path.
                        result = temp;
                        path[start][set] = x;
                    }
                }
            }

            dp[start][set] = result;
            return result;
        }
    }

    private void getPath(int start, int set) {
        if (path[start][set] == -1) {
            return;
        }
        int x = path[start][set];
        int mask = nPow - 1 - (int) Math.pow(2, x);
        int masked = set & mask;
        outputArray.add(x);
        getPath(x, masked);
    }

    public static void main(String[] args) {

        int[][] inputArray = {{0, 12, 11, 16}, {15, 0, 15, 10}, {8, 14, 0, 18}, {9, 11, 17, 0}};

        TSPEngine tspEngine = new TSPEngine();
        System.out.println("result:" + tspEngine.computeTSP(inputArray, 4));
    }
}

模拟退火算法解决TSP问题：

思路：

参数选取，包括初始温度、冷却系数(coolingFactor, 一般选取0.98或0.99)；
随机选取某个旅行顺序作为起始值；
开始退火过程，步骤如下：
3.1 随机交换当前旅行顺序中的两个元素，计算出新的路径值newEnergy，与现有的currentEnergy作对比：
① 如果newEnergy < currentEnergy，则接受新的方案；
② 如果exp((currentEnergy - newEnergy) / temperature) > Random(0, 1)，则接受新的方案。temperature越大，越有可能接受较差的值。
3.2 降温冷却，temperature = temperature * coolingFactor。当温度冷却至1度以下时，结束循环，否则重复执行步骤3。