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

1、Email : skyfish_引入状态总数为状态总数为指数级指数级以集合信息为状态以集合信息为状态 我的论文针对其中的一类问题进行探讨和我的论文针对其中的一类问题进行探讨和研究研究 状态中需要记录若干个元素之间状态中需要记录若干个元素之间的的连通连通情况，称为情况，称为【例】Formula 1 (Ural1519) 一个一个 m * n 的棋盘的棋盘 有的格子存在障碍有的格子存在障碍 求经过所有非障碍格子的哈密顿回路个数求经过所有非障碍格子的哈密顿回路个数m, n12初步分析 问题特点：问题特点： 数据规模小数据规模小m, n12搜索?O(mn)!)状态压缩! 棋盘模型棋盘模型划分阶段：从上

2、到下，从左到右逐格递推划分阶段：从上到下，从左到右逐格递推基本概念：插头，轮廓线基本概念：插头，轮廓线基本概念 插头一个格子某个方向的插头存在一个格子某个方向的插头存在表示这个格子在这个方向与相表示这个格子在这个方向与相邻格子相连邻格子相连 轮廓线已决策格子和未决策格已决策格子和未决策格子的分界线子的分界线轮廓线上方与其相连的轮廓线上方与其相连的有有n+1个插头，包括个插头，包括n个个下插头和下插头和1个右插头个右插头初步分析 问题特点：问题特点： 数据规模小数据规模小 棋盘模型棋盘模型每个插头是否存在每个插头是否存在 所有的非障碍格子连通所有的非障碍格子连通插头之间的连通性插头之间的连通性!

3、确立状态 设设 f (i, j, S) 表示转移完表示转移完(i, j) ，轮廓线上从左到轮廓线上从左到右右n+1个插头是否存在以及它们的连通性为个插头是否存在以及它们的连通性为S的方案总数的方案总数 如何表示如何表示S? 最小表示法12201 无插头标记无插头标记0 0，有插头标记一个正整数，有插头标记一个正整数 连通的插头标记相同的数字连通的插头标记相同的数字 从左到右依次标记从左到右依次标记f (3,2,1,2,2,0,1)状态转移 考虑每个格子的状态考虑每个格子的状态, 根据上一个状态根据上一个状态O(n)扫扫描计算出新的最小表示状态描计算出新的最小表示状态 对于对于m = n = 1

4、2的无障碍棋盘的极限数据的无障碍棋盘的极限数据, 扩展扩展状态总数为状态总数为1333113 , 问题已经基本解决问题已经基本解决 本题为一个棋盘模型的本题为一个棋盘模型的简单回路简单回路问题问题针对问题的特殊性针对问题的特殊性, 是否有更好的方法呢是否有更好的方法呢?进一步分析 每个非障碍格子恰好有每个非障碍格子恰好有2个插头个插头 轮廓线以上由若干条互不相交的路径构成轮廓线以上由若干条互不相交的路径构成 每条路径的两端对应两个插头每条路径的两端对应两个插头插头两两匹配 从左到右一定不会出现从左到右一定不会出现4个插头个插头a, b, c, d，a, c匹配，匹配，b, d匹配匹配dcab插

