第七讲 动态规划 算法的设计与分析课件.pptVIP

第七章 动态规划 —A powerful method for combinatorial problems 2018-5-25 Algorithms Design Techniques and Analysis 2 主要内容 基本概念 简介 两个例子 动态规划范式 用动态规划策略处理的问题 最长公共子序列问题 矩阵链相乘 所有点对的最短路径问题 背包问题 2018-5-25 Algorithms Design Techniques and Analysis 3 7.1 简介 动态规划 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。 2018-5-25 Algorithms Design Techniques and Analysis 4 7.1 简介 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。 如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。 Those who cannot remember the past are doomed to repeat it. -----George Santayana, (1905) 2018-5-25 Algorithms Design Techniques and Analysis 5 例子（求Fibonacci 序列） 定义Fibonacci 序列fn，序列中的每一个数是它前面两个数的和： 我们来看这个序列的递归定义 这个定义暗示一个看起来像下面那样表示的过程： : procedure f(n) if (n=1) or (n=2) then return 1 else return f(n-1)+f(n-2) 传统的解决方法是什么? 2018-5-25 Algorithms Design Techniques and Analysis 8 另一个例子（二项式系数计算） 二项式系数定义如下: 与Fibonacci 系数类似, 递归算法的时间复杂度正比于其自身： 此函数增长迅速. 例如, 当k=n/2 (假设 n 是偶数), 可知： 2018-5-25 Algorithms Design Techniques and Analysis 9 一种有效方法 有效计算 的方法可以用按行构造帕斯卡三角来进行， 一旦计算出 的值，计算就立即停止。 帕斯卡三角形 2018-5-25 Algorithms Design Techniques and Analysis 10 动态规划和分治方法 共同点: 动态规划与分治方法相似，通过合并多个子问题的解来解决整体问题。 2018-5-25 Algorithms Design Techniques and Analysis 11 动态规划和分治方法 区别: 分治法是把大问题分解成一些相互独立的子问题，递归的求解这些子问题然后将他们合并来得到整个问题的解 2. 动态规划是通过组合子问题的解来解决整个大问题。各个子问题不是独立的，也就是各个子问题包含公共子问题。它可以避免遇到的子问题的重复求解。 2018-5-25 Algorithms Design Techniques and Analysis 12 最优化问题 通常采用动态规划对问题进行优化。对于一个问题，可以有很多可能的解决方案。每个解决方案有一个值，我们希望找到一个最佳的（最小或最大）值对应的解决方案，我们称这样的解决办法为最优的解决方案。 2018-5-25 Algorithms Design Techniques and Analysis 13 动态规划基本步骤 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 2018-5-25 Algorithms Design Techniques and Analysis 14 动态规划算法的基本要素1(最优子结构) 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导