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

基于连通性状态压缩的动态规划问题 长沙市雅礼中学　陈丹琦 引入 状态压缩动态规划 【例】Formula 1 (Ural1519) 一个 m * n 的棋盘 初步分析 问题特点： 基本概念 插头 初步分析 问题特点： 确立状态 无插头标记0，有插头标记一个正整数 状态转移 考虑每个格子的状态, 根据上一个状态O(n)扫描计算出新的最小表示状态． 进一步分析 每个非障碍格子恰好有2个插头 括号表示法 状态的转移 每次转移相当于轮廓线上当前决策格子的左插头改成下插头，上插头改成右插头的状态． Case 1 Case 2 Case 2 Case 2 Case 3 实验比较 拓展 如果求经过所有非障碍格子的哈密顿路径的个数呢? 广义的括号匹配 括号表示法需要满足一个连通块内恰好有2个插头． 广义的括号表示法 左括号与右括号匹配对应的插头连通 总结 全文研究内容 棋盘染色问题 k连通块问题 记录轮廓线上n个格子的连通性和染色情况． 相邻的格子是否相连取决于两个格子的颜色是否相同． 棋盘与非棋盘问题的共通点 存在一个序，在这个序中有边相连的点的距离不超过k． k一定是一个比较小的数，以这k个数为轮廓线确立状态． Formula 1中点的序即为从左到右，从上到下，k = n． Noi2007的生成树计数一题, 序为1 .. n, 有边相连的点距离不超过5． Rocket Mania 一个9 * 6的棋盘, 左边9根火柴, 右边9根火箭．每个格子可能为空格,也可能为一段管道． Analysis 状态：f [i][j][S][Fire] Analysis 状态：f [i][j][S][Fire] 问题的特点 数据规模中某一维或某几维非常小，这是状态压缩的基础． 哈密顿路径的转移 考虑与独立插头有关的几种转移： 哈密顿路径的转移 考虑与独立插头有关的几种转移： 哈密顿路径的转移 考虑与独立插头有关的几种转移： 相关试题 Uva10531 Maze Statistics SRM312 CheapestIsland IPSC2007 Delicious Cake NWERC2004 Pipes Hnoi2007 Park Poj1739 Tony’s Tour … 括号表示法的优势 参考文献 刘汝佳、黄亮《算法艺术与信息学竞赛》 金恺 《Black White》解题报告, 2004年 毛子青《动态规划算法的优化技巧》, 2001年　 /onlinejudge http://acm.timus.ru 致谢 感谢CCF给我提供一个与大家交流的平台 感谢朱全民老师在我写这篇论文时对我的指导 感谢刘汝佳教练对我的指导和启发 感谢刘宸亨和金斌同学对我的论文的帮助 感谢集训队员郑暾，周冬，余林韵，俞华程，顾研，周梦宇，肖汉骏对我的帮助 II. 上插头和左插头都存在 左括号插头 独立插头 独立插头 右括号插头 左括号插头和独立插头连接起来后，左括号插头对应的右括号插头成为了新的独立插头． III. 上插头和左插头恰好有一个存在 左括号插头 右括号插头 独立插头 左括号插头被“封住”，成为路径的一端，它所对应的右括号插头成为了一个新的独立插头． 元素之间相对独立 转移代价低，常数因子小 更加直观，清晰，自然 * * Email : skyfish_cdq@163.com 状态总数为指数级 以集合信息为状态 我的论文针对其中的一类问题进行探讨和研究—— 状态中需要记录若干个元素之间的连通情况，称为基于连通性状态压缩的动态规划问题 有的格子存在障碍 求经过所有非障碍格子的哈密顿回路个数 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 连通的插头标记相同的数字 从左到右依次标记 f (3,2,{1,2,2,0,1}) 对于m = n = 12的无障碍棋盘的极限数据, 扩展状态总数为1333113 , 问题已经基本解决． 本题为一个棋盘模型的简单回路问题． 　针对问题的特殊性, 是否有更好的方法呢? 轮廓线以上由若干条互不相交的路径构成 每条路径的两端对应两个插头 插头两两匹配 从左到