动态规划求解旅行商问题java实现添加注释

public class TSP {

    private int[][] distance; // 存储城市间的距离
    private int numCities; // 城市数量

    public TSP(int[][] distance) {
        this.distance = distance;
        this.numCities = distance.length;
    }

    public int tsp() {
        int[][] dp = new int[1 << numCities][numCities]; // dp数组，表示访问某些城市的最短路径
        for (int i = 0; i < (1 << numCities); i++) { // 初始化为最大值
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[1][0] = 0; // 初始化：访问第一个城市，距离为0
        for (int mask = 1; mask < (1 << numCities); mask += 2) { // 枚举所有城市集合
            for (int i = 0; i < numCities; i++) { // 枚举终点城市
                if ((mask & (1 << i)) != 0) { // 该城市已访问
                    for (int j = 0; j < numCities; j++) { // 枚举起点城市
                        if ((mask & (1 << j)) != 0 && i != j) { // 起点城市已访问且不等于终点城市
                            dp[mask][i] = Math.min(dp[mask][i], dp[mask ^ (1 << i)][j] + distance[j][i]); // 状态转移方程
                        }
                    }
                }
            }
        }
        int res = Integer.MAX_VALUE; 
        for (int i = 1; i < numCities; i++) { // 枚举所有终点城市
            res = Math.min(res, dp[(1 << numCities) - 1][i] + distance[i][0]); // 计算最短路径
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] distance = { // 城市间的距离矩阵
                {0, 10, 15, 20},
                {10, 0, 35, 25},
                {15, 35, 0, 30},
                {20, 25, 30, 0}
        };
        TSP tsp = new TSP(distance); // 创建TSP对象
        int shortestPath = tsp.tsp(); // 求解最短路径
        System.out.println("The shortest path is " + shortestPath); // 输出结果
    }

}