状态压缩动态规划 (Bitmask DP) 解决旅行商问题 (TSP)

View Original Problem
Table of Contents

状态压缩动态规划（Bitmask DP）是解决旅行商问题（Traveling Salesperson Problem, TSP）等NP-Hard问题的经典方法。它通过二进制位操作巧妙地表示集合状态，将指数级的搜索空间压缩至可计算的范围。

1. 旅行商问题（Traveling Salesperson Problem, TSP）

定义

给定一组城市（节点）以及每对城市之间的距离（权重），旅行商需要找到一条最短的路径，使得他能够：

  1. 访问每个城市恰好一次。
  2. 最后回到出发城市。

组合爆炸与NP难

从本质上讲，TSP 是一个关于排列（Permutation）的问题。 如果只有3个城市，路径很少。如果有 个城市，可能的路径总数是 （假设是对称TSP，即A到B的距离等于B到A，且方向不重要）。

  • 组合爆炸：随着城市数量 的线性增加，可能的路径数量呈阶乘级（Factorial）增长。
    • 10个城市：约 18万条路径。
    • 20个城市：约 条路径。
    • 50个城市：路径数量超过宇宙中的原子总数。

复杂性分类

TSP 属于 NP-hard 问题。

  • 这意味着目前人类尚未发现任何多项式时间算法（Polynomial Time Algorithm）能保证在所有情况下快速找到最优解。
  • 如果有人能找到一个高效解决TSP的通用公式，那么 这一千禧年数学难题将被解决，现有的密码学体系也将崩溃。

度量空间与非度量空间

  • 欧几里得TSP (Metric TSP)：满足三角不等式（A到C的距离 A到B + B到C）。这是我们直觉中的地图。
  • 非欧几里得TSP：不满足三角不等式。例如，廉价航空机票。从A飞到C可能比从A飞B再转机到C要贵得多。这种情况下，许多基于几何直觉的优化算法（如2-Opt）将失效。

2. 核心困境

核心困境：状态的维度爆炸

旅行商问题要求寻找一条路径：从起点出发，经过所有城市恰好一次，最后回到起点，且总路径最短。

如果我们尝试使用简单的递归或贪心算法：

  • 贪心失效：每次只去最近的邻居往往会导致后期被迫走极远的路，从而失去全局最优解。
  • 暴力枚举失效：全排列的时间复杂度是 。当 时，，这是现有计算能力无法处理的。

动态规划的切入点：无后效性

动态规划（DP）的核心在于：只要当前状态确定，如何到达这个状态并不重要。

在 TSP 中，假设我们要决定下一步去哪里。我们需要知道两件事：

  1. 当前在哪里（Current Location）。
  2. 哪些城市已经访问过了（Visited Set）。

只要知道这两点，我们就不需要关心具体的访问顺序（是先去A再去B，还是先去B再去A，只要结果都是“目前在C，且A、B已访问”即可）。这就构成了我们的 DP 状态。

为什么需要“状态压缩”？

我们需要记录“哪些城市已访问”。如果使用哈希表（HashSet）或布尔数组来存储这个集合，作为 DP 的索引会非常低效且难以编码。

状态压缩的核心思想是：利用整数的二进制位（Bit）来一一对应集合中的元素。一个整数就是一个集合。

3. 算法过程

第一步：定义状态

我们需要定义 ：

  • (State)：一个整数，其二进制表示记录了所有已访问的城市集合。
  • (Last City)：当前所在的城市编号（必须包含在 mask 中）。
  • 的值：从起点出发，访问了 中标记的所有城市，且最后停留在城市 的最短路径长度。

第二步：状态转移方程

我们需要思考：状态 是由谁转移过来的？ 在到达城市 之前，我们在某个城市 。这意味着：

  1. 之前的状态掩码是 mask ^ (1 << i)（即从 mask 中去掉城市 ）。
  2. 之前的最后停留城市是 。

因此，转移方程为：

其中：

  • 是 中除了 以外的任意一个已访问城市。
  • 是城市 到 的距离。

第三步：初始化

通常假设从城市 0 出发。

  • ：表示仅访问了城市 0，且目前就在城市 0，距离为 0。
  • 其余所有 值初始化为无穷大 ()。
  • (注：掩码 1 对应二进制 ...001，即第0位为1)

第四步：计算顺序

我们需要按“已访问城市的数量”从小到大进行遍历。

  1. 枚举 mask 从 1 到 。
  2. 枚举当前所在城市 （必须在 mask 中）。
  3. 枚举上一个城市 （必须在 mask 中且 ）。

第五步：最终答案

TSP 要求回到起点。假设起点是 0。 遍历所有可能的终点 （此时 mask 应当是全 1，即 ），加上从 回到 0 的距离：

3. 位运算技巧

为了实现上述逻辑，必须熟练掌握以下位运算技巧：

  1. 判断第 个城市是否在集合中： if ((mask >> i) & 1)
  2. 从集合中移除第 个城市： prev_mask = mask ^ (1 << i)
  3. 构造全集掩码： full_mask = (1 << N) - 1

4. 复杂度分析

