动态规划算法时间效率优化策略-研究

《动态规划算法时间效率优化策略-研究》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、动态规划算法思想及其在时间效率上的优化3.4.2合理组织已求解的状态.................................213.4.3运用贪心思想优化动态规划算法.........................233.5状态转移时间的优化.........................................253.6本章小结...................................................26第4章动态规划优化措施在背包问题中的应用研究.....................274.10/1背包问题..

2、.............................................274.1.1问题描述.............................................274.1.2问题的动态规划算法...................................274.1.3动态规划算法改进.....................................294.1.4实验与分析...........................................324.2完全背包问题.................

3、..............................364.2.1问题描述.............................................364.2.2问题的动态规划算法设计...............................364.2.3动态规划算法改进.....................................374.2.4实验与分析...........................................404.3本章小结....................................

4、...............45第5章总结与展望.................................................465.1总结.......................................................465.2展望.......................................................46参考文献..........................................................48致谢.....................

5、.......................................51附录A攻读学位期间发表的学术论文.................................52万方数据中南民族大学硕士学位论文摘要二十世纪五十年代，美国数学家理查德贝尔曼（R.E.Bellman）根据一类多阶段决策优化问题的特点，提出了最优化原理即无论问题的初始状态如何，问题以后的决策相对于初始状态都是最优策略，最优化原理是动态规划的基础。动态规划的基本思想就是将待求解的问题划分成若干子问题，通过将子问题逐一解决从而解决整个问题。动态规划思想可以有效地解决一类多阶段决策优化问题。

6、动态规划是一种算法设计思想。在过去的五十多年里，动态规划在各个领域中得到了广泛的应用。例如最短路径、项目群资源优化、资产的投资决策、字符串匹配、设备更新、地图导航、水资源的调度分配等问题。在适用的情况下，动态规划可以高效率地解决一类动态决策问题，因此，无论是在理论还是在实践上对动态规划算法的研究都具有重要的意义。本文主要研究了动态规划的理论基础，及其时间效率优化等几个方面的内容。具体包括：（1）从动态规划算法的基础理论入手，概述了动态规划中的术语，如阶段、状态、多阶段决策、指标函数、状态的无后效、重叠子结构等一些专有名词，并归纳了动态规划中常见的子问题模型。探讨了动态

7、规划与常见算法的比较，通过与其它算法的比较凸显了动态规划在解决实际问题时空间消耗大，全局最优以及时间效率高等特点。（2）探究动态规划在时间效率上的优化。现有的研究一般针对具体问题的特点设计优化措施，当问题不同时，相应的优化措施就失去作用。论文从影响动态规划算法时间复杂度的因素出发，从影响其时间效率的三大方面：问题中需要计算的状态个数、状态转移时涉及的状态数、状态转移的时间进行优化。优化时实现三者的平衡，从而在整体上提升算法的时间效率，使其能够适用于数据规模更大的问题。（3）为了验证动态规划算法时间效率优化措施的有效性，将动态规划方法运用于经典的组合优