滚动状压 DP：用 C++ 实现旅行商问题 (TSP) 的空间优化

滚动状压 DP：空间优化利器

滚动状压 DP 是一种将滚动优化和状压 DP 相结合的技巧，通过减少状态空间的维度，进一步减少空间复杂度。它在解决许多组合优化问题时，能有效地提高算法效率。

核心概念

状态定义: 根据问题的具体要求，确定需要维护的状态。每个状态可以用一个整数来表示，其中每一位表示某一种状态的取值。
状态转移方程: 根据问题的要求，将状态之间的转移关系表示为状态转移方程。在滚动状压 DP 中，我们通常使用二进制位运算来表示状态之间的转移。
状态压缩: 通过将状态的维度压缩成一个整数，减少状态所占用的空间。我们可以使用一个一维数组来表示状态，其中数组的每个元素表示某个状态的取值。

旅行商问题 (TSP) 例子

问题描述: 给定一个有 n 个城市的旅行商问题，旅行商要从起点城市出发，途经所有城市恰好一次，最后回到起点城市。每个城市之间的距离已知，求解旅行商的最短路径。

代码实现:

#include <iostream>
#include <vector>
#include <cstring>
#include <climits>

using namespace std;

const int MAXN = 15;  // 最大城市数

int tsp(int n, vector<vector<int>>& dist) {
    int dp[1 << MAXN][MAXN];  // 滚动状压 DP 数组
    memset(dp, INT_MAX, sizeof(dp));

    dp[1][0] = 0;  // 起点城市

    for (int mask = 1; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                for (int j = 0; j < n; j++) {
                    if (j != i && (mask & (1 << j)) != 0) {
                        dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i]);
                    }
                }
            }
        }
    }

    int ans = INT_MAX;
    for (int i = 1; i < n; i++) {
        ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]);
    }

    return ans;
}

int main() {
    int n;  // 城市数
    cin >> n;

    vector<vector<int>> dist(n, vector<int>(n, 0));  // 城市之间的距离
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }

    int shortestPath = tsp(n, dist);
    cout << "Shortest Path: " << shortestPath << endl;

    return 0;
}

代码解释:

dp[mask][i] 表示已经访问过的城市集合为 mask，当前位于城市 i 时的最短路径。
使用二进制位运算来判断某个城市是否已经访问过。mask & (1 << i) 如果不为 0，则表示城市 i 已经被访问过。
状态转移方程 dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i]) 表示从城市 j 转移到城市 i 的最短路径。
遍历所有的终点城市 i，找到 dp[(1 << n) - 1][i] + dist[i][0] 的最小值，即为旅行商的最短路径。

总结

滚动状压 DP 能够有效地减少空间复杂度，特别是在解决状态空间较大的组合优化问题时，能显著提高算法效率。通过理解状态定义、状态转移方程和状态压缩的技巧，我们可以运用滚动状压 DP 解决更多复杂的问题。