状压 DP 入门：旅行商问题

1 一句话问题

n 个城市，给出距离矩阵 d[i][j]（从 i 走到 j 的距离）。 从 0 号城市出发，每个城市恰好经过一次，最后回到 0 号。求最短总路程。

这就是大名鼎鼎的旅行商问题（TSP）。

2 ★ 关键一步（一）：一个集合就是一个整数

这件事你在第 3 章（二进制枚举子集）就见过了，只不过那时候它是「枚举手段」。 这一章它要升级成状态。

点「运行 ▶」看结果

① 4 个元素，一共 16 个集合：

  整数   二进制   集合里有谁
  ----   ------   --------------------
     0     0000   {空集}
     1     0001   {0}
     2     0010   {1}
     3     0011   {0, 1}
     …
    15     1111   {0, 1, 2, 3}

3 手算一遍：4 个城市，六个数字贯穿全章

        到 0   到 1   到 2   到 3
   从 0    0      1      4      5
   从 1    2      0      9      1
   从 2    7      9      0      7
   从 3    6      9      2      0

（注意 d[0][1] = 1 而 d[1][0] = 2 —— 这就是「不对称」。）

从 0 出发，剩下 3 个城市有 3! = 6 种排法，全列出来：

正确答案 11。 后面五个数字都是写错的代码跑出来的：

11 / 2 / 4 / 12 / 20 / −1 —— 这六个数后面每一步都会回来验。

4 暴力：全排列枚举访问顺序

点「运行 ▶」看结果

跑出来 11，和手算一致。

这份代码里没有集合、没有位运算、没有 f 表 —— 它就是把「先去哪、再去哪」的所有排法 列一遍，各自加一加。正解那边是「按集合编号填表」，两边连状态的概念都没有 —— 这正是它当标准答案的资格（第 20 章那条规矩）。

5 ★ 关键一步（二）：状态里要带上「人现在在哪」

f[S][i] = 已经走过的城市集合恰好是 S（且 i ∈ S），此刻人停在 i，
          从 0 号出发走到这里的最短路程

f[S | 1<<j][j] = min( f[S][i] + d[i][j] )        j ∉ S

点「运行 ▶」看结果

跑出来 11。想看整张表长什么样，跑这份：

点「运行 ▶」看结果

   S   二进制   集合                 f[S][0]   f[S][1]   f[S][2]   f[S][3]
  --   ------   ------------------   -------   -------   -------   -------
   1     0001   {0}                        0         -         -         -
   3     0011   {01}                       -         1         -         -
   5     0101   {02}                       -         -         4         -
   7     0111   {012}                      -        13        10         -
   9     1001   {03}                       -         -         -         5
  11     1011   {013}                      -        14         -         2
  13     1101   {023}                      -         -         7        11
  15     1111   {0123}                     -        16         4        14

（- 表示这个局面根本到不了，比如「集合里没有 0 号，人却停在 0 号」。）

每一行用到的都只是上面某一行。 最后一行 S = 15 就是走遍全部城市， 三个落脚点各加一段回程：16+2 = 18、4+7 = 11、14+6 = 20 → 答案 11。

6 实测：两边都是指数，但指数的底完全不一样

本机实测（./genBig n，固定种子）：

n = 14 那一行差了将近一万倍。而状压 DP 还远没到极限：

暴力    (n-1)!      n = 20 → 19! ≈ 1.2 × 10¹⁷      （宇宙热寂也跑不完）
状压    2ⁿ · n²     n = 20 → 2²⁰ × 400 ≈ 4 亿      （零点几秒）

7 动画：一行一行往下填，目标永远在下方

每一行是一个集合（编号 / 二进制 / 里面有谁），每一列是「人停在哪」。 蓝色是正在处理的那一格，推出去的目标格会标成 绿色（目标还没处理，更新有效） 或 红色（目标早就定稿了，这笔更新白写）。

请注意目标行永远在当前行的下方 —— 那就是「加一个元素，整数一定变大」的画面版。

现在把顺序切成「从大到小」：

8 三种「答案有数但是错的」写法

点「运行 ▶」看结果

跑出来 2。求最小值的 DP，初值必须是「不可能达到的大数」。 设成 0 之后，每一个还没算出来的局面都变成了「白送的 0 代价」， 于是 min 会一路取到那些根本到不了的格子上。

check:viz 用 300 组数据钉死了它的样子：输出恒等于 min over i≠0 of d[i][0]， 也就是「谁离起点最近」—— 和整条路线毫无关系。

初值不是「随便填个数」，初值是在回答「哪些局面根本不存在」。 （第 23 章 exact.cpp 那一节说的是同一件事。）

点「运行 ▶」看结果

跑出来 4。

点「运行 ▶」看结果

跑出来 20。走遍所有城市之后人可以停在任何一个城市，回程各不相同， 必须把 n-1 种都试一遍。只看一个，等于凭空规定「最后一个必须是 3 号」。

（回头看第 3 步那张表：0→2→1→3→0 正好是 20 —— 那是所有「以 3 号结尾」的走法里最好的。）

9 ★ 主角登场：方向写反

点「运行 ▶」看结果

跑出来 12。人是从 i 走到 j，代价当然是 d[i][j]； 写成 d[j][i] 就是按回程的价钱付去程的钱。

这个 bug 不难看懂，但它是这一章的主角 —— 原因在第 12 步。先看它错得多离谱：

10 动画：把每条路线「真的走一遍」再算一次账

城市摆成一圈，蓝色是起点。实线是这份代码选出来的路线，绿色虚线是回起点那一段。

★ 右边那两个大数字是重点：上面是它自己报的答案，下面是拿真实距离把它选的路线 真的走一遍要花多少。

11 输出路线：删一个元素也只是一次位运算

点「运行 ▶」看结果

最短总路程 = 11

路线：0 -> 1 -> 3 -> 2 -> 0

  第几段   从 -> 到   这一段   累计
  ------   --------   ------   ----
       1     0 -> 1         1      1
       2     1 -> 3         1      2
       3     3 -> 2         2      4
       4     2 -> 0         7     11   <- 回起点这一段最容易忘

还是第 26、27 章那套：记下 from[S][i] = 「走到这个局面之前人在哪」，然后回溯。

★ 回溯时要「退回上一个局面」，也就是把当前城市从集合里去掉 —— S & ~(1 << i)。 一次位运算。 这正是「集合就是整数」最舒服的地方。

（check:viz 对这份输出做的是硬验证：路线必须从 0 出发、每个城市恰好一次、 最后回到 0，逐段加起来必须正好是 11。）

12 ★ 对拍：一个 bug 藏在「对称性」里

300 轮实测，六个错误版本：

13 这一章可以带走的四样东西

14 自测