论文部分内容阅读
二十世纪五十年代,美国数学家理查德贝尔曼(R.E.Bellman)根据一类多阶段决策优化问题的特点,提出了最优化原理即无论问题的初始状态如何,问题以后的决策相对于初始状态都是最优策略,最优化原理是动态规划的基础。动态规划的基本思想就是将待求解的问题划分成若干子问题,通过将子问题逐一解决从而解决整个问题。动态规划思想可以有效地解决一类多阶段决策优化问题。动态规划是一种算法设计思想。在过去的五十多年里,动态规划在各个领域中得到了广泛的应用。例如最短路径、项目群资源优化、资产的投资决策、字符串匹配、设备更新、地图导航、水资源的调度分配等问题。在适用的情况下,动态规划可以高效率地解决一类动态决策问题,因此,无论是在理论还是在实践上对动态规划算法的研究都具有重要的意义。本文主要研究了动态规划的理论基础,及其时间效率优化等几个方面的内容。具体包括:(1)从动态规划算法的基础理论入手,概述了动态规划中的术语,如阶段、状态、多阶段决策、指标函数、状态的无后效、重叠子结构等一些专有名词,并归纳了动态规划中常见的子问题模型。探讨了动态规划与常见算法的比较,通过与其它算法的比较凸显了动态规划在解决实际问题时空间消耗大,全局最优以及时间效率高等特点。(2)探究动态规划在时间效率上的优化。现有的研究一般针对具体问题的特点设计优化措施,当问题不同时,相应的优化措施就失去作用。论文从影响动态规划算法时间复杂度的因素出发,从影响其时间效率的三大方面:问题中需要计算的状态个数、状态转移时涉及的状态数、状态转移的时间进行优化。优化时实现三者的平衡,从而在整体上提升算法的时间效率,使其能够适用于数据规模更大的问题。(3)为了验证动态规划算法时间效率优化措施的有效性,将动态规划方法运用于经典的组合优化难题——背包问题。首先分析了解决0/1背包问题和完全背包问题的经典动态规划算法;接着利用动态规划的优化措施改进原有的动态规划算法;然后通过实验得出不同动态规划算法在解决背包问题时的时间效率。实验结果表明本文提出的改进算法在一定程度上降低了时间复杂度。