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

论文摘要

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

论文目录

• 摘要
• Abstract
• 引言
• 1 绪论
• 1.1 动态规划的本质
• 1.1.1 多阶段决策问题
• 1.1.2 阶段与状态
• 1.1.3 决策和策略
• 1.1.4 最优化原理与无后效性
• 1.1.5 最优指标函数和规划方程
• 1.2 动态规划的设计与实现
• 1.2.1 动态规划的多样性
• 1.2.2 动态规划的模式性
• 1.2.3 动态规划的技巧性
• 1.3 动态规划与一些算法的比较
• 1.3.1 动态规划与分治
• 1.3.2 动态规划与递推
• 1.3.3 动态规划与搜索
• 1.4 本章小结
• 2 动态规划算法在三个具体问题中的应用
• 2.1 “过河”问题
• 2.1.1 问题描述
• 2.1.2 样例分析
• 2.1.3 算法分析
• 2.1.4 问题实现
• 2.1.5 测试结果
• 2.2 “金明的预算方案”问题
• 2.2.1 问题描述
• 2.2.2 样例分析
• 2.2.3 算法分析
• 2.2.4 问题实现
• 2.2.5 测试结果
• 2.3 “矩阵取数游戏”问题
• 2.3.1 问题描述
• 2.3.2 样例分析
• 2.3.3 算法分析
• 2.3.4 问题实现
• 2.3.5 测试结果
• 3 动态规划算法在时间效率上的优化
• 3.1 动态规划在时间效率上优化的必要性
• 3.2 动态规划时间复杂度的分析
• 3.3 减少状态总数
• 3.3.1 选择适当的规划方向
• 3.3.2 改进状态表示
• 3.4 减少每个状态转移的状态数
• 3.4.1 四边形不等式和决策的单调性
• 3.4.2 决策量的优化
• 3.4.3 合理组织状态
• 3.4.4 细化状态转移
• 3.5 减少状态转移的时间
• 3.5.1 减少决策时间
• 3.5.2 减少计算递推式的时间
• 3.6 本章小结
• 4 实验结果
• 4.1 第三章例一“大理石划分 Divide”问题
• 4.2 第三章例二“石子合并（最小得分）”问题
• 4.3 第三章例三“邮局post”问题
• 4.4 第三章例四“石子合并（最大得分）”问题
• 4.5 第三章例五“求最长单调上升子序列”问题
• 5 总结与展望
• 5.1 本文工作总结
• 5.2 今后工作展望
• 致谢
• 参考文献