状态压缩动态规划中的状态与时间

《状态压缩动态规划中的状态与时间》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、状态压缩动态规划中的状态与时间大丰市高级中学韩旭目录：【关键字】【概述】【正文】1.基础知识1.1动态规划的概述····················································11.1.1动态规划的概念··············································11.1.2一些常见术语················································11.1.3和递推的区别··········································

2、······11.1.4一些必要性质················································11.2状态压缩动态规划的使用动机及其特点1.2.1状态压缩动态规划的使用动机································11.2.2状态压缩动态规划的特点·····································21.3位运算的引入及其优化效果1.3.1位运算的引入················································21.3.2位运算的特殊用法及

3、其优化效果······························22.常见的状态压缩类型概述2.1常见集合型的状态压缩2.1.1含义························································22.1.2-11-性能极其特点···············································22.1.3例题························································22.2基于联通性的状态压缩2.2.1含义········

4、················································32.2.2性能极其特点···············································32.2.3例题························································32.3小结3.典型例题的优化及其效果3.1改变状态及其优化效果··············································53.1.1含义························

5、·································53.1.2例题·························································53.2去重消冗及其优化效果··············································83.2.1含义·························································83.2.2例题··················································

6、·······83.3小结【参考文献】【附件】-11-【关键字】动态规划状态压缩去重消冗改变状态降低时耗【概述】随着社会的发展以及社会生产技术的变革，世界也在从工业化转向信息化。与之而来的也就是信息学的快速发展，即其在生产生活中的大范围运用。但是很多的实际问题到目前为止并没有太多十分有效的算法，也就是无法在多项式时间复杂度内得出结果，但却依然需要快速解决，状态压缩的概念也就被引入进来并用以解决特定的一定范围内的问题。然而繁琐的状态压缩方法以及冗余的状态表述依然是制约效率的因素之一。于是去重消冗与改变状态来提高时空效率也就是我们需要做的，通过下面题目的分析，

7、希望能对大家起到抛砖引玉的作用。（ps:基础知识可直接跳过，常见的状态压缩类型举例可以适当跳过）【正文】【第一部分】基础知识1.1.1动态规划的概念：动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。动态规划是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。其往往是针对一种最优化问题。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。1.1.2一些常见术语：阶段，状态，决策1.1.3和递推的区别：决策的存在1.1.4一些必要

8、性质：无后效性：对于状态，如果给定某一阶段的状态，则在这一阶段以后