旅行商问题（TSP）- 状态压缩DP
📌 定义
旅行商问题（Traveling Salesman Problem, TSP）：给定 n 个城市和它们之间的距离，求访问所有城市恰好一次并返回起点的最短路径。
示例:
城市: 0, 1, 2, 3
距离矩阵:
0 1 2 3
0 [ 0 10 15 20 ]
1 [ 10 0 35 25 ]
2 [ 15 35 0 30 ]
3 [ 20 25 30 0 ]
最短路径: 0 → 1 → 3 → 2 → 0
总距离: 10 + 25 + 30 + 15 = 80
核心思路
使用状态压缩动态规划：
- 状态表示：用 n 位二进制数表示访问城市的集合
- DP定义：
dp[mask][i]= 从起点出发，访问了 mask 中的城市，当前在城市 i 的最短路径 - 状态转移：枚举下一个要访问的城市
状态压缩示例（4个城市）:
mask = 1011 (二进制)
表示访问了城市 0, 1, 3
第0位=1: 访问了城市0 ✓
第1位=1: 访问了城市1 ✓
第2位=0: 未访问城市2
第3位=1: 访问了城市3 ✓
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力枚举 | O(n!) | O(n) | 枚举所有排列 |
| 状态压缩DP | O(n² × 2^n) | O(n × 2^n) | 实际可行的最优解 |
| 近似算法 | O(n²) ~ O(n³) | O(n) | 不保证最优 |
Go 代码
Go 实现
package main
import (
"fmt"
"math"
)
func tsp(dist [][]int) int {
n := len(dist)
INF := math.MaxInt32 / 2
// dp[mask][i]
dp := make([][]int, 1<<n)
for i := range dp {
dp[i] = make([]int, n)
for j := range dp[i] {
dp[i][j] = INF
}
}
// 初始状态
dp[1][0] = 0
// 状态转移
for mask := 1; mask < (1 << n); mask++ {
for i := 0; i < n; i++ {
if (mask & (1 << i)) == 0 {
continue
}
if dp[mask][i] == INF {
continue
}
for j := 0; j < n; j++ {
if (mask & (1 << j)) != 0 {
continue
}
nextMask := mask | (1 << j)
dp[nextMask][j] = min(
dp[nextMask][j],
dp[mask][i]+dist[i][j],
)
}
}
}
// 计算结果
finalMask := (1 << n) - 1
result := INF
for i := 1; i < n; i++ {
result = min(result, dp[finalMask][i]+dist[i][0])
}
return result
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
dist := [][]int{
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0},
}
result := tsp(dist)
fmt.Printf("最短路径长度: %d\n", result)
}思路展开
状态压缩详解
4个城市，mask用4位二进制表示:
mask = 1011
位 | 3 | 2 | 1 | 0
城市 | 3 | 2 | 1 | 0
值 | 1 | 0 | 1 | 1
含义: 访问了城市 0, 1, 3
状态转移详解
dp[mask][i] = 访问了mask中的城市，当前在城市i的最短路径
转移方程:
dp[mask | (1<<j)][j] = min(
dp[mask | (1<<j)][j],
dp[mask][i] + dist[i][j]
)
从城市i转移到城市j:
1. mask中包含i（已访问）
2. mask中不包含j（未访问）
3. 将j加入访问集合
4. 更新到达j的最短距离
完整示例
4个城市，dist矩阵:
0 1 2 3
0 [ 0 10 15 20 ]
1 [ 10 0 35 25 ]
2 [ 15 35 0 30 ]
3 [ 20 25 30 0 ]
=== 初始化 ===
dp[0001][0] = 0 (只访问城市0)
=== mask=0001 (只有城市0) ===
当前城市i=0，可以去城市1,2,3:
dp[0011][1] = dp[0001][0] + dist[0][1] = 0 + 10 = 10
dp[0101][2] = dp[0001][0] + dist[0][2] = 0 + 15 = 15
dp[1001][3] = dp[0001][0] + dist[0][3] = 0 + 20 = 20
=== mask=0011 (访问了0,1) ===
当前城市i=1，可以去城市2,3:
dp[0111][2] = dp[0011][1] + dist[1][2] = 10 + 35 = 45
dp[1011][3] = dp[0011][1] + dist[1][3] = 10 + 25 = 35
=== mask=0101 (访问了0,2) ===
当前城市i=2，可以去城市1,3:
dp[0111][1] = dp[0101][2] + dist[2][1] = 15 + 35 = 50
dp[1101][3] = dp[0101][2] + dist[2][3] = 15 + 30 = 45
...（继续直到访问所有城市）
=== mask=1111 (所有城市) ===
从城市1,2,3返回城市0:
result = min(
dp[1111][1] + dist[1][0], # 从1回0
dp[1111][2] + dist[2][0], # 从2回0
dp[1111][3] + dist[3][0] # 从3回0
)
经典题目
LeetCode 问题
- 旅行商问题 - LeetCode 943（最短超级串，类似TSP）
- 访问所有节点的最短路径 - LeetCode 847
- 最小化旅行的最大时间 - LeetCode 2065
TSP变体
- 对称TSP vs 非对称TSP
- 多旅行商问题（mTSP）
- 带时间窗的TSP
⚖️ 优缺点
优点
- ✅ 保证最优解：动态规划找到全局最优
- ✅ 可处理中等规模：n ≤ 20 可以接受
- ✅ 可扩展：容易修改处理变体问题
缺点
- ❌ 指数级复杂度：n > 20 不可行
- ❌ 空间消耗大：需要 O(n × 2^n) 空间
- ❌ 大规模问题：需要使用近似算法
🎨 应用场景
- 路线规划：城市、仓库或服务节点数量较少时，求访问全部节点的最短闭环。
- 任务访问顺序：把“已完成任务集合 + 当前任务”作为状态，求最优执行顺序。
- 小规模全排列优化：当
n不大但暴力排列重复计算严重时，用状态压缩保存公共子问题。
💡 优化技巧
- 遍历未访问城市时，用
remaining := fullMask ^ mask取出候选集合，再用bit := remaining & -remaining每次删除一个最低位。 - 对称距离矩阵可以固定起点，并利用反向路径等价性减少重复状态。
- 当
n超过状态压缩 DP 的适用范围，改用分支限界或近似算法，不要硬撑O(n2^n)。
💡 近似算法
- 最近邻：每次走向最近的未访问城市，速度快但不保证最优。
- 最小生成树加倍：先求 MST，再通过遍历顺序构造一条可行回路，适合需要快速得到近似解的场景。
- 局部搜索：对已有路线尝试 2-opt 等交换，持续消除明显的交叉和冗余。