1、 本 科 毕 业 论 文 动态规划算法应用 及其优化 The Practice And Optimize Of Dynamic Programming Algorithm 姓 名： 学 号： 学 院：软件学院 系：软件工程 专 业：软件工程 年 级： 指导教师： 年 月 摘 要 动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法 。 它 建立在最优原则的基 础上 ,是基本算法中设计难度相当大的一种 。采用动态规划方法，可以高效地解决许多用贪婪算法或分治 算法无法解决的问题， 是信息学竞赛 选手必须熟练掌握的一种算法 ,以其多元性广受出题者的喜爱 。 动态规划算法没有一个固定的解题模式，
2、技巧性很强 。 涉及优化问题，一般都离不开动态规划，然而因为在程序算法中动态规划属于最难理解的算法之列，这也使得许多人对此望而却步。 本文从数字三角形问题入手， 逐步 深入动态规划算法 。 介 绍了 该算法的 理论基础， 基本概念，涉及 领域 和 解题步骤。 通过矩阵连乘，炮弹拦截， 最长单调上升子序列 等实际问题的讨论 ， 探讨动态规划的基本思想。同时本文还对两个与动态规划有密切联系的其他方法进行了比较。 在对该算法的基本问题比较全面的论述后，本文 接着探讨了 动态规划算法的优化 。 从三个方面讨论了动态规划算法时间复杂度的优化，从两个实例讨论了动态规划算法空间复杂度的优化。 关键词 ： 动
3、态规划；备忘录方法；算法优化 Abstract Dynamic programming is a branch of operational research. It is the mathematical method for solving the optimization decision-making process. It is the one that very difficult to design in the basic algorithms. It is built on the basis of optimization principle. By the dynamic
4、 programming, we can solve many problem, which cant solve by the greedy algorithm or divide and rule algorithm, elegantly and effectively. It is the algorithm that players must master in the competition. It is popular with the examiners for its diversity. Dynamic programming algorithm does not have
5、a fixed problem-solving mode. It is Skillful. Optimization problems generally are solved by the dynamic programming. But many people do not have the courage to learn dynamic programming algorithm because it is the most difficult algorithm. This article discussed the dynamic programming algorithm ste
6、p by step started from the question of the number-triangle, and introduced its theory, domain, conception and steps to use. It explored the basic idea of dynamic programming through the matrix chain problem and missile intercepting problem. At the same time, this article compared two other algorithm
7、s similar to the dynamic programming algorithm. Then this article discussed how to optimize the dynamic programming algorithm. It discussed how to optimize the time complexity from three aspects and how to optimize the space complexity from two aspects. Key words: dynamic programming; memorandum; op
8、timize algorithm 目 录 第一章 问题的引入 . 1 1.1 问题描述 . 1 1.2 穷举搜索法解题 . 1 第二章 初识动态规划 . 4 2.1 分析最优解的性质 . 4 2.2 递归地定义最优值 . 5 2.3 计 算最优值 . 5 2.4 构造最优解 . 8 第三章 从理论 角 度看动态规划 . 9 3.1 最优化原理 . 9 3.2 基本术语 . 10 3.3 动态规划的基本思想 .11 3.4 动态规划问题的特征 .11 3.5 动态规划基本步骤 . 12 第四章 从应用 角 度看动态规划 . 13 4.1 矩阵连乘问题 . 13 4.1.1 问题描述 . 13 4
9、.1.2 最优解的性质 . 14 4.1.3 递归定义最优值 . 15 4.1.4 计算最优值 . 15 4.1.5 构造最优解 . 17 4.2 导弹拦截问题 . 17 4.2.1 问题描述 . 17 4.2.2 最优子结构性质 . 18 4.2.3 递归的定义最优值 . 18 4.2.4 计算最优解 . 19 4.2.5 构造最优解 . 20 第五章 动态规划与其它算法比较 . 21 5.1 动态规划与搜索算法 . 21 5.2 动态规划与备忘录方法 . 22 第六章 动态规划算法的优化 . 25 6.1 动态规划时间优化 . 25 6.1.1 减少状态总数 . 25 6.1.2 减少每个
10、状态转移的状态数 . 28 6.1.3 减少状态转移的时间 . 30 6.2 动态规划空间优化 . 32 6.2.1 最长公共子序列问题空间优化 . 32 6.6.2 数字三角形问题空间优化 . 35 第七章 总结 . 36 致谢 . 37 参考文献 . 38 Content Chapter 1 Introduction. 1 1.1Question . 1 1.2Frist answer . 1 Chapter 2 Understand dynamic programming . 4 2.1The nature of the optimal solution . 4 2.2Optimal v
11、alue . 5 2.3Get optimal value . 5 2.4Get optimal solution. 8 Chapter 3 Theory Of Dynamic programming . 9 3.1Optimization Principle . 9 3.2Terms . 10 3.3The basic idea .11 3.4Features .11 3.5Steps. 12 Chapter 4 Practice Of Dynamic programming . 13 4.1 Matrix chain problem . 13 4.1.1 Question . 13 4.1
12、.2 The nature of the optimal solution . 14 4.1.3 Optimal value . 15 4.1.4 Get optimal value . 15 4.1.5 Get optimal solution. 17 4.2 Missile intercepting problem. 17 4.2.1 Question . 17 4.2.2 The nature of the optimal solution . 18 4.2.3 Optimal value . 18 4.2.4 Get optimal value . 19 4.2.5 Get optim
13、al solution. 20 Chapter 5 Compare . 21 5.1 Compare to search algorithm . 21 5.2 Compare to memorandum algorithm . 22 Chapter 6 Optimize The Dynamic Programming . 25 6.1 Optimize the time complexity . 25 6.1.1Reduce the state . 25 6.1.2 Reduce the state transition . 28 6.1.3 Reduce the time of state
14、transition . 30 6.2 Optimize the space complexity . 32 6.2.1 Example 1 . 32 6.6.2 Example 2 . 35 Chapter 7 Summarize . 36 Acknowledgement . 37 References . 38 动态规划算法应用及其规划 1 第一章 问题的引入 天才设题，智者解题 对于 绝 大多数没有数据结构和算法知识的编程人员，穷举搜索法经常成了 克敌制胜的关键法宝，它也似乎是可以解决一切问题的万能钥匙。如今计算机的处理器不是号称一秒钟可以处理 好多 亿条指令，那么穷举搜索法好像是没有什
15、么好担心的了。 事实真的 如此吗， 先来看看下面这个例子。 1.1 问题 描述 如下所示为一个数字三角形： 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 请编 写 一 个程序计算从顶至底的某一条路径，使该路径所经过的数字的总和最大 ，要求满足一下三个条件： 每一步可沿直线向下或右斜线向下走 ； 1 = 三角形行数 = 100； 三角形中的数字为整数 0， 1， ， 99。 1.2 穷举搜索法解题 分 析上面的题目，要计算所有路径中所经过数字总和最大的路径，那么 可以穷举出所有可能的路径，然后从中选出总和最大的路径。 要 怎么实现对所有路径的穷举呢，使用深度搜索可以很好的 完成任务
16、。 用搜索法写出如下的算法程序： /参数： i， 路径起始位置所在的行 。 j， 路径起始位置所在的列 。 动态规划算法应用及其规划 2 / n， 三角形的总行数 。 triangle， 存储三角形的二维数组 。 int maxPath(int i, int j, int n, int* triangle) int iMax1, iMax2; if (i = n) return triangleij; else iMax1 = maxPath(i + 1, j, n, triangle); iMax2 = maxPath(i + 1, j + 1, n, triangle); if (iMax
17、1 iMax2) return iMax2 + triangleij; return iMax1 + triangleij; 接下来， 对上面的算法进行数据规模测试，记录下该算法对于不同数据规模（在此表现为 n 值的大小）运行所需要的时间， 如 表 1-1 所示 ： 表 1-1： 递归搜索法的运行时间测试 数据规模 (n) =23 24 25 26 27 28 29 30 运行时间 (s) = 1 1 3 6 13 28 60 122 从上表可以看出，当 n 大于 25 时，运行所需时间就超过 1 秒，并且随着 n的增长 而迅速增长（实际上是按 所需时间随指数增长 ）。 所以，即使 你所使用的
18、动态规划算法应用及其规划 3 电脑 性能确实比 上面的测试机 好上好几倍 ，也 解决 不了 问题 。 再看看 题目的数据规模 (n 值 )是 100，而 搜索算法 只能解决 n24 的数据规模 (相信你也忍受不了运行好几秒甚至几十秒才出来的结果吧 )。 分析上面算法，算法进行了很多重复的运算，例如第三行的第二个数，在计算第二行第一个数时 调用计算了一次，计算第二行第二个数时又调用计算了一次，共调用计算了 2次。同样道理，得出各行数据调用运算的次数如下： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 上面的调用运算次数实际上是一个杨辉三角。 大量重复的运算使得 搜索算法的时间复杂度 随指数增长，导致运算时间严重超标。 穷举搜索法不再是万能钥匙了， 那么有没有什么办法解决这个问题呢，或是应该采用更加先进的算法 ?
