2008-陈丹琦-基于连通性状态压缩的动态规划问题_Cdq

基于连通性状态压缩的动态规划问题长沙市雅礼中学陈丹琦Email:[e-mail]引入状态压缩动态规划状态总数为指数级以集合信息为状态•我的论文针对其中的一类问题进行探讨和研究——状态中需要记录若干个元素之间的连通情况，称为基于连通性状态压缩的动态规划问题【例】Formula1(Ural1519)•一个m*n的棋盘•有的格子存在障碍•求经过所有非障碍格子的哈密顿回路个数初步分析•问题特点：•数据规模小m,n≤12搜索?O((mn)!)状态压缩!√•棋盘模型划分阶段：从上到下，从左到右逐格递推基本概念：插头，轮廓线基本概念•插头一个格子某个方向的插头存在表示这个格子在这个方向与相邻格子相连．•轮廓线已决策格子和未决策格子的分界线轮廓线上方与其相连的有n+1个插头，包括n个下插头和1个右插头．初步分析•问题特点：•数据规模小•棋盘模型每个插头是否存在•所有的非障碍格子连通插头之间的连通性!确立状态•设f(i,j,S)表示转移完(i,j)，轮廓线上从左到右n+1个插头是否存在以及它们的连通性为S的方案总数．•如何表示S?•最小表示法12201•无插头标记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匹配．dcab插头不会交叉括号序列!()(())()括号表示法(()))(0：无插头状态，用#表示1：左括号插头，用(表示2：右括号插头，用)表示3进制#(1120212)3状态的转移•每次转移相当于轮廓线上当前决策格子的左插头改成下插头，上插头改成右插头的状态．Case1没有上插头和左插头，有下插头和右插头，相当于构成一个新的连通块．)插头(插头(###)(()#)转移时间：O(1)Case2有上插头和左插头，这种情况下相当于合并两个连通分量预处理每个状态每的括号所匹配的括号转移时间:O(1)(插头(插头#(())###()(插头Case2.1上插头和左插头均为(插头Case2有上插头和左插头转移时间：O(1)(#)()(###)(插头)插头Case2.2左插头为)插头，上插头为(插头Case2有上插头和左插头(插头)插头路径的两端连接起来形成回路Case2.3左插头为(插头，上插头为)插头Case3上插头和左插头恰好有一个，这种情况相当于延续原来的连通分量)插头)插头无插头转移时间：O(1)(()#)(()#)实验比较测试数据最小表示7Based最小表示8Based括号表示3Based括号表示4Basedm=n=10无障碍31ms15ms0ms0msm=n=11(1,1)为障碍187ms109ms46ms31msm=n=12无障碍873ms499ms265ms140ms建议使用2k进制，位运算效率高拓展•如果求经过所有非障碍格子的哈密顿路径的个数呢?独立插头•0→无插头状态•1→左括号插头•2→右括号插头•3→独立插头3进制→4进制•如果一个连通块只有1个插头或大于2个插头呢?广义的括号匹配•括号表示法需要满足一个连通块内恰好有2个插头．•对于一个大于2个插头的连通块最左边的插头标记为(最右边的插头标记为)中间的插头标记为)(•单独为一个连通块的插头标记为()广义的括号表示法广义的括号表示法•左括号与右括号匹配对应的插头连通•例:最小表示法→广义括号表示法12234321(()((())))总结简单回路最小表示法括号表示法拓展简单路径3进制→4进制括号表示法的改进广义的括号表示法全文研究内容•一类简单路径问题•一类棋盘染色问题•一类基于非棋盘模型的问题•一类最优性问题的剪枝优化RocketMania(Zju2125)生成树计数(NOI2007)Black&White(Uva10532)Formula1(Ural1519)Formula2(改编自Formula1)Thankyouforlistening!Questionsarewelcome.