位运算状压DP与TSP经典解法

可视化演示

状态压缩DP利用位运算表示集合，适用于n小于等于20的小规模组合优化问题。本文详解TSP的O(n^2*2^n)... 切换模式查看不同维度。

TSP问题模型

阿青把六座城市的名字写在集章册封面上，围着地图看了半天。它发现：所谓最优路线，本质是「访问完全部城市后回到原点」的一圈走法，城市之间可以直飞，但每座城市恰好落地一次。这就是旅行商问题（TSP）——一个在快递线路、芯片布线、机器人路径规划里反复出现的经典组合优化问题。

要找到最短的那一圈，最笨的办法是把所有可能的拜访顺序全部枚举出来：第一站有 5 种选择，第二站 4 种，第三站 3 种……总共有 5! = 120 条路线（固定起点后）。对 6 座城市这还好办，但 n 变成 20 时，排列数会膨胀到 1.2×10¹⁷——这个数字大到即使每秒检查一亿条路线，也要跑将近四十年。

阿青盯着这个天文数字直摇头：靠一只青蛙挨个试走法，下辈子也集不齐章。它突然想到，很多路线的「前缀」其实是重复的——比如先到 1 号城再到 2 号城，和先到 2 号城再到 1 号城，后续要面对的都是「剩下四座城市怎么走」这个同样的问题。如果能把这些重复的子问题记下来，不就能省下海量计算吗？这个念头，正是动态规划的种子。

位运算表示集合

怎么「记下来」呢？阿青低头看了看集章册：六页纸，每页只有「盖了章 / 空白」两种状态。这不就是二进制吗！把集章册拍扁成一串数位：第 i 位是 1 表示去过第 i 座城市，是 0 表示没去过。于是一整本册子就缩成了一个普通整数——这就是「状态压缩」的名字由来：把一个集合压进一个整数里。

这个表示集合的整数，业界叫它「掩码」（mask）。阿青需要三套手指功夫：判断某座城市是否已盖章（检查某一位是否为 1）、盖章（把某一位变成 1）、撕章（把某一位变回 0）。位运算把它们做得干净利落：

有了这套指法，阿青的集章册变成了一张轻盈的「位图」。6 座城市只有 2⁶ = 64 种盖章组合，20 座城市也不过 2²⁰ ≈ 104 万种——一张小表格就能记下所有「已访问集合」。阿青感叹：原来把册子拍扁，世界就变小了。

状态定义与初始化

光有集章册还不够，阿青在每页册子上又添了一行字：「此刻我站在哪座城市」。因为同样盖了 {0,1,2} 三枚章，从 2 号城出发继续赶路，和从 0 号城出发继续赶路，未来的路程完全是两码事。于是它定义了这样的记录：

这个二维表格就是 DP 的「账本」。阿青从老家 0 号城出发，此时册子上只有 0 号城的章，走过的距离是 0；其它「还没发生」的状态，距离统统记为一个极大的数 INF（想象成∞，表示「这条路线目前还不存在」）。注意 mask 的初始值不是 0，而是含有起点的 1，因为访问集合永远至少包含出发城市：

阿青把账本空页全部填上「∞」，郑重地在第一页写下 dp[1][0] = 0——这是整趟旅程的起跑线。它深吸一口气：有了这么清晰的记账规则，接下来只需要一条铁律：每盖一枚新章，就翻旧账、算新账。

转移方程推导

阿青发现一个精妙的倒推法：想算出「册子盖满 6 枚章、我站在 i 城」的最短距离，不必从头算起——只要看「撕掉 i 城这一页章后，我上一站站在哪个城市 j」。当时册子上的章比现在少一枚，走过的路记在账本 dp[mask 去掉 i][j] 里，再加上从 j 飞到 i 的距离 dist[j][i]，就拼出了当前状态的一条候选路线。把所有可能的上一站 j 都试一遍，取最小即可：

最终，阿青等册子盖满所有章（mask = 全 1），站在某个城市 i，再飞回老家 0 号城收尾，取全程最小，就是 TSP 的答案：

阿青合上账本，长长舒了口气：原来「倒着撕章」比「正着排路线」聪明太多了。每一笔账都站在前一笔账的肩膀上，重复的子问题被压缩成一次查询——这就是动态规划化腐朽为神奇的地方。

复杂度与空间优化

