旅行商问题详解（C语言实现动态规划求解TSP最短路径算法）

为什么选择动态规划？

暴力枚举所有可能路径的时间复杂度是 O(n!)，当城市数量 n 超过 10 时，计算量将变得极其庞大。而使用动态规划可以将时间复杂度优化到 O(n²·2ⁿ)，虽然仍是指数级，但对于 n ≤ 15 的情况已经非常实用。

核心思想：状态压缩 + 动态规划

我们用一个整数 mask 来表示已访问的城市集合（利用位运算）。例如，mask = 5（二进制 101）表示第0号和第2号城市已被访问。

定义 dp[mask][i] 表示：当前已访问的城市集合为 mask，且当前位于城市 i 时，从起点出发到这里的最短路径长度。

C语言实现步骤

1. 读取城市数量 n 和距离矩阵 dist[n][n]
2. 初始化 dp 数组（大小为 (1<
3. 设置初始状态：dp[1][0] = 0（从城市0出发）
4. 遍历所有状态 mask，更新 dp[mask][j]
5. 最终答案：min{ dp[(1<

完整C语言代码

#include <stdio.h>#include <limits.h>#define MAX_N 15#define INF 100000000int dist[MAX_N][MAX_N];int dp[1 << MAX_N][MAX_N];int min(int a, int b) {    return (a < b) ? a : b;}int main() {    int n;    printf("请输入城市数量（最多15个）: ");    scanf("%d", &n);    printf("请输入 %d x %d 的距离矩阵:\n", n, n);    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            scanf("%d", &dist[i][j]);        }    }    // 初始化dp数组    for (int mask = 0; mask < (1 << n); mask++) {        for (int i = 0; i < n; i++) {            dp[mask][i] = INF;        }    }    // 起点为城市0    dp[1][0] = 0;    // 动态规划填表    for (int mask = 1; mask < (1 << n); mask++) {        for (int i = 0; i < n; i++) {            if (!(mask & (1 << i))) continue; // 城市i不在当前集合中            for (int j = 0; j < n; j++) {                if (mask & (1 << j)) continue; // 城市j已在集合中，跳过                int new_mask = mask | (1 << j);                dp[new_mask][j] = min(dp[new_mask][j], dp[mask][i] + dist[i][j]);            }        }    }    // 计算回到起点的最短路径    int ans = INF;    int full_mask = (1 << n) - 1;    for (int i = 1; i < n; i++) {        ans = min(ans, dp[full_mask][i] + dist[i][0]);    }    printf("\n最短旅行路径长度为: %d\n", ans);    return 0;}

如何运行这段代码？

1. 将代码保存为 tsp.c
2. 在终端执行：gcc tsp.c -o tsp && ./tsp
3. 输入城市数量（例如4）
4. 输入4×4的距离矩阵（对角线通常为0）

注意事项

• 本算法适用于城市数量 ≤ 15 的情况（因使用 2ⁿ 状态）
• 距离矩阵应是对称的（即 dist[i][j] == dist[j][i]），但非对称TSP也可处理
• 若存在不可达城市，请用一个大数（如 INF）表示

总结

通过本教程，你已经掌握了如何用C语言算法结合动态规划TSP思想解决经典的旅行商问题。虽然该方法不能处理超大规模实例，但对于学习最短路径算法和状态压缩技巧非常有价值。建议你动手敲一遍代码，修改输入数据，观察输出结果，加深理解！

© 2023 算法学习指南 | 专注C语言与经典算法教学