TSP · 旅行商问题

题目链接：https://qycode64.com/p/TSP

标签：状态压缩 DP、旅行商问题

一、题意

有 $n$ 座城市（编号 $1\sim n$），对任意两座不同城市 $i,j$，都存在一条有向边 $i\to j$，花费为 $c_{i,j}$。注意 $c_{i,j}$ 与 $c_{j,i}$ 不一定相等。

一名旅行商从城市 $1$ 出发，要求恰好访问每座城市一次，最后**回到城市 **$1$。求最小总花费。

• $2\le n\le 18$
• $1\le c_{i,j}\le 10^9$（$i\ne j$），$c_{i,i}=0$

---

二、思路

1. 从哈密顿路径说起

哈密顿路径（Hamiltonian Path）：在一张图中，经过每个顶点恰好一次的路径。

哈密顿回路（Hamiltonian Cycle）：在哈密顿路径的基础上，起点与终点相同，形成一条闭合的回路。

本题要求「从城市 1 出发，每座城市恰好访问一次，最后回到城市 1」，这正是求一条权值最小的哈密顿回路，即经典的旅行商问题（TSP，Travelling Salesman Problem）。

TSP 是 NP-hard 问题，没有多项式时间解法。但本题 $n\le 18$，提示我们可以用指数级算法——状态压缩 DP（状压 DP）。

2. 为什么暴力不行

最朴素的做法是枚举城市的全排列，共 $n!$ 种。当 $n=18$ 时 $18!\approx 6.4\times 10^{15}$，远超时间限制。必须换一种枚举方式，避免对同一子问题的重复计算。

3. 状态压缩的核心思想

一条哈密顿回路可以拆成「起点固定为城市 1（下文用 0 编号） + 一条以城市 0 开头的哈密顿路径 + 回到 0 的最后一条边」。

于是问题转化为：求一条从 0 出发、经过所有城市、最后停在某个城市 $i$ 的最小花费路径，再补上 $c_{i,0}$ 取最小值即可。

这里关键的观察是：当前路径的最优性只依赖于「已经访问过哪些城市」和「当前停在哪个城市」，而与访问的先后顺序无关。也就是说：

• 已经访问过的城市集合 $S$
• 当前所在城市 $i$

这两者就足以描述一个子问题。集合 $S$ 可以用一个 $n$ 位二进制数表示（第 $k$ 位为 1 表示城市 $k$ 已访问），这就是「状态压缩」。

4. 状态定义

$$dp[\text{mask}][i] = \text{从城市 0 出发，恰好访问 mask 中的城市（必须包含 0 和 i），最后停在 i 的最小花费}$$

• mask 是一个 $n$ 位二进制数，表示已访问城市的集合。
• $i$ 是当前所在城市（必须在 mask 中）。

初始状态：$dp[1][0]=0$，即只访问了起点 0，花费为 0。其余均为 $+\infty$。

5. 状态转移

对每个状态 $(\text{mask}, i)$，尝试从 $i$ 走到一个尚未访问的城市 $j$：

$$dp[\text{mask}\cup\{j\}][j] = \min\big(dp[\text{mask}\cup\{j\}][j],\ dp[\text{mask}][i]+c_{i,j}\big)$$

即「已访问集合」加入 $j$，终点变为 $j$，花费增加 $c_{i,j}$。

枚举顺序：按 mask 从小到大递推（因为 mask | (1<<j) > mask，保证无后效性）。

6. 计算答案

当 mask 包含全部 $n$ 座城市（即 mask = (1<<n)-1）时，路径已访问所有城市，停在某个 $i$。最后还需回到起点 0：

$$\text{ans} = \min_{i}\big(dp[\text{full}][i]+c_{i,0}\big)$$

由于 $n\ge 2$ 且图是完全图，必然存在合法回路，答案一定存在。

7. 复杂度分析

• 状态数：$2^n\times n$
• 每个状态转移：$O(n)$
• 总时间复杂度：$O(2^n\cdot n^2)$，$n=18$ 时约 $8.5\times 10^7$，可接受。
• 空间复杂度：$O(2^n\cdot n)$，约 $4.7\times 10^6$ 个 long long，需要约 38 MiB，在 256 MiB 限制内。
• 注意总花费可达 $(n-1)\times 10^9\approx 1.7\times 10^{10}$，超过 int 范围，须用 long long。

---

要点：

• 城市内部用 0-indexed，起点为城市 0。
• dp[1][0]=0 为唯一初始状态。
• 枚举 mask 时跳过不含城市 0 的集合（不可能从 0 出发却没访问 0）。
• 答案为 $\min_i dp[\text{full}][i]+c_{i,0}$。

所以代码如下：

#include <bits/stdc++.h>
using namespace std;
int main () {
    int n;
    scanf ("%d", &n);
    vector <vector <long long> > c (n, vector <long long> (n));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) scanf("%lld", &c[i][j]);
    }
    const long long INF = 1e18;
    vector <vector <long long> > dp (1 << n, vector <long long> (n, INF));
    dp[1][0] = 0;
    for(int mask = 1; mask < (1 << n); mask++){
        if(!(mask & 1)) continue;
        for(int i = 0; i < n; i++){
            if(!(mask & (1 << i))) continue;
            if(dp[mask][i] >= INF) continue;
            for(int j = 0; j < n; j++){
                if(mask & (1 << j)) continue;
                int nmask = mask | (1 << j);
                if(dp[nmask][j] > dp[mask][i] + c[i][j]) dp[nmask][j] = dp[mask][i] + c[i][j];
            }
        }
    }
    long long ans = INF;
    int full = (1 << n) - 1;
    for(int i = 0; i < n; i++) {
        if(dp[full][i] < INF) ans = min (ans, dp[full][i] + c[i][0]);
    }
    printf ("%lld\n", ans);
    return 0;
}