5、头不会交叉 括号表示法( () (0：无插头状态，用：无插头状态，用 # 表示表示1：左括号插头，用：左括号插头，用 ( 表示表示 2：右括号插头，用：右括号插头，用 ) 表示表示3进制进制#(1 1 2 0 2 1 2)3状态的转移 每次转移相当于轮廓线上当前决策格子的左插每次转移相当于轮廓线上当前决策格子的左插头改成下插头，上插头改成右插头的状态头改成下插头，上插头改成右插头的状态Case 1没有上插头和左插头，有下插头和右插头，没有上插头和左插头，有下插头和右插头，相当于相当于构成一个新的连通块构成一个新的连通块 ) 插头插头 ( 插头插头转移时间：转移时间：O(1)Case 2有上插头

6、和左插头，这种情况下相当于有上插头和左插头，这种情况下相当于合并合并两个连通分量两个连通分量预处理每个状态每的预处理每个状态每的括号所匹配的括号括号所匹配的括号转移时间转移时间: : O(1) ( 插头插头(插头插头 ( 插头插头Case 2.1 上插头和左插头均为上插头和左插头均为( (插头插头Case 2有上插头和左插头有上插头和左插头转移时间：转移时间：O(1) ( 插头插头)插头插头Case 2.2 左插头为左插头为) )插头，上插头为插头，上插头为( (插头插头Case 2有上插头和左插头有上插头和左插头 ( 插头插头)插头插头路径的两端连接路径的两端连接起来形成回路起来形成回路Ca

7、se 2.3 左插头为左插头为( (插头，上插头为插头，上插头为) )插头插头Case 3上上插头和左插头恰好有一个，这种情况相当插头和左插头恰好有一个，这种情况相当于于延续原来的连通分量延续原来的连通分量 ) 插头插头)插头插头无插头无插头转移时间：转移时间：O(1)实验比较测试数据 最小表示 7Based最小表示 8Based括号表示 3Based括号表示 4Basedm = n = 10无障碍31ms15ms0ms0msm = n = 11(1,1)为障碍187ms109ms46ms31msm = n = 12无障碍873ms499ms265ms140ms建议使用建议使用2k进制，位运算

8、效率高进制，位运算效率高拓展 如果求经过所有非障碍格子的如果求经过所有非障碍格子的哈密顿哈密顿路径路径的个数呢的个数呢?独立插头独立插头 0 无插头状态无插头状态 1 左括号插头左括号插头 2 右括号插头右括号插头 3 独立插头独立插头3进制进制4进制进制 如果一个连通块只有如果一个连通块只有1个插头或大于个插头或大于2个插头呢个插头呢?广义的括号匹配 括号表示法需要满足一个括号表示法需要满足一个连通块内恰好有连通块内恰好有2个插头个插头特殊性 对于一个对于一个大于大于2个插头的个插头的连通块连通块 最左边的插头标记为最左边的插头标记为 ( 最右边的插头标记为最右边的插头标记为 ) 中间的插头

9、标记为中间的插头标记为 )( 单独为一个连通块的插头标记为单独为一个连通块的插头标记为 ( )广义的括号表示法 左括号与右括号匹配对应的插头连通左括号与右括号匹配对应的插头连通 例例: 最小表示法最小表示法 广义括号表示法广义括号表示法12234321()()普适性总结简单回路简单回路最小表示法最小表示法一般性一般性特殊性特殊性括号表示法括号表示法拓拓展展简单路径简单路径3 3进制进制4 4进制进制括号表示法的改进括号表示法的改进广广义义的的括括号号表表示示法法全文研究内容 一类简单路径问题一类简单路径问题 一类棋盘染色问题一类棋盘染色问题 一类基于非棋盘模型的问题一类基于非棋盘模型的问题 一

10、类最优性问题的剪枝优化一类最优性问题的剪枝优化Rocket Mania (Zju2125)生成树计数 (NOI2007)Black & White(Uva10532)Formula 1(Ural1519)Formula 2(改编自Formula 1)Thank you for listening!Questions are welcome. 棋盘染色问题 k连通块问题连通块问题 记录轮廓线上记录轮廓线上n个格子的连通性和染色情个格子的连通性和染色情况况 相邻的格子是否相连取决于两个格子的相邻的格子是否相连取决于两个格子的颜色是否相同颜色是否相同棋盘与非棋盘问题的共通点 存在一个序，在这

11、个序中有边相连的点的距离存在一个序，在这个序中有边相连的点的距离不超过不超过k k一定是一个比较小的数，以这一定是一个比较小的数，以这k个数为轮廓线个数为轮廓线确立状态确立状态 Formula 1中点的序即为从左到右，从上到下，中点的序即为从左到右，从上到下，k = n Noi2007的生成树计数一题的生成树计数一题, 序为序为1 . n, 有边相有边相连的点距离不超过连的点距离不超过5Rocket Mania 一个一个9 * 6的棋盘的棋盘, 左边左边9根火柴根火柴, 右边右边9根火根火箭每个格子可能为空格箭每个格子可能为空格,也可能为一段管道也可能为一段管道 管道有管道有4种：种： 点燃左

12、边第点燃左边第X根火根火柴，要求旋转每个柴，要求旋转每个管道使得发射的火管道使得发射的火箭尽可能的多箭尽可能的多Analysis 状态状态：f ijSFire 剪枝一：如果剪枝一：如果没有一个插头被火柴点燃，没有一个插头被火柴点燃，那么这个状态可以舍去那么这个状态可以舍去 剪枝二：如果一个插头没有被火柴点燃，剪枝二：如果一个插头没有被火柴点燃，并且这个插头为一个独立的连通块，那并且这个插头为一个独立的连通块，那么这个插头为无效插头么这个插头为无效插头, 可以设置为无可以设置为无效插头状态效插头状态Analysis 状态状态：f ijSFire 剪枝三：最优性剪枝，对于一个剪枝三：最优性剪枝，对

13、于一个(i, j)选选择择Fire中包含中包含1最多的状态最多的状态Best，如果一如果一个状态的所有插头在个状态的所有插头在Best中不仅存在而中不仅存在而且都被火柴点燃，那么这个状态就可以且都被火柴点燃，那么这个状态就可以舍去舍去问题的特点 数据规模中某一维或某几维非常小，这是状数据规模中某一维或某几维非常小，这是状态压缩的基础态压缩的基础 需要满足动态规划的基本性质：最优性原理需要满足动态规划的基本性质：最优性原理和无后效性和无后效性 它与图论模型有着密切的关联，问题本身与它与图论模型有着密切的关联，问题本身与连通性有关或者隐含着连通信息连通性有关或者隐含着连通信息哈密顿路径的转移 考虑

14、与独立插头有关的几种转移：考虑与独立插头有关的几种转移：I. 上插头和左插头都不存在上插头和左插头都不存在独立插头独立插头一个右插头或下插头成为了路径的一端一个右插头或下插头成为了路径的一端哈密顿路径的转移 考虑与独立插头有关的几种转移：考虑与独立插头有关的几种转移：II. 上插头和左插头都存在上插头和左插头都存在左括号插头左括号插头独立插头独立插头独立插头独立插头右括号插头右括号插头左括号插头和独立插头连接起来后，左括号插左括号插头和独立插头连接起来后，左括号插头对应的右括号插头成为了新的独立插头头对应的右括号插头成为了新的独立插头哈密顿路径的转移 考虑与独立插头有关的几种转移：考虑与独立插

15、头有关的几种转移：III. 上插头和左插头恰好有一个存在上插头和左插头恰好有一个存在左括号插头左括号插头右括号插头右括号插头独立插头独立插头左括号插头被左括号插头被“封住封住”，成为路径的一端，它所，成为路径的一端，它所对应的右括号插头成为了一个新的独立插头对应的右括号插头成为了一个新的独立插头相关试题 Uva10531 Maze Statistics SRM312 CheapestIsland IPSC2007 Delicious Cake NWERC2004 Pipes Hnoi2007 Park Poj1739 Tonys Tour 括号表示法的优势 元素之间相对独立元素之间相对独立 转移代价低，常数因子小转移代价低，常数因子小 更加直观，清晰，自然更加直观，清晰，自然参考文献刘汝佳、黄亮算法艺术与信息学竞赛金恺 Black & White解题报告, 2004年毛子青动态规划算法的优化技巧, 2001年/onl