算法分析与设计第3章详解.ppt

第3章 动态规划; 学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。;通过应用范例学习动态规划算法设计策略。 （1）矩阵连乘问题； （2）最长公共子序列； （3）最大子段和 （4）凸多边形最优三角剖分； （5）多边形游戏； （6）图像压缩； （7）电路布线； （8）流水作业调度； （9）背包问题； （10）最优二叉有哪些信誉好的足球投注网站树。 ;动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题;但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。;如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。;动态规划基本步骤;3.1 矩阵连乘问题;完全加括号的矩阵连乘积;完全加括号的矩阵连乘积;矩阵连乘问题;矩阵连乘问题;矩阵连乘问题;矩阵连乘问题;思考四：分治法;思考四：分治法;思考四：分治法;矩阵连乘问题;特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。;2、建立递归关系;3、计算最优值;用动态规划法求最优解;A1;4、构造最优解;4、构造最优解;3.2 动态规划算法的基本要素;3.2 动态规划算法的基本要素;实例一、数字三角形问题;实例一、数字三角形问题;2．解题思路 这道题可以用动态规划成功地解决，但是，如果对问题的最优结构刻画得不恰当(即状态表示不合 适)，则无法使用动态规划。 ? 状态表示法一： 用一元组D(X)描述问题，D(X)表示从顶层到达第X 层的最小路径得分。因此，此问题就是求出D(N)(若 需要，还应求出最优路径)。这是一种很自???的想法 和表示方法。遗憾的是，这种描述方式并不能满足 最优子结构性质。因为D(X)的最优解(即最优路径) 可能不包含子问题例如D(X-1)的最优解。如下图所 示：;? 显然，D(4)＝2+6+1+1＝10 ，其最优解(路径)为 2-6-1-1。而D(3)＝2+2+4＝8 ，最优解(路径)为2-2-4。故D(4)的最优解不包含子问题D(3)的最优解。 由于不满足最优子结构性质，因而无法建立子问题 最优值之间的递归关系，也即无法使用动态规划。;? 状态表示法二： 用二元组D(X,y)描述问题，D(X,y)表示从顶层到 达第X层第y个位置的最小路径得分。 最优子结构性质：容易看出，D(X,y)的最优路径 Path(X,y)一定包含子问题D(X-1,y)或D(X-1,y-1) 的最优路径。 否则，取D(X-1,y)和D(X-l,y-1)的最优路径中得 分小的那条路径加上第X层第y个位置构成的路径得 分必然小于Path(X,y)的得分，这与Path(X,y)的最 优性是矛盾的。;如上图所示，D(4,2)的最优路径为2-6-1-5，它 包含D(3,1)最优路径2-6-1。因此，用二元组 D(X,y)描述的计算D(X,y)的问题具有最优子结构 性质。;34;? 状态表示法三： 采用状态表示法二的方法是从顶层开始，逐步向下至底层来求出原问题的解。事实上，还可以从相反的方向考虑。仍用二元组D(X,y)描述问题，D(X,y)表示从第X层第y个位置到达底层的最小路径得分。原问题的最小路径得分即为D(1,1)。 ? 最 优 子 结 构 性 质 ： 显 然 ， D(X,y) 的最优路径Path(X,y)一 定包含子问题D(X+1,y)或D(X+1,y+1)的最优路径，否则，取D(X+1,y)和D(X+1,y+1)的最优路径中得分小的那条路径加上第X层第y个位置构成的路径得分必然小于Path(X,y) 的得分，这与Path(X,y)的最优性矛盾。;36;37;动态规划算法的基本要素;动态规划算法的基本要素;3.3最长公共子序列;最长公共子序列的结构;子问题的递归结构;计算最优值;计算最优值;算法的改进;给定字符串A=“xzyzzyx”和B=“zxyyzxz”，使用LCS算法求最长公共子串，并给出一个最长公共子串。 解：计算求得C矩阵如下， ;3.4 最大子段和问题;1 、最大子段和问题的简单算法;1 、最大子段和问题的简单算法;2 、最大子段和问题的分治算法;3、最大子段和问题的动态规划算法;3、最大子段和问题的动