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

基于连通性状态压缩的动态规划问题长沙市雅礼中学 陈丹琦【摘要】基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题在状态压缩的基础上，有一类问题的状态中必须要记录若干个元素的连通情况，我们称这样的问题为基于连通性状态压缩的动态规划问题，本文着重对这类问题的解法及优化进行探讨和研究 本文主要从动态规划的几个步骤划分阶段，确立状态，状态转移以及程序实现来介绍这类问题的一般解法，会特别针对到目前为止信息学竞赛中涌现出来的几类题型的解法作一个探讨结合例题，本文还会介绍作者在减少状态总数和降低转移开销两个方面对这类问题优化的一些心得【关键词】 状态压缩连通性括号表示法 轮廓线插头棋盘模型 【目录】【序言】3【正文】5一. 问题的一般解法5【例1】Formula 15问题描述5算法分析5小结11二. 一类简单路径问题12【例2】Formula 215问题描述15算法分析15小结