算法课件资料第3章动态规划.pptVIP

第3章 动态规划 学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 （1）找出最优解的性质，并刻划其结构特征。 （2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。 （4）根据计算最优值时得到的信息，构造最优解。 通过应用范例学习动态规划算法设计策略。 （1）矩阵连乘问题； （2）最长公共子序列； （3）最大子段和； （4）凸多边形最优三角剖分； （5）多边形游戏； （6）图像压缩； （7）0-1背包问题 数塔问题：有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。 最短路径问题： （多阶段图）地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，我们想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少？ A - E B1 - E, B2 - E C1-E, C2-E, C3-E C2-E, C4-E …… 再看一例： 旅行售货员问题（货郎担问题） 动态规划基本步骤 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 0-1背包问题 （要交）算法分析题： 3-1，3-3，3-7 （不交）算法实现题： 3-2，3-6，3-7，3-13，3-18 方法三、动态规划 例：当（ ）＝（-2，11，－4，13，－5，－2）时，如何填充b数组，( ) 解： b[1]＝max{0, a[1]}={0, -2}=0 b[2]＝max{b[1]+a[2], a[2]}={0+11, 11}=11 b[3]＝max{b[2]+a[3], a[3]}={11-4, -4}=7 b[4]＝max{b[3]+a[4], a[4]}={7+13, 13}=20 b[5]＝max{b[4]+a[5], a[5]}={20-5, -5}=15 b[6]＝max{b[5]+a[6], a[6]}={15-2, -2}=13 那么，最大子段和为： 显然，这个算法仅对原数组做了一次扫描，即计算时间 ，借助的空间 。 ——“高效”的算法 最大子段和算法推广到“高维” 最大子矩阵和问题 —— 向“二维”的推广 略讲解 最大m子段和问题 —— 在子段个数上推广 自看 最大子矩阵和问题 1）最大子矩阵和问题 问题描述 给定一个m行n列的整数矩阵A，试求矩阵A的一个子矩阵，使得其各元素之和最大。 用二维数组a[1:m][1:n]表示给定的m行和n列的整数矩阵。子数组a[i1:i2][j1:j2]表示左上角和右下角行列坐标分别为(i1, j1)和 (i2, j2)的子矩阵，其各元素之和记为： 最大子矩阵和问题的最优值为： 先将条状矩阵纵向相加存于b数组，而后可以借助一维的“最大子段和”动态规划解法MaxSum来求得二维的最大子矩阵和。 最大子矩阵和问题 效率分析 解最大子段和问题的动态规划算法MaxSum需要O(n)的时间，故最大子矩阵问题的算法需要 的时间,其中包含： ①小矩阵纵向逐渐拉长，O(m)； ②计算b[j],每计算一个b元素，要进行纵向的累加，O(m)； ③最多有O(n)个b[j]元素，进行求最大子段和问题，耗费时间O(n)。 特别地，当m=O(n)时，算法MaxSum2需要 的 计算时间。 最大子矩阵和问题 思考：继续向高维（三维）推广 ---- 最大子长方体问题：长方体长宽高m*n*p可分割为单位小立方体，每个小立方体内一个整数，求具有最大和值的最大子长方体。 凸多边形最优三角剖分 用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。 若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。 多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。 给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。 凸多边形的三角剖分与完全加括号的矩阵连乘有密切关系。 如何将它们联系起来？ —— 这两个问题的