一谈基于连通性状态压缩的动态规划

《基于连通性状态压缩的动态规划》是长沙市雅礼中学陈丹琦同学在国家集训队中写的一篇论文。名字很长,但民间好像都叫这个东西“插头dp”。

第一次接触:在GDKOI2016前一个晚上,宋老师把一些以往的同学参加GDKOI写的解题报告发到了微信群上,便学习之。他们多次提到了轮廓线这个概念,但我一头雾水,完全没概念。然而Day1 Problem3就用到了!我的内心是崩溃的。后来上网查了才略知一二。

今天刚考完GDOI2016 Day2。第二题(home)十分明显是插头DP,n=8,O(n2)O(n^2)时间复杂度,常数稍高,但仍然绰绰有余。但我在此之前仅仅是读过论文,并没有真正写过,后果就体现出来了:考试的时候花了一个半个小时设计算法,编了半个小时的码,还碰到很多技术难关。卒暴力之,回溯!:(

何为连通性(联通性)?

寻找路径、矩形完美覆盖等问题中都需要考虑连通性问题。举一个简单的例子,在一个哈密顿回路中,随便切一刀,这个回路可能被切好几段。把切割线一侧的回路抹掉,看剩下的一半,我们要求出未知的那一半。程序中,我们只考虑当前切割线上回路的状态,不需要理会已经求出来的那一半究竟是怎么布线的。但是我们需要知道的一个事情是,排在切割线上的回路,究竟哪个和哪个是连在一起的?如果不维护这些信息的话,很可能创建出好几个回路,或者有一些必须包含在回路里的元素没有接上。

何为状态压缩?

状态压缩是动态规划中使用的一个概念。一般来说,动态规划在状态转移的时候需要根据前面已得知的一些信息来进行选择。但是有些问题的状态比较繁琐,信息量比较大,所以需要将状态压缩了才能储存。

何为动态规划?

。。。

连通性+状态压缩+动态规划=?

我在网上看到一篇SprintfWater博主写的文章[1],也是一位OIer。这位仁兄写的非常激动,非常有感情,可以看出对算法深深的爱。请允许我转载一小段:

acm记忆:在很久很久以前 ,当插头DP还只是被称作“基于连通性状态压缩动态规划”的时候,楼教主就将其化为男人八题 之列 !引得无数自认为很man的英雄豪杰欲AC之 而后快 !而吾等菜鸟是这学期才听闻 到还有插头DP一说 ,故欲快速刷之以解心中愁!遂捧着cdq(性别 :女)关于基于连通性状态压缩动态规划的论文研读数遍 ,别人一女生在论文里讲得貌似很简单,简单而我这个男生却看得 我神乎其神 !纠结数日不得解!思己既然 选择了做男人,那还是 要男人一会,所以不想去看这题 的解题报告,后放下 男人八题 ,在Timus的oj上 找到了需要用插头DP算法解决的 Formular1题,将各大神牛的代码结合 起来研读数日,终领会其精髓果断重拾 男人八题,可悲剧的是编码花了2小时,调试用 了哥哥一天的时间才AC,囧囧囧囧!在攻插头DP的过程中,多次都有认为自己 不像男人,但最终AC之后,才感觉重新做回了男人 !

…好吧。下午还有解题报告,我得先走了。


华丽丽的时间分割线


刚从解题大会上回来,出题人打我的脸打得真爽。他一上场就说:“出这道题本意是想考搜索的,你们没有人想用插头DP做吧?”听了顿时火冒三丈,怒发冲冠,但对于我一个用搜索水掉40分的人,心里还是暗爽的。不管了,我反正本来就要谈谈插头DP的。

总体思路

逐格扫描,对每一格的轮廓线上的插头情况逐一进行转移。论文中也提到了逐行扫描,未能深入研究。反正没有逐格扫描方便就对了。

轮廓线

当前格子的上边界及其右边所有的边界,当前格子的左边界,以及当前格子下边界左边的所有的边界。

轮廓线

插头

路径怎么可能不穿过轮廓线呢,但是我们处理格子是一个一个从上到下从左到右处理的,所以在轮廓线以下的格子状态还是未知的。但是又不能扔掉已经有的轮廓线,所以呢,就晾它在那里好了。伸出来一点小东西是不是很像插头?后面的格子会负责把它接好,但是究竟是怎么接上去,到时候再说。

对当前格子的处理

有很多插头伸下来等着接上。对当前格子的处理是要分情况的,不同的题目不一样。拿CDQ论文里面提到的一个题来说吧,要在棋盘上找经过所有非障碍格子的哈密顿回路的数量。情况:

  • 障碍。当然是不能把插头插这里面啊,就算你再硬也插不进去吧,硬插就只能弯掉咯。果断舍弃之,对当前格子有插头的情况全部不计,没有插头的不做处理直接转移,障碍也是伸不出插头的。
  • 非障碍。非障碍又分好几类:
    • 直线型。这一类要求当前格子左边和上面有且仅有一个插头,转移后有且仅有那个插头对面的插头。
    • 拐角型。拐角型比较复杂,因为开始涉及到连通性了。
      • 左下连接以及上右连接比较好处理。要求左上有且仅有一个插头。输出一个相邻的插头。
      • 左上连接,完成回路。无插头输出。看起来简单,但是涉及到连通性状态的更新,以后再谈。
      • 右下连接,输出两个插头,要求左上都没有插头。

分每种情况讨论时,把当前的状态数推送到目标格子目标状态上,加起来即可。

一些实现上的细节

连通性的状态压缩

连通性可以用数字表示,若这个位置有插头,则用一个非零数字表示这个插头;所有在轮廓线以上与这个插头联通的插头都用这个数字标上号。然后把一整行的状态都保存下来,放在f[i][j][状态]这里,完成状态压缩。可以用最大数+1进制来表示。优点:速度快,遍历所有状态方便;缺点:占内存空间大,读取状态麻烦。同时为了提升速度,建议使用位运算而不是除法/取余操作,所以进制都最好用2/4/8/16进制存储。

优化加速

很多状态因为插头冲突的问题,事实上是不存在的。这个时候,很多时候如果用三个for循环把所有点和它的所有状态都遍历一遍,事实上是没有必要的,既浪费时间也浪费空间。CDQ在论文中推荐使用队列+哈希的方法将有可能的状态加入队列中逐一处理。

我在考试的时候为了解决状态可能太多,内存超限,也是用类似的方法。定义一个结构体,建立关于结构体的队列,结构体内储存坐标、连通性信息,这样非常省空间,而且高效。问题在于,对同一个坐标同一个状态进行第两次更新的时候,要不再加入一次队列,对那个坐标那个状态更新两次,以及以后所有的操作都多来几遍,这些显然是低效的,时间复杂度又退化成暴搜的指数级别;或者用哈希定位状态在队列中的位置,然后再更新,加上可能数。而且推完一行之后的转移也特别麻烦,在考试的时候想不了那么多,最后只能回归到暴力的方法。

一个简化了的插头DP问题

题目:4.5算法之动态规划 1665:完美覆盖

这个问题来自NOI题库,也是一个经典的问题。在数学上已经有组合的大神搞出了递推式以及通项公式,所以纵观他人代码,竟有一半没超过500K。。。

我们来分析一下。一个1×2的矩形可以覆盖两个格子,也就是说,我们把这个矩形放到一个格子上,必然多出来一半等着填到另一个格子里面去,那么我们可以把这一半看作一个插头。

逐格递推是肯定的了。在轮廓线上,插头没有连通性的问题,只是有没有的问题,所以用二进制压缩状态。因为列数比较少而且固定,我们可以把列和行交换来研究问题,不影响结果。状态数少,所以没有必要用队列,直接枚举所有情况就可以了。对于每一格,有四种情况:

  • 左边上面都有。这种情况是不可行的,所以不进行转移。
  • 只有左边有,或者只有上面有。把这个插头接上就好。转移后这个格子没有插头。
  • 两边都没有,那么只能创造新的插头。插头可以朝下,也可以朝上。

一行处理完之后,只有最右边界没有插头的状态才可以转移到下一行最左边没有插头的状态。O(状态数)转移即可。

这里是我的AC代码。我也是初学,所以不知道有没有更简洁的做法,让高人见笑了,还请指正。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int f[33][4][1<<4],n;
int main(){
    cin>>n;
    while(n!=-1){
        memset(f,0,sizeof(f));
        f[0][0][0]=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                for(int k=0;k<16;k++){
                    //up:k>>(i+1)
                    //left:k>>i
                    if((k>>(j+1))&1){
                        if((k>>j)&1){
                            //have up have left
                            //no solution
                        }else{
                            //no left have up
                            //end up blcok
                            f[i][j+1][k^(1<<(j+1))]+=f[i][j][k];
                        }
                    }else{
                        if((k>>j)&1){
                            //no up have left
                            f[i][j+1][k^(1<<j)]+=f[i][j][k];
                        }else{
                            //no up no left
                            //create new ones
                            f[i][j+1][k^(1<<j)]+=f[i][j][k];
                            f[i][j+1][k^(1<<(j+1))]+=f[i][j][k];
                        }
                    }
                }
            }
            for(int k=0;k<8;k++){
                f[i+1][0][k*2]=f[i][3][k];
            }
        }
        cout<<f[n][0][0]<<endl;
        cin>>n;
    }
}

这个简化了的模型十分好做,但是论文里面的问题我还没能实战一遍。等下次继续研究透了,我们再谈。


  1. http://blog.csdn.net/sprintfwater/article/details/7748375

avatar
Kerry Su