状态压缩动态规划中的状态与时间

1、状态压缩动态规划中的状态与时间大丰市高级中学韩旭目录：【关键字】【概述】【正文】基础知识 TOC o 1-5 h z HYPERLINK l bookmark28 o Current Document 1.1动态规划的概述11.1.1动态规划的概念1 HYPERLINK l bookmark31 o Current Document 一些常见术语1 HYPERLINK l bookmark35 o Current Document 1.1.3和递推的区别1 HYPERLINK l bookmark38 o Current Document 1.1.4 一些必要性质11.2状态压缩动态规划的使用

2、动机及其特点 HYPERLINK l bookmark42 o Current Document 1.2.1状态压缩动态规划的使用动机1 HYPERLINK l bookmark45 o Current Document 1.2.2状态压缩动态规划的特点d1.3位运算的引入及其优化效果 HYPERLINK l bookmark48 o Current Document 1.3.1位运算的引入2 HYPERLINK l bookmark51 o Current Document 1.3.2位运算的特殊用法及其优化效果2常见的状态压缩类型概述2.1常见集合型的状态压缩含义2 HYPERLINK l

3、 bookmark58 o Current Document 2.1.2性能极其特点2例题22.2基于联通性的状态压缩2.2.1含义.3 HYPERLINK l bookmark69 o Current Document 2.2.2性能极其特点3例题32.3小结典型例题的优化及其效果3.1改变状态及其优化效果.5含义5例题5 HYPERLINK l bookmark86 o Current Document 3.2去重消冗及其优化效果g HYPERLINK l bookmark89 o Current Document 含义8例题83.3小结【参考文献】【附件】【关键字】动态规划 状态压缩去重

4、消冗 改变状态 降低时耗【概述】随着社会的发展以及社会生产技术的变革，世界也在从工业化转向信息化。与 之而来的也就是信息学的快速发展，即其在生产生活中的大范围运用。但是很多的 实际问题到目前为止并没有太多十分有效的算法，也就是无法在多项式时间复杂度 内得出结果，但却依然需要快速解决，状态压缩的概念也就被引入进来并用以解决 特定的一定范围内的问题。然而繁琐的状态压缩方法以及冗余的状态表述依然是制 约效率的因素之一。于是去重消冗与改变状态来提高时空效率也就是我们需要做 的，通过下面题目的分析，希望能对大家起到抛砖引玉的作用。（ps:基础知识可直接跳过，常见的状态压缩类型举例可以适当跳过）【正文】【

5、第一部分】基础知识1.1.1动态规划的概念：动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。动态规划是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。其 往往是针对一种最优化问题。由于各种问题的性质不同，确定最优解的条件也互不 相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在 一种万能的动态规划算法，可以解决各类最优化问题。一些常见术语：阶段，状态，决策1.1.3和递推的区别：决策的存在一些必要性质：无后效性：对于状态，如果给定某一阶段的状态，则在这一阶段以后过程的发 展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。最优子结构

6、性质：要求问题的最优策略的子策略也是最优。1.2.1状态压缩动态规划的使用动机：一般的状态描述不满足无后效性原则，或者保存的信息不足够进行决策。将当前一部分局面信息压缩存储，结合常见的一些局面描述，使得构成的状态 满足无后效性原则，从而可以实现动态规划来解决问题。1.2.2状态压缩动态规划的特点：压缩后本身要满足动态规划的性质(最优性原理、无后效性)。数据规模比较小，可以进行可行的压缩。1.3.1位运算的引入： 按位与运算 (and)效果是逐位全一为一，反之为零。 按位或运算 (or)效果是逐位有一为一，反之为零。 按位异或运算(xor)效果是逐位不同为一，反之为零。1.3.2位运算的特殊用法

7、及其优化效果： 按位与运算(and)可以取出二进制中的某些位，也可以取出二进制数的最后一位非零位。按位与运算(or)可以将二进制某些位上添上1。按位异或运算(xor)可以将二进制某些位上的元素取反【第二部分】常见的状态压缩类型及其压缩方式2.1常见集合型的状态压缩：2.1.1含义：以一个集合内的元素信息作为状态，状态总数为指数级别的状态压缩动态规划 方式。(其通常带有较为明显的集合色彩，如在于不在，取或者不取，亦或是取的 数量是多少多少这样的情况)。2.1.2性能极其特点：这种方式往往是最简单最直接的状态压缩的方式，思考的复杂度不是很高，但 在这类状态压缩中往往不同的压缩方式其效率差距很大，状

