《基于连通性状态压缩的动态规划问题课件.ppt》由会员分享，可在线阅读，更多相关《基于连通性状态压缩的动态规划问题课件.ppt（36页珍藏版）》请在三一办公上搜索。
1、基于连通性状态压缩的动态规划问题,长沙市雅礼中学陈丹琦,Email : skyfish_,基于连通性状态压缩的动态规划问题长沙市雅礼中学陈丹琦Em,引入,状态压缩动态规划,状态总数为指数级,以集合信息为状态,我的论文针对其中的一类问题进行探讨和研究 状态中需要记录若干个元素之间的连通情况，称为基于连通性状态压缩的动态规划问题,引入 状态压缩动态规划状态总数为指数级以集合信息为状态我的论,【例】Formula 1 (Ural1519),一个 m * n 的棋盘,有的格子存在障碍,求经过所有非障碍格子的哈密顿回路个数,m, n12,【例】Formula 1 (Ural1519)一个 m *,初步分
2、析,问题特点：,数据规模小,m, n12,搜索?,O(mn)!),状态压缩!,棋盘模型,划分阶段：从上到下，从左到右逐格递推,基本概念：插头，轮廓线,初步分析问题特点：数据规模小m, n12搜索?O(mn),基本概念,插头,一个格子某个方向的插头存在表示这个格子在这个方向与相邻格子相连,轮廓线,已决策格子和未决策格子的分界线,轮廓线上方与其相连的有n+1个插头，包括n个下插头和1个右插头,基本概念插头一个格子某个方向的插头存在轮廓线已决策格子和未决,初步分析,问题特点：,数据规模小,棋盘模型,每个插头是否存在,所有的非障碍格子连通,插头之间的连通性!,初步分析问题特点：数据规模小棋盘模型每个插
3、头是否存在所有的非,确立状态,设 f (i, j, S) 表示转移完(i, j) ，轮廓线上从左到右n+1个插头是否存在以及它们的连通性为S的方案总数,如何表示S?,最小表示法,1,2,2,0,1,无插头标记0，有插头标记一个正整数,连通的插头标记相同的数字,从左到右依次标记,f (3,2,1,2,2,0,1),确立状态设 f (i, j, S) 表示转移完(i, j),状态转移,考虑每个格子的状态, 根据上一个状态O(n)扫描计算出新的最小表示状态,对于m = n = 12的无障碍棋盘的极限数据, 扩展状态总数为1333113 , 问题已经基本解决,本题为一个棋盘模型的简单回路问题针对问题的
4、特殊性, 是否有更好的方法呢?,状态转移考虑每个格子的状态, 根据上一个状态O(n)扫描计,进一步分析,每个非障碍格子恰好有2个插头,轮廓线以上由若干条互不相交的路径构成,每条路径的两端对应两个插头,插头两两匹配,从左到右一定不会出现4个插头a, b, c, d，a, c匹配，b, d匹配,插头不会交叉,括号序列!,( ) ( ( ) ) ( ),进一步分析每个非障碍格子恰好有2个插头轮廓线以上由若干条互不,括号表示法,(,(,),),),(,#,(1 1 2 0 2 1 2)3,括号表示法()(0：无插头状态，用 # 表示#(1 1,状态的转移,每次转移相当于轮廓线上当前决策格子的左插头改成
5、下插头，上插头改成右插头的状态,状态的转移每次转移相当于轮廓线上当前决策格子的左插头改成下插,Case 1,没有上插头和左插头，有下插头和右插头，相当于构成一个新的连通块,) 插头,( 插头,转移时间：O(1),Case 1没有上插头和左插头，有下插头和右插头，相当于构成,Case 2,有上插头和左插头，这种情况下相当于合并两个连通分量,预处理每个状态每的括号所匹配的括号,转移时间: O(1),( 插头,(插头,( 插头,Case 2.1 上插头和左插头均为(插头,Case 2有上插头和左插头，这种情况下相当于合并两个连通分,Case 2,有上插头和左插头,转移时间：O(1),( 插头,)插头
6、,Case 2.2 左插头为)插头，上插头为(插头,Case 2有上插头和左插头转移时间：O(1)(#)()(#,Case 2,有上插头和左插头,( 插头,)插头,路径的两端连接起来形成回路,Case 2.3 左插头为(插头，上插头为)插头,Case 2有上插头和左插头 ( 插头)插头路径的两端连接起,Case 3,上插头和左插头恰好有一个，这种情况相当于延续原来的连通分量,) 插头,)插头,无插头,转移时间：O(1),Case 3上插头和左插头恰好有一个，这种情况相当于延续原来,实验比较,建议使用2k进制，位运算效率高,实验比较测试数据最小表示最小表示括号表示括号表示m = n,拓展,如果求
7、经过所有非障碍格子的哈密顿路径的个数呢?,独立插头,0 无插头状态,1 左括号插头,2 右括号插头,3 独立插头,3进制4进制,拓展如果求经过所有非障碍格子的哈密顿路径的个数呢?独立插头0,如果一个连通块只有1个插头或大于2个插头呢?,广义的括号匹配,括号表示法需要满足一个连通块内恰好有2个插头,特殊性,对于一个大于2个插头的连通块 最左边的插头标记为 ( 最右边的插头标记为 ) 中间的插头标记为 )(,单独为一个连通块的插头标记为 ( ),广义的括号表示法,如果一个连通块只有1个插头或大于2个插头呢?广义的括号匹配括,广义的括号表示法,左括号与右括号匹配对应的插头连通,例: 最小表示法 广义
8、括号表示法,(,(,)(,(,(),),),),普适性,广义的括号表示法左括号与右括号匹配对应的插头连通例: 最小,总结,简单回路,最小表示法,一般性,特殊性,括号表示法,拓展,简单路径,3进制4进制,括号表示法的改进,广义的括号表示法,总结简单回路最小表示法一般性特殊性括号表示法拓展简单路径3进,全文研究内容,一类简单路径问题,一类棋盘染色问题,一类基于非棋盘模型的问题,一类最优性问题的剪枝优化,Rocket Mania (Zju2125),生成树计数 (NOI2007),Black & White(Uva10532),Formula 1(Ural1519)Formula 2(改编自Form
9、ula 1),全文研究内容一类简单路径问题一类棋盘染色问题一类基于非棋盘模,Thank you for listening!,Questions are welcome.,Thank you for listening!Questi,棋盘染色问题,k连通块问题记录轮廓线上n个格子的连通性和染色情况相邻的格子是否相连取决于两个格子的颜色是否相同,棋盘染色问题 k连通块问题,棋盘与非棋盘问题的共通点,存在一个序，在这个序中有边相连的点的距离不超过kk一定是一个比较小的数，以这k个数为轮廓线确立状态Formula 1中点的序即为从左到右，从上到下，k = nNoi2007的生成树计数一题, 序为1
10、. n, 有边相连的点距离不超过5,棋盘与非棋盘问题的共通点存在一个序，在这个序中有边相连的点的,Rocket Mania,一个9 * 6的棋盘, 左边9根火柴, 右边9根火箭每个格子可能为空格,也可能为一段管道,管道有4种：,点燃左边第X根火柴，要求旋转每个管道使得发射的火箭尽可能的多,Rocket Mania 一个9 * 6的棋盘, 左边9根火,Analysis,状态：f ijSFire,剪枝一：如果没有一个插头被火柴点燃，那么这个状态可以舍去,剪枝二：如果一个插头没有被火柴点燃，并且这个插头为一个独立的连通块，那么这个插头为无效插头, 可以设置为无效插头状态,Analysis状态：f i
11、jSFire剪枝,Analysis,状态：f ijSFire,剪枝三：最优性剪枝，对于一个(i, j)选择Fire中包含1最多的状态Best，如果一个状态的所有插头在Best中不仅存在而且都被火柴点燃，那么这个状态就可以舍去,Analysis状态：f ijSFire剪枝,问题的特点,数据规模中某一维或某几维非常小，这是状态压缩的基础,需要满足动态规划的基本性质：最优性原理和无后效性,它与图论模型有着密切的关联，问题本身与连通性有关或者隐含着连通信息,问题的特点数据规模中某一维或某几维非常小，这是状态压缩的基础,哈密顿路径的转移,考虑与独立插头有关的几种转移：,I. 上插头和左插头都不存在,独立
12、插头,一个右插头或下插头成为了路径的一端,哈密顿路径的转移考虑与独立插头有关的几种转移：I. 上插头和,哈密顿路径的转移,考虑与独立插头有关的几种转移：,II. 上插头和左插头都存在,左括号插头,独立插头,独立插头,右括号插头,左括号插头和独立插头连接起来后，左括号插头对应的右括号插头成为了新的独立插头,哈密顿路径的转移考虑与独立插头有关的几种转移：II. 上插头,哈密顿路径的转移,考虑与独立插头有关的几种转移：,III. 上插头和左插头恰好有一个存在,左括号插头,右括号插头,独立插头,左括号插头被“封住”，成为路径的一端，它所对应的右括号插头成为了一个新的独立插头,哈密顿路径的转移考虑与独立
13、插头有关的几种转移：III. 上插,相关试题,Uva10531 Maze StatisticsSRM312 CheapestIslandIPSC2007 Delicious CakeNWERC2004 PipesHnoi2007 ParkPoj1739 Tonys Tour,相关试题Uva10531 Maze Statistics,括号表示法的优势,元素之间相对独立,转移代价低，常数因子小,更加直观，清晰，自然,括号表示法的优势元素之间相对独立转移代价低，常数因子小更加直,参考文献,刘汝佳、黄亮算法艺术与信息学竞赛金恺 Black & White解题报告, 2004年毛子青动态规划算法的优化技巧, 2001年http:/icpcres.ecs.baylor.edu/onlinejudgehttp:/acm.timus.ruhttp:/,参考文献刘汝佳、黄亮算法艺术与信息学竞赛,致谢,感谢CCF给我提供一个与大家交流的平台感谢朱全民老师在我写这篇论文时对我的指导感谢刘汝佳教练对我的指导和启发感谢刘宸亨和金斌同学对我的论文的帮助感谢集训队员郑暾，周冬，余林韵，俞华程，顾研，周梦宇，肖汉骏对我的帮助,致谢感谢CCF给我提供一个与大家交流的平台,
