状态压缩DP

· · 个人记录

二进制状态压缩

  二进制状态压缩，是指将一个长度为 m 的 bool 数组用一个 m 位二进制整数表示并存储的方法。利用下列位运算操作可以实现原 bool 数组中对应下标元素的存取。
  这种方法运算简便，并且节省了程序运行的时间和空间。当 m 不太大时，可以直接使用一个整数类型存储。当 m 较大时，可以使用若干个整数类型(int数组),也可以直接利用\ C++STL\ 为我们提供的 bitset 实现。

【例题】最短Hamilton路径 CH0103

  给定一张 n(n<20) 个点的带权无向图，点从 0{\sim}n-1 标号，求起点 0 到终点 n-1 的最短 Hamilton 路径。
  Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

【分析】

  很容易想到本题的一种朴素做法，就是枚举 n 个点的全排列，计算路径长度取最小值，时间复杂度为 O(n* n!))，使用下面的二进制状态压缩 DP 可以优化到 O(n^2* 2^n)。
  在任意时刻如何表示哪些点已经被经过，哪些点没有被经过？可以使用一个 n 位二进制数，若其第 i 位 (0≤i<n) 为 1 ，则表示第 i 个点已经被经过，反之未被经过。在任意时刻还需要知道当前所处的位置，因此我们可以使用 F[i][j](0≤i<2^n,0≤j<n) 表示“点被经过的状态“对应的二进制数为 i ，且目前处于点 j 时的最短路径。
  在起点时，有F[1][0]=0，即只经过点 0 (i 只有第 0 位为 1 )，目前处于起点 0，最短路长度为 0。方便起见，我们将 F 数组其他的值设为无穷大。 最终目标是F[(1<<n)-1][n-1]，即经过所有点( i 的所有位都是 1 )，处于终点 n-1 的最短路。
  在任意时刻，有公式 F[i][j]=min\{ F[i\ xor\ (1<<j)][k]+mp[k][j]\}，其中 0≤k<n 并且 ((i>>j))\ \&\ 1)=1，即当前时刻“被经过的点的状态”对应的二进制数为 i，处于点 i。因为 j 只能被恰好经过一次,所以一定是刚刚经过的，故在上一时刻“被经过的点的状态”对应的二进制数的第 j 位应该赋值为 0，也就是 i\ xor\ (1<<j)。另外，上一时刻所处的位置可能是 i\ xor\ (1<<j)) 中任意一个是 1 的数位 k，从 k 走到 j 需经过 mp[k][j] 的路程，可以考虑所有这样的 k 取最小值。这就是该公式的由来。
  最需要注意的地方是:大小关系比较的符号优先于 “位与” “异或” “位或” 运算。 在程序实现时，如果不确定优先级，建议加括号保证运算顺序的正确性。

【代码】

#include<bits/stdc++.h>
using namespace std;
int f[1<<20][20],mp[20][20],n;
int hamilton(int n,int mp[20][20]) 
{
    memset(f,0x3f,sizeof(f));
    f[1][0]=0;
    for(int i=1;i<(1<<n);i++)
        for(int j=0;j<n;j++) 
            if(i>>j&1)
                for(int k=0;k<n;k++) 
                    if((i^1<<j)>>k&1)
                        f[i][j]= min(f[i][j],f[i^1<<j][k]+mp[k][j]);
    return f[(1<<n)-1][n-1];
}
int main() 
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>mp[i][j];
    cout<<hamilton(n,mp)<<endl;
    return 0; 
}

