状态压缩动态规划

引入
首先来说说“状态压缩动态规划”这个名称，顾名思义，状态压缩动态规划这个算法包括两个特点，第一是“状态压缩”，第二是“动态规划”。

状态压缩：

从状态压缩的特点来看，这个算法适用的题目符合以下的条件：
1.解法需要保存一定的状态数据（表示一种状态的一个数据值），每个状态数据通常情况下是可以通过2进制来表示的。这就要求状态数据的每个单元只有两种状态，比如说棋盘上的格子，放棋子或者不放，或者是硬币的正反两面。这样用0或者1来表示状态数据的每个单元，而整个状态数据就是一个一串0和1组成的二进制数。
2.解法需要将状态数据实现为一个基本数据类型，比如int，long等等，即所谓的状态压缩。状态压缩的目的一方面是缩小了数据存储的空间，另一方面是在状态对比和状态整体处理时能够提高效率。这样就要求状态数据中的单元个数不能太大，比如用int来表示一个状态的时候，状态的单元个数不能超过32（32位的机器）。

这里举一个可以状态压缩的例子，比如poj上的第1753题Flip Game（见poj1753解题报告），虽然这道题目不是用动态规划做，但是可以用状态压缩，4×4的格子，每个格子的状态为黑或者白，这样就可以用一个16位的二进制数来表示，在实现的时候可以用一个int类型来表示这个二进制数。在状态和状态对比和转换的时候可以用位操作来完成。

位操作实现技巧：
如果要获得第i位的数据，判断((data&(0X<<i))==0),若真，为0，假，为1；
如果要设置第i位为1，data=(data|(0X1<<i));
如果要设置第i位为0，data=(data&(~(0X1<<i)));
如果要将第i位取反，data=(data^(0X1<<i);
如果要取出一个数的最后一个1(lowbit)：(data&(-data))

动态规划：
如果说状态压缩是数据结构的话，那么动态规划应该是算法了。题目通过动态规划来解通常有两个动机，第一是利用递归的重叠子问题，进行记忆话求解，即递归法的优化。第二是把问题看作多阶段决策的过程来求解问题。在状态压缩动态规划中我们讨论的是第二种动机。

多阶段决策过程求解问题的动态规划最重要的是划分阶段和找到状态转移方程。对于划分阶段，是根据不同阶段之间的独立性来划分，通常会用状态数组的第一个下标来记录这个阶段的标记（比如01背包问题中的状态数组第一个下标为物品的个数，棋盘放棋子问题中的状态数组的第一个下标为棋盘的行数等等）。另一个重要的便是状态转移方程，状态转移方程是递推时得到一个状态数据的重要根据。通常情况下状态数组的除了第一个下标以外都是表示状态数据的，而状态数组的值是和所求结果紧密结合的。在后面的几个例题中会重点说明状态转移方程。

当状态压缩和动态规划结合的时候便形成了一类问题的一种算法，即状态压缩动态规划的算法。这种算法最常见在棋盘问题上或者网格问题上，因为这一类问题的状态数据的单元较少，可以通过状态压缩来对当前棋盘或者网格的状态进行处理。

例题解析
例：在n*n(n≤20)的方格棋盘上放置n 个车，某些格子不能放，求使它们不能互相攻击的方案总数。
分析：
首先看到这道题目，我们可能会想到8皇后问题，用深度优先搜索。但是这里放这道题目是用来说明此题可以状态压缩动态规划，而且状态压缩动态规划相比于深度优先搜索可以应对更多的变化情况和拥有更高的效率。

用状态压缩动态规划算法
1.划分阶段，本题比较简单，以行来划分阶段，即一行一行的放车。
2.找状态转移方程，因为前i行的状态是根据前i-1行的状态来确定的，所以，在状态数组中要记录多行状态。故设计状态数组为f[i][x]，i表示这是前i行的状态，x在这里是就是一个压缩的状态，记录一个二进制数从而来表示前i行的状态，f的值记录形成前i行的x状态有多少种方案。状态转移方程是f[i][a]=SUM{f[i-1][b]},下面讨论a状态与b状态的关系。先举个例子，如果a状态为01011，表明前i行中的第0，1，3列都放置了一个车（从右往左看）。于是b的状态就可能是01010，01001，00011三种状态，于是f[3][01011]=f[2][01010]+f[2][01001]+f[2][00011]。再看普遍的情况，a-b的值的二进制表示中只有一个1。而且要保证a状态，b状态不能和非可用的格子冲突。综上，状态转移方程为：
f[i][a]=SUM{f[i-1][b]} (a-b的值的二进制表示中只有一个1; a,b不与题目中的约束条件冲突)
这样通过递推可以得到f[n][1…1]的方案数即为最后的方案总数。


算法总结：
1.断定这道题目可以用数据压缩动态规划来做。重点是看它的特点，是否符合状态压缩动态规划的条件。
2.划分阶段。像棋盘和网格问题大多数是一行一行的进行操作，故以行来划分阶段，当然也有其他的阶段划分方法，具体问题具体分析。
3.找状态转移方程
3.1设计状态数组。通常数组的第一个参数为阶段的标志，其他几个参数为记录状态用（如果第i行的状态可以通过第i-1行的状态来确定，则需要一个参数，即第i行的状态；如果像炮兵阵地那题一样，第i行的状态需要根据第i-1行和第i-2行来确定，则需要两个参数，分别为第i行的状态和第i-1行的状态，具体见附录）。数组的值与结果挂钩，通常有以下几种情况：a.题目要求一共有多少的方案，这时数组的值为当前状态的方案数。（比如poj2411以及例题）b.题目要求最佳方案，这是数组的值为最佳方案的值。（比如poj1185炮兵阵地）。
3.2列出状态转移方程，对应与上面的a，b两种情况，a情况时，状态转移方程为f[i][a]=sum{f[i-1][b]}; b情况时，状态转移方程为f[i][a]=max{f[i][b]}+sth.
3.3找出状态转移方程中a，b之间的关系。即为状态转移方程添加约束条件。
4.在很多情况下需要对每一个阶段的可能值进行dfs来找出所有的可能值存储起来，以便在对每一个阶段处理的时候能够很快的运用以提高效率。

评论

1 楼 gxy5088805 2013-11-04  

擦。。我居然看到了你的帖！！！！