8、态压缩方式的选择往往 是影响这类方法效率的关键。例题：炮兵阵地(NOI2001)在N*M网格地图上部署炮兵部队。每个炮兵可以控制横纵2格范围。任意一对炮兵互相不能处于控制范围。炮兵的火力覆盖范围为右图所示。地图上有些点不能部署部队。（N = 100； M = 10）分析：方案一：首先这道题目中炮兵的射程只有横纵各两个格子而已，也就是说每个炮兵只会 影响之后的两行。此外对于任意一种炮兵安置方案中炮兵的安置顺序对全局不构成 影响，因而我们可以逐行的放置炮兵，且只需要记录放置行的向上连续两行的状态。 于是我们可以设出这样的状态：optijk（j，k为=进制的表达形式）表示到第i行未放置之前第i-1行

9、的状 态为j以及第i-2行的状态为k的最大放置炮兵数目。其状态的数量级为 O（n*2”m*2m）。方案二：如果我们不是从炮兵的存在与否来考虑状态的压缩，而是从每个炮兵放置后影 响的范围进行考虑的话，我们可以设出这样的状态：optij（k为三进制的表达形式）表示到第i行未放置之前，之前的每一列最 下方的炮兵到当前行的距离集合为j （每个跑兵包括其本身格子在内最多向下延伸3 行）的情况下的最大放置炮兵数目。其状态的数量级为O（n*3”m）。2.2基于联通性的状态压缩：2.2.1含义：除了以一个集合内的元素信息作为状态，在其状态中还需要记录若十个元素之 间的连通情况，称为基于连通性状态压缩的动态规划

10、问题。（其通常与图形相结合， 如线路、管道等等，通常是要求求得线路的数量或是最值）2.2.2性能极其特点：这种方式往往是根据图形来进行一些状态压缩，往往就是用插头去进行拼接。 这类状态压缩的方式通常较为单一，状态压缩方式的决定对效率的影响不是很大， 但消除重复运算和不必要运算往往对效率的提高有奇效。例题：Formula 1 （Ural 1519）给你一个m * n的棋盘，有的格子是障碍，问共有多少条回路使得经过每个非 障碍格子恰好一次。（m = 12； n = 12）分析：这是一道经典的插头DP，我们显然是逐行逐列的推导来划分状态。对于每个格 子里的线路会有以下的一些情况：我们可以设出这样的状

11、态fijk （k为一个三进制的表达形式，用以表示 括号匹配来表示插头的联通状况）表示第i行第j列没有确定线路的状况下轮廓线上 的插头情况为k时路线的方案数目。每次我们可以把上述的6个方格中的某一个放入 第i行第j列，使得线路得以延续推导出新的状态。其状态的数量级为O（n*m*3”m）。动态规划过程中转移时需要分类讨论插头方向。当前格上方左方均有插头：只能将这两个连通块连接。当前格只有上方有插头：将这个插头向下向右延伸。当前格只有左方有插头：将这个插头向下向右延伸。当前格周围无插头：若当前格为障碍物，则无插头，否则插入一个折线形插头。对于第一种情况，需要合并连通块，若不加限制，则会计算出包含多条

12、回路的 情况。（在我们和并连通块时，若两个插头属于同一个连通块，则当且仅当在最后 一个有效格子中可以将这两个插头连接）2.3常见的状态压缩的小结：以上就是两种常见的状态压缩类型及其压缩方式。通常的压缩方式和它们是非 常类似的，出现的题目类型也是两者中的某一种，虽然其中状态表述丰富繁杂，但 万变不离其宗，其目的都是将复杂无序的状态压缩后用有序的数学结构进行表述以便进行下一步的操作，实质都是一样的。【第三部分】典型例题的优化及其效果3.1改变状态及其优化效果：3.1.1含义：用状态压缩动态规划解决问题时，往往我们可以有很多种状态可以进行选择， 不同的状态在状态的数量、转移的复杂度以及应用中的优缺点

