第3章动态规划.pptxVIP

第3章 动态规划 郭艺辉 广东金融学院 计算机科学与技术系 办公室：1622 电 Email：校内邮箱 gdufguo@126.com 第3章 动态规划 基本思想： 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。 第3章 动态规划 美国哲学家乔治.桑塔雅那(George Santayana)，忽略历史会使我们重蹈覆辙，而记住过去可以使我们走向光明的未来。 Those who cannot remember the past are doomed to repeat it. ——George Santayana, The life of Reason, Book I: Introduction and Reason in Common Sense (1905) 4 本章主要知识点： 3.1 矩阵连乘问题 3.2 动态规划算法的基本要素 3.3 最长公共子序列问题 3.4 最大子段和 3.5 凸多边形的最优三角剖分 3.6 多边形游戏 3.7 图像压缩 3.8 电路布线 3.9 流水作业调度 3.10 0-1背包问题 3.11 最有二叉有哪些信誉好的足球投注网站树 3.12 动态规划加速原理 第3章 动态规划 动态规划基本步骤 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 3.1 矩阵连乘问题 问题提出： 给定n个矩阵{A1,A2,...,An}，其中Ai与Ai+1是可乘的，i=1,2,...,n-1。考察这n个矩阵的连乘积A1A2...An。 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。 3.1 矩阵连乘问题 完全加括号的矩阵连乘积可递归地定义为： 单个矩阵是完全加括号的； 矩阵连乘积B是完全加括号的，则B可表示为2个完全加括号的矩阵连乘积A1和A2的乘积并加括号，即B=(A1A2)。 设有三个矩阵A1，A2 ，A3，它们的维数分别是： A1 =10×100， A2 =100×5， A3=5×50 总共有两种完全加括号的方式： ((A1A2 )A3) 、 (A1(A2 A3)) 其数乘次数分别为：7500, 75000。 3.1 矩阵连乘问题 穷举有哪些信誉好的足球投注网站法 问题描述：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。 3.1 矩阵连乘问题 动态规划法——1.分析最优解的结构 预处理： 将矩阵连乘积AiAi+1...Aj简记为A[i:j]，这里i≤j。 考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤kj，则其相应完全加括号方式为（AiAi+1... Ak）（Ak+1 Ak+2... Aj ）。 计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量。 3.1 矩阵连乘问题 这个问题的一个关键特征是：计算A［1：n]的最优次序所包含的计算矩阵子链A［1：k]和A「k＋1：n]的次序也是最优的。事实上，若有一个计算A[1：k］的次序需要的计算量更少，则用此次序替换原来计算A［1：k]的次序，得到的计算A［1：n]的计算量将比最优次序所需计算量更少，这是一个矛盾。同理可知，计算A［l：n]的最优次序所包含的计算矩阵子链A[k+1：n]的次序也是最优的。 因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。 3.1 矩阵连乘问题 2建立递归关系 设计动态规划算法的第2步是递归地定义最优值。对于矩阵连乘积的最优计算次序问题，设计算A「i：j」，l＜=i＜=j＜=n，所需的最少数乘次数为m[i][j]，则原问题的最优值为m[1][n]。 当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n。 当ij时，m[i,j]=m[i,k]+m[