旅行商问题详解（Java语言实现TSP算法从入门到实践）

一、问题建模

假设我们有 n 个城市，编号为 0 到 n-1。我们可以用一个二维数组 dist[i][j] 表示城市 i 到城市 j 的距离。我们的任务是找到一个排列（路径），使得总距离最小，并且形成一个环（起点=终点）。

二、暴力回溯法（适合小规模数据）

对于城市数量较少（比如 n ≤ 10）的情况，我们可以使用回溯算法枚举所有可能的路径。虽然效率不高，但逻辑清晰，非常适合初学者理解回溯算法解决TSP的核心思想。

Java代码实现（回溯法）：

import java.util.*;public class TSPBacktrack {    private static int n;    private static int[][] dist;    private static boolean[] visited;    private static int minCost = Integer.MAX_VALUE;    public static void main(String[] args) {        // 示例：4个城市        n = 4;        dist = new int[][]{            {0, 10, 15, 20},            {10, 0, 35, 25},            {15, 35, 0, 30},            {20, 25, 30, 0}        };        visited = new boolean[n];        visited[0] = true; // 从城市0出发        backtrack(0, 0, 1); // 当前城市, 当前成本, 已访问城市数        System.out.println("最短路径长度为: " + minCost);    }    private static void backtrack(int current, int cost, int count) {        if (count == n) {            // 所有城市已访问，返回起点            minCost = Math.min(minCost, cost + dist[current][0]);            return;        }        for (int i = 0; i < n; i++) {            if (!visited[i]) {                visited[i] = true;                backtrack(i, cost + dist[current][i], count + 1);                visited[i] = false; // 回溯            }        }    }}

这段代码通过递归尝试所有未访问的城市，记录当前路径成本。当访问完所有城市后，加上返回起点的距离，更新全局最小值。这就是典型的回溯算法解决TSP的思路。

三、动态规划法（Held-Karp算法）

当城市数量稍大（如 n = 15~20）时，暴力法会超时。此时可以使用动态规划TSP的经典算法——Held-Karp算法，时间复杂度为 O(n²2ⁿ)，比 O(n!) 的暴力法高效得多。

核心思想：

定义状态 dp[mask][i] 表示：已经访问了 mask 所代表的城市集合（用位掩码表示），当前位于城市 i 时的最小路径成本。

Java代码实现（动态规划）：

public class TSPDP {    public static int tsp(int[][] dist) {        int n = dist.length;        int V = 1 << n; // 状态总数：2^n        int[][] dp = new int[V][n];        // 初始化为无穷大        for (int i = 0; i < V; i++) {            Arrays.fill(dp[i], Integer.MAX_VALUE / 2); // 防止溢出        }        dp[1][0] = 0; // 从城市0出发，mask=0001        for (int mask = 1; mask < V; mask++) {            for (int u = 0; u < n; u++) {                if ((mask & (1 << u)) == 0) continue; // u不在mask中                for (int v = 0; v < n; v++) {                    if ((mask & (1 << v)) != 0) continue; // v已在mask中，跳过                    int newMask = mask | (1 << v);                    dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + dist[u][v]);                }            }        }        int fullMask = V - 1;        int result = Integer.MAX_VALUE;        for (int i = 1; i < n; i++) {            result = Math.min(result, dp[fullMask][i] + dist[i][0]);        }        return result;    }    public static void main(String[] args) {        int[][] dist = {            {0, 10, 15, 20},            {10, 0, 35, 25},            {15, 35, 0, 30},            {20, 25, 30, 0}        };        System.out.println("最短路径长度为: " + tsp(dist));    }}

这个实现利用位运算高效表示城市集合，是动态规划TSP的标准解法，适合中等规模问题。

四、总结与扩展

通过本教程，你已经掌握了用Java实现TSP的两种基础方法：

• 回溯法：简单直观，适用于 n ≤ 10；
• 动态规划（Held-Karp）：更高效，适用于 n ≤ 20。

对于更大规模的TSP问题（如 n > 20），通常需要使用启发式算法，如遗传算法、模拟退火或蚁群优化。这些内容可作为后续学习方向。

无论你是学生、算法爱好者，还是准备面试的开发者，理解旅行商问题及其解法都将极大提升你的算法思维能力。动手试试吧！