《动态规划之状态压缩》由会员分享，可在线阅读，更多相关《动态规划之状态压缩（21页珍藏版）》请在金锄头文库上搜索。
1、状态压缩Abstract信息学发展势头迅猛，信息学奥赛的题目来源遍及各行各业，经常有一些在实际应用中很有价值的问题被引入信息学并得到有效解决。然而有一些问题却被认为很可能不存在有效的(多项式级的)算法，本文以对几个例题的剖析，简述状态压缩思想及其应用。Keywords状态压缩、Hash、动态规划、递推ContentIntroduction作为Olers,我们不同程度地知道各式各样的算法。这些算法有的以O(logn)的复杂度运行，如二分查找、欧几里德GCD算法(连续两次迭代后的余数至多为原数的一半)、平衡树，有的以0(万)运行，例如二级索引、块状链表，再往上有0(n)、O(nplogqn)大部分
2、问题的算法都有一个多项式级别的时间复杂度上界1，我们一般称这类问题2为P(deterministicPolynomial-time)类问题，例如在有向图中求最短路径。然而存在几类问题，至今仍未被很好地解决，人们怀疑他们根本没有多项式时间复杂度的算法,卿0和NPHfNRHaM就是其中的两类，例如问一个图是否存在哈密顿圈(NPC)、问一个图是否不存在哈密顿圈(NPH)、求一个完全图中最短的哈密顿圈(即经典的TravelingSalesmanProblem货郎担问题，NPH)、在有向图中求最长(简单)路径(NPH)，对这些问题尚不知有多项式时间的算法存在。P和NPC都是NP(Non-determin
3、isticPolynomial-time)的子集，NPC则代表了NP类中最难的一类问题，所有的NP类问题都可以在多项式时间内归约到NPC问题中去。NPH包含了NPC和其他一些不属于NP(也更难)的问题，NPC问题的函数版本(相对于判定性版本)一般是NPH的，例如问一个图是否存在哈密顿圈是NPC的，但求最短的哈密顿圈则是NPH的，原因在于我们可以在多项式时间内验证一个回路是否真的是哈密顿回路，却无法在多项式时间内验证其是否是最短的，NP类要求能在多项式时间内验证问题的一个解是否真的是一个解，所以最优化TSP问题不是NP的，而是NPH的。存在判定性TSP问题，它要求判定给定的完全图是否存在权和小于
4、某常数v的哈密顿圈，这个问题的解显然可以在多项式时间内验证，因此它是NP1请注意，大O符号表示上界，即O(n丿的算法可以被认为是O(n2丿的，O(nplogqn丿可以被认为是O(nP+1)的。2在更正式的定义中，下面提到的概念都只对判定性问题或问题的判定版本才存在(NPH除外)。Levin给出了一个适用于非判定问题的更一般的概念，但他的论文比Cook的晚发表2年。的，更精确地说是NPC的。1如上所述，对于NPC和NPH问题，至今尚未找到多项式时间复杂度的算法。然而它们的应用又是如此的广泛，我们不得不努力寻找好的解决方案。毫无疑问，对于这些问题，使用暴力的搜索是可以得到正确的答案的，但在信息学竞
5、赛那有限的时间内，很难写出速度可以忍受的暴力搜索。例如对于TSP问题，暴力搜索的复杂度是O(n!),如此高的复杂度使得它对于高于10的数据规模就无能为力了。那么，有没有一种算法，它可以在很短的时间内实现，而其最坏情况下的表现比搜索好呢？答案是肯定的状态压缩加的Compression，SC)O作为对下文的准备，这里先为使用Pascal的Olers简要介绍一下C/C+样式的位运算(bitwiseoperation)。一、基本运算符名称C/C+样式Pascal样式简记法则按位与&and全一则一(bitwiseAND)否则为零按位或|or有一则一(bitwiseOR)否则为零按位取反not是零则一(b
6、itwiseNOT)是一则零按位异或人xor不同则一(bitwiseXOR)相同则零以上各运算符的优先级从高到低依次为：,&,八二、特殊应用a) and：i. 用以取出一个数的某些二进制位ii. 取出一个数二进制中的最后一个1(lowbit)2：x&-xb) or：用以将一个数的某些位设为1c) not：用以间接构造一些数：0u=4294967295=232-1d) xor：i. 不使用中间变量交换两个数：a=aAb;b=aAb;a=aAb;ii. 将一个数的某些位取反有了这些基础，就可以开始了。1 不应该混淆P、NP、NPC、NPH的概念。这里只是粗略介绍，详见关于算法分析的书籍(实际上一篇
7、paper根本讲不完，因为还有co-NP、co-NPC、#P、#PC后文会给出一(#PC的例子)，这会使新手读者的理论水平上一个台阶。弄不明白也没关系，基本不影响对本文其他部分的理解A_A2具有同样作用的还有处U&X，这个的道理更容易理解。lowbit在树状数组(某种数据结构)中可以用到，这里不再单独介绍，感兴趣的可以参阅各牛的论文，或者加我QQ。建议掌握，否则可能会看不懂我的部分代码。GettingStarted我们暂时避开状态压缩的定义，先来看一个小小的例题。【引例】1在n*n（nW20）的方格棋盘上放置n个车（可以攻击所在行、列），求使它们不能互相攻击的方案总数。【分析】这个题目之所以是
8、作为引例而不是例题，是因为它实在是个非常简单的组合学问题：我们一行一行放置，则第一行有n种选择，第二行n-1,，最后一行只有1种选择，根据乘法原理，答案就是n!。这里既然以它作为状态压缩的引例，当然不会是为了介绍组合数学。我们下面来看另外一种解法：状态压缩递推（StatesCompressingRecursion,SCR）。我们仍然一行一行放置。取棋子的放置情况作为状态，某一列如果已经放置棋子则为1，否则为0。这样，一个状态就可以用一个最多20位的二进制数2表示。例如n=5,第1、3、4列已经放置，则这个状态可以表示为01101（从右到左）。设f为达到状态s的方案数，则可以尝试建立f的递推关系
9、。考虑n=5,s=01101。这个状态是怎么得到的呢？因为我们是一行一行放置的，所以当达到s时已经放到了第三行。又因为一行能且仅能放置一个车，所以我们知道状态s一定来自：前两行在第3、4列放置了棋子（不考虑顺序，下同），第三行在第1列放置；第#页共16页第#页共16页上图依次为这三种情况，（红,蓝），（红，绿）分别代表两种顺序。这三种情况互不相交，且只可能有这三种情况，根据加法原理，/应该等于这三种情况的和。写成递推式就是：f=f+f+f01101011000100100101根据上面的讨论思路推广之，得到引例的解决办法：f=1s-2if=工fs其中s的右起第汁1位为1（其实就是在枚举s的二进
10、制表示中的1）3。反思这个算法，其正确性毋庸置疑（可以和n!对比验证）。但是算法的时间复杂度为O（n2），空间复杂度0（2“），是个指数级的算法，比循环计算n!差了好多,它有什么优势？较大的推广空间。41本文所有例题的C+代码均可以在附件中找到。2 方便、整齐起见，本文中不在数的后面标明进制。3 考虑上节介绍的位运算的特殊应用，可以更精巧地实现。4还有一个很的用处，即对新手说：“来看看我这个计算n!的程序，连这都看不懂就别OI了”SampleProblems【例1】1在n*n(nW20)的方格棋盘上放置n个车，某些格子不能放，求使它们不能互相攻击的方案总数。【分析】对于这个题目，如果组合数学学
11、得不够扎实，是否还能一眼看出解法？应该很难。对于这个题目，确实存在数学方法(容斥原理)，但因为和引例同样的理由，这里不再赘述。联系引例的思路，发现我们并不需要对算法进行太大的改变。引例的算法是在枚举当前行(即s中1的个数，设为r)的放置位置(即枚举每个1),而对于例1,第r行可能存在无法放置的格子，怎么解决这个问题呢？枚举1的时候判断一下嘛！事实的确是这样，枚举1的时候判断一下是否是不允许放置的格子即可。但是对于n=20,O(n2n丿的复杂度已经不允许我们再进行多余的判断。所以实现这个算法时应该应用一些技巧。对于第r行,我们用a表示不允许放置的情况,r如果第r行某一位不允许放置则此位为0，否则
12、为1，这可以在读入数据阶段完成。运算时，对于状态s,用tmps=s&ar来代替s进行枚举，即不枚举s中的1转而枚举tmps中的1。因为tmps保证了不允许放置的位为0,这样就可以不用多余的判断来实现算法，代码中只增加了计算a数组和r的部分，而时间复杂度没有太大变化。这样，我们直接套用引例的算法就使得看上去更难的例1得到了解决。读者可能会说，这题用容斥原理更快。没错，的确是这样。但是，容斥原理在这题上只有当棋盘为正方形、放入的棋子个数为n、且棋盘上禁止放置的格子较少时才有简单的形式和较快的速度。如果再对例1进行推广，要在m*n的棋盘上放置k个车，那么容斥原理是无能为力的，而SCR算法只要进行很少
13、的改变就可以解决问题题目来源：经典组合学问题。如果这样改编，则状态的维数要增加，如有疑问可以参考下面的几个例子，这里不再赘述。题目来源：经典问题改编。这也体现出了引例中给出的算法具有很大的扩展潜力。棋盘模型是状态压缩最好的展示舞台之一。下面再看几个和棋盘有关的题目。【例2】3给出一个n*m的棋盘(n、mW80,n*mW80),要在棋盘上放k(kW20)个棋子，使得任意两个棋子不相邻。每次试验随机分配一种方案，求第一次出现合法方案时试验的期望次数，答案用既约分数表示。【分析】显然，本题中的期望次数应该为出现合法方案的概率的倒数，则问题转化为求出现合法方案的概率。而概率=合法方案数，方案总数显然为
14、C(n*m,k),则问方案总数题转化为求合法方案数。整理一下，现在的问题是：在n*m的棋盘上放k个棋子，求使得任意两个棋子不相邻的放置方案数。这个题目的状态压缩模型是比较隐蔽的。观察题目给出的规模，n、mW80,这个规模要想用SC是困难的，若同样用上例的状态表示方法(放则为1，不放为0),280无论在时间还是在空间上都无法承受。然而我们还看到n*mW80,这种给出数据规模的方法是不多见的，有什么玄机呢？能把状态数控制在可以承受的范围吗？稍微一思考，我们可以发现：9*9=8180，即如果n,m都大于等于9,将不再满足n*mW80这一条件。所以，我们有n或m小于等于8,而28是可以承受的。我们假设
15、mWn(否则交换，由对称性知结果不变)n是行数m是列数，则每行的状态可以用m位的二进制数表示。但是本题和例1又有不同：例1每行每列都只能放置一个棋子，而本题却只限制每行每列的棋子不相邻。但是，上例中枚举当前行的放置方案的做法依然可行。我们用数组s保存一行中所有的num个放置方案1,则s数组可以在预处理过程中用DFS求出，同时用ci保存第ii个状态中1的个数以避免重复计算。开始设计状态。如例1的注释所说，维数需要增加，原因在于并不是每一行只放一个棋子，也不是每一行都要求有棋子，原先的表示方法已经无法完整表达一个状态。我们用f.k表示第i行的状态为s.且前i行已经放置了k个棋子2的方案数。沿用枚举当前行方案的做法，只要当前行的方案和上一行的方案不冲突即可，“微观”地讲，即s初和sid(i1)没有同为1sid(i)sid(i-1)的位，其中sid(x丿表示第x行的状态的编号。然而，虽然我们枚举了第i行的放置方案，但却不知道其上一行(第i-1行)的方案。为了解决这个问题，我们不得不连第i-1行的状态一起枚举，则可以写出递推式：f=1(要求亏与SP不冲突)0,1,0fi,j,k=i,j,k其中s1=0,即在当前行不放置棋子；j和P是需要枚举的两个状态编
