第3章 节 动态规划 计算机算法设计与分析（第3版）.pptVIP

第3章 动态规划; 学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。;通过应用范例学习动态规划算法设计策略。 （1）矩阵连乘问题； （2）最长公共子序列； （3）最大子段和 （4）凸多边形最优三角剖分； （5）多边形游戏； （6）图像压缩； （7）电路布线； （8）流水作业调度； （9）背包问题； （10）最优二叉有哪些信誉好的足球投注网站树。 ;基本思想也是将待求解问题分解成若干个子问题。（与分治法相似）;子问题往往不是互相独立的。 不同子问题的数目常常只有多项式量级。（与分治法区别：有些子问题被重复计算了许多次。）;矩阵连乘积;（1）单个矩阵是完全加括号的； （2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 ;16000 10500 36000 87500 34500;矩阵连乘问题;矩阵连乘问题;矩阵连乘问题;矩阵连乘问题;矩阵连乘问题;特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。;第二步 建立递归关系(最少乘次数);第三步 计算最优值;;;第四步 构造最优解（P52）;动态规划算法的基本要素;动态规划算法的基本要素;递归式计算A[i,j];动态规划算法的基本要素;int LookupChain(int i，int j) { if (m[i][j] 0) return m[i][j]; if (i == j) return 0; int u = LookupChain(i，i) + LookupChain(i+1，j) + p[i-1]*p[i]*p[j]; s[i][j] = i; for (int k = i+1; k j; k++) { int t = LookupChain(i，k) + LookupChain(k+1，j) + p[i-1]*p[k]*p[j]; if (t u) { u = t; s[i][j] = k; } } m[i][j] = u; return u; };;凸多边形最优三角剖分;凸多边形最优三角剖分;???多边形最优三角剖分;三角剖分的结构及其相关问题;三角剖分的结构及其相关问题;第一步 最优子结构性质;第二步 递归结构;第三步 计算最优值;第四步 构造最优解;0-1背包问题;0-1背包问题