13、都是不同的。于是往 往有一类题目，我们最直观的想法及最直接的压缩方式，其空间复杂度和时间复杂 度都很大，同时很难优化。这时我们就要转化问题，转化到一些状态表述更为精炼、 简便的问题，从而便于我们解题。3.1.2例题：局部极小值（cqoi2012）【题意简述】有一个n行m列的整数矩阵，其中1到nm之间的每个整数恰好出现一次。如果一 个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是 局部极小值。给出所有局部极小值的位置，你的任务是判断有多少个可能的矩阵。【分析】这道题目具有很明显的状态压缩的味道，同时其数据规模非常的小，且具有常 见集合型的状态压缩的特点，所以很容易联想到使

14、用状态压缩来解决这个问题，但 如何进行状态压缩呢？首先我们需要考虑的是如何定义一个状态使得每次我们填入一个数之后做出 的结果没有后效性。最直接最简单的想法就是和传统的状态压缩方式类似采用二进 制来表示每个数的使用状况且逐行逐列的进行放置。这样放置的好处显然就是每一 步我们都可以知道哪些数已经用过了，哪些数没有用过可以放置在当前位置上。但 其不足也非常的明显甚至致命，就是没有办法表示其周边数的大小比较情况。很显 然一个格子和四周最多有四个格子相连，因为我们是逐行逐列进行放置，所以只需 要关心每个数的上方和左方数的大小，对于左方的数我们可以进行记载，但上方的 数我们就没有办法进行记录和压缩了。这样

15、的方法显然是解决不了问题的，于是我 们必须寻找其它的办法。方案一：对于n*m的矩阵，其中有一维非常的小，至少不大于4,这是不是提醒我们可以 把上一行的数记录下来呢？设想一下如果我们把上一行的数字记录下来的话，那么 之后每填充一个数后必然就能知道其与之前的数的大小关系了。但这样又带来了一 个新的问题，就是我们没有办法知道当前填进格子里的数之前是否已经被使用过了, 这个问题是否可以解决呢？如果解决不了，必然这个状态也是无效的。我们再进行 思考不难发现，每个数在大小上只影响后面的一行，至于再后面的行里放的数就和 当前的数没有关系了。每当我们放完一行后，后面的可以放置的数必然都是不同的， 因而也就具有

16、的大小顺序。于是我们考虑记录的就不是上一行放的是什么数了，而 是上一行的数在后续数中排在第几位，考虑放置的也就不是具体的什么数了，而是 放的数是后续数中排在第几位的数。由于有一维只有4,算成轮廓线也只有5,所以 这样压缩成的状态再第一行有。篇种情况，第二行及其之后会更少。于是我们初步 拟定了这样的状态:optijkl（k为一个组合压成的状态，l为一个二进制表 达形式）表示第i行第j列未放置数之前轮廓线上的若干个数在之后的数中的排名状 态为k以及之前是否有数比轮廓线上数小的状态为l的情况下的方案个数。如上图的状态就可以表示为opt24num1num2（其中num2为10110的表示， numl为

17、6、4、8、23、3组合在一起的压缩编号，10110含义就是6、9、25四周有比 其小的值，6、4、8、23、3含义就是指6、4、9、25、3在红色轮廓线之后的数中的 大小排名）。这样的状态已经是一种满足我们需要的表述方式了，但细算下来，这样的状态 因为需要记录之前是否有相邻的数比轮廓线上数小的情况，使我们的状态数目陡增 不少。如果没有.必须为非最小值得限制，这样的压缩方法还是可行的，但对于 这道题目，这样的压缩方式还是无法有效解决。方案二：换了个角度我们继续看问题。对于一个合法的数填写方案，其中的数放置的顺 序对其是没有影响的，于是我们可以从1开始填数，并且一个一个地填进格子。如 果采取这样

