算法设计与分析课件第3章 节 动态规划8.pptVIP

第3章 动态规划; 学习要点 理解动态规划算法的概念。 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。;通过应用范例学习动态规划算法设计策略 （1）矩阵连乘问题； （2）最长公共子序列； （3）最大子段和 （4）背包问题； ;其实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易。 动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以处理不具备贪心准则的问题。;动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题.; 一个最优化多步决策问题适合用动态规划法求解有两个要素： 最优子结构性质 当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。 重叠子问题性质;动态规划基本步骤; （1）单个矩阵是完全加括号的； （2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 ;完全加括号的矩阵连乘积;16000, 10500, 36000, 87500, 34500;矩阵连乘问题;矩阵连乘问题;矩阵连乘问题;矩阵连乘问题;特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。;建立递归关系;建立递归关系;计算最优值;计算最优值;用动态规划法求最优解;用动态规划法求最优解;用动态规划法求最优解;用动态规划法求最优解;用动态规划法求最优解;动态规划算法的基本要素;动态规划算法的基本要素;动态规划算法的基本要素;动态规划算法的基本要素;动态规划算法的基本要素;动态规划算法的基本要素;动态规划算法的基本要素;动态规划算法的基本要素;动态规划算法的基本要素;动态规划算法的基本要素;动态规划算法的基本要素;动态规划算法的基本要素;动态规划算法的基本要素;动态规划算法的基本要素;最长公共子序列;最长公共子序列;最长公共子序列的结构;要找出序列X={x1, x2,…, xm}和Y={y1, y2,…, yn}的最长公共子序列，可按下述递推方式计算： 当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm即可得到X和Y的最长公共子序列； 当xm≠yn时，必须求解两个子问题： （1）找出Xm-1和Y的最长公共子序列以及 （2）X和Yn-1的最长公共子序列， 这两个公共子序列中的较长者即为X和Y的最长公共子序列。;子问题的递归结构; 由此，把序列X={x1, x2,…, xm}和Y={y1, y2,…, yn}的最长公共子序列的有哪些信誉好的足球投注网站分为m个阶段， 第1阶段，计算X1和Yj的最长公共子序列长度c[1][j]（1≤j≤n）， 第2阶段，计算X2和Yj的最长公共子序列长度c[2][j]（1≤j≤n），依此类推， 最后在第m阶段，计算Xm和Yj的最长公共子序列长度c[m][j]（1≤j≤n），则c[m][n]就是序列Xm和Yn的最长公共子序列的长度。 ; 为了得到序列Xm和Yn具体的最长公共子序列，设二维表b[m+1][n+1]，其中b[i][j]表示在计算b[i][j]的过程中的有哪些信誉好的足球投注网站状态，并且有： ;计算最优值;计算最优值;算法的改进;算法的改进;(a) 长度矩阵c (b) 状态矩阵b;例：序列X=(a, b, c, b, d, b)，Y=(a, c, b, b, a, b, d, b, b)，建立两个(m+1)×(n+1)的二维表c和表b，分别存放有哪些信誉好的足球投注网站过程中得到的子序列的长度和状态。结果？;例：序列X=(a, b, c, b, d, b)，Y=(a, c, b, b, a, b, d, b, b)，建立两个(m+1)×(n+1)的二维表c和表b，分别存放有哪些信誉好的足球投注网站过程中得到的子序列的长度和状态。结果？;动态规划 最长公共子序列 例题;最长公共子序列的两个存储表;最长公共子序列的状态表及有哪些信誉好的足球投注网站 ;最长公共子序列的状态表及有哪些信誉好的足球投注网站 ;最长公共子序列的状态表及有哪些信誉好的足球投注网站 ;最大子段和问题 ;最大子段和问题的简单算法;最大子段和