状态压缩DP

  动态规划的过程是随着“阶段”的增长，在每个状态维度上不断扩展的。在任意时刻，已经求出最优解的状态与尚未求出最优解的状态在各维度上的分界点组成了DP扩展的“轮廓”。对于某些问题，我们需要在动态规划的“状态”中记录一个集合，保存这个“轮廓”的详细信息，以便进行状态转移。若集合大小不超过 N，集合中每个元素都是小于 K 的自然数，则我们可以把这个集合看作一个 N 位 K 进制数，以一个 [0,K^{N-1}] 之间的十进制整数的形式作为DP状态的一维。这种把集合转化为整数记录在DO状态中的一类算法，就被称为状态压缩的动态规划算法。
  上题已经展示了简单的状态压缩DP思想。在求解最短 Hamilton 路径时，整个状态空间可看作 N 维，每维代表一个节点，只有 0（尚未访问）和 1（已访问）两个值。可以想象DP的“轮廓”以“访问过的节点数目”为阶段，从 (0,0,···,0) 扩展到 (1,1,···,1)。为了记录当前状态在每个维度上的坐标是 0 还是 1，我们使用了一个 N 位二进制数，即 [0,2^N-1] 之间的十进制整数存储节点的访问情况。另外，为了知道最后经过的节点是哪一个，我们把该节点编号作为附加信息，也保存在DP的状态中。因此，该状态压缩DP的数组就由大小分别为 2^N 和 N 的两个维度构成。

【例题】 Mondriaan's Dream POJ-2411

  求把 N* M(1≤N,M≤11) 的棋盘分割成若干个 1* 2 的长方形，有多少种方案。例如当 N=2,M=4 时，共有 5 种方案。当 N=2,M=3 时，有 3 种方案。如下图所示：

【分析】


  对于任意一种方案，考虑以某一行为界，把整个棋盘横着分成两半，如上图所示。在上半部分最后一行中：
  1.每个灰色背景的部分都是一个竖着的 1* 2 长方形的 一半，决定了下一行必须继续补全该长方形。
  2.其余部分对下半部分的分割方法没有影响。下一行既可以在连续两个位置安排一个横着的 1* 2 长方形,也可以让某个位置作为一个竖着的 1* 2 长方形的一半。
  综上所述，我们可以把“行号”作为DP的“阶段”，把“上半部分”不断向下扩展，直至确定整个棋盘的分割方法。为了描述上半部分最后一行的详细形态，我们可以使用一个 M 位二进制数，其中第 k(0≤k<M) 位为 1 表示第 k 列是一个竖着的 1* 2 长方形的上面一半，第 k 位为 0 表示其他情况。
  设 F[i][j] 表示第 i 行的形态为 j 时，前 i 行分割方案的总数。j 是用十进制整数记录的 M 位二进制数。
  第 i-1 行的形态 k 能转移到第 i 行的形态 j，当且仅当:
  1.j 和 k执行按位与运算的结果是 0。
  这保证了每个数字 1 的下方必须是数字 0，代表继续补全竖着的 1* 2 长方形。
  2.j 和 k 执行按位或运算的结果的二进制表示中，每一段连续的 0 都必须有偶数个。
  这些 0 代表若干个横着的 1* 2 长方形，奇数个 0 无法分割成这种状态。
  可以在DP前预处理出 [0,2^M-1] 内所有满足“二进制下每一段连续的 0 都有偶数个”的整数，记录在集合 S 中。

F[i][j]=\sum\limits_{j\&k=0\text{且}j|k\in S}F[i-1][k]

  边界条件：F[0][0]=1，其余均为 0。
  目标：F[N][0]。
  时间复杂度：O(2^M2^MN)=O(4^MN)。

【代码】

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long f[12][1<<11];
bool in_s[1<<11];
int main()
{
    while(cin>>n>>m&&n)
    {
        for(int i=0;i<1<<m;i++)
        {
            bool cnt=0,has_odd=0;
            for(int j=0;j<m;j++)
            {
                if(i>>j&1)
                    has_odd=has_odd|cnt,cnt=0;
                else
                    cnt=cnt^1;
                in_s[i]=has_odd|cnt?0:1;
            }
            f[0][0]=1;
            for(int i=1;i<=n;i++)
            {
                for(int j=0;j<1<<m;j++)
                {
                    f[i][j]=0;
                    for(int k=0;k<1<<m;k++)
                        if((j&k)==0&&in_s[j|k])
                            f[i][j]=f[i][j]+f[i-1][k];
                }
            }
        }
        cout<<f[n][0]<<endl;
    }
    return 0; 
}