[小学教育]第3章 动态规划.ppt

计算机算法设计与分析 Design and Analysis of Computer Algorithms 第三章 动态规划 Dynamic Programming 提纲 一、动态规划算法的基本思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉有哪些信誉好的足球投注网站树 提纲 一、动态规划算法的思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉有哪些信誉好的足球投注网站树 1.1 总体思想 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，但分解后的子问题往往不是相互独立的。 Divide-and-conquer技术的问题 子问题是相互独立的； 如果子问题不是相互独立的，分治方法将重复计算公共子问题，效率很低。 Dynamic Programming特点 把原始问题划分成一系列子问题； 求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间； 自底向上地计算。 1.2 适用范围 适用范围 一类最优化问题：可分为多个相关子问题，子问题的解被重复使用。 最优化问题 给定一组约束条件和一个代价函数，在解空间中有哪些信誉好的足球投注网站具有最小或最大代价的最优解； 很多最优化问题可分为多个子问题，子问题相互关联，子问题的解被重复使用。 1.3 基本要素 使用动态规划算法的条件： 最优子结构(optimal sub-structure) 当一个问题的最优解包含了子问题的最优解时，称这个问题具有最优子结构； 最优子结构使得能自底而上地完成求解过程； 通常可用“剪贴”(cut and paste)技术判定最优子结构。 重叠子问题(overlapping sub-problems) 在问题的求解过程中，很多子问题的解将被多次使用。 1.4 设计步骤 1.分析最优解的结构； 2.递归地定义最优值； 3.自底向上地计算出最优值，并获取构造最优解的信息； 4.根据构造最优解的信息构造优化解。 提纲 一、动态规划算法的基本思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉有哪些信誉好的足球投注网站树 2.1 问题定义 Matrix-chain Multiplication 输入：A1,A2,...,An,Ai是矩阵，Ai与Ai＋1可乘，i＝1,2,…(n-1)； 输出：计算A1?A2?...?An的最小代价方法 2.1 问题定义 矩阵连乘法的实现 矩阵乘法满足结合律； 计算一个矩阵链的乘法可有多种方法: 例如, （A1?A2?A3?A4） =（A1?(A2?(A3?A4))) =（(A1?A2)?(A3?A4）) .... = (（A1?A2）?A3)?A4) 2.1 问题定义 完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可 表示为2个完全加括号的矩阵连乘积B和 C 的乘积并加括号，即A=(B*C) 2.1 问题定义 矩阵连乘法的代价与计算顺序的关系 设A1=10?100矩阵, A2=100?5矩阵, A3=5?50矩阵 T((A1?A2)?A3)=10?100?5+10?5?50=7500 T(A1?(A2?A3))=100?5?50+10?100?50=75000 2.2 矩阵连乘问题的解空间 设p(n)=计算n个矩阵乘积的不同计算次序 p(n)的递归方程： Catalan数是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。 　　原理： 　　令h(0)=1,h(1)＝1,catalan数满足递归式： 　　h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n=2) 　　该递推关系的解为： 　　h(n)=C(2n,n)/(n + 1) (n=1,2,3,...) 2.3求解矩阵连乘问题的动态规划算法 分析最优解的结构； 递归地定义最优值； 自底向上地计算出最优值，并获取构造最优解的信息； 根据构造最优解的信息构造优化解。 2.3.1 分析最优解的结构 两个记号 A[i:j]=Ai?Ai+1?....?Aj m[i][j]=计算A[i:j]的最少乘法次数 最优解的结构 若计算A[1:n]的最优顺序在k处断开矩阵链, 即A[1:n]=A[1:k]?A[k+1:n]，则在A[1:n]的最优顺序中，对应于子问题A[1:k]的解必须是A[1:k