状态压缩.ppt
《状态压缩.ppt》由会员分享,可在线阅读,更多相关《状态压缩.ppt(56页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、状态压缩状态压缩主讲:主讲:ftfish(ftfish(周伟周伟 天津大学天津大学20072007级级)邮箱:邮箱:zhouwei-zhouwei- 手机:手机:137 5213 1713137 5213 1713Q Q Q Q:155 175 157155 175 157状态压缩状态压缩信息学发展势头迅猛,信息学奥赛的题目来源遍及各行各业,经常有一些在实际应用中很有价值的问题被引入信息学并得到有效解决。然而有一些问题却被认为很可能不存在有效的(多项式级的)算法,这里以对几个例题的剖析,简述状态压缩思想及其应用。状态压缩状态压缩预备知识预备知识名称名称C/C+样样式式Pascal样样式式简记简
2、记法法则则按位与按位与&and全一全一则则一,否一,否则为则为零零按位或按位或|or有一有一则则一,否一,否则为则为零零按位取反按位取反not是零是零则则一,是一一,是一则则零零按位异或按位异或xor不同不同则则一,相同一,相同则则零零左移位左移位shlashrak等价于等价于a/2k作为对下文的准备,这里先为使用Pascal的OIers简要介绍一下C/C+样式的位运算(bitwise operation)。其优先级:notandxoror状态压缩状态压缩预备知识预备知识位运算的特殊应用位运算的特殊应用and:用以取出一个数的某些二进制位取出一个数二进制中的最后一个1(lowbit):x&-x
3、or:将一个数的某些位设为1not:间接构造一些数:0u=4294967295=232-1xor:不使用中间变量交换两个数:a=ab;b=ba;a=ab;将一个数的某些位取反状态压缩状态压缩引例引例在n*n(n20)的方格棋盘上放置n个车(可以攻击所在行、列),求使它们不能互相攻击的方案总数。10秒时间思考状态压缩状态压缩引例引例这个题目之所以是作为引例而不是例题,是因为它实在是个非常简单的组合学问题我们一行一行放置,则第一行有n种选择,第二行n-1,最后一行只有1种选择,根据乘法原理,答案就是n!这里既然以它作为状态压缩的引例,当然不会是为了介绍组合数学。我们下面来看另外一种解法:状态压缩递
4、推状态压缩递推(States Compressing Recursion,SCR)状态压缩状态压缩引例解法引例解法我们仍然一行一行放置。取棋子的放置情况作为状态,某一列如果已经放置棋子则为1,否则为0。这样,一个状态就可以用一个最多20位的二进制数表示。例如n=5,第1、3、4列已经放置,则这个状态可以表示为01101(从右到左)。设fs为达到状态s的方案数,则可以尝试建立f的递推关系。状态压缩状态压缩引例解法引例解法考虑n=5,s=01101因为我们是一行一行放置的,所以当达到s时已经放到了第三行。又因为一行能且仅能放置一个车,所以我们知道状态s一定来自:状态压缩状态压缩引例解法引例解法前两
5、行在第3、4列放置了棋子(不考虑顺序,下同),第三行在第1列放置;前两行在第1、4列放置了棋子,第三行在第3列放置;前两行在第1、3列放置了棋子,第三行在第4列放置。状态压缩状态压缩引例解法引例解法这三种情况互不相交,且只可能有这三种情况,根据加法原理,fs应该等于这三种情况的和。写成递推式就是:状态压缩状态压缩引例解法引例解法根据上面的讨论思路推广之,得到引例的解决办法:其中s的右起第i+1位为1(其实就是在枚举其实就是在枚举s的二进制表示中的的二进制表示中的1)状态压缩状态压缩引例引例的实现的实现Prog P0read(n);int64 f1.220=0;f0=1;for(int i=1;
6、i0;t-=t&-t)fi+=fi(t&-t);write(f2n-1);状态压缩状态压缩对引例的思考对引例的思考反思这个算法,其正确性毋庸置疑(可以和n!对比验证)但是算法的时间复杂度为O(n2n),空间复杂度O(2n),是个指数级的算法,比循环计算n!差了好多,它有什么优势?(还有一个很的用处,即对新手说:“来看看我这个计算n!的程序,连这都看不懂就别OI了”)可扩展性!可扩展性!状态压缩状态压缩例例1在n*n(n20)的方格棋盘上放置n个车,某些格子不能放,求使它们不能互相攻击的方案总数。30s思考时间状态压缩状态压缩例例1分析分析对于这个题目,如果组合数学学得不够扎实,应该很难一眼看出
7、解法。本题确实存在数学方法(容斥原理),但因为和引例同样的理由,这里不再赘述。引例的算法是在枚举当前行(即s中1的个数,设为r)的放置位置(即枚举每个1)而对于例1,第r行可能存在无法放置的格子,怎么解决?枚举枚举1的时候判断一下嘛!的时候判断一下嘛!状态压缩状态压缩例例1解法解法事实上,我们并不需要对引例的算法进行太大的改变,只要在枚举s中的1的时候判断一下是否是不允许放置的格子即可然而对于n=20,O(n2n)的复杂度已经不允许我们再进行多余的判断。所以实现这个算法时应该应用一些技巧。我们用ar表示第r行不允许放置的情况,如果第r行某一位不允许放置则ar此位为0,否则为1,这可以在读入数据
8、阶段完成状态压缩状态压缩例例1解法解法然后对于需要处理的状态s,用ts=s&ar来代替s进行枚举,即不枚举s中的1转而枚举ts中的1。因为ts保证了不允许放置的位为0,这样就可以不用其它的判断来实现算法代码中只增加了计算a数组和r的部分,而时间复杂度没有变化。状态压缩状态压缩对例对例1的思考的思考我们直接套用引例的算法就使得看上去更难的例1得到了解决。虽然这题用容斥原理更快,但容斥原理在这题上只有当棋盘为正方形、放入的棋子个数为n、且棋盘上禁止放置的格子较少时才有较简单的形式和较快的速度。如果再对例1进行推广,要在m*n的棋盘上放置k个车,那么容斥原理是无能为力的,而SCR算法只要进行很少的改
9、变就可以解决问题。这也体现出了引例中给出的算法的扩展潜力。状态压缩状态压缩例例2有一个n*m的棋盘(n、m80,n*m80)要在棋盘上放k(k20)个棋子,使得任意两个棋子不相邻。求合法的方案总数5min思考、讨论、提问时间状态压缩状态压缩例例2分析分析观察题目给出的规模,n、m80,这个规模要想用SC是困难的,280无论在时间还是空间上都无法承受然而我们还看到n*m80稍微思考我们可以发现:9*9=8180,即如果n,m都大于等于9,将不再满足n*m80这一条件。所以,我们有n或m小于等于8,而28是可以承受的!状态压缩状态压缩例例2分析分析我们假设mn,n是行数m是列数,则每行的状态可以用
10、m位的二进制数表示但是本题和例1又有不同:例1每行每列都只能放置一个棋子,而本题却只限制每行每列的棋子不相邻上例中枚举当前行的放置方案的做法依然可行。我们用数组s保存一行中所有的num个放置方案,则s数组可以在预处理过程中用DFS求出,同时用ci保存第i个状态中1的个数以避免重复计算状态压缩状态压缩例例2分析分析开始设计状态。本题状态的维数需要增加,原因在于并不是每一行只放一个棋子,也不是每一行都要求有棋子,原先的表示方法已经无法完整表达一个状态。我们用fi,j,k表示第i行的状态为sj且前i行总共放置k个棋子(下面用pn代替原题中的k)的方案数。沿用枚举当前行方案的做法,只要当前行的放置方案
11、和上一行的不冲突。微观地讲,就是要两行的状态s1和s2中没有同为1的位即可,亦即s1&s2=0状态压缩状态压缩例例2解法解法然而,虽然我们枚举了第i行的放置方案,但却不知道其上一行(第i-1行)的方案为了解决这个问题,我们不得不连第连第i-1行行的状态一起枚举的状态一起枚举,则可以写出递推式:其中其中s s1 1=0=0,即在当前行不放置棋子;,即在当前行不放置棋子;j j和和p p是需要枚举的两个状态编号。是需要枚举的两个状态编号。状态压缩状态压缩例例2解法解法本题至此基本解决。当然,实现上仍有少许优化空间,例如第i行只和第i-1行有关,可以用滚动数组节省空间。这个算法时间复杂度O(n*pn
12、*num2),空间复杂度(滚动数组)O(pn*num)运用简单的组合数学知识可以求出本题中的num=144,因而对于本题的数据规模可以很快出解状态压缩状态压缩例例3给出一个n*m(n100,m10)的棋盘,一些格子不能放置棋子。求最多能在棋盘上放置多少个棋子,使得每一行每一列的任两个棋子间至少有两个空格。题目来源:NOI2001炮兵阵地TOI 1023;POJ 118530s 思考时间状态压缩状态压缩例例3分析分析仍然先用DFS搜出一行可能状态s,依旧用c保存s中1的个数,依照例1的预处理搞定不能放置棋子的格子(应该有这种意识)问题是,这个题目的状态怎么选?继续像例2那样似乎不行,原因在于棋子
13、的攻击范围加大了状态压缩状态压缩例例3分析分析但是我们照葫芦画瓢:例2的攻击范围只有一格,所以我们的状态中只需要有当前行的状态,再枚举上一行的状态即可进行递推;而本题攻击范围是两格,因此增加一维来表示上一行的状态。状态压缩状态压缩例例3解法解法用fi,j,k表示第i行状态为sj、第i-1行状态为sk时前i行至多能放置的棋子数。则状态转移方程很容易写出:显然,算法时间复杂度为O(n*num3),空间复杂度(滚动数组)O(num2)因为棋子攻击范围为两格,可以直观地想像到本题的num不会很大。的确,可以算出本题num60。状态压缩状态压缩例例3题外话题外话此算法还有优化空间我们分别枚举了三行的状态
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 状态 压缩
限制150内