状态压缩动态规划浅谈

《状态压缩动态规划浅谈》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、状态压缩动态规划浅谈——郑暾peter112358@163.com基础知识动态规划(dynamicprogramming)运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。动态规划是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。其往往是针对一种最优化问题。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。基础知识一些常见术语：阶段，状态，决策和递推的区别：决策！基本知识一些必要性质：无后效

2、性：对于状态，如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。最优子结构性质：要求问题的最优策略的子策略也是最优。基本知识状态压缩动态规划的使用动机：一般的状态描述不满足无后效性原则，或者保存的信息不足够进行决策。将当前一部分局面信息压缩存储，结合常见的一些局面描述，使得构成的状态满足无后效性原则基础知识名称：基于状态压缩的动态规划、集合动态规划。含义：以一个集合内的元素信息作为状态，状态总数为指数级别的动态规划。特点：1、本身要满足动态规划的性质：最优性原理、无后效性。2

3、、数据某几维规模比较小。传统集合动态规划例题一：给定n个点的有向带权图，求一条经过每个点一次的回路，并要求权和最小。范围n<=15。传统集合动态规划显然对于某一个中间状态，影响它的最后结果的仅仅是当前所在点以及之前已经经过的点。而之前的路径行走情况与之后的解无关。状态F[i,opt]，i表示当前所在点，opt是用2进制记录每个点是否已经经过。传统集合动态规划例题二：炮兵阵地（NOI2001）在N*M网格地图上部署炮兵部队。每个炮兵可以控制横纵2格范围。任意一对炮兵互相不能处于控制范围。地图上有些点不能部署部队。N<=100；M<=10。传统集合动

4、态规划例题三：K-排列问题考虑一个1~n的排列a[1],a[2],a[3]…a[n]，若max(abs(a[i]-i))=K，那么这个排列就称为K-排列。求n个数的K-排列的个数。范围：n<=100,K<=5传统集合动态规划例题四：生成树计数（NOI2007）环状图，任意两个点距离不超过k则连边，求生成树个数。K<=5实现插头法转移的复杂度降低时间复杂度降低传统集合动态规划例题AnotherChocolateManiac(Sgu132)给定一个M*N的网格，网格中存在一些障碍物。在网格空地处放置最少的1*2的矩形块，使得网格中无法再放入1*2的矩

5、形块。1<=M<=701<=N<=7基于连通性的状态压缩动态规划在网格中寻找一条或多条路径（回路）满足一定的条件，求方案数或路径总长度最短。状态除了记录路径“出口”，还要记录其连通性。基于连通性的状态压缩动态规划例题一：Formula1（Ural1519）给你一个m*n的棋盘，有的格子是障碍，问共有多少条回路使得经过每个非障碍格子恰好一次．m,n≤12．基于连通性的状态压缩动态规划思想：状态压缩动态规划。一个单元格中可能出现的路径情况：实现细节总体实现：插头法实现方法：记忆化搜索F[i,j,opt]表示当前是i行j列，最后扫描的总共m个格子的状态

6、为opt的方案数。Opt的记录：m个格子向下伸出插头的情况，以及最后一个格子向右伸出插头的情况。插头记录：0表示无插头，具体数字表示插头的属性（染色法记录属于第几个连通块，最小表示）。对于本题最多同时存在6个连通块的插头。实现细节转移：分类讨论插头方向。1、当前格上方左方均有插头：只能将这两个连通块连接。（1种）2、当前格只有上方有插头：将这个插头向下向右延伸。（2种）3、当前格只有左方有插头：将这个插头向下向右延伸。（2种）4、当前格周围无插头：若当前格为障碍物，则无插头，否则插入一个折线形插头。实现细节合并连通块：对于第一种情况，需要合并连通

7、块。若不加限制，则会计算出包含多条回路的情况。限制：和并连通块时，若两个插头属于同一个连通块，则当且仅当在最后一个有效格子中可以将这两个插头连接。最后统计：计算到最后一个有效格子时，需要统计答案。此时，要保证当前状态没有剩余的插头。实现细节一些可能存在的问题：直接开数组用序列记录插头好还是把状态压缩后记录好？最小表示的如何实现？如何减小常数？实现细节一个优化：若当前格子连出的插头指向一个障碍物格子，可以直接剪枝。对有障碍的情况，能减少很多无效状态。基于连通性的状态压缩动态规划例题二：ManhattanWriting（Japan2006）n*m网格

8、有一些障碍，要求把两个2和两个3分别用折线连起来，总长度尽量小。n,m<=9基于连通性的状态压缩动态规划主体思想与之前相同。不同点：需要