18、的做法，那么所有的“X”必然要在其周边所有的格子填数之前就填好 一个数，而X 有多少呢？很显然最多只有8个而已。这时我们就可以想到这样的一 个状态压缩方式：optij（j是一个二进制表达）表示的是i及其以后的数还没 有填进格子，被填写了数的“X”集合状态为j的情况下的方案数。X3X】X2X，X&如上图4*7的矩阵中，红色的X表示已经填写数的X，红色的格子表示已经 填写数的非X格子，那么可以表述成这样的状态opt8num （8表示已经填写了7 个数，下一个填写8, num是011010的表示，含义是第2、3、5个X已经填写了数了）如果我们转移的话就会有两种情况：第一种情况就是把i填进一个X中，这

19、个显然只要枚举一下放哪一个X，然 后把这个X加入表示的集合里就可以了。X3X】X2X，X6如上图，下一步我们填写X 是可以随意的，因为只要存在解，任意的X 都是 互不影响的。当前的状态为f8num1（numl为011010的表示），可以推导到 f9num2（num2为 111010、011110、011011 的表示）。第二种情况就是把i填进一个非X 中，这样的选择就有很多了。对于全图我们 一共有n*m个格子，若没有填进去数的X 格子以及其周边的格子共有tot个，显然 这tot个格子都是不能填i的（因为填进的是一个非X，并且一个没有填进去数的 X格子其周边因为都要比它小，所以这两者都不可以填i

20、），又因为已经填写了1到 i-1所有的数，所以剩下能填的选择数就是n*m-tot-（i-1）。X3X】X2X,X6如上图，所有的蓝色区域都是无法填写i的，而下一步能填写的格子就只有白 色的格子，即4*7-17-7=4个格子。由于这样的处理方式，尤其是第二种转移可能会导致非X 点变为最小值，所 以还需要使用容斥原理来解决。3.2去重消冗及其优化效果3.2.1含义：很多情况下我们的状态记录了一些不必要的状态，这些冗杂多余的状态不仅占 用了不少空间，同时也消耗了很多时间。去重消冗的方法就是从状态本身出发，在 不对状态本身进行巨大变动的前提下尽可能去除重复的状态从而提高效率的方法。 由于状态压缩动态规

21、划中状态的数量级别为指数级的，所以这里面的优化空间是很 大的，因而这种不对状态伤筋动骨的方法往往是很有效的。总之就是减少状态、简 化转移以提高效率。3.2.2例题：迷宫改造【题意简述】给定一个n行m列的迷宫，相邻的两个单元之间存在一堵墙或者一扇门，墙是 不可逾越的，而门是双向的且可以任意通过。现已知不多于三对的起始点与终点， 要求让尽量少的墙变为门后使得没对起始点与终点之间联通，且每对起点与终点之 间的路径只能不断向右向下蔓延。（3=N，M=20）【分析】对于这道题目的状态表述是非常容易想到的，就是optijklm 表示以 i,j为转折点的轮廓线上，前后三个起始点分别联通到轮廓线上的第k、1、

22、m个格子， 并在这个情况下最少的墙变为门的数量。这样的最大状态数为 20*20*21*21*21=3704400种。如上图的就可以表述为opt54368（表示轮廓线上的转折点为第5行 第4列的格子，第一个起点联通到轮廓线上第3个格子（红色），第二起点联通到轮 廓线上第6个格子（蓝色），第三个起点联通到轮廓线上第8个格子（绿色）。由于每次转折线左侧和上侧的点可以选择向下亦或是向右，转移的复杂度近似 于0（1），所以最后的时间复杂度也为O（n*m*（m+1）”3）。理论上来说这样的算法似乎 已经可以满足我们的需要了，但实现这个算法的时候却不难发现，高维又数目众多 的数组常数很大使得效率受到了影响，于是就要寻求优化来提高效率。优化一：其实这道题目启用类似传统连通性状态压缩动态规划的轮廓线是非常没有必 要的，因为联通的线段的数量很少。虽然传统连通性状态压缩动态规划的轮廓线使 得转移的复杂度达到最低，但同时也使得状态数量的增多。我们不妨就原始一点， 将轮廓线扳直，用optijkl表述状态（三个起点分别联通到第i行的第j、k、 l个格子的最优值）。这样的状态虽然转移的复杂度略微提高，但状态数却少了一个 数量级。优化二如果我们采用4维的状态数，转移的话每个起始点连出的路径都需要向右或是 向下。但实际上是每一个状态我们只需要每次拓展一个路