G状压 DP

集合状压 / TSP

最短 Hamilton·吃奶酪

本课摘要

集合状压 / TSP课程回答“集合访问状态如何保证 Hamilton 路径不重不漏”。内容以最短 Hamilton·吃奶酪为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。

  • 判断集合状压 / TSP的适用条件与状态边界
  • 围绕“最短 Hamilton·吃奶酪”推导转移与计算顺序
  • 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节

正在整理目录…

走遍所有点，暴力为何不行

旅行商问题（TSP）：从起点出发，不重不漏地走遍所有 nn 个点，让总路程最短。最直白的想法是枚举点的排列——nn 个点有 n!n! 种走法，n=12n=12 已接近五亿，n=15n=15 就上万亿，彻底不可行。

但仔细想：走到某一步时，接下来怎么走最优，只跟两件事有关——「已经走过了哪些点」（一个集合）和「此刻站在哪个点」。至于这些点是按什么顺序走到的，对未来毫无影响。这就把 n!n! 条路径，坍缩成了「已访问集合 × 当前点」这么多状态。

维度一：已访问集合 S（用点阵表示）03121100S = 0110 → 已到过点 1、2维度二：当前停在点 ii=2dp[0110][2] = 到此最短路
TSP 状态两个维度：已访问集合 S（用比特点阵表示）+ 当前停留的点 i。

「已访问集合」用状态压缩再合适不过：nn 个点的子集，正好是一个 nn 位二进制数 SS，第 ii 位为 11 表示点 ii 已访问。集合共 2n2^n 个，配上 nn 个「当前点」，状态总数 2n⋅n2^n\cdot n——n=18n=18 也只有约 470470 万，可以承受。

状态与转移：dp[S][i]

定状态。设 dp[S][i]dp[S][i] 表示：已经走过的点集合恰为 SS、当前停在点 ii（ii 必属于 SS）时，走出这条路径的最短总长。

转移。从 dp[S][i]dp[S][i] 出发，选一个还没访问过的点 jj（即第 jj 位在 SS 里是 00），走过去。新集合是 SS 点亮第 jj 位，当前点变成 jj，路程加上 dist(i,j)dist(i,j)：

已在集合 S={0,1}、当前停在点 1，下一步去未访问的点 2 或 30123+dist(1,2)新状态：S ∪ {2} = 0111dp[0111][2]
从当前点 i 走向未访问点 j：集合并入 j，用 S ∪ {j} 更新 dp[S∪{j}][j]。
dp[S∪{j}][j]=min⁡(dp[S∪{j}][j], dp[S][i]+dist(i,j))dp[S\cup\{j\}][j]=\min\big(dp[S\cup\{j\}][j],\ dp[S][i]+dist(i,j)\big)

边界：dp[{0}][0]=0dp[\{0\}][0]=0（从点 0 出发，只到过点 0，路程 0）。答案：走遍全集后停在终点 tt，即 dp[(1<<n)−1][t]dp[(1{<}{<}n)-1][t]。 实现时按 SS 从小到大枚举——因为并入新点后 S∪{j}>SS\cup\{j\}>S，保证每个状态被用到时，它依赖的子状态已经算好。

本质

状压把「已访问哪些点」这个集合编码成一个整数下标，于是「走过的历史」被压进 dpdp 的第一维。n!n! 条排列坍缩为 O(2n⋅n)O(2^n\cdot n) 个状态、每个状态 O(n)O(n) 转移，总复杂度 O(2n⋅n2)O(2^n\cdot n^2)——这是 n≤20n\le 20 的 TSP 唯一可行的通用解法。

跟着算一遍

取 44 个点，起点为 00，看几个关键状态怎么被填出来。集合用 4 位二进制表示（最高位是点 3）：

