旅行商问题（Traveling Salesman Problem，TSP）是组合优化领域最具代表性的NP-hard问题之一。问题描述极为直观：一位商人需要拜访若干城市，每对城市之间有已知距离，要求找到一条从起点出发、经过每个城市恰好一次并最终回到起点的最短回路。本文用Java实现基于状态压缩动态规划的精确解法，深入讲解位运算状态表示、子集递推与路径重建的完整流程。
问题建模与复杂度分析
问题定义
给定n个城市组成的完全图，城市编号为0到n-1，dist[i][j]表示城市i到城市j的距离。目标是找到一条哈密顿回路（经过每个顶点恰好一次的环），使得总距离最小。
为什么暴力不可行
n个城市的排列共有(n-1)!/2种（固定起点并消除方向对称）。当n=20时，排列数约为6×10^16，穷举完全不可行。因此需要更聪明的算法——动态规划。
动态规划的核心思想
TSP具有最优子结构：假设最短回路中从城市0出发，第一步走到城市k，那么从k出发走完剩余所有城市并返回0的子路径，也必须是最短的。基于此，定义状态：
dp[mask][i] = 从城市0出发，已经访问过的城市集合为mask，当前位于城市i的最短距离
其中mask是一个n位二进制数，第j位为1表示城市j已被访问。
状态压缩的位运算技巧
状态表示
mask的范围是0到(1<<n)-1，共2^n种状态- 检查城市i是否被访问：
if ((mask & (1 << i)) != 0) - 将城市i标记为已访问：
mask | (1 << i) - 将城市i从集合中移除：
mask ^ (1 << i)或mask & ~(1 << i)
状态转移方程
dp[mask][i] = min(dp[mask ^ (1 << i)][j] + dist[j][i]) 对所有 j∈mask 且 j≠i 且 j≠0
含义：要到达状态(mask, i)，上一步必然在某个城市j，从j走到i。去掉i后得到子状态(mask^(1<<i), j)。
初始化与边界
dp[1 << 0][0] = 0：只访问了城市0，当前位于城市0，距离为0- 其余所有状态初始化为正无穷
最终答案
answer = min(dp[(1<<n)-1][i] + dist[i][0]) 对所有 i≠0
所有城市都已访问（mask全为1），从最后一个城市i返回起点0。
完整Java实现
以下代码实现了TSP的状态压缩DP解法，包含核心算法、路径重建与复杂度分析。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/**
* 旅行商问题（TSP）—— 状态压缩动态规划精确解法
* 时间复杂度: O(n^2 * 2^n)
* 空间复杂度: O(n * 2^n)
* 适用规模: n <= 20（状态数 2^20 ≈ 100万）
*/
public class TravelingSalesmanProblem {
// 无穷大表示不可达或初始状态
private static final int INF = Integer.MAX_VALUE / 2;
private final int n; // 城市数量
private final int[][] dist; // 距离矩阵
private int[][] dp; // dp[mask][i]: 已访问mask集合，当前在i的最短距离
private int[][] parent; // 路径重建：记录dp[mask][i]是从哪个城市转移而来
public TravelingSalesmanProblem(int[][] dist) {
this.n = dist.length;
this.dist = new int[n][n];
for (int i = 0; i < n; i++) {
this.dist[i] = Arrays.copyOf(dist[i], n);
}
// dp数组大小: 2^n * n
int totalStates = 1 << n;
this.dp = new int[totalStates][n];
this.parent = new int[totalStates][n];
for (int[] row : dp) {
Arrays.fill(row, INF);
}
for (int[] row : parent) {
Arrays.fill(row, -1);
}
}
/**
* 执行状态压缩动态规划求解TSP
* @return 最短回路的总距离
*/
public int solve() {
// 初始状态：只访问了城市0，当前位于城市0
dp[1 << 0][0] = 0;
// 枚举所有状态mask
for (int mask = 1; mask < (1 << n); mask++) {
// 如果当前状态没有访问城市0，跳过（起点必须是0）
if ((mask & 1) == 0) continue;
// 枚举当前所在城市i
for (int i = 0; i < n; i++) {
// 如果当前状态mask中没有城市i，跳过
if ((mask & (1 << i)) == 0) continue;
// 如果dp[mask][i]不可达，跳过
if (dp[mask][i] == INF) continue;
// 尝试从城市i前往下一个未访问的城市j
for (int j = 0; j < n; j++) {
// j必须是未访问的城市，且不能是起点0（最后才回起点）
if ((mask & (1 << j)) != 0) continue;
int nextMask = mask | (1 << j);
int newDist = dp[mask][i] + dist[i][j];
if (newDist < dp[nextMask][j]) {
dp[nextMask][j] = newDist;
parent[nextMask][j] = i; // 记录从i转移到j
}
}
}
}
// 所有城市都已访问，从最后一个城市返回起点0
int fullMask = (1 << n) - 1;
int minTour = INF;
int lastCity = -1;
for (int i = 1; i < n; i++) {
if (dp[fullMask][i] == INF) continue;
int tourLength = dp[fullMask][i] + dist[i][0];
if (tourLength < minTour) {
minTour = tourLength;
lastCity = i;
}
}
return minTour;
}
/**
* 重建最短回路路径
* @return 城市访问顺序列表（包含起点作为首尾）
*/
public List<Integer> reconstructPath() {
int fullMask = (1 << n) - 1;
int minTour = INF;
int lastCity = -1;
// 找到最终状态中的最优终点
for (int i = 1; i < n; i++) {
if (dp[fullMask][i] == INF) continue;
int tourLength = dp[fullMask][i] + dist[i][0];
if (tourLength < minTour) {
minTour = tourLength;
lastCity = i;
}
}
if (lastCity == -1) {
return Collections.emptyList();
}
// 逆序回溯路径
List<Integer> path = new ArrayList<>();
int mask = fullMask;
int cur = lastCity;
while (cur != -1) {
path.add(cur);
int prev = parent[mask][cur];
mask ^= (1 << cur);
cur = prev;
}
Collections.reverse(path);
path.add(0); // 回到起点，形成回路
return path;
}
/**
* 打印dp状态表（仅用于小规模调试）
*/
public void printDPState() {
System.out.println("=== DP状态表 ===");
for (int mask = 0; mask < (1 << n); mask++) {
System.out.printf("mask=%d: ", mask);
for (int i = 0; i < n; i++) {
if (dp[mask][i] == INF) {
System.out.print("INF ");
} else {
System.out.print(dp[mask][i] + " ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
// 示例：4个城市及其之间的距离矩阵
// 城市0=A, 1=B, 2=C, 3=D
int[][] dist = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
TravelingSalesmanProblem tsp = new TravelingSalesmanProblem(dist);
int minLength = tsp.solve();
System.out.println("=== 旅行商问题（TSP）状态压缩DP求解 ===\n");
System.out.println("最短回路总距离: " + minLength);
List<Integer> path = tsp.reconstructPath();
System.out.print("最优访问顺序: ");
for (int i = 0; i < path.size(); i++) {
char city = (char) ('A' + path.get(i));
System.out.print(city);
if (i < path.size() - 1) {
System.out.print(" -> ");
}
}
System.out.println();
// 更大规模测试（8个城市）
System.out.println("\n=== 8城市规模测试 ===");
int[][] dist8 = {
{0, 29, 82, 46, 68, 52, 72, 42},
{29, 0, 55, 46, 42, 43, 43, 23},
{82, 55, 0, 68, 46, 55, 23, 43},
{46, 46, 68, 0, 82, 15, 72, 31},
{68, 42, 46, 82, 0, 74, 23, 52},
{52, 43, 55, 15, 74, 0, 61, 23},
{72, 43, 23, 72, 23, 61, 0, 42},
{42, 23, 43, 31, 52, 23, 42, 0}
};
TravelingSalesmanProblem tsp8 = new TravelingSalesmanProblem(dist8);
long start = System.currentTimeMillis();
int min8 = tsp8.solve();
long elapsed = System.currentTimeMillis() - start;
System.out.println("8城市最短距离: " + min8);
System.out.println("计算耗时: " + elapsed + "ms");
System.out.print("最优路径: ");
for (int city : tsp8.reconstructPath()) {
System.out.print(city + " ");
}
System.out.println();
}
}
路径重建原理
路径重建依赖parent[mask][i]数组。在状态转移时，一旦dp[nextMask][j]被更新，就记录parent[nextMask][j] = i，表示到达状态(nextMask, j)的最优路径中，上一个城市是i。
重建时从最终状态(fullMask, lastCity)出发，不断查询parent并移除当前城市对应的位，逆序收集所有城市后反转即可。最后将起点0追加到末尾，形成完整回路。
复杂度分析
| 指标 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n² × 2ⁿ) | 共2ⁿ个状态，每个状态转移需O(n) |
| 空间复杂度 | O(n × 2ⁿ) | dp与parent两个二维数组 |
| 适用规模 | n ≤ 20 | 2²⁰ ≈ 100万状态，可秒级求解 |
| 精确性 | 全局最优 | 与穷举等价，保证找到最短回路 |
当n > 20时，状态数呈指数爆炸，此时应转向启发式算法（如模拟退火、遗传算法、蚁群算法）或近似算法（如最近邻、最小生成树近似）。
扩展：非对称TSP
上述实现天然支持非对称距离（dist[i][j] ≠ dist[j][i]），只需在输入时提供任意距离矩阵即可。若某些城市之间不可达，可将对应距离设为INF，算法会自动排除这些边。
总结
旅行商问题是理解NP-hard问题与动态规划结合的绝佳案例。状态压缩技巧将指数级枚举转化为”状态×当前位置”的递推结构，利用位运算高效表示集合，使得中等规模（n≤20）的TSP可以在可接受时间内精确求解。本文实现的Java版本完整覆盖了算法核心、路径重建与性能测试，可直接集成到路径优化、物流调度等实际项目中。
