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

基于连通性状态压缩的动态规划问题 长沙市雅礼中学 陈丹琦 【摘要】 基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数 级的特殊的动态规划问题．在状态压缩的基础上，有一类问题的状态中必须要记 录若干个元素的连通情况，我们称这样的问题为基于连通性状态压缩的动态规划 问题，本文着重对这类问题的解法及优化进行探讨和研究． 本文主要从动态规划的几个步骤——划分阶段，确立状态，状态转移以及程 序实现来介绍这类问题的一般解法，会特别针对到目前为止信息学竞赛中涌现出 来的几类题型的解法作一个探讨．结合例题，本文还会介绍作者在减少状态总数 和降低转移开销两个方面对这类问题优化的一些心得． 【关键词】 状态压缩 连通性 括号表示法 轮廓线 插头 棋盘模型 IOI2008 中国国家集训队论文 长沙市雅礼中学 陈丹琦 【目录】 【序言】3 【正文】5 一. 问题的一般解法5 【例1】Formula 1 5 问题描述5 算法分析5 小结 11 二. 一类简单路径问题 11 【例2 】Formula 2 14 问题描述 14 算法分析 15 小结 16 三. 一类棋盘染色问题 16 【例3 】Black White 16 问题描述 17 算法分析 17 小结 19 四. 一类基于非棋盘模型的问题 19 【例4 】生成树计数 19 问题描述 19 算法分析 19 小结20 五. 一类最优性问题的剪枝技巧20 【例5】Rocket Mania 20 问题描述21 算法分析21 小结23 六.总结23 【参考文献】23 【感谢】24 【附录】24 第 2 页 IOI2008 中国国家集训队论文 长沙市雅礼中学 陈丹琦 【序言】 先看一个非常经典的问题——旅行商问题(即TSP 问题，Traveling Salesman Problem) ：一个n(≤15)个点的带权完全图，求权和最小的经过每个点恰好一次的 封闭回路．这个问题已经被证明是NP 完全问题，那么对于这样一类无多项式算 法的问题，有哪些信誉好的足球投注网站算法是不是解决问题的唯一途径呢? 答案是否定的．不难发现任 何时候我们只需要知道哪些点已经被遍历过而遍历点的具体顺序对以后的决策 是没有影响的，因此不妨以当前所在的位置i，遍历过的点的集合S 为状态作动 态规划： ，其中ji ，i，j in S ． f (i , S ) m i nf{ j ( S, i { } )d i s t (j i, ) } n 2 动态规划的时间复杂度为O(2 * n ) ，虽然为指数级算法，但是对于n = 15 的数据规模来说已经比朴素的O(n!) 的有哪些信誉好的足球投注网站算法高效很多了．我们通常把这样一 类以