当前位置：首页 > news >正文

旅行商问题（TSP）的 C++ 动态规划解法教学攻略

news 2025/6/7 7:53:55

一、问题描述

旅行商问题（TSP）是一个经典的组合优化问题。给定一个无向图，图中的顶点表示城市，边表示两个城市之间的路径，边的权重表示路径的距离。一个售货员需要从驻地出发，经过所有城市后回到驻地，要求总的路程最短。

二、输入输出形式

输入形式

输入的第一行包含两个整数 n 和 m，分别表示顶点个数和边数。接下来的 m 行中，每行包含三个整数 u、v 和 w，表示顶点 u 和顶点 v 之间有一条边，边的权重为 w。

输出形式

输出一个整数，表示最短路程的总长度。

三、样例输入输出

样例输入

样例输出

16

四、算法分析与设计

1. 动态规划算法

旅行商问题可以通过动态规划（DP）来解决。其核心思想是利用状态压缩来记录已经访问过的城市集合，并使用动态规划表来存储到达每个城市的最短路径。

2. 状态表示

定义 dp[S][i] 表示已经访问了集合 S 中的城市，最后到达城市 i 的最短路径。其中，S 是一个位掩码，表示已经访问过的城市集合。例如，S = (1 << n) - 1 表示所有城市都被访问过。

3. 状态转移

对于每个状态 S，遍历所有可能的城市 i，如果 i 在集合 S 中，则尝试将未访问的城市 j 加入集合 S，更新新的状态 S | (1 << j) 的最短路径。

4. 初始状态和结果提取

初始状态为 dp[full][i] = dist[i][0]，其中 full 表示所有城市都被访问过，dist[i][0] 是城市 i 回到起点 0 的距离。最终结果从 dp[1][0] 中提取，表示从起点 0 出发，访问所有城市后回到起点的最短路径。

五、代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;const int INF = 0x3f3f3f3f;int main() {int n, m;cin >> n >> m;// 初始化邻接矩阵vector<vector<int>> dist(n, vector<int>(n, INF));for (int i = 0; i < n; i++) {dist[i][i] = 0;}// 输入边信息并构建邻接矩阵for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;u--; // 转换为从 0 开始的索引v--;dist[u][v] = w;dist[v][u] = w;}// 动态规划表int full = (1 << n) - 1;vector<vector<int>> dp(1 << n, vector<int>(n, INF));// 初始化动态规划表，full 表示所有城市都被访问过for (int i = 0; i < n; i++) {dp[full][i] = dist[i][0];}// 填充动态规划表for (int S = full; S >= 0; S--) {if ((S & 1) == 0) continue; // 必须包含起点（城市 0）for (int i = 0; i < n; i++) {if (!((S >> i) & 1)) continue; // 城市 i 不在集合 S 中时跳过if (S == full) {continue; // full 已经初始化}for (int j = 0; j < n; j++) {if ((S >> j) & 1) continue; // 城市 j 已经在集合 S 中时跳过dp[S][i] = min(dp[S][i], dp[S | (1 << j)][j] + dist[i][j]);}}}// 输出结果cout << dp[1][0] << endl;return 0;
}