C++实现旅行商问题（TSP）详解：从零开始掌握最短路径算法

为什么TSP这么难？

对于n个城市，可能的路径数量为 (n-1)! / 2（因为回路对称）。例如：

• n = 5 → 12 种路径
• n = 10 → 181,440 种路径
• n = 20 → 超过 6×10¹⁶ 种路径！

暴力枚举在城市数较多时完全不可行。因此，我们需要更聪明的算法，比如动态规划。

C++动态规划解法原理

我们使用状态压缩动态规划（Bitmask DP）来解决小规模TSP（通常 n ≤ 20）。核心思想是：

• 用一个整数 mask 表示已访问的城市集合（二进制位表示）
• dp[mask][i] 表示：已访问 mask 中的城市，当前位于城市 i，回到起点的最短路径长度
• 通过递归+记忆化搜索或自底向上填表求解

完整C++代码实现

以下是一个完整的、可运行的C++程序，使用动态规划求解TSP：

#include <iostream>#include <vector>#include <climits>#include <algorithm>using namespace std;const int MAXN = 20;const int INF = INT_MAX / 2; // 防止加法溢出int n;int dist[MAXN][MAXN];int dp[1 << MAXN][MAXN];// 动态规划求解TSPint tsp(int mask, int pos) {    // 如果所有城市都访问过了    if (mask == (1 << n) - 1) {        return dist[pos][0]; // 回到起点    }    // 如果已经计算过，直接返回    if (dp[mask][pos] != -1) {        return dp[mask][pos];    }    int ans = INF;    // 尝试访问每一个未访问的城市    for (int city = 0; city < n; city++) {        if ((mask & (1 << city)) == 0) { // 如果city未被访问            int newAns = dist[pos][city] + tsp(mask | (1 << city), city);            ans = min(ans, newAns);        }    }    return dp[mask][pos] = ans;}int main() {    cout << "请输入城市数量（最多20个）: ";    cin >> n;    cout << "请输入距离矩阵（" << n << "x" << n << "）:\n";    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            cin >> dist[i][j];        }    }    // 初始化dp数组为-1    for (int i = 0; i < (1 << n); i++) {        for (int j = 0; j < n; j++) {            dp[i][j] = -1;        }    }    int result = tsp(1, 0); // 从城市0出发，mask=1表示已访问城市0    cout << "\n最短路径长度为: " << result << endl;    return 0;}

如何编译和运行？

1. 将上述代码保存为 tsp.cpp
2. 打开终端，执行：
g++ -o tsp tsp.cpp
3. 运行程序：
./tsp

输入示例（4个城市）：

0 10 15 2010 0 35 2515 35 0 3020 25 30 0

输出应为：80（即最短回路长度）

算法复杂度分析

• 时间复杂度：O(n² × 2ⁿ) —— 对于每个状态（共 2ⁿ × n 个），需要 O(n) 时间转移
• 空间复杂度：O(n × 2ⁿ) —— 存储 dp 表

虽然仍是指数级，但比暴力法的 O(n!) 好得多。这也是为什么该方法适用于 n ≤ 20 的场景。

总结

通过本教程，你已经学会了如何用C++实现旅行商问题的动态规划解法。这不仅帮助你理解了TSP算法的核心思想，也掌握了C++动态规划在组合优化中的应用。虽然该方法不能解决大规模问题，但它是学习更高级启发式算法（如遗传算法、模拟退火）的重要基础。

记住，TSP不仅是理论问题，它在物流配送、电路板钻孔、DNA测序等领域都有实际应用。掌握最短路径算法将为你打开算法世界的大门！