时间复杂度

  • 状态数量：。
  • 每个状态的转移代价：需要枚举 ，代价为 。
  • 总复杂度：。

空间复杂度

  • 我们需要存储 表格。
  • 总空间：。

为什么这是“可行”的？

相比于暴力枚举的 ，这是一个巨大的进步。

  • 当 时：
    • (不可计算)。
    • (现代计算机可在几秒内完成)。

局限性与扩展

  1. N 的限制：由于指数级增长，Bitmask DP 仅适用于 的情况。如果 增大到 30 或更多，需要使用近似算法（如模拟退火、遗传算法）或启发式搜索（如 Lin-Kernighan）。
  2. 变种问题：
    • 非闭合路径 TSP：不要求回到起点。此时答案就是 。
    • 必须要经过特定集合：Mask 初始化或终止条件会有所不同。
  3. 空间优化：虽然状态需要 ，但由于转移只依赖于“少一个元素”的状态，这不像背包问题那样容易进行滚动数组优化，因为依赖关系是基于集合包含关系的拓扑序，而不是简单的线性层级。

5. 其他求解算法：启发式与元启发式

  • 最近邻居法 (Nearest Neighbor)：

    • 从起点开始，每次移动到最近的未访问城市。
    • 特点：极快，但解的质量通常较差（平均比最优解差25%）。

  • 2-Opt 优化 (局部搜索)：

    • 步骤：先随机生成一条路径。然后，切断路径中的两条边，交换连接方式，如果新路径更短，就保留变化。
    • 直观理解：消除路径中的“交叉”。在一个欧几里得平面上，最优路径绝不会自相交叉（三角形两边之和大于第三边）。2-Opt 就是不断解开交叉结的过程。

  • 模拟退火 (Simulated Annealing) & 遗传算法 (Genetic Algorithms)：

    • 这些算法引入了“随机性”来跳出局部最优陷阱。
    • 模拟退火：允许偶尔接受一个“更差”的解（像金属退火时的热运动），以防止卡在局部山谷中，从而有机会找到全局最低点。

6. 题目解析

Warehouse Robot Delivery

该问题是一个经典的旅行商问题 (TSP) 变体，具体表现为在一个无障碍的二维网格图中，寻找一条从起点 出发，经过指定的中间节点集合 ，最终到达终点 的最短路径。

我们将问题转化为一个包含 个节点（ 以及 个取货点）的图论问题。

坐标转换

输入给出的是基于 到 的线性索引。由于需要计算曼哈顿距离，首先必须将所有关键点（）转换为二维坐标 。 对于编号 ：

  • (此处使用 0-indexed 以方便计算)

状态定义

使用一个整数 mask 的二进制位来表示集合中哪些包裹已经被拿取。

  • 令 表示：已经访问的包裹集合由 的二进制位为 1 的位置决定，且当前停留在第 个取货点（）时的最小总移动步数。
    • : 一个 到 的整数。若 的第 位为 ，表示 已被访问。
    • : 当前所在的取货点索引，。

状态转移

  • 含义：从当前状态 出发，前往一个未访问的点 （即 的第 位为 0）。
  • 代价更新：旧的总代价 + 从 到 的曼哈顿距离。

代码实现

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

void solve() {
    unsigned int n, m;
    cin >> n >> m;
    ll s, t;
    cin >> s >> t;

    auto to2d = [&](ll x) -> pll {
        x--;
        return {x / (ll)n, x % (ll)n};
    };

    auto dist = [&](ll x, ll y) -> ll {
        pll px = to2d(x);
        pll py = to2d(y);
        return abs(px.first - py.first) + abs(px.second - py.second);
    };

    if (m == 0) {
        ll ans = dist(s, t);
        cout << ans << endl;
        return;
    }

    vector<ll> p(m);
    for (int i = 0; i < m; i++) {
        cin >> p[i];
    }

    const ll INF = 1e10 + 5;
    vector<vector<ll>> dp((1 << m), vector<ll>(m + 1, INF));

    for (int i = 0; i < m; i++) {
        ll d = dist(s, p[i]);
        dp[(1 << i)][i] = d;
    }

    for (unsigned int mask = 1; mask <= (1 << m) - 2; mask++) {
        for (int u = 0; u < m; u++) {
            if (((mask >> u) & 1) == 0)
                continue;
            if (dp[mask][u] == INF)
                continue;
            for (int v = 0; v < m; v++) {
                if (((mask >> v) & 1) == 1)
                    continue;
                unsigned int newMask = mask | (1 << v);
                ll cost = dp[mask][u] + dist(p[u], p[v]);
                dp[newMask][v] = min(dp[newMask][v], cost);
            }
        }
    }

    ll ans = INF;
    for (int i = 0; i < m; i++) {
        ans = min(ans, dp[(1 << m) - 1][i] + dist(p[i], t));
    }

    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

7. 总结

状态压缩 DP 解决 TSP 的本质，是将排列问题（顺序重要）转化为子集问题（组合重要）。通过位掩码将集合映射为整数，使得我们能够在 时间内索引集合状态，从而利用动态规划的记忆化特性消除重复计算。