动态规划算法应用及其在时间效率上的优化

【作者】 吴涛；

【导师】 孙兴华；

【作者基本信息】 南京理工大学 ， 计算机应用技术， 2008， 硕士

【摘要】 算法设计是软件设计的灵魂内容,动态规划作为相对成熟的算法设计技术,不断地被运用到工农业生产、经济、军事、工程技术等很多方面,显示出其高效、实用的性能和宽阔的应用前景。本文对动态规划所涉及的诸多方面进行了深入的研究,通过大量的程序设计实例阐述了包括动态规划的理论基础、实际应用、优化方法在内的几大方面的问题。具体包括:一、从动态规划的本质入手,介绍了多阶段决策问题、阶段与状态、决策与策略、最优化原理与无后效性、最优指标函数和规划方程等一些专有名词的定义;利用一些常见的实例阐述了动态规划在设计与实现时的多样性、模式性和技巧性等特点;通过与一些常见算法的比较,讲解了动态规划与这些算法的区别和联系,突出了使用动态规划时的最优化、高效率和高消费等特性。二、从三个具体问题的解决过程中可以看出,动态规划是必不可少的有力工具。通过问题描述、样例分析、算法设计、问题实现、测试结果等几个步骤详细讨论了动态规划在应用中的实现过程和思考方法,体现出在应用中相应的实践指导意义。三、鉴于动态规划在简单设计后还存在很大的时间冗余,从构成其时间复杂度的三个方面:状态总数、每个状态转移的状态数、每次状态转移的时间进行优化,使得动态规划在时间效率上得到了进一步的提升,以期面对并解决更大数据规模的问题。不仅给出了优化的理论依据和具体方法,而且还给出了五个引用实例在优化前后的实验运行对比结果。最后,总结全文,分析了动态规划的应用和优化在面对不同问题时需要进一步完善的地方,并指出了今后工作的研究方向。更多还原

【Abstract】 The design of the algorithm is the main content of software design. As a mature technique of algorithm design, dynamic programming is widely used in industry, agriculture, economy, military, engineering and some other fields, which indicates that it is efficient and practical and it has a bright future. The dissertation deals with many aspects of dynamic programming. By using many examples of programming, it gives a detailed explanation of dynamic programming’s rationale, application and optimization method. The details listed as follows:First, through the introduction of its essence, it introduces the definition of some terms such as multistage decision-making, stage and state, decision-making and strategy, optimality principle, non-aftereffect, optimal target function, programming equation and so on. By using some common examples, it gives a full description of the diversity, the pattern and the artifice of dynamic programming in designing and application. By comparing with some common algorithms, it explains their differences and relationships and emphasizes its characteristics--- optimized, efficient, and consumptive.Second, through solving three problems, we can find dynamic programming is a necessity. With the help of the following steps, like problem describing, sample analyzing, algorithm designing, problem solving and result testing, it gives a full explanation of the implementation process and thinking methods of dynamic programming in application. It also shows that dynamic programming is very useful and helpful in application.Third, There is a time redundancy after dynamic programming is used to design algorithm simply, so I try to optimize the dynamic programming in three aspects of time complexity---total quantities of state, state quantities of every state transition and time of every state transition, which helps it improve a lot in time efficiency and makes it possible for the newly-- designed algorithm to solve the problem with large-sized data. Not only does it provide the theoretical basis and methods of optimization, but also it provides the comparison results of five experiments before it optimized and after it optimized.In conclusion, the dissertation not only analyzes the improvements of the application and optimization of dynamic programming in solving other problems, but also points out the research direction of the work in the future.更多还原