状态压缩dp

午夜问路

贡献于2011-07-28

字数:0 关键词: C/C++开发

状态压缩 郑州 101 中学/天津大学 周伟 第 1 页 共 12 页 状态压缩 Abstract 信息学发展势头迅猛,信息学奥赛的题目来源遍及各行各业,经常有一些在 实际应用中很有价值的问题被引入信息学并得到有效解决。然而有一些问题却被 认为很可能不存在有效的(多项式级的)算法,本文以对几个例题的剖析,简述状 态压缩思想及其应用。 Keywords 状态压缩、集合、Hash、NPC Content Introduction 作为 OIers,我们不同程度地知道各式各样的算法。这些算法有的以 O(logn) 的复杂度运行,如二分查找、欧几里德 GCD 算法(连续两次迭代后的余数至多为 原数的一半)、平衡树,有的以 O( n )运行,例如二级索引、块状链表,再往上 有 O(n)、O(nplogqn)……大部分问题的算法都有一个多项式级别的时间复杂度上 界1,我们一般称这类问题2为 P 类(deterministic Polynomial-time)问题,例如在有 向图中求最短路径。然而存在几类问题,至今仍未被很好地解决,人们怀疑他们 根本没有多项式时间复杂度的算法,它们是 NPC(NP-Complete) 和 NPH(NP-Hard)类,例如问一个图是否存在哈密顿圈(NPC)、问一个图是否不存 在哈密顿圈(NPH)、求一个完全图中最短的哈密顿圈(即经典的 Traveling Salesman Problem 货郎担问题,NPH)、在有向图中求最长(简单)路径(NPH),对这些问题 尚不知有多项式时间的算法存在。P 和 NPC 都是 NP(Non-deterministic Polynomial-time)的子集,NPC 则代表了 NP 类中最难的一类问题,所有的 NP 类 问题都可以在多项式时间内归约到 NPC 问题中去。NPH 包含了 NPC 和其他一 些不属于 NP(也更难)的问题(即 NPC 是 NP 与 NPH 的交集), NPC 问题的最优 化版本一般是 NPH 的,例如问一个图是否存在哈密顿圈是 NPC 的,但求最短的 哈密顿圈则是 NPH 的,原因在于我们可以在多项式时间内验证一个回路是否真 的是哈密顿回路,却无法在多项式时间内验证其是否是最短的,NP 类要求能在 多项式时间内验证问题的一个解是否真的是一个解,所以最优化 TSP 问题不是 NP 的,而是 NPH 的。存在判定性 TSP 问题,它要求判定给定的完全图是否存 在权和小于某常数 v 的哈密顿圈,这个问题的解显然可以在多项式时间内验证, 1 请注意,大 O 符号表示上界,即 O(n)的算法可以被认为是 O(n2)的,O(nplogqn)可以被认为是 O(np+1)的。 2 在更正式的定义中,下面提到的概念都只对判定性问题或问题的判定版本才存在。Levin 给出了一个适用 于非判定问题的更一般的概念,但他的论文比 Cook 的晚发表 2 年。 状态压缩 郑州 101 中学/天津大学 周伟 第 2 页 共 12 页 因此它是 NP 的,更精确地说是 NPC 的。1 如上所述,对于 NPC 和 NPH 问题,至今尚未找到多项式时间复杂度的算法。 然而它们的应用又是如此的广泛,我们不得不努力寻找好的解决方案。毫无疑问, 对于这些问题,使用暴力的搜索是可以得到正确的答案的,但在信息学竞赛那有 限的时间内,很难写出速度可以忍受的暴力搜索。例如对于 TSP 问题,暴力搜 索的复杂度是 O(n!),如此高的复杂度使得它对于高于 10 的数据规模就无能为力 了。那么,有没有一种算法,它可以在很短的时间内实现,而其最坏情况下的表 现比搜索好呢?答案是肯定的——状态压缩(States Compression,SC)。 作为对下文的准备,这里先为使用 Pascal 的 OIers 简要介绍一下 C/C++样式 的位运算(bitwise operation)。 一、基本运算符 名称 C/C++样式 Pascal 样式 简记法则 按位与 (bitwise AND) & and 全一则一 否则为零 按位或 (bitwise OR) | or 有一则一 否则为零 按位取反 (bitwise NOT) ~ not 是零则一 是一则零 按位异或 (bitwise XOR) ^ xor 不同则一 相同则零 以上各运算符的优先级从高到低依次为:~,&,^,| 二、特殊应用 a) and: i. 用以取出一个数的某些二进制位 ii. 取出一个数的最后一个 1(lowbit) 2:x&-x b) or :用以将一个数的某些位设为 1 c) not:用以间接构造一些数:~0=4294967295=232-1 d) xor: i. 不使用中间变量交换两个数:a=a^b;b=a^b;a=a^b; ii. 将一个数的某些位取反 有了这些基础,就可以开始了。 1 不应该混淆 P、NP、NPC、NPH 的概念。这里只是粗略介绍,详见关于算法分析的书籍,这会使新手读 者的理论水平上一个台阶。弄不明白也没关系,基本不影响对本文其他部分的理解^_^ 2 具有同样作用的还有(x-1)&x^x,这个的道理更容易理解。lowbit 在树状数组(某种数据结构)中可以用 到,这里不再单独介绍,感兴趣的可以参阅各牛的论文,或者加我 QQ。建议掌握,否则可能会看不懂我 的部分代码。 状态压缩 郑州 101 中学/天津大学 周伟 第 3 页 共 12 页 Getting Started 我们暂时避开状态压缩的定义,先来看一个小小的例题。 【引例】1 在 n*n(n≤20)的方格棋盘上放置 n 个车(可以攻击所在行、列),求使它们不 能互相攻击的方案总数。 【分析】 这个题目之所以是作为引例而不是例题,是因为它实在是个非常简单的组合 学问题:我们一行一行放置,则第一行有 n 种选择,第二行 n-1,……,最后一 行只有 1 种选择,根据乘法原理,答案就是 n!。这里既然以它作为状态压缩的引 例,当然不会是为了介绍组合数学。我们下面来看另外一种解法:状态压缩递推 (States Compressing Recursion,SCR)。 我们仍然一行一行放置。取棋子的放置情况作为状态,某一列如果已经放置 棋子则为 1,否则为 0。这样,一个状态就可以用一个最多 20 位的二进制数2表 示。例如 n=5,第 1、3、4 列已经放置,则这个状态可以表示为 01101(从右到左)。 设 f[s]为达到状态 s 的方案数,则可以尝试建立 f 的递推关系。 考虑 n=5,s=01101。这个状态是怎么得到的呢?因为我们是一行一行放置的, 所以当达到 s 时已经放到了第三行。又因为一行能且仅能放置一个车,所以我们 知道状态 s 一定来自: ①前两行在第 3、4 列放置了棋子(不考虑顺序,下同),第三行在第 1 列放置; ②前两行在第 1、4 列放置了棋子,第三行在第 3 列放置; ③前两行在第 1、3 列放置了棋子,第三行在第 4 列放置。 这三种情况互不相交,且只可能有这三种情况。根据加法原理,f[s]应该等于这 三种情况的和。写成递推式就是: f[01101]=f[01100]+f[01001]+f[00101] 根据上面的讨论思路推广之,得到引例的解决办法: f[0]=1 f[s]=∑f[s^2i] 其中 s∈[0…01,1…11],s 的右起第 i+1 位为 1。3 反思这个算法,其正确性毋庸置疑(可以和n!对比验证)。但是算法的时间复 杂度为 O(n2n),空间复杂度 O(2n),是个指数级的算法,比循环计算 n!差了好多, 它有什么优势?较大的推广空间。4 Sample Problems 【例 1】5 在 n*n(n≤20)的方格棋盘上放置 n 个车,某些格子不能放,求使它们不能互 1 本文所有例题的 C++代码均可以在附件中找到。 2 方便、整齐起见,本文中不在数的后面标明进制。 3 考虑上节介绍的位运算的特殊应用,可以更精巧地实现。 4 还有一个很…的用处,即对新手说:“来看看我这个计算 n!的程序,连这都看不懂就别 OI 了~” 5 题目来源:经典组合学问题。 状态压缩 郑州 101 中学/天津大学 周伟 第 4 页 共 12 页 相攻击的方案总数。 【分析】 对于这个题目,如果组合数学学得不够扎实,你是否还能一眼看出解法?应 该很难。对于这个题目,确实存在数学方法(容斥原理),但因为和引例同样的理 由,这里不再赘述。 联系引例的思路,发现我们并不需要对算法进行太大的改变。引例的算法是 在枚举当前行(即 s 中 1 的个数,设为 r)的放置位置(即枚举每个 1),而对于例 1, 第 r 行可能存在无法放置的格子,怎么解决这个问题呢?枚举 1 的时候判断一下 嘛!事实的确是这样,枚举 1 的时候判断一下是否是不允许放置的格子即可。 但是对于 n=20,O(n2n)的复杂度已经不允许我们再进行多余的判断。所以实 现这个算法时应该应用一些技巧。对于第 r 行,我们用 a[r]表示不允许放置的情 况,如果某一位不允许放置则为 1,否则为 0,这可以在读入数据阶段完成。运 算时,对于状态 s,用 tmps=s^a[r]来代替 s 进行枚举,即不枚举 s 中的 1 转而枚 举 tmps 中的 1。因为 tmps 保证了无法放置的位为 0,这样就可以不用多余的判 断来实现算法,代码中只增加了计算 a 数组和 r 的部分,而时间复杂度没有太大 变化。 这样,我们直接套用引例的算法就使得看上去更难的例 1 得到了解决。你可 能会说,这题用容斥原理更快。没错,的确是这样。但是,容斥原理在这题上只 有当棋盘为正方形、放入的棋子个数为 n、且棋盘上禁止放置的格子较少时才有 简单的形式和较快的速度。如果再对例 1 进行推广,要在 m*n 的棋盘上放置 k 个车,那么容斥原理是无能为力的,而 SCR 算法只要进行很少的改变就可以解 决问题1。这也体现出了引例中给出的算法具有很大的扩展潜力。 棋盘模型是状态压缩最好的展示舞台之一。下面再看几个和棋盘有关的题 目。 【例 2】2 给出一个 n*m 的棋盘(n、m≤80,n*m≤80),要在棋盘上放 k(k≤20)个棋子, 使得任意两个棋子不相邻。每次试验随机分配一种方案,求第一次出现合法方案 时试验的期望次数,答案用既约分数表示。 【分析】 显然,本题中的期望次数应该为出现合法方案的概率的倒数,则问题转化为 求出现合法方案的概率。而概率= 方案总数 合法方案数 ,方案总数显然为 C(n*m,k),则 问 题转化为求合法方案数。整理一下,现在的问题是:在 n*m 的棋盘上放 k 个棋 子,求使得任意两个棋子不相邻的放置方案数。 这个题目的状态压缩模型是比较隐蔽的。观察题目给出的规模,n、m≤80, 这个规模要想用 SC 是困难的,若同样用上例的状态表示方法(放则为 1,不放为 0),280 无论在时间还是在空间上都无法承受。然而我们还看到 n*m≤80,这种 给出数据规模的方法是不多见的,有什么玄机呢?能把状态数控制在可以承受的 1 如果这样改编,则状态的维数要增加,如有疑问可以参考下面的几个例子,这里不再赘述。 2 题目来源:经典问题改编。 状态压缩 郑州 101 中学/天津大学 周伟 第 5 页 共 12 页 范围吗?稍微一思考,我们可以发现:9*9=81>80,即如果 n,m 都大于等于 9, 将不再满足 n*m≤80 这一条件。所以,我们有 n 或 m 小于等于 8,而 28 是可以 承受的。我们假设 m≤n(否则交换,由对称性知结果不变)n 是行数 m 是列数, 则每行的状态可以用 m 位的二进制数表示。但是本题和例 1 又有不同:例 1 每 行每列都只能放置一个棋子,而本题却只限制每行每列的棋子不相邻。但是,上 例中枚举当前行的放置方案的做法依然可行。我们用数组 s[1..num]1保存一行中 所有的 num 个放置方案,则 s 数组可以在预处理过程中用 DFS 求出,同时用 c[i] 保存第 i 个状态中 1 的个数以避免重复计算。开始设计状态。如注释一所说,维 数需要增加,原因在于并不是每一行只放一个棋子,也不是每一行都要求有棋子, 原先的表示方法已经无法完整表达一个状态。我们用 f[i][j][k]表示第 i 行的状态 为 s[j]且前 i 行已经放置了 k 个棋子2的方案数。沿用枚举当前行方案的做法,只 要当前行的方案和上一行的方案不冲突即可,“微观”地讲,即 s[snum[i]]和 s[snum[i-1]]没有同为 1 的位,其中 snum[x]表示第 x 行的状态的编号。然而,虽 然我们枚举了第 i 行的放置方案,但却不知道其上一行(i-1)的方案。为了解决这 个问题,我们不得不连第 i-1 的状态一起枚举,则可以写出递推式: f[0][1][0]=1; f[i][j][k]=∑f[i-1][p][k-c[j]] 其中 s[1]=0,即在当前行不放置棋子;j 和 p 是需要枚举的两个状态编号,且要 求 s[j]与 s[p]不冲突,即 s[j]&s[p]=0。3 当然,实现上仍有少许优化空间,例如第 i 行只和第 i-1 行有关,可以用滚动数 组节省空间。 有了合法方案数,剩下的问题就不是很困难了,需要注意的就只有C(n*m,k) 可能超出 64 位整数范围的问题,这可以通过边计算边用 GCD 约分来解决,具体 可以参考附件中的代码。这个算法时间复杂度 O(n*pn*num2),空间复杂度(滚动 数组)O(pn*num),对于题目给定的规模是可以很快出解的。 通过上文的例题,读者应该已经对状态压缩有了一些感性的认识。下面这个 题目可以作为练习。 【例 3】4 在 n*n(n≤10)的棋盘上放 k 个国王(可攻击相邻的 8 个格子),求使它们无法 互相攻击的方案数。 【分析】 其实有了前面几个例子的分析,这个题目应该是可以独立解决的。不过既然 确实有疑问,那我们就来分析一下。 1 运用简单的组合数学知识可以求出:在格数为 m 的一行上放棋子且相邻两个棋子中间的空格不能少于 d 的 num=g[m+d+1],其中 g[i]=1 (i=1..d+1); g[j]=g[j-d-1]+g[j-1] (j>d)。对于本题, num=144。此式在下文也有应用。 2 为了避免歧义,下文中用 pn 代替原题中的 k。 3 请读者停下来仔细揣摩这个递推式,否则可能影响对本文后面内容的理解! 4 题目来源:SGU.223《Little Kings》 状态压缩 郑州 101 中学/天津大学 周伟 第 6 页 共 12 页 首先,你应该能想到将一行的状态 DFS 出来(如果不能,请返回重新阅读, 谢谢),仍然设为 s[1..num],同时仍然设有数组 c[1..num]记录状态对应的 1 的个数。 和例 2 相同,仍然以 f[i][j][k]表示第 i 行状态为 s[j],且前 i 行已经放置了 k 个棋 子的方案数。递推式仍然可以写作: f[0][1][0]=1; f[i][j][k]=∑f[i-1][p][k-c[j]] 其中仍要求 s[j]和 s[p]不冲突。 可是问题出来了:这题不但要求不能行、列相邻,甚至不能对角线相邻!s[j]、 s[p]不冲突怎么“微观地”表示呢?其实,稍微思考便可以得出方法:用 s[p] 分别和 s[j]、s[j]*2、s[j]/2 进行冲突判断即可,原理很显然。解决掉这唯一 的问题,接下来的工作就没有什么难度了。算法复杂度同例 2。 下一个例题是状态压缩棋盘模型的经典题目,希望解决这个经典的题目能够 增长你的自信。 【例 4】1 给出一个 n*m(n≤100,m≤10)的棋盘,一些格子不能放置棋子。求最多能在 棋盘上放置多少个棋子,使得每一行每一列的任两个棋子间至少有两个空格。 【分析】2 显然,你应该已经有 DFS 搜出一行可能状态的意识了(否则请重新阅读之前 的内容 3 遍,谢谢),依然设为 s[1..num],依旧有 c[1..num]保存 s 中 1 的个数,依 照例 1 的预处理搞定不能放置棋子的格子。 问题是,这个题目的状态怎么选?继续像例 2、3 那样似乎不行,原因在于 棋子的攻击范围加大了。但是我们照葫芦画瓢:例 2、3 的攻击范围只有一格, 所以我们的状态中只需要有当前行的状态即可进行递推,而本题攻击范围是两 格,因此增加一维来表示上一行的状态。用 f[i][j][k]表示第 i 行状态为 s[j]、第 i-1 行状态为 s[k]时前 i 行至多能放置的棋子数,则状态转移方程很容易写出: f[i][j][k]=max{f[i-1][k][l]}+c[j] 其中要求 s[j],s[k],s[l]互不冲突。 因为棋子攻击范围为两格,可以直观地想象到 num 不会很大。的确,由例 2 中得到的 num 的计算式并代入 d=2、m=10,得 到 num=60。显然算法时间复杂度 为 O(n*num3),空间复杂度(滚动数组)O(num2)。此算法还有优化空间。我们分别 枚举了三行的状态,还需要对这三个状态进行是否冲突的判断,这势必会重复枚 举到一些冲突的状态组合。我们可以在计算出 s[1..num]后算出哪些状态可以分别 作为两行的状态,这样在 DP 时就不需要进行盲目的枚举。这样修改后的算法理 论上比上述算法更优,但因为 num 本身很小,所以这样修改没有显著地减少运 行时间。值得一提的是,本题笔者的算法虽然在理论上并不是最优3,但由于位 运算的使用,截至 2 月 9 日,笔者的程序在 PKU OJ 上长度最短,速度第二快。 这个题目是国内比赛中较早出现的状态压缩题。它告诉我们状态压缩不仅可 以像前几个例题那样求方案数,而且可以求最优方案,即状态压缩思想既可以应 用到递推上(SCR),又可以应用到 DP 上(SCDP),更说明其有广泛的应用空间。 1 题目来源:NOI2001《炮兵阵地》;PKU.1185 2 读者应该独立思考一个小时后再看分析,它值得这样。 3 有种应用三进制的方法理论上可能更优,但因为手工转换进制效率远不如系统的位运算高,且无法使用 位运算判断可行性,程序效率并不比文中的高,故不再赘述那种方法。下文的一些题目将用到多进制。 状态压缩 郑州 101 中学/天津大学 周伟 第 7 页 共 12 页 看了这么多棋盘模型应用状态压缩的实例,你可能会有疑问,难道状态压缩 只在棋盘上放棋子的题目中有用?不是的。我们暂时转移视线,来看看状态压缩 在其他地方的应用——覆盖模型。 【例 5】1 给出 n*m (1≤n、m≤11)的方格棋盘,用 1*2 的长方形骨牌不重叠地覆盖这 个棋盘,求覆盖满的方案数。 【分析】 这也是个经典的组合数学问题:多米诺骨牌完美覆盖问题(或所谓二聚物问 题)。有很多关于这个问题的结论,甚至还有个专门的公式:如果 m、n 中至少 有一个是偶数,则结果= ∏∏ == ⎥⎦ ⎤ ⎢⎣ ⎡ + 2 2 11 )1+n *j(cos4)1+m *i(4cos 22 m n ij ππ 。这个公式形式比较 简单,且计算的复杂度是 O( 4 *nm )的,很高效。但是这个公式内还有三角函数, 且中学生几乎不可能理解,所以对我们能力的提高没有任何帮助。用 SCR 算法 能较好地解决这个问题。 显然,如果 n、m 都是奇数则无解(由棋盘面积的奇偶性知),否则必然有至 少一个解(很容易构造出),所 以 假 设 n、m 至少有一个偶数,且 m≤n(否则交换)。 我们依然像前面的例题一样把每行的放置方案 DFS 出来,逐行计算。用 f[i][s] 表示把前 i-1 行覆盖满、第 i 行覆盖状态为 s 的覆盖方案数。因为在第 i 行上放置 的骨牌最多也只能影响到第 i-1 行,则容易得递推式: f[0][1…11]=1 f[i][s1]=∑f[i-1][s2] 其中(s1,s2)整体作为一个放置方案,可以把所有方案 DFS 预处理出来。下面讨 论一下本题的一些细节。 首先讨论 DFS 的一些细节。对于当前行每一个位置,我们有 3 种放置方法: ①竖直覆盖,占据当前格和上一行同一列的格;②水平覆盖,占据当前格和该行 下一格;③不放置骨牌,直接空格。如何根据这些枚举出每个(s1,s2)呢?下面介 绍两种方法: 第一种: DFS 共 5 个参数,分别为:p(当前列号),s1、s2(当前行和上一行的覆盖 情况),b1、b2(上一列的放置对当前列上下两行的影响,影响为 1 否则为 0)。 初始时 s1=s2=b1=b2=0。①p=p+1,s1=s1*2+1,s2=s2*22,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。 当 p 移出边界且 b1=b2=0 时记录此方案。 第二种: 观察第一种方法,发现 b2 始终为 0,知这种方法有一定的冗余。换个更 自然的方法,去掉参数 b1、b2。①p=p+1,s1=s1*2+1,s2=s2*2;②p=p+2, 1 题目来源:经典问题;PKU.2411《Mondriaan's Dream》 2 注意!第 i 行的放置方案用到第 i-1 行的某格时,s2 中该格应为 0! 状态压缩 郑州 101 中学/天津大学 周伟 第 8 页 共 12 页 s1=s1*4+3,s2=s2*4+3;③p=p+1,s1=s1*2,s2=s2*2+1。当 p 移出边界时记 录此方案。这样,我们通过改变 p 的移动距离成功简化了 DFS 过程,而且这 种方法更加自然。 DFS 过程有了,实现方法却还有值得讨论的地方。前面的例题中,我们为什 么总是把放置方案 DFS 预处理保存起来?是因为不合法的状态太多,每次都重 新 DFS 太浪费时间。然而回到这个题目,特别是当采用第二种时,我们的 DFS 过程中甚至只有一个判断(递归边界),说明根本没有多少不合法的方案,也就没 有必要把所有方案保存下来,对于每行都重新 DFS 即可,这不会增加运行时间 却可以节省一些内存。 这个算法时间复杂度为多少呢?因为 DFS 时以两行为对象,每行 2m,共进 行 n 次 DFS,所以是 O(n*4m)?根据“O”的上界意义来看并没有错,但这个界 并不十分精确,也可能会使人误以为本算法无法通过 1≤n、m≤11 的测试数据, 而实际上本算法可以瞬间给出 m=10,n=11 时的解。为了计算精确的复杂度,必 须先算出 DFS 得到的方案数。 考虑当前行的放置情况。如果每格只有①③两个选择,则应该有 2m 种放置 方案;如果每格有①②③这 3 个选择,且②中 p 只移动一格,则应该有 3m 种放 置方案。然而现在的事实是:每格有①②③这 3 个选择,但②中 p 移动 2 格,所 以可以知道方案数应该在 2m 和 3m 之间。考虑第 i 列,则其必然是:第 i-1 列采 用①③达到;第 i-2 列采用②达到。设 h[i]表示前 i 列的方案数,则得到 h[i]的递 推式: h[0]=1,h[1]=2 h[i]=2*h[i-1]+h[i-2] 应用组合数学方法1求得其通项公式 h[m]= mm )21(4 22)21(4 22 −−+++ 。注 意到式子的第二项是多个绝对值小于 1 的数的乘积,其对整个 h[m]的影响甚小, 故略去,得到方案数 h[m]≈0.85*2.414m,符合 2m

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 20 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档

相关文档