01112030
集合 S = 0011：点 0、1 已访问，点 2、3 待访问（顶端为点编号）。
0
起点。 dp[0001][0]=0dp[0001][0]=0——集合只含点 0，停在 0，路程 0。其余状态先设为 +∞+\infty。
1
从 0 走到 1。 j=1j=1 未访问：dp[0011][1]=dp[0001][0]+dist(0,1)=dist(0,1)dp[0011][1]=dp[0001][0]+dist(0,1)=dist(0,1)。集合从 00010001 点亮第 1 位成 00110011。
2
再从 1 走到 2。 现在 S=0011S=0011、当前在 11，去 j=2j=2：dp[0111][2]=dp[0011][1]+dist(1,2)dp[0111][2]=dp[0011][1]+dist(1,2)。集合变 01110111。
3
收尾。 当 S=1111S=1111（全走过）时，dp[1111][i]dp[1111][i] 就是「走遍四点、停在 ii」的最短路。开环 TSP 取 min⁡idp[1111][i]\min_i dp[1111][i] 即答案。
下面的演示把 dp[S][i]dp[S][i] 直接铺成网格：行是集合 mask，列是当前点。拖动小地图上的点、增删点数，看整张表怎么从起点一格格点亮。

dp[S][i] 就是一张表

dp[S][i]dp[S][i] 有两个下标，天生就是二维表格：把 2n2^n 个集合当作行、nn 个当前点当作列。每一步转移，都是从某个已算好的格子，指向「集合更大一位、当前点为 jj」的新格子。

点位（点 0 = 起点 · 可移动 · 曼哈顿距离）
0123
移动每个点
0
1,1
1
5,2
2
4,6
3
1,5
点数 4
行 = 已访问集合 mask（二进制，共 2^4 行）；列 = 当前停留的点。看它如何从起点 0001 逐步点亮，最后一行取最小即答案。
0
1
2
3
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
·
·
·
·
0
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
当前计算 依赖来源 被选转移 已确定
dp[{0}][0]=0dp[\{0\}][0]=0
起点：dp[0001][0]=0，只访问点 0 并停在点 0。
已暂停，第 1 步，共 17 步，1 倍速

开环还是闭环：一个 +dist(i,0) 的差别

上面求的是Hamilton 路径——走遍所有点就结束，不必回到起点，答案是 min⁡idp[(1<<n)−1][i]\min_i dp[(1{<}{<}n)-1][i]。这是「最短 Hamilton 路径」和「吃奶酪」的形态。

但「售货员的难题」要求走一圈回到出发城市——这是闭环 TSP（Hamilton 回路）。状态转移一模一样，只有最后一步不同：停在 ii 后还得补上回起点的边，答案变成 min⁡i(dp[(1<<n)−1][i]+dist(i,0))\min_i\big(dp[(1{<}{<}n)-1][i]+dist(i,0)\big)。

开环：Hamilton 路径01234终态 dp[(1<<n)−1][i]闭环：售货员回路01234末尾必须 +dist(i,0)
开环：走遍即止；闭环：末尾必须再加一条回到起点 0 的边（虚线）。差别只在收尾。

常见陷阱：开环 / 闭环、有向 / 无向别混

闭环忘了 +dist(i,0)+dist(i,0) 会算成开环，答案偏小；开环误加了回边则偏大。另外「售货员」是有向图，dist(i,j)dist(i,j) 未必等于 dist(j,i)dist(j,i)，转移里务必用方向正确的那条边。起点固定为 00 是惯例——回路从哪点断开都一样，固定起点可省去一层枚举。

例题

