基于连通性状态压缩的动态规划问题

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