《状态压缩动态规划中的状态与时间》由会员分享，可在线阅读，更多相关《状态压缩动态规划中的状态与时间（36页珍藏版）》请在金锄头文库上搜索。
1、状态压缩动态规划中的状态与时间,江苏省大丰中学 韩旭,概述,随着社会的发展以及社会生产技术的变革，世界也在从工业化转向信息化。与之而来的也就是信息学的快速发展，即其在生产生活中的大范围运用。但是很多的实际问题到目前为止并没有太多十分有效的算法，也就是无法在多项式时间复杂度内得出结果，但却依然需要快速解决，状态压缩的概念也就被引入进来并用以解决特定的一定范围内的问题。然而繁琐的状态压缩方法以及冗余的状态表述依然是制约效率的因素之一。于是去重消冗与改变状态来提高时空效率也就是我们需要做的，通过下面题目的分析，希望能对大家起到抛砖引玉的作用。 （ps:这里是废话）,状态压缩动态规划的基本概念,大家对
2、这些东西一定非常了解，在此不做过多赘述。因此直接跳过,刚才扯了一会淡，现在才是正文开始,状态压缩动态规划的局限性,状态压缩的作用无非是将原本分散的状态集约化、符号化、有序化，所以很多时候其状态数目依然是指数级别的。同时，状态之间复杂的关系使得两两状态之间的转移也受到影响。简而言之，状态压缩动态规划的状态与转移使得它只能处理数据在一个比较小的范围内的问题。,解决之道,总的来说我们并没有能彻底解决上述问题完美办法，我们能做的无非是进行一些枝枝末末的优化。常见的优化方法有以下几种:改善状态和转移选用不同的压缩方式引入位运算进行常数优化,解决之道,引入位运算进行常数优化是非常普遍的做法，在此也不做过多
3、的讨论。而减少重复状态、简化转移以及选用不同的压缩方式是我今天主要的讨论对象。,迷宫改造,【问题描述】给定一个n行m列的迷宫，相邻的两个单元之间存在一堵墙或者一扇门，墙是不可逾越的，而门是双向的且可以任意通过。现已知不多于三对的起始点与终点，要求让尽量少的墙变为门后使得没对起始点与终点之间联通，且每对起点与终点之间的路径只能不断向右向下蔓延。（3=N，M=20）,迷宫改造,样例输入：样例输出： 4 4 4 5 SESE 1 1 1 2 SSS 2 1 3 1 ESEE 2 2 3 2 4 2 4 3 1 4 2 4 3 2 1 4 3 1 2 4 2 3 1 4 4,迷宫改造,样例图示,迷宫改
4、造,分析： 题目的数据范围很容易让我们联系到状态压缩动态规划上，实际上此题的状态也是容易想到的。 所有的路径都是由上向下的，并且最多只有3个人，所以最直观的想法就是自上向下拓展这些人的路径并且记录下每个人路径的位置以便拓展。,迷宫改造,此时我们可以得到这样的一种状态： optijs1s2s3表示所有人的路径已经延伸到第i行的第1j列或者是第i-1行的第jm列，且三个人的路径分别到达这轮廓线上的第s1、s2、s3个格子时的最优解。,迷宫改造,如右图的状态就可以表示为(5,3,3,6,8),迷宫改造,这样的话状态数可以看成是N*M*(M+1)3的，因为对于每个状态optijs1s2s3我们只需要拓
5、展处在(i，j)这个格子里的路径向右或者是向下，因而每个状态的转移可以看做是O(1)的。 N*M*(M+1)3最大为3704400。所以理论上这种状态压缩的方式是可以解决问题的。,迷宫改造,但是 上述方法我实践之后非常扯淡的只有80分 这是什么原因呢？ 根据本人并不十分严谨和科学的大胆YY，初步分析是程序写萎了。 不过巨大的状态量以及高维数组的巨大常数也是造成写萎的原因之一 所以要寻求一些小小的改善。,迷宫改造,试想一下我们为什么一定要表示成刚才的折线式轮廓线而不是直线式轮廓线呢？答案就是因为前者的转移复杂度是常数级的而后者的转移复杂度为指数级的。 但这道题目中只有3个人，即使是指数级的转移，
6、复杂度也不是很大。,迷宫改造,此时我们可以得到这样的一种状态： optis1s2s3表示所有人的路径已经延伸到第i行，且三个人的路径分别到达这行上的第s1、s2、s3个格子时的最优解。 这样的状态，转移的时候就要使用指数级的枚举了，因为每个人都可以向右或者向下延伸路径。,迷宫改造,这样的话状态数可以看成是N*M3的，N*M3最大为160,000。 转移时由于每个人只有向右或者向下，所以复杂度最多为23=8种。 所以综合来看，虽然后者的转移复杂度变高，但总的来说无论是从复杂度上看还是常数上看都较前者优秀。,时间对比,迷宫改造,其实单纯的消除冗余的状态也是可以优化许多的。 对于最初的状态optij
7、s1s2s3，如果我们要拓展(i，j)这个格子里的路径，必然在这个格子里有一条路径，那么后面的s1、s2、s3并不是都需要记录的，由此我们就可以将原本较大的状态量缩小很多。,总结,从刚才那道题目不难看出，一般状态压缩动态规划的题目，想到一种状态不难，至于能不能解决问题就不得而知了，所以需要优化。 而涉及到的一些优化也不是非常高深莫测的东西。改善状态和转移或者选择一种合适的状态表示会需要的只是一些个人“奇葩”的想法，同时也要我们进行全盘的考虑，而这些就要看个人的经验问题了。 总之状态决定了时间，时间则体现了效率。,到此结束！ 谢谢！ 再谢！ 欢迎大家提问,局部极小值,【题目描述】有一个n行m列的
8、整数矩阵，其中1到nm之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。（3=N，M=20）,局部极小值,输入：2 2 X. .X 1 3 .X.,输出： 02,局部极小值,这道题目很容易让人想到是状态压缩，但对于这道题目用状态压缩解决的话，有两个地方比较“蛋疼”： 第一个就是只有“X“是局部最小值，其余不是。 第二个就是要填写数值很多。 这些东西怎么办呢？,局部极小值,考虑第一个问题，我们可以看出：如果解决的问题是“X“是局部最小值，其余无需考虑的话，那么问题就可解多了。而我们如果解决了这个问题又怎么回到第一个问题上去呢？
9、答案就是使用容斥原理。,局部极小值,如果我们设在所有的“X“都符合要求的基础上第i个格子(此格子不为“X“)为局部最小值的方案为 ，那么最后我们的结果就是这个式子是可以使用容斥原理来解决的。而容斥原理要解出每一项 ,每一项 其实就是一种无需考虑非“X“的情况,局部极小值,现在的问题就转化到求解莫一些格子一定是最小值而其余的格子不一定是的方案数的问题。第一个拦路虎基本上算是解决了。 现在我们再考虑第二个拦路虎。,局部极小值,刚才我们说道此题状态压缩另一个问题就是填写数值的很多，至少我们是没法用一个集合记录数值使用情况的。所以我们状态压缩的关键就是要采用一种不类似刚才的集合形式的状态压缩方式。 这
10、个又如何实现呢？ 我们还是立足基础想法来拓展。,局部极小值,试想一下我们记录一个数值使用集合的原因，无非是为了避免之后放置数的时候出现重复使用的情况。 但实际上我们只要每次都按照1、2、3、4这种由小到大的顺序来放置数就可以很方便的解决上面的问题了。因为这样放置的话其使用集合必然是一个连续的区间，这是很方便记录的。,局部极小值,而我们按照上述的放置方式后会出现新的问题，就是如何保证我们放完后所有的数后“X“一定是局部最小值呢？ 那就是让“X“在其周边的格子之前被放置一个数。这点并不是非常令人费解。,局部极小值,如右图(红色的都是已经放置了数的格子)，下一步我们放置8(有7个格子已经放过了)的话
11、，能放置的只能是所有的黑色的“X“或者白色的格子。,局部极小值,综上我们可以得到一组状态fij(i表示我们已经放置了数的个数，而j则是我们已经放置的“X“的集合)，其中的值自然就是方案了。 右图即可表示为f7011010(011010自然就是“X“的取舍情况)。,局部极小值,上述状态转移的话只要分两种情况就可以了。 一是在“X“上放数 二是在非“X“的可行格子放数,当前状态为f7011010 在“X“上放数的话选择有三种且分别推导到f8num2 (num2为111010、011110、011011的表示)。 在白色格子放的话有4*7-17-7=4种选择但只能推导到f7011010的状态,局部极小值,局部极小值,至此，套用刚刚的状态并使用容斥原理就可以解决问题了。,