P10447最短 Hamilton 路径洛谷原生普及+/提高
题意
给定 nn 个点的带权无向图（n≤20n\le 20），求从点 00 到点 n−1n-1、恰好经过每个点各一次的最短路径长。
为什么选它
TSP 状压最纯的模板：没有坐标、没有几何，输入直接给邻接矩阵，让你把注意力全放在 dp[S][i]dp[S][i] 的状态设计和「枚举未访问点」的转移上。先立骨架就选它。
状态 · 转移 · 复杂度
dp[S][i]dp[S][i]=走过 SS、停在 ii 的最短路；dp[S∪{j}][j]=min⁡(⋅,dp[S][i]+wij)dp[S\cup\{j\}][j]=\min(\cdot,dp[S][i]+w_{ij})；O(2nn2)O(2^n n^2)。
参考代码
C++
在洛谷打开 P10447 
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
int w[25][25];               // 两点间边权
int f[1 << 20][25];          // f[S][i]：走过集合 S、当前停在 i 的最短路

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> w[i][j];

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;                            // 只到过点 0、停在 0，路程 0

    for (int S = 1; S < (1 << n); S++)      // 枚举集合（升序保证子集先算）
        for (int i = 0; i < n; i++)
        {
            if (!(S >> i & 1)) continue;    // i 必须已在集合内
            if (f[S][i] == 0x3f3f3f3f) continue;
            for (int j = 0; j < n; j++)
            {
                if (S >> j & 1) continue;   // ★j 必须尚未访问
                int T = S | (1 << j);       // 把 j 加入集合
                f[T][j] = min(f[T][j], f[S][i] + w[i][j]);
            }
        }

    cout << f[(1 << n) - 1][n - 1] << endl; // 走遍全集、停在点 n-1
    return 0;
}
P1433吃奶酪洛谷原生普及+/提高
题意
平面上 nn 块奶酪（n≤15n\le 15），老鼠从原点 (0,0)(0,0) 出发，求吃完所有奶酪走过的最短欧氏距离。
换个视角
把原点也当作一个点（编号 0），就化归为「从 0 出发的开环 TSP」，只是边权是欧氏距离（用 doubledouble）。题面亲切、坐标直观，是把抽象 TSP 落到几何上的最佳过渡。
参考代码
C++
在洛谷打开 P1433 
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
double x[20], y[20];
double dist[20][20];
double f[1 << 16][16];       // 下标 0 代表原点 (0,0)，1..n 为奶酪

int main()
{
    cin >> n;
    x[0] = y[0] = 0;                        // 原点当作第 0 个点
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            dist[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j])
                            + (y[i] - y[j]) * (y[i] - y[j]));

    int m = n + 1;                          // 连原点共 m 个点
    for (int S = 0; S < (1 << m); S++)
        for (int i = 0; i < m; i++) f[S][i] = 1e18;
    f[1][0] = 0;                            // 从原点出发

    for (int S = 1; S < (1 << m); S++)
        for (int i = 0; i < m; i++)
        {
            if (!(S >> i & 1) || f[S][i] > 1e17) continue;
            for (int j = 0; j < m; j++)
            {
                if (S >> j & 1) continue;
                int T = S | (1 << j);
                f[T][j] = min(f[T][j], f[S][i] + dist[i][j]);
            }
        }

    double ans = 1e18;
    for (int i = 1; i < m; i++)             // 吃完所有奶酪，停哪都行
        ans = min(ans, f[(1 << m) - 1][i]);
    printf("%.2f\n", ans);
    return 0;
}
P1171售货员的难题洛谷原生普及+/提高
题意
nn 个村庄，售货员从家（1 号）出发，走遍所有村庄再回到家，给定两两距离，求最短总路程（n≤20n\le 20）。
换个视角
与前两题的关键差别：这是闭环——末尾必须 +dist(i,0)+dist(i,0) 回到起点。把它和开环并排，正好暴露「回不回起点」这个最常见的 TSP 坑。
参考代码
C++
在洛谷打开 P1171 
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
int w[25][25];
int f[1 << 20][25];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> w[i][j];

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;                            // 从 1 号城市（下标 0）出发

    for (int S = 1; S < (1 << n); S++)
        for (int i = 0; i < n; i++)
        {
            if (!(S >> i & 1) || f[S][i] == 0x3f3f3f3f) continue;
            for (int j = 0; j < n; j++)
            {
                if (S >> j & 1) continue;
                int T = S | (1 << j);
                f[T][j] = min(f[T][j], f[S][i] + w[i][j]);
            }
        }

    int ans = 0x3f3f3f3f;
    for (int i = 1; i < n; i++)             // ★闭环：末尾必须再回到起点 0
        ans = min(ans, f[(1 << n) - 1][i] + w[i][0]);
    cout << ans << endl;
    return 0;
}

练习

P2831[NOIP2016 提高组] 愤怒的小鸟换个集合含义：S=已消灭的猪的集合。预处理每条抛物线能打掉哪些猪（压成 mask），转移选一条线覆盖新猪——是 TSP 之外的「集合覆盖」状压，见下一类。在洛谷打开
P2915[USACO08NOV] Mixed Up Cows G排列型集合状压，与 TSP 同构：f[S][i]=用完集合 S、末位是 i 的合法排列数，转移要求相邻编号差 > K。把「最短路」换成「计数」。在洛谷打开

已进入 集合状压 / TSP · 状压 DP · DP大师