旅行售货员问题

问题描述

• 给定一组城市和每对城市之间的距离，访问每个城市一次，然后返回起点，求最短的可能路线。

算法设计

• 将城市0（假设为第0个节点）作为起点和终点，由于路线是循环的，所以我们可以把任何一点作为起点。
• 以DFS(Depth-First-Search）方式开始从源到相邻节点的遍历。
• 计算每次遍历的距离，跟踪最小距离，并不断更新最小距离存储值，以最低距离返回结果。

代码实现

public class test {

    public static void main(String[] args) {
        // 顶点（结点）的数量。
        int n = 4;
        int[][] graph = {
                {0, 10, 15, 20},
                {10, 0, 35, 25},
                {15, 35, 0, 30},
                {20, 25, 30, 0}
        };
        // boolean类型的数组 v 用来标记一个城市结点是否被访问过。
        boolean[] v = new boolean[n];
        // 标记第 0 个结点已经被访问过，所以v[0]=true
        v[0] = true;
        int ans = Integer.MAX_VALUE;
        // 查找最小权重的回路。
        ans = tsp(graph, v, 0, n, 1, 0, ans);
        System.out.println(ans);

    }

    static int tsp(int[][] graph, boolean[] v, int currPos, int n, int count, int cost, int ans) {
        // 判断访问是否完成，并将本次访问结果的路程与之前的路径取最小值并返回。
        if (count == n && graph[currPos][0] > 0) {
            ans = Math.min(ans, cost + graph[currPos][0]);
            return ans;
        }
        for (int i = 0; i < n; i++) {
            // 遍历访问未被标记且距离大于0的节点。
            if (!v[i] && graph[currPos][i] > 0) {
                // 标记结点被访问过。
                v[i] = true;
                // 递归搜索下一个节点，同时计数增加1，并按graph[currPos][i]值增加代价。
                ans = tsp(graph, v, i, n, count + 1, cost + graph[currPos][i], ans);
                // 回溯撤回结点标记。
                v[i] = false;
            }
        }
        return ans;
    }
}

• tsp(int[][] graph, boolean[] v, int currPos, int n, int count, int cost, int ans)：计算TSP问题的最优解。
  • int[][] graph：存储节点与路径的邻接表矩阵。
  • boolean[] v：记录节点是否被访问过。
  • int currPos：表示当点所在的节点。
  • int count：表示当前已经访问了几个节点，如果等于总节点数，即访问完成。
  • int cost：表示代价总和。即总路径。
  • int ans：表示当前最小的总路径。