【作者】 李强；

【导师】 蓝雯飞；

【作者基本信息】 中南民族大学 ， 计算机应用技术， 2015， 硕士

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

【Abstract】 In the 1950 s, American mathematician R.E.Bellman puts forward the famous optimization, the optimized principle which had laid a solid foundation for Dynamic Programming, the basic thought of dynamic programming to solve the optimization problem is to decompose the problem into some sub problems,So the original problem can transform into some sub problems, first solve the sub problems, and then solve the original problem by combining sub problem solutions. Dynamic programming is a powerful tool to solve the problem of multistage decision.Dynamic programming is an important thinking in program design. In the past 50 years,Dynamic programming has been widely used in various fields to solve problems of various types.Such as the shortest path problem, project group of resource optimization, capital investment decisions, string matching, equipment update, map navigation, scheduling of water resources allocation problem and so on.most of the case, the dynamic.programming can solve the dynamic decision problems efficiently.So the study of the dynamic programming algorithm both in theory and in practice has important meaning.This article mainly state the basis theoretical of dynamic planning, time efficiency optimization to improve the aspects of content.Specific as below.Terminology used in dynamic programming are introduced, such as phase, status, multistage decision-making, index function, the state of the nature of optimal substructure and no aftereffect, overlapping substructure, such as some proper nouns,and summarizes the common child problems in dynamic programming mode,acrossing the basic theory of dynamic programming algorithm.Compared with common algorithm, dynamic programming is discussed by comparison with other algorithms to get to know the dynamic programming of high space consumption, global optimization and high efficiency, etc.To explore the optimization of dynamic programming in time efficiency. Existing research general design the optimization measures for the characteristics of the specific,when the problem is different, the corresponding optimization measures will not work. Due to the dynamic programming method tend to exist a certain amount of time redundancy after the simple design. This paper analyzed the time complexity of the dynamic programming method, will affect its time efficiency from three aspects:need to compute the number of the state in the Problems, the number of involved in the transfer of state, optimization of the state transition time. So on the whole, it can solve the problem of larger data size by promoting the algorithm’s time efficiency.In order to verify the effectiveness of the dynamic programming algorithm of time efficiency optimization measures, apply dynamic programming in knapsack problem, a classic optimization problem.First, this paper researches a kind of conventional to solve 0/1 knapsack problem and the multiple knapsack problem of the dynamic programming algorithm,Then using dynamic programming optimization measures to improve the original dynamic programming algorithm.In dealing with the same scale and different algorithm through the experiment data set time efficiency.更多还原