状态压缩.ppt

状态压缩状态压缩l信息学发展势头迅猛，信息学奥赛的题目来源遍及各行各业，经常有一些在实际应用中很有价值的问题被引入信息学并得到有效解决。l然而有一些问题却被认为很可能不存在有效的(多项式级的)算法，这里以对几个例题的剖析，简述状态压缩思想及其应用。状态压缩状态压缩预备知识预备知识名称名称C/C+样样式式Pascal样样式式简记简记法法则则按位与按位与&and全一全一则则一，否一，否则为则为零零按位或按位或|or有一有一则则一，否一，否则为则为零零按位取反按位取反not是零是零则则一，是一一，是一则则零零按位异或按位异或xor不同不同则则一，相同一，相同则则零零左移位左移位shlashrak等价于等价于a/2k作为对下文的准备，这里先为使用Pascal的OIers简要介绍一下C/C+样式的位运算(bitwise operation)。其优先级：notandxoror状态压缩状态压缩预备知识预备知识位运算的特殊应用位运算的特殊应用and：用以取出一个数的某些二进制位取出一个数二进制中的最后一个1(lowbit)：x&-xor：将一个数的某些位设为1not：间接构造一些数：0u=4294967295=232-1xor：不使用中间变量交换两个数：a=ab;b=ba;a=ab;将一个数的某些位取反状态压缩状态压缩引例引例l在n*n(n20)的方格棋盘上放置n个车(可以攻击所在行、列)，求使它们不能互相攻击的方案总数。l10秒时间思考状态压缩状态压缩引例引例l这个题目之所以是作为引例而不是例题，是因为它实在是个非常简单的组合学问题l我们一行一行放置，则第一行有n种选择，第二行n-1，最后一行只有1种选择，根据乘法原理，答案就是n!l这里既然以它作为状态压缩的引例，当然不会是为了介绍组合数学。我们下面来看另外一种解法：状态压缩递推状态压缩递推(States Compressing Recursion,SCR)状态压缩状态压缩引例解法引例解法l我们仍然一行一行放置。l取棋子的放置情况作为状态，某一列如果已经放置棋子则为1，否则为0。这样，一个状态就可以用一个最多20位的二进制数表示。l例如n=5,第1、3、4列已经放置，则这个状态可以表示为01101(从右到左)。设fs为达到状态s的方案数，则可以尝试建立f的递推关系。状态压缩状态压缩引例解法引例解法l考虑n=5,s=01101l因为我们是一行一行放置的，所以当达到s时已经放到了第三行。又因为一行能且仅能放置一个车，所以我们知道状态s一定来自：状态压缩状态压缩引例解法引例解法l前两行在第3、4列放置了棋子(不考虑顺序，下同)，第三行在第1列放置；l前两行在第1、4列放置了棋子，第三行在第3列放置；l前两行在第1、3列放置了棋子，第三行在第4列放置。状态压缩状态压缩引例解法引例解法l这三种情况互不相交，且只可能有这三种情况，根据加法原理，fs应该等于这三种情况的和。写成递推式就是：状态压缩状态压缩引例解法引例解法l根据上面的讨论思路推广之，得到引例的解决办法：其中s的右起第i+1位为1(其实就是在枚举其实就是在枚举s的二进制表示中的的二进制表示中的1)状态压缩状态压缩引例的实现引例的实现Prog P0read(n);int64 f1.220=0;f0=1;for(int i=1;i0;t-=t&-t)fi+=fi(t&-t);write(f2n-1);状态压缩状态压缩对引例的思考对引例的思考l反思这个算法，其正确性毋庸置疑(可以和n!对比验证)l但是算法的时间复杂度为O(n2n)，空间复杂度O(2n)，是个指数级的算法，比循环计算n!差了好多，它有什么优势？l（还有一个很的用处，即对新手说：“来看看我这个计算n!的程序，连这都看不懂就别OI了”）可扩展性！可扩展性！状态压缩状态压缩例例1l在n*n(n20)的方格棋盘上放置n个车，某些格子不能放，求使它们不能互相攻击的方案总数。l30s思考时间状态压缩状态压缩例例1分析分析l对于这个题目，如果组合数学学得不够扎实，应该很难一眼看出解法。l本题确实存在数学方法(容斥原理)，但因为和引例同样的理由，这里不再赘述。l引例的算法是在枚举当前行(即s中1的个数，设为r)的放置位置(即枚举每个1)l而对于例1，第r行可能存在无法放置的格子，怎么解决？枚举枚举1的时候判断一下嘛！的时候判断一下嘛！状态压缩状态压缩例例1解法解法l事实上，我们并不需要对引例的算法进行太大的改变，只要在枚举s中的1的时候判断一下是否是不允许放置的格子即可l然而对于n=20，O(n2n)的复杂度已经不允许我们再进行多余的判断。所以实现这个算法时应该应用一些技巧。l我们用ar表示第r行不允许放置的情况，如果第r行某一位不允许放置则ar此位为0，否则为1，这可以在读入数据阶段完成状态压缩状态压缩例例1解法解法l然后对于需要处理的状态s，用ts=s&ar来代替s进行枚举，即不枚举s中的1转而枚举ts中的1。l因为ts保证了不允许放置的位为0，这样就可以不用其它的判断来实现算法l代码中只增加了计算a数组和r的部分，而时间复杂度没有变化。状态压缩状态压缩对例对例1的思考的思考l我们直接套用引例的算法就使得看上去更难的例1得到了解决。l虽然这题用容斥原理更快，但容斥原理在这题上只有当棋盘为正方形、放入的棋子个数为n、且棋盘上禁止放置的格子较少时才有较简单的形式和较快的速度。l如果再对例1进行推广，要在m*n的棋盘上放置k个车，那么容斥原理是无能为力的，而SCR算法只要进行很少的改变就可以解决问题。这也体现出了引例中给出的算法的扩展潜力。状态压缩状态压缩例例2l有一个n*m的棋盘(n、m80,n*m80)要在棋盘上放k(k20)个棋子，使得任意两个棋子不相邻。求合法的方案总数l5min思考、讨论、提问时间状态压缩状态压缩例例2分析分析l观察题目给出的规模，n、m80，这个规模要想用SC是困难的，280无论在时间还是空间上都无法承受l然而我们还看到n*m80l稍微思考我们可以发现：9*9=8180，即如果n,m都大于等于9，将不再满足n*m80这一条件。所以，我们有n或m小于等于8，而28是可以承受的！状态压缩状态压缩例例2分析分析l我们假设mn，n是行数m是列数，则每行的状态可以用m位的二进制数表示l但是本题和例1又有不同：例1每行每列都只能放置一个棋子，而本题却只限制每行每列的棋子不相邻l上例中枚举当前行的放置方案的做法依然可行。我们用数组s保存一行中所有的num个放置方案，则s数组可以在预处理过程中用DFS求出，同时用ci保存第i个状态中1的个数以避免重复计算状态压缩状态压缩例例2分析分析l开始设计状态。本题状态的维数需要增加，原因在于并不是每一行只放一个棋子，也不是每一行都要求有棋子，原先的表示方法已经无法完整表达一个状态。l我们用fi,j,k表示第i行的状态为sj且前i行总共放置k个棋子（下面用pn代替原题中的k）的方案数。沿用枚举当前行方案的做法，只要当前行的放置方案和上一行的不冲突。微观地讲，就是要两行的状态s1和s2中没有同为1的位即可，亦即s1&s2=0状态压缩状态压缩例例2解法解法l然而，虽然我们枚举了第i行的放置方案，但却不知道其上一行(第i-1行)的方案l为了解决这个问题，我们不得不连第连第i-1行的状行的状态一起枚举态一起枚举，则可以写出递推式：其中其中s s1 1=0=0，即在当前行不放置棋子；，即在当前行不放置棋子；j j和和p p是需要枚举的两个状态编号。是需要枚举的两个状态编号。状态压缩状态压缩例例2解法解法l本题至此基本解决。当然，实现上仍有少许优化空间，例如第i行只和第i-1行有关，可以用滚动数组节省空间。l这个算法时间复杂度O(n*pn*num2)，空间复杂度(滚动数组)O(pn*num)l运用简单的组合数学知识可以求出本题中的num=144，因而对于本题的数据规模可以很快出解状态压缩状态压缩例例3l给出一个n*m(n100,m10)的棋盘，一些格子不能放置棋子。求最多能在棋盘上放置多少个棋子，使得每一行每一列的任两个棋子间至少有两个空格。题目来源：NOI2001炮兵阵地TOI 1023；POJ 1185l30s 思考时间状态压缩状态压缩例例3分析分析l仍然先用DFS搜出一行可能状态s，依旧用c保存s中1的个数，依照例1的预处理搞定不能放置棋子的格子（应该有这种意识）l问题是，这个题目的状态怎么选？继续像例2那样似乎不行，原因在于棋子的攻击范围加大了状态压缩状态压缩例例3分析分析l但是我们照葫芦画瓢：例2的攻击范围只有一格，所以我们的状态中只需要有当前行的状态，再枚举上一行的状态即可进行递推；而本题攻击范围是两格，因此增加一维来表示上一行的状态。状态压缩状态压缩例例3解法解法l用fi,j,k表示第i行状态为sj、第i-1行状态为sk时前i行至多能放置的棋子数。则状态转移方程很容易写出：显然，算法时间复杂度为O(n*num3)，空间复杂度(滚动数组)O(num2)因为棋子攻击范围为两格，可以直观地想像到本题的num不会很大。的确，可以算出本题num60。状态压缩状态压缩例例3题外话题外话l此算法还有优化空间l我们分别枚举了三行的状态，还需要对这三个状态进行是否冲突的判断，这势必会重复枚举到一些冲突的状态组合l在DFS出s后，我们可以算出哪些状态对可以分别作为两行的状态，这样在DP时就不需要进行盲目的枚举，理论上效率会更高。但因为num本身很小，所以这样修改没有显著地减少运行时间状态压缩状态压缩例例3题外话题外话l值得一提的是，本题笔者的算法虽然在理论上并不是最优（有种应用三进制的方法），但由于位运算的使用，截至07年8月17日，笔者的程序在PKU OJ上长度最短，速度第二快。l但是很不幸，公元2007年8月18日，天津大学06级的某同学去掉本算法的一些关键判断，达到了更短的长度，但其速度慢了3倍状态压缩状态压缩例例3题外话题外话l这个题目是国内比赛中较早出现的状态压缩题。它告诉我们状态压缩不仅可以像前几个例题那样求方案数，而且可以求最优方案，即状态压缩思想既可以应用到递推上(SCR)，又可以应用到DP上(SCDP)，更说明其有广泛的应用空间。状态压缩状态压缩新的模型新的模型l看了这么多棋盘模型应用状态压缩的实例，可能会让人产生错觉，以为状态压缩只在棋盘上放棋子的题目中有用。我们暂时转移视线，来看看状态压缩在其他地方的应用覆盖模型覆盖模型。状态压缩状态压缩例例4l给出n*m(1n、m11)的方格棋盘，用1*2的长方形骨牌不重叠地覆盖这个棋盘，求覆盖满的方案数。经典问题TOJ 1343;POJ 2411Have a break!状态压缩状态压缩例例4背景背景l这也是个经典的组合数学问题：多米诺骨牌完美覆盖问题(或所谓二聚物问题)。有很多关于这个问题的结论，甚至还有个专门的公式:谁看得懂、记得住？状态压缩状态压缩例例4分析分析l显然，如果n、m都是奇数则无解(由棋盘面积的奇偶性知)，否则必然有至少一个解(很容易构造出)l因此假设n、m至少有一个偶数，且mnl我们依然依然像前面的例题一样把每行的放置方案DFS出来，逐行计算状态压缩状态压缩例例4解法解法l用fi,s表示把前i-1行覆盖满、第i行覆盖状态为s的覆盖方案数l因为在第i行上放置的骨牌最多也只能影响到第i-1行，则容易得递推式：状态压缩状态压缩例例4细节细节l首先讨论DFS的一些细节。l对于当前行每一个位置，我们有3种放置方法：竖直覆盖，占据当前格和上一行同一列的格；水平覆盖，占据当前格和该行下一格；不放置骨牌，直接空格。l如何根据这些枚举出每个(s1,s2)呢？下面介绍两种方法。状态压缩状态压缩例例4 DFS方法方法1lDFS共5个参数，分别为：p(当前列号)，s1、s2(当前行和上一行的覆盖情况)，b1、b2(上一列的放置对当前列两行的影响，影响为1否则为0)。初始时s1=s2=b1=b2=0。p=p+1，s1=s1*2+1，s2=s2*2（注意：第i行的放置方案用到第i-1行的某格时，s2中该格应为0！），b1=b2=0；p=p+1，s1=s1*2+1，s2=s2*2+1，b1=1，b2=0；p=p+1，s1=s1*2，s2=s2*2+1，b1=b2=0。l当p移出边界且b1=b2=0时记录此方案。状态压缩状态压缩例例4 DFS方法方法2l观察第一种方法，发现b2始终为0，知这种方法有一定的冗余。换个更自然的方法，去掉参数b1、b2。p=p+1，s1=s1*2+1，s2=s2*2；p=p+2，s1=s1*4+3，s2=s2*4+3；p=p+1，s1=s1*2，s2=s2*2+1。l当p移出边界时记录此方案。l这样，我们通过改变p的移动距离成功简化了DFS过程，而且这种方法更加自然。状态压缩状态压缩例例4 细节细节lDFS过程有了，实现方法却还有值得讨论的地方l前面的例题中，我们为什么总是把放置方案DFS预处理保存起来？是因为不合法的状态太多，每次都重新DFS太浪费时间。l然而回到这个题目，特别是当采用第二种时，我们的DFS过程中甚至只有一个判断(递归边界)，说明根本没有多少不合法的方案，也就没有必要把所有方案保存下来，对于每行都重新DFS即可状态压缩状态压缩例例4 细节细节l这个算法时间复杂度为多少呢？因为DFS时以两行为对象，每行2m，共进行n次DFS，所以是O(n*4m)？l这会使人误以为本算法无法通过1n、m11的测试数据，而实际上本算法可以瞬间给出m=10,n=11时的解l为了计算精确的复杂度，必须先算出DFS得到的方案数。状态压缩状态压缩例例4 复杂度分析复杂度分析l考虑当前行的放置情况。l如果每格只有两个选择，则应该有2m种放置方案；如果每格有这3个选择，且中p只移动一格，则应该有3m种放置方案。l然而现在的事实是：每格有这3个选择，但中p移动2格，所以可以知道方案数应该在2m和3m之间状态压缩状态压缩例例4 复杂度分析复杂度分析l考虑第i列，则其必然是：第i-1列采用达到；第i-2列采用达到。l设hi表示前i列的方案数，则得到hi的计算式：状态压缩状态压缩例例4 复杂度分析复杂度分析l注意到式子的第二项是多个绝对值小于1的数的乘积，其对整个hm的影响甚小，故略去，得到方案数hm0.85*2.414m，符合2mhm3m的预想。l因为总共进行了n次DFS，每次复杂度为O(hm)，所以算法总时间复杂度为O(n*hm)=O(n*0.85*2.414m)，对m=10,n=11不超时也就不足为奇了。应用滚动数组，空间复杂度为O(2m)。状态压缩状态压缩例例5l给出n*m(1n、m9)的方格棋盘，用1*2的矩形的骨牌和L形的(2*2的去掉一个角)骨牌不重叠地覆盖，求覆盖满的方案数。SGU.131Hardwood Floor状态压缩状态压缩例例5解法解法l观察题目条件，只不过是比上例多了一种L形的骨牌。又因为本题中两种骨牌的最大长度和上例一样，所以本题的状态表示与转移方程与上例完全一样。l上例中有两种DFS方案，其中第二种实现起来较第一种简单。但在本题中，新增的L形骨牌让第二种DFS难以实现，故回到第一种DFS。覆盖情况 条件 参数 s 变化 参数 b 变化 1 0 0 0 0 无 s1=s1*2+b1 s2=s2*2+1-b2 b1=0 b2=0 2 0 0 1 1 b1=0 s1=s1*2+1 s2=s2*2+1-b2 b1=1 b2=0 3 1 0 1 0 b1=0 b2=0 s1=s1*2+1 s2=s2*2 b1=0 b2=0 4 1 0 1 1 b1=0 b2=0 s1=s1*2+1 s2=s2*2 b1=1 b2=0 5 0 1 1 1 b1=0 s1=s1*2+1 s2=s2*2+1-b2 b1=1 b2=1 6 1 1 0 1 b2=0 s1=s1*2+b1 s2=s2*2 b1=1 b2=1 7 1 1 1 0 b1=0 b2=0 s1=s1*2+1 s2=s2*2 b1=0 b2=1 状态压缩状态压缩例例5 DFS参数参数状态压缩状态压缩例例5解法解法l容易看出，在本题中此种DFS方式实现很简单，只要耐心认真实现各种情况。l因为L形骨牌不太规则，笔者没能找到方案数的一维递推公式，因此无法给出复杂度的解析式。但当m=9时，算法共生成放置方案79248个，则对于n=m=9,算法的复杂度为O(9*79248)，可以瞬间出解l和上例一样，本题也没有必要保存所有放置方案，同时也避免MLE状态压缩状态压缩棋盘棋盘 小结小结l棋盘是SCR、SCDP算法很好的用武之地。l上面的例子的很多扩展都可以用SC来解决。例如新的骨牌形状：2*3、1*k（k较小）等l应用的方式一般为把行或列当成阶段，把每行的放置方案当状态，通过枚举所有放置方案进行转移。状态压缩状态压缩本质本质l上面通过对几个经典的应用状态压缩的题目的详解，从应用的角度描述了状态压缩的一般思路。那么如何理解其本质呢？状态压缩状态压缩本质本质l纵观上文讨论的题目，几乎都是普普通通的一个递推公式或者状态转移方程，只不过其中的一维或多维是“压缩的”，即把一个状态(一个方案、一个集合等)压缩成一个整数。l这很明显是一个Hash的过程，所以SCDP又被称为Hash DP或集合集合DP。l除去这一点区别，我们发现它和普通递推/DP没有什么差别，都是从已有的状态推知新的状态，所做的决策都没有后效那我们为什么要用状态压缩，即状态压缩的动机是什么？状态压缩状态压缩本质本质 动机动机l回想前述的题目，以多米诺骨牌覆盖为例，如果我们不状态压缩，能否正确解答呢？l先来进行一下尝试。尝试fi表示前i行最多能放的骨牌数，我们发现这样的表示方法太“粗糙”，根本无法表达出行与行之间因放置骨牌产生的细微的变化l这样的状态表示无法得到正确的递推或状态转移关系。因此我们增加将每行“细化”为每格的一维，即状态压缩l所以，状态太粗糙以致无法正确转移状态太粗糙以致无法正确转移是状态压缩的一个动机。状态压缩状态压缩终例终例l最后，以一个跟棋盘完全没有关系的例子来结束这次状态压缩之旅l给出一个有向图(顶点数n20)，求这个图的合法的拓扑序列的个数。经典问题状态压缩状态压缩终例终例 解法解法l既然是状态压缩，就要先确定取什么作为状态。l有了前面的介绍，应该可以尝试以已经访问过的点的集合作为状态。l状态S表示当前已经访问过的节点的集合，则fS表示访问S中的点的合法的拓扑序的个数l有了合适的状态表示，再联系递推的一般思路，我们发现只需要枚举最后到达的点即可。状态压缩状态压缩终例终例 解法解法l假设集合S中最后到达的点为x，则有：l虽然我们描述此算法用的是集合的语言，但实现这个算法仍然是用二进制即S01101表示已经访问了顶点1、3、4要求x到S中剩余的点都没有有向边状态压缩状态压缩总结总结l状态压缩是一种思想，理论上在任何有“状态”的算法中都可以应用l这里只是对其应用进行了简单的阐述l经过应用的磨练，总有一天状态压缩会进入每个Coder的潜意识中