第3讲动态规划ppt课件.ppt

《第3讲动态规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3讲动态规划1广州大学华软软件学院算法分析与设计学习要点理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）多边形游戏；（6）图像压缩；（7）电路布线；（8）流水作业调度；（9）背包问题；（1

2、0）最优二叉搜索树。主要内容1、算法思想2、例题（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）多边形游戏；（6）图像压缩；（7）电路布线；（8）流水作业调度；（9）背包问题；（10）最优二叉搜索树。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=1、算法总体思想但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。nT(n)=n/2T

3、(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)1.1最优子结构组合优化问题，指的是问题有多个可行

4、解，每一个可行解对应一个目标值，目的是要在可行解中求得目标值最优者（最大或最小）。最优子结构特性指的是问题的最优解包含的子问题的解相对于子问题而言也是最优的。1.2子问题重叠问题的一个递归算法在每个递归步骤产生分支子问题时并不总是新的，而是对部分子问题解了又解。当一个递归算法一次又一次地访问同一个子问题时，我们说该最优化问题具有重叠子问题的特性。1.3动态规划针对具有上述两个特征的优化问题，动态规划算法通常需要做如下的3步工作：（1）利用最优子结构定义一个关于解的目标值的递归方程。鉴于子问题的重叠性，如果自顶向下地用递归技术解每一个

5、遇到的子问题，则可能陷入一个“时间黑洞”。（2）因此，动态规划以自底向上地对每个新产生的子问题仅解一次且将其解保存在一个表格中，需要时可以在表中查找，且能在常数时间内完成查找。（3）根据计算出的最优解的值构造对应的最优解。动态规划基本步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。2、例题2.1矩阵链乘法给定一个由n个矩阵构成矩阵序列（链），要将它们相乘（假定它们按此序列是乘法相容的：Ai是pi-1pi矩阵，而Ai+1是pi

6、pi+1矩阵），计算积：A1A2...An只要对此序列加上括号，确定运算顺序，就可以算得它们的积。矩阵链的积称为是完全加括号的，若它或是单一的矩阵，或是两个完全加括号的矩阵子链之积，并用一对括号括起来。（1）单个矩阵是完全加括号的；（2）矩阵连乘积是完全加括号的，则可表示为2个完全加括号的矩阵连乘积和的乘积并加括号，即16000,10500,36000,87500,34500完全加括号的矩阵连乘积可递归地定义为：设有四个矩阵，它们的维数分别是：总共有五中完全加括号的方式矩阵连乘问题给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连

7、乘积由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：对于

8、n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：穷举法动态规划将矩阵连乘积简记为A[i:j]，这里i≤j考察计