旅行商问题（TSP）与状态压缩动态规划详解

经典算法模型：旅行商问题 (TSP) 与状压 DP

旅行商问题 (Traveling Salesperson Problem, TSP) 是计算机科学中最著名的 NP-Hard 问题之一。 问题描述：给定一系列城市和每对城市之间的距离，求解访问每一座城市恰好一次并回到起始城市的最短回路。

因为它是 NP-Hard 问题，目前没有多项式时间复杂度的精确解法。当城市数量 N \leq 20 时，我们通常使用状态压缩动态规划 (状压 DP) 来求解，可以将暴力排列的 O(N!) 复杂度极大地优化至 O(N^2 \cdot 2^N)。

1. 核心思想：为什么需要状压 DP？

如果使用暴力搜索（DFS 全排列），我们需要枚举所有城市的访问顺序，复杂度是 O(N!)。当 N = 15 时，15! \approx 1.3 \times 10^{12}，任何计算机都无法在合理时间内算完。

冗余计算在哪里？ 假设有 10 个城市，起点是 0。 路径 A：0 -> 1 -> 2 -> 3，距离 100 路径 B：0 -> 2 -> 1 -> 3，距离 120 此时我们都在城市 3，并且都已经访问过了集合 {0, 1, 2, 3}。对于后续还要访问的城市 {4, 5... 9} 来说，它们根本不在乎你是怎么到达 3 的，它们只关心：

1. 你现在在哪里？（决定下一步出发的距离）
2. 你已经访问了哪些城市？（决定还有哪些城市可以走）

因此，保留路径 B 是毫无意义的。我们可以将状态抽象为 “已访问的集合” 和 “当前所在的城市”。

2. 状态定义与转移方程

2.1 状态定义

使用一个二进制整数 S 来表示城市的访问集合。例如 S = 11_{10} = 1011_2，表示第 0, 1, 3 号城市已经被访问，第 2 号城市未访问。

设 dp[S][i] 表示：

• 当前已经访问过的城市集合为 ​S。
• 当前最后一步恰好停留在城市 ​i (​i \in S)。
• dp[S][i] 的值是从起点出发，满足上述条件的最短路径长度。

2.2 状态转移方程

我们是如何到达状态 dp[S][i] 的呢？ 必然是在上一步处于某个城市 j（j \in S 且 j \ne i），然后从城市 j 走了一步到达了 i。 那么到达 i 时的访问集合就应该是 S 扣除掉 i 之后的集合，记作 S \setminus \{i\}。

这引出了核心的转移方程：

位运算翻译：

• S 包含 i：(S & (1 << i)) != 0
• S 排除 i：S ^ (1 << i)
• dist[j][i]：城市 ​j 到 ​i 的距离。

2.3 初始化与最终答案

• 起点：假设从城市 0 出发。初始状态集合中只有 0 被访问，且停留在 0。 dp[1][0] = 0 (因为 ​1 的二进制是 ​00..01，表示仅第 0 位为 1)。 其他所有状态初始化为无穷大 INF。
• 终点：当所有城市都被访问过时，集合变为 ​(1 << N) - 1。但此时我们停留在某个城市 ​i 还没回到起点 0。 最终答案为：

3. C++ 标准模板代码

下面是一份极其标准、带有详细注释的 TSP 状压 DP 模板代码。城市编号统一采用 0 到 N-1，这能让位运算 1 << i 完美契合数组下标。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    int n;
    // 假设输入格式为：第一行 n 表示城市数量
    // 接下来 n 行 n 列表示城市间的距离矩阵 dist[i][j]
    if (!(cin >> n)) return 0;

    vector<vector<int>> dist(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> dist[i][j];
        }
    }

    // dp[S][i]: 集合S已被访问，当前在城市i的最短距离
    int max_state = 1 << n;
    vector<vector<int>> dp(max_state, vector<int>(n, INF));

    // 1. 初始化
    // 假设从城市 0 出发，集合为 1 (二进制 00..01)，停在 0，代价为 0
    dp[1][0] = 0;

    // 2. 状态转移
    // 外层循环从小到大枚举所有的状态集合 S
    for (int S = 1; S < max_state; ++S) {
      
        // 枚举当前所在的城市 i
        for (int i = 0; i < n; ++i) {
          
            // 剪枝：如果当前状态 S 中根本没有包含城市 i，则该状态不合法，跳过
            if ((S & (1 << i)) == 0) continue;
          
            // 如果 dp 值为 INF，说明这个状态不可达，直接跳过
            if (dp[S][i] == INF) continue;

            // 枚举下一步要去哪一个城市 j
            for (int j = 0; j < n; ++j) {
                // 如果城市 j 已经在集合 S 中，说明已经访问过了，不能重复访问
                if (S & (1 << j)) continue;

                // 尝试将 j 加入集合：新集合为 S | (1 << j)
                int next_S = S | (1 << j);
                dp[next_S][j] = min(dp[next_S][j], dp[S][i] + dist[i][j]);
            }
        }
    }

    // 3. 计算最终答案
    // 我们需要访问所有城市，即满状态 max_state - 1
    // 然后还要从最后停留的城市 i 走回起点 0
    int ans = INF;
    int full_state = max_state - 1;
    for (int i = 1; i < n; ++i) {
        // 满状态下，从城市 i 回到 0 的代价
        if (dp[full_state][i] != INF) {
            ans = min(ans, dp[full_state][i] + dist[i][0]);
        }
    }

    // 如果原图就是 1 个点，答案为 0
    if (n == 1) ans = 0;

    cout << "最短回路长度为: " << ans << "\n";

    return 0;
}

推包式写法 vs 拉包式写法 上面的代码采用的是 “推包式 (Push-style)”（或者叫刷表法）：用已知的 dp[S][i] 去更新未来的 dp[next_S][j]。在状压 DP 中，由于需要判断不可达的无效状态，这种写法通常比“拉包式（用过去更新现在）”代码更少，且能避开很多 -1 边界越界的问题。

4. 复杂度分析与拓展

• 时间复杂度：外层循环遍历所有状态 ​2^N，内层两重循环枚举当前点 ​i 和下一个点 ​j，耗时 ​O(N^2)。总时间复杂度为 ​O(N^2 \cdot 2^N)。当 ​N = 20 时，操作次数约为 ​4 \times 10^8，在部分要求严格的 OJ 上可能卡常，通常 ​N \leq 16 是绝对安全的。
• 空间复杂度：需要存储 dp 数组，大小为 ​2^N \cdot N，空间复杂度 ​O(N \cdot 2^N)。对于 ​N = 20，大约需要 ​20 \cdot 2^{20} \approx 20 \text{MB} 内存。

经典变体：

1. 哈密顿路径 (Hamiltonian Path)：不要求回到起点，只需要走遍所有点。答案就是 ​\min_{i} dp[(1<<N)-1][i]。
2. 多源起点：如果没有固定起点，可以将初始化改为对于所有 ​i，dp[1 << i][i] = 0。