基干连通性状态压缩动态规划问题.pptVIP

广义的括号表示法 左括号与右括号匹配对应的插头连通 例: 最小表示法 → 广义括号表示法 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根火柴，要求旋转每个管道使得发射的火箭尽可能的多． 各位老师，各位同学，大家好! 我是来自长沙市雅礼中学的陈丹琦，我今天论文演讲的主题是”基于连通性状态压缩的动态规划问题”． * 基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题． 状态压缩在信息学竞赛中非常的普遍． 在状态压缩的基础上，有一类问题的状态中必须要记录若干个元素的连通情况，我们称这样的问题为 基于连通性状态压缩的动态规划问题，我的论文针对这类问题的解法及优化进行探讨和研究． 今天我将着重介绍我论文中的一个部分~~~~一类简单路径问题的解法及优化． * 我们先来看一个例子： 一个m * n的棋盘 有的格子存在障碍 求经过所有非障碍格子的哈密顿回路个数． 数据范围为m, n = 12． 下面这个图共有2条不同的哈密顿回路． * 首先我们来分析一下问题的特点： 它给我们的第一印象是数据规模很小，考虑使用有哪些信誉好的足球投注网站算法，时间复杂度为O((mn)!)，实在太高了． 对于小规模数据的问题，我们不妨考虑基于状态压缩的动态规划来解决． 本题具有特殊的棋盘模型，很自然地我们可以考虑按从上到下，从左到右的顺序逐格来划分阶段． 我们先来明确两个很基本的概念：插头和轮廓线． * 对于一个4-连通的棋盘模型的问题来说，一个格子最多有上下左右4个插头． 一个格子某个方向的插头存在表示这个格子在这个方向可以与外面相连． 轮廓线是已决策格子和未决策格子的分界线，它随着转移的过程不断变化． 轮廓线上方与其直接相连的有n+1个插头，包括轮廓线上方n个格子的下插头和最后一个决策格子的下插头． 只有这n+1个插头的状态对以后的决策产生直接的影响． * 那么状态中需要记录这n+1个插头的哪些信息呢? 很明显我们必须要记录n+1个插头是否存在，但是仅仅记录插头是否存在是不够的． 题目要求最后所有的非障碍格子连通，而如右图出现了2个回路! 因此我们必须在状态中压缩n+1个插头之间的连通性! * 设f[i][j][S]表示转移完(i,j)后轮廓线上n+1个插头是否存在以及它们之间的连通性为S的方案总数． 那么我们该如何表示S呢? 为了避免一个连通信息有多个状态表示，我们通常使用最小表示法． 最小表示法即从左到右依次给每个未标记的插头标记，连通的插头标记上相同的正数，不存在的插头标记为0． * 状态转移的时候我们只需要考虑每个格子的状态，根据上一个状态与当前的决策计算出当前状态的最小表示． 对于m = n = 12的无障碍棋盘的极限数据，扩展的状态总数为1333113，问题已经基本解决了． 本题为一类简单回路问题，刚刚我们的提到这个解题思路具有一般性， 并没有充分利用简单回路问题的性质，那么针对问题的特殊性，是否可以提出更好的方法呢? * 下面我们来进一步分析简单回路问题的特殊性． 观察这个图，可以发现每个非障碍格子恰好有2个插头，而轮廓线以上是由若干条不相交的路径构成． 图中共有三条不同的路径．每条路径为一个连通块，它的两端恰好对应两个插头． 可以看出，插头是两两匹配的． 此外，不难发现一个性质：轮廓线上从左到右4个插头a, b, c, d，一定不可