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

长沙市雅礼中学　陈丹琦 状态压缩动态规划 一个 m * n 的棋盘 问题特点： 插头 问题特点： 无插头标记0，有插头标记一个正整数 考虑每个格子的状态, 根据上一个状态O(n)扫描计算出新的最小表示状态． 每个非障碍格子恰好有2个插头 每次转移相当于轮廓线上当前决策格子的左插头改成下插头，上插头改成右插头的状态． 如果求经过所有非障碍格子的哈密顿路径的个数呢? 括号表示法需要满足一个连通块内恰好有2个插头． 左括号与右括号匹配对应的插头连通 k连通块问题 记录轮廓线上n个格子的连通性和染色情况． 相邻的格子是否相连取决于两个格子的颜色是否相同． 存在一个序，在这个序中有边相连的点的距离不超过k． k一定是一个比较小的数，以这k个数为轮廓线确立状态． Formula 1中点的序即为从左到右，从上到下，k = n． Noi2007的生成树计数一题, 序为1 .. n, 有边相连的点距离不超过5． 一个9 * 6的棋盘, 左边9根火柴, 右边9根火箭．每个格子可能为空格,也可能为一段管道． 状态：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给我提供一个与大家交流的平台 感谢朱全民老师在我写这篇论文时对我的指导 感谢刘汝佳教练对我的指导和启发 感谢刘宸亨和金斌同学对我的论文的帮助 感谢集训队员郑暾，周冬，余林韵，俞华程，顾研，周梦宇，肖汉骏对我的帮助 全文研究内容 一类简单路径问题 一类棋盘染色问题 一类基于非棋盘模型的问题 一类最优性问题的剪枝优化 Rocket Mania (Zju2125) 生成树计数 (NOI2007) Black White(Uva10532) Formula 1(Ural1519) Formula 2(改编自Formula 1) Thank you for listening! Questions are welcome. 棋盘染色问题 棋盘与非棋盘问题的共通点 Rocket Mania 管道有4种： 点燃左边第X根火柴，要求旋转每个管道使得发射的火箭尽可能的多． Analysis 剪枝一：如果没有一个插头被火柴点燃，那么这个状态可以舍去． 剪枝二：如果一个插头没有被火柴点燃，并且这个插头为一个独立的连通块，那么这个插头为无效插头, 可以设置为无效插头状态． Analysis 状态：f [i][j][S][Fire] 剪枝三：最优性剪枝，对于一个(i, j)选择Fire中包含1最多的状态Best，如果一个状态的所有插头在Best中不仅存在而且都被火柴点燃，那么这个状态就可以舍去． 问题的特点 需要满足动态规划的基本性质：最优性原理和无后效性． 它与图论模型有着密切的关联，问题本身与连通性有关或者隐含着连通信息． 哈密顿路径的转移 I. 上插头和左插头都不存在 独立插头 一个右插头或下插头成为了路径的一端． 哈密顿路径的转移 II. 上插头和左插头都存在 左括号插头 独立插头 独立插头 右括号插头 左括号插头和独立插头连接起来后，左括号插头对应的右括号插头成为了新的独立插头． 哈密顿路径的转移 III. 上插头和左插头恰好有一个存在 左括号插头 右括号插头 独立插头 左括号插头被“封住”，成为路径的一端，它所对应的右括号插头成为了一个新的独立插头． 相关试题 括号表示法的优势 元素之间相对独立 转移代价低，常数因子小 更加直观，清晰，自然 参考文献 致谢 各位老师，各位同学，大家好! 我是来自长沙市雅礼中学的陈丹琦，我今天论文演讲的主题是”基于连通性状态压缩的动态规划问题”． 基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题． 状态压缩在信息学竞赛中非常的普遍． 在状态压缩的基础上，有一类问题的状态中必须要记录若干个元素的连通情况，我们称这样的问题为 基于连通性状态压缩的动态规划问题，我的论文针对这类问题的解法及优化进行探讨和研究． 今天我将着重介绍我论文中的一个部分~~~~一类简单路径问题的解法及优化．