 C++ 解法)
旅行商问题（TSP）是经典的组合优化问题，核心是给定 n 个城市及城市间的距离，求访问所有城市一次且仅一次后回到起点的最短路径。这里介绍两种易理解的解法：暴力枚举法（适合小规模数据）和动态规划法（适合中等规模数据）。
一、 暴力枚举法
原理
枚举所有城市的排列组合，计算每种排列的路径长度，取最小值。n 个城市的排列数为 (n-1)! （起点固定，减少重复计算）。
C++ 代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
// 计算路径总长度
int calculatePath(const vector<vector<int>>& dist, const vector<int>& path) {
int total = 0;
int n = path.size();
for (int i = 0; i < n - 1; i++) {
total += dist[path[i]][path[i + 1]];
}
total += dist[path[n - 1]][path[0]]; // 回到起点
return total;
}
int TSP_brute(const vector<vector<int>>& dist) {
int n = dist.size();
vector<int> path(n);
for (int i = 0; i < n; i++) path[i] = i; // 初始化路径 0->1->2->...->n-1
int min_dist = INT_MAX;
// 固定起点为0，枚举其余城市的排列
do {
if (path[0] != 0) break;
int current = calculatePath(dist, path);
if (current < min_dist) {
min_dist = current;
}
} while (next_permutation(path.begin(), path.end()));
return min_dist;
}
int main() {
// 邻接矩阵表示城市距离，dist[i][j]是城市i到j的距离
vector<vector<int>> dist = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
int min_path = TSP_brute(dist);
cout << "最短路径长度：" << min_path << endl;
return 0;
}
优缺点
优点：逻辑简单，容易理解和实现。
缺点：时间复杂度极高 O((n-1)!) ，n>10 时运行效率极低。
二、 动态规划法
原理
基于状态压缩 DP，用 dp[mask][u] 表示访问过的城市集合为 mask，当前位于城市 u 时的最短路径长度。
mask 是二进制数，第 i 位为 1 表示城市 i 已访问。
初始状态： dp[1<<0][0] = 0 （只访问起点 0，路径长度为 0）。
状态转移： dp[mask][u] = min(dp[mask ^ (1<<u)][v] + dist[v][u]) （v 是 mask 中已访问的城市）。
最终答案： min(dp[(1<<n)-1][u] + dist[u][0]) （访问所有城市后回到起点）。
C++ 代码
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int INF = INT_MAX / 2; // 防止加法溢出
int TSP_dp(const vector<vector<int>>& dist) {
int n = dist.size();
int max_mask = 1 << n;
// dp[mask][u]: 状态mask，当前在u的最短路径
vector<vector<int>> dp(max_mask, vector<int>(n, INF));
dp[1 << 0][0] = 0; // 初始状态
for (int mask = 1; mask < max_mask; mask++) {
for (int u = 0; u < n; u++) {
if (!(mask & (1 << u))) continue; // u不在mask中，跳过
// 枚举上一个访问的城市v
for (int v = 0; v < n; v++) {
if (u == v || !(mask & (1 << v))) continue;
dp[mask][u] = min(dp[mask][u], dp[mask ^ (1 << u)][v] + dist[v][u]);
}
}
}
// 访问所有城市后回到起点0
int min_dist = INF;
int full_mask = (1 << n) - 1;
for (int u = 1; u < n; u++) {
min_dist = min(min_dist, dp[full_mask][u] + dist[u][0]);
}
return min_dist;
}
int main() {
vector<vector<int>> dist = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
int min_path = TSP_dp(dist);
cout << "最短路径长度：" << min_path << endl;
return 0;
}
优缺点
优点：时间复杂度 O(n²×2ⁿ) ，比暴力法高效，能处理 n≤20 的数据。
缺点：空间复杂度 O(n×2ⁿ) ，n 过大时内存消耗大。
三、 测试与总结
1. 上述代码的测试用例是 4 个城市，最短路径长度为 80。
2. 暴力法适合理解 TSP 问题本质，动态规划法是入门级高效解法。
3. 对于更大规模数据，可学习贪心算法或遗传算法等近似解法。