阿青算了算账本的规模：mask 有 2ⁿ 种取值，每种 mask 对应 n 个可能的「当前城市」，所以账本最多 n·2ⁿ 格。每格在转移时要枚举 n 个候选上一站，总计算量就是 n²·2ⁿ。这套复杂度是状压 DP 的「身份证」：

n=20 时，2²⁰ ≈ 104 万，乘上 20 约 2000 万格子，现代计算机轻松拿下；但 n=30 时 2³⁰ 超过 10 亿，直接内存爆炸。所以 n ≤ 20 是状压 DP 的「舒适区」。空间上还能再省：转移只依赖「少一枚章」的 mask，若按 mask 中 1 的个数分层递推，同层状态算完后即可丢弃，内存可从 n·2ⁿ 压到大约 2ⁿ（只保留上一层），这就是滚动数组思想。不过竞赛与工程中，n≤20 时直接开满也完全够用，空间优化更多是为了优雅。

阿青看着账本尺寸，心里有了底：六座城市 64 格，二十座也才一百万格——背包里的小笔记本完全装得下。它提醒自己：一旦城市超过二十座，就必须换蒙特卡洛、遗传算法这类近似手段了，这是状压 DP 的物理边界。

代码实现范式

阿青把账本法整理成了一套标准「青蛙操作手册」：第一，mask 从 0 到 2ⁿ-1 升序遍历，保证算到某个 mask 时，比它少一枚章的所有子状态都已就绪；第二，三重循环——外层枚举 mask，中层枚举尾城市 u，内层枚举新城市 v；第三，只有 u 在 mask 中、v 不在 mask 中时才转移，用 INF 跳过无效项。这套范式逻辑严谨、不易出错：

阿青把手册揣进怀里，又额外添了一条锦囊：想还原具体路线而不是只求距离，就在每次更新 dp 时顺手把「上一站 j」记入 pre[mask][i] 数组，最后从满章状态沿着 pre 一路回溯，就能像倒放录像一样把完整旅程捋出来。它拍了拍集章册，踏上了归途——这一次，它带的不是 720 种犹豫，而是一本写得明明白白的账。

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-def solve_tsp(dist):    """TSP 状压 DP 求解。    dist[i][j] 表示城市 i 到 j 的距离，城市编号从 0 开始。    返回最短环游距离。    """    n = len(dist)    INF = float('inf')    size = 1 << n    dp = [[INF] * n for _ in range(size)]    dp[1][0] = 0  # 起点在城市 0，集合只有 {0}    pre = [[-1] * n for _ in range(size)]     for mask in range(size):        for u in range(n):            if not (mask >> u) & 1:      # u 不在集合中                continue            if dp[mask][u] == INF:        # 状态不可达                continue            for v in range(n):                if (mask >> v) & 1:       # v 已访问过                    continue                nmask = mask | (1 << v)   # 盖上新章                nd = dp[mask][u] + dist[u][v]                if nd < dp[nmask][v]:                    dp[nmask][v] = nd                    pre[nmask][v] = u      # 记录路径前驱     full = size - 1    ans = min(dp[full][i] + dist[i][0] for i in range(n))    # 路径还原（可回溯出完整顺序）    last = min(range(n), key=lambda i: dp[full][i] + dist[i][0])    path = []    p = last    m = full    while p != -1:        path.append(p)        p = pre[m][p]        m = m ^ (1 << p)  # 本题中 pre 记录上一站，需提前保存再撕章    # 上面路径还原为简化演示，实际 pre 回溯需另存上一 mask    _ = path    return ans if __name__ == '__main__':    dist = [        [0, 10, 15, 20],        [10, 0, 35, 25],        [15, 35, 0, 30],        [20, 25, 30, 0]    ]    print('最短环游距离:', solve_tsp(dist))  # 期望输出 80

1. size = 1 << n状态总数，n 座城市共有 2ⁿ 种「已访问集合」。
2. dp = [[INF] * n for _ in range(size)]账本初始化：所有状态距离先记为无穷大。
3. dp[1][0] = 0起点记账：只有城市 0 被访问，站在城市 0，距离为 0。
4. if not (mask >> u) & 1:查章：u 不在当前集合中，直接跳过非法状态。
5. nmask = mask | (1 << v)盖章：把新城市 v 加入集合，得到下一个状态。
6. if nd < dp[nmask][v]:更新账本：只保留更短路线，体现「取最小值」。
7. ans = min(dp[full][i] + dist[i][0] for i in range(n))收尾：最后一站飞回起点，取最小环游距离。

常见误区

面试题