《状态压缩动态规划浅谈1》由会员分享，可在线阅读，更多相关《状态压缩动态规划浅谈1（32页珍藏版）》请在金锄头文库上搜索。
1、状态压缩动态规划浅谈状态压缩动态规划浅谈 郑郑 暾暾 基础知识基础知识n n动态规划动态规划(dynamic programming)(dynamic programming) 运筹学运筹学的一个分支，是求解决策过程的一个分支，是求解决策过程(decision (decision process)process)最优化的数学方法。最优化的数学方法。n n动态规划是对解最优化问题的一种途径、一种方动态规划是对解最优化问题的一种途径、一种方 法，而不是一种特殊算法。其往往是针对一种最法，而不是一种特殊算法。其往往是针对一种最 优化问题。由于各种问题的性质不同，确定最优优化问题。由于各种问题的性质不
2、同，确定最优 解的条件也互不相同，因而动态规划的设计方法解的条件也互不相同，因而动态规划的设计方法 对不同的问题，有各具特色的解题方法，而不存对不同的问题，有各具特色的解题方法，而不存 在一种万能的动态规划算法，可以解决各类最优在一种万能的动态规划算法，可以解决各类最优 化问题。化问题。基础知识基础知识n n一些常见术语：阶段，状态，决策一些常见术语：阶段，状态，决策n n和递推的区别：决策！和递推的区别：决策！基本知识基本知识n n一些必要性质：一些必要性质：n n无后效性：对于状态，如果给定某一阶段无后效性：对于状态，如果给定某一阶段 的状态，则在这一阶段以后过程的发展不的状态，则在这一阶
3、段以后过程的发展不 受这阶段以前各段状态的影响，所有各阶受这阶段以前各段状态的影响，所有各阶 段都确定时，整个过程也就确定了。段都确定时，整个过程也就确定了。n n最优子结构性质：要求问题的最优策略的最优子结构性质：要求问题的最优策略的 子策略也是最优。子策略也是最优。基本知识基本知识n n状态压缩动态规划的使用动机：状态压缩动态规划的使用动机：n n一般的状态描述不满足无后效性原则，或一般的状态描述不满足无后效性原则，或 者保存的信息不足够进行决策。者保存的信息不足够进行决策。n n将当前一部分局面信息压缩存储，结合常将当前一部分局面信息压缩存储，结合常 见的一些局面描述，使得构成的状态满足
4、见的一些局面描述，使得构成的状态满足 无后效性原则无后效性原则基础知识基础知识n n名称：基于状态压缩的动态规划、集合动名称：基于状态压缩的动态规划、集合动 态规划。态规划。n n含义：以一个集合内的元素信息作为状态含义：以一个集合内的元素信息作为状态 ，状态总数为指数级别的动态规划。，状态总数为指数级别的动态规划。n n特点：特点：n n1 1、本身要满足动态规划的性质：、本身要满足动态规划的性质： 最优性原理、无后效性。最优性原理、无后效性。n n2 2、数据某几维规模比较小。、数据某几维规模比较小。传统集合动态规划传统集合动态规划n n例题一：例题一：n n给定给定n n个点的有向带权图
5、，求一条经过每个个点的有向带权图，求一条经过每个 点一次的回路，并要求权和最小。点一次的回路，并要求权和最小。n n范围范围n=15n=15。传统集合动态规划传统集合动态规划n n显然对于某一个中间状态，影响它的最后显然对于某一个中间状态，影响它的最后 结果的仅仅是当前所在点以及之前已经经结果的仅仅是当前所在点以及之前已经经 过的点。而之前的路径行走情况与之后的过的点。而之前的路径行走情况与之后的 解无关。解无关。n n状态状态Fi,optFi,opt，i i表示当前所在点，表示当前所在点，optopt是用是用2 2 进制记录每个点是否已经经过。进制记录每个点是否已经经过。传统集合动态规划传统
6、集合动态规划n n例题二：炮兵阵地例题二：炮兵阵地 （NOI2001NOI2001）n n在在N*MN*M网格地图上部署炮兵部队。每个炮网格地图上部署炮兵部队。每个炮 兵可以控制横纵兵可以控制横纵2 2格范围。任意一对炮兵互格范围。任意一对炮兵互 相不能处于控制范围。相不能处于控制范围。n n地图上有些点不能部署部队。地图上有些点不能部署部队。n nN = 100N = 100；M = 10M = 10。 传统集合动态规划传统集合动态规划n n例题三：例题三：K-K-排列问题排列问题n n考虑一个考虑一个1n1n的排列的排列a1,a2,a3a1,a2,a3anan， 若若max(abs(ai-
7、i)=Kmax(abs(ai-i)=K，那么这个排列就称，那么这个排列就称 为为K-K-排列。排列。n n求求n n个数的个数的K-K-排列的个数。排列的个数。n n范围：范围：n=100, K=5n=100, K=5传统集合动态规划传统集合动态规划n n例题四：生成树计数（例题四：生成树计数（NOI2007NOI2007）n n环状图，任意两个点距离不超过环状图，任意两个点距离不超过k k则连边，则连边， 求生成树个数。求生成树个数。n nK=5K=5实现实现n n插头法插头法n n转移的复杂度降低转移的复杂度降低n n时间复杂度降低时间复杂度降低传统集合动态规划传统集合动态规划n n例题例
8、题 Another Chocolate Maniac (Sgu132)Another Chocolate Maniac (Sgu132)n n给定一个给定一个M*NM*N的网格，网格中存在一些障的网格，网格中存在一些障 碍物。在网格空地处放置最少的碍物。在网格空地处放置最少的1*21*2的矩形的矩形 块，使得网格中无法再放入块，使得网格中无法再放入1*21*2的矩形块。的矩形块。n n1=M=701=M=70n n1=N=71=N=7基于连通性的状态压缩动态规划基于连通性的状态压缩动态规划n n在网格中寻找一条或多条路径（回路）满在网格中寻找一条或多条路径（回路）满 足一定的条件，求方案数或路
9、径总长度最足一定的条件，求方案数或路径总长度最 短。短。n n状态除了记录路径状态除了记录路径“ “出口出口” ”，还要记录其连通，还要记录其连通 性。性。基于连通性的状态压缩动态规划基于连通性的状态压缩动态规划n n例题一：例题一：Formula 1 Formula 1 （Ural 1519Ural 1519）n n给你一个给你一个m * nm * n的棋盘，有的格子是障碍，的棋盘，有的格子是障碍， 问共有多少条回路使得经过每个非障碍格问共有多少条回路使得经过每个非障碍格 子恰好一次子恰好一次n nm, n 12m, n 12 基于连通性的状态压缩动态规划基于连通性的状态压缩动态规划n n思
10、想：状态压缩动态规划。思想：状态压缩动态规划。n n一个单元格中可能出现的路径情况：一个单元格中可能出现的路径情况：实现细节实现细节n n总体实现：插头法总体实现：插头法n n实现方法：记忆化搜索实现方法：记忆化搜索n nFi,j,optFi,j,opt表示当前是表示当前是i i行行j j列，最后扫描的总共列，最后扫描的总共mm个个 格子的状态为格子的状态为optopt的方案数。的方案数。n nOptOpt的记录：的记录：mm个格子向下伸出插头的情况，以及个格子向下伸出插头的情况，以及 最后一个格子向右伸出插头的情况。最后一个格子向右伸出插头的情况。n n插头记录：插头记录：0 0表示无插头，
11、具体数字表示插头的属表示无插头，具体数字表示插头的属 性（染色法记录属于第几个连通块，最小表示）性（染色法记录属于第几个连通块，最小表示） 。对于本题最多同时存在。对于本题最多同时存在6 6个连通块的插头。个连通块的插头。实现细节实现细节n n转移：分类讨论插头方向。转移：分类讨论插头方向。n n1 1、当前格上方左方均有插头：只能将这两个连通、当前格上方左方均有插头：只能将这两个连通 块连接。（块连接。（1 1种）种）n n2 2、当前格只有上方有插头：将这个插头向下向右、当前格只有上方有插头：将这个插头向下向右 延伸。（延伸。（2 2种）种）n n3 3、当前格只有左方有插头：将这个插头向
12、下向右、当前格只有左方有插头：将这个插头向下向右 延伸。（延伸。（2 2种）种）n n4 4、当前格周围无插头：若当前格为障碍物，则无、当前格周围无插头：若当前格为障碍物，则无 插头，否则插入一个折线形插头。插头，否则插入一个折线形插头。实现细节实现细节n n合并连通块：合并连通块：n n对于第一种情况，需要合并连通块。若不加限制对于第一种情况，需要合并连通块。若不加限制 ，则会计算出包含多条回路的情况。，则会计算出包含多条回路的情况。n n限制：和并连通块时，若两个插头属于同一个连限制：和并连通块时，若两个插头属于同一个连 通块，则当且仅当在最后一个有效格子中可以将通块，则当且仅当在最后一个
13、有效格子中可以将 这两个插头连接。这两个插头连接。n n最后统计：计算到最后一个有效格子时，需要统最后统计：计算到最后一个有效格子时，需要统 计答案。此时，要保证当前状态没有剩余的插头计答案。此时，要保证当前状态没有剩余的插头 。实现细节实现细节n n一些可能存在的问题：一些可能存在的问题：n n直接开数组用序列记录插头好还是把状态直接开数组用序列记录插头好还是把状态 压缩后记录好？压缩后记录好？n n最小表示的如何实现？最小表示的如何实现？n n如何减小常数？如何减小常数？实现细节实现细节n n一个优化：一个优化：n n若当前格子连出的插头指向一个障碍物格若当前格子连出的插头指向一个障碍物格
14、 子，可以直接剪枝。子，可以直接剪枝。n n对有障碍的情况，能减少很多无效状态。对有障碍的情况，能减少很多无效状态。基于连通性的状态压缩动态规划基于连通性的状态压缩动态规划n n例题二：例题二：Manhattan WritingManhattan Writing（Japan2006Japan2006）n nn*mn*m网格有一些障碍，要求把两个网格有一些障碍，要求把两个2 2和两个和两个 3 3分别用折线连起来，总长度尽量小。分别用折线连起来，总长度尽量小。n nn,m=9n,m=9基于连通性的状态压缩动态规划基于连通性的状态压缩动态规划n n主体思想与之前相同。主体思想与之前相同。n n不同
15、点：不同点：n n需要专门两种属性记录与数需要专门两种属性记录与数2 2和数和数3 3的连通的连通 插头。插头。n n无需考虑多余回路情况。（解肯定劣）无需考虑多余回路情况。（解肯定劣）状态压缩动态规划中的剪枝状态压缩动态规划中的剪枝n n状态数是指数级别。状态数是指数级别。n n最小表示以减少状态数。最小表示以减少状态数。n n根据题目尽可能早地删去不可能成为最优根据题目尽可能早地删去不可能成为最优 的状态或不可行的状态。的状态或不可行的状态。状态压缩动态规划中的剪枝状态压缩动态规划中的剪枝n n例题：中国烟花例题：中国烟花 （zju2125zju2125）n n给你一个给你一个9 * 69
16、 * 6的棋盘，棋盘的左边的棋盘，棋盘的左边 有有9 9根火柴，右边有根火柴，右边有9 9个火箭棋盘个火箭棋盘 中的每一个格子可能是一个空格子中的每一个格子可能是一个空格子 也可能是一段管道，管道的类型有也可能是一段管道，管道的类型有4 4 种：种：L L型，一型，型，一型，T T型，十型。型，十型。n n给定棋盘的初始状态以及给定棋盘的初始状态以及X X，你的目，你的目 标是旋转每个格子内的管道标是旋转每个格子内的管道0 0，9090， 180180或或270270度，使得当点燃左边第度，使得当点燃左边第X X根根 火柴后，被发射的火箭个数尽可能火柴后，被发射的火箭个数尽可能 多。多。状态压缩动态规划中的剪枝状态压缩动态规划中的剪枝n n状态：按照从左到右，从上到下的顺序依状态：按照从左到右，从上到下的顺序依 次考虑每
