算法设计与分析第3章

《算法设计与分析第3章》由会员分享，可在线阅读，更多相关《算法设计与分析第3章（68页珍藏版）》请在金锄头文库上搜索。

1、第第3 3章章 动态规划动态规划1学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。2通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）多边形游戏； （6）图像压缩；（7）电路布线；（8）流水作业调度；（9）背包问题；（10）最优二叉搜索树。3n动态规划算法与分治法类似，其基本思想也是将待求解

2、问 题分解成若干个子问题算法总体思想算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=4n但是经分解得到的子问题往往不是互相独立的。不同子问 题的数目常常只有多项式量级。在用分治法求解时，有些子 问题被重复计算了许多次。算法总体思想算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 5n如果能够保存已解决的子问题的答案，而在需要时再找出 已求得的答案，就可以避免大量重复计算，从而得到多

3、项式 时间算法。算法总体思想算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)6动态规划基本步骤动态规划基本步骤n找出最优解的性质，并刻划其结构特征。n递归地定义最优值。n以自底向上的方式计算出最优值。n根据计算最优值时得到的信息，构造最优 解。74.1 4.1 矩阵连乘问题矩阵连乘问题n给定n个矩阵 ， 其中 与 是可乘的 ， 。考察这n个矩阵的连乘积 n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许 多不同的计算次序。这种计算次序可以用加括号的方式来确 定

4、。n若一个矩阵连乘积的计算次序完全确定，也就是说该连乘 积已完全加括号，则可以依此次序反复调用2个矩阵相乘的 标准算法计算出矩阵连乘积8矩阵连乘问题矩阵连乘问题给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1 ，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此 次序计算矩阵连乘积需要的数乘次数最少。 u穷举法：列举出所有可能的计算次序，并计算出每一种计 算次序相应需要的数乘次数，从中找出一种数乘次数最少的 计算次序。 算法复杂度分析： 对于n个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题： (A1.Ak)(Ak+1An

5、)可以得到关于P(n)的递推式如下：9（1）单个矩阵是完全加括号的； （2）矩阵连乘积 是完全加括号的，则 可表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 16000, 10500, 36000, 87500, 34500u完全加括号的矩阵连乘积可递归地定义为：u设有四个矩阵 ，它们的维数分别是：u总共有五中完全加括号的方式完全加括号的矩阵连乘积完全加括号的矩阵连乘积10矩阵连乘问题矩阵连乘问题u穷举法 u动态规划将矩阵连乘积 简记为Ai:j ，这里ij 考察计算Ai:j的最优计算次序。设这个计算次序在矩阵 Ak和Ak+1之间将矩阵链断开，ik 0) return mij;if (

6、i = j) return 0;int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj;sij = i;for (int k = i+1; k =cij-1) cij=ci-1j; bij=2;else cij=cij-1; bij=3; 构造最长公共子序列 void LCS(int i，int j，char *x，int *b)if (i =0 | j=0) return;if (bij= 1) LCS(i-1，j-1，x，b); coutsum) sum=thissum;besti=i;bestj=j; return sum;

7、n时间复杂度为O(n3)n因 n第三个for循环可省去n减少一个for循环后的改进算法 Int MaxSum(int n,int *a,intfor (int i=1;isum) sum=thissum;besti=i;bestj=j; return sum; n时间复杂度为O(n2)，改进表现 在充分利用已得到的结果。252.最大子段和问题的分治算法n若将序列a1:n分为长度相等 的两段 a1:n/2和an/2+1:n，分 别求出最大子段和，则a1:n的 最大字段和分三种情形：n1）a1:n的最大字段和与 a1:n/2相等；n2） a1:n的最大字段和与 an/2+1:n 相等；n3）a1:

8、n的最大字段和为 且10?aleft:0;elseint center=(left+right)/2;int leftsum=MaxSubSum(a,left,center);int rightsum=MaxSubSum(a, center+1,right);int s1=0;int lefts=0;for (int i=center;i=left ; i-) lefts+=ai;if(leftss1) s1=lefts;int s2=0;int rights=0;for (int i=center+1;is2) s2= rights;if (sum0时，bj=bj-1+aj, 否则bj=aj

9、,因而可得bj 的动态规划递归式：n可令j从小到大，一次计 算bj，记下和更大的， 于是得到相应的算法。n动态规划算法 Int MaxSum(int n,int *) int sum=0;int b=0;for (int i=1;i0) b+=ai;else b=aj;if(bsum) sum=b;return sum; n时间复杂度为O(n) 。n可推广到二维情形：最大 子矩阵和问题273.5 3.5 凸多边形最优三角剖分凸多边形最优三角剖分凸多边形：若多边形边界上或其内部任意两点连线所得的直线段上所有点 都在多边形内部或边界上，则称为凸多边形。 凸多边形表示：用多边形顶点的逆时针序列表示凸

10、多边形，即 P=v0,v1,vn-1表示具有n条边的凸多边形。 若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦 将多边形分割成2个多边形vi,vi+1,vj和vj,vj+1,vi。 多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。在有 n个顶点的凸多边形的三角剖分中，恰有n-3条弦和n-2个三角形。 最优三角剖分问题：给定凸多边形P，以及定义在由多边形的边和弦组成的 三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分 中诸三角形上权之和为最小。 如取权函数w(vivjvk ) = |vivj|+|vjvk|+ |vkvi|281. 1

11、.三角剖分的结构及其相关问题三角剖分的结构及其相关问题凸多边形的三角剖分与表达式的完全加括号有紧密联系。 它们的相关性可从它们对应的完全二叉树的同构性看出。 一个表达式的完全加括号方式相应于一棵完全二叉树，称 为表达式的语法树。例如，完全加括号的矩阵连乘积 (A1(A2A3)(A4(A5A6)所相应的语法树如图 (a)所示。 凸多边形v0,v1,vn-1的三角剖分也可以用语法树表示。例 如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树 表示。 凸n+1多边形的三角剖分 与n个矩阵的完全加括号 乘积一一对应：矩阵连 乘积中的每个矩阵Ai对应 于凸(n+1)边形中的一条 边vi-1vi

12、。三角剖分中的一 条弦vivj，in 时，顶点i+s实际编号为（i+s）mod n。按上述递推式计算 出的min1即为游戏首次删去第i条边后得到的最大得 分。 38计算最优值及构造最优解Void Min_Max (int n, int i,int s,int j,int /该函数计算minf(i,j,s)和maxf(i,j,s)int a=mis0,b=mis1,r=(i+s-1)%n+1, c=mrj-s0, d=mrj-s1; if (opr= =+) minf=a+c; maxf=b+d; else e1=a*c; e2=a*d; e3=b*c; e4=b*d minf=e1; maxf

13、=e1; for (int r=2;rer) minf=er; if (maxfminf) mij0=minf; If(mij1si-j +j*bmax)si = si-j + j*bmax;li =j; si+=header; Int length(int i) int k=1;i=1/2;while(i0) k+;i=i/2;return k; 算法复杂度分析： 由于算法compress中对j的循环次数不超这256，故对 每一个确定的i，可在时间O(1)内完成的计算。因此整 个算法所需的计算时间为O(n)。 43电路布线电路布线在一块电路板的上、下2端分别有n个接线柱。根据电路设计 ，要求

14、用导线(i,(i)将上端接线柱与下端接线柱相连，如图所 示。其中(i)是1,2,n的一个排列。导线(i,(i)称为该电路 板上的第i条连线。对于任何1i(j)。 电路布线问题要确定将哪些连线安排在第一层上，使得该层上 有尽可能多的连线。换句话说，该问题要求确定导线集 Nets=(i,(i),1in的最大不相交子集。 44记 。N(i,j)的最大不相交子 集为MNS(i,j)。Size(i,j)=|MNS(i,j)|。 (1)当i=1时，(2)当i1时， 2.1 j1时45流水作业调度流水作业调度n个作业1，2，n要在由2台机器M1和M2组成的流水线上 完成加工。每个作业加工的顺序都是先在M1上

15、加工，然后在 M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。 流水作业调度问题要求确定这n个作业的最优加工顺序，使得从 第一个作业在机器M1上开始加工，到最后一个作业在机器M2上 加工完成所需的时间最少。分析： 直观上，一个最优调度应使机器M1没有空闲时间，且机器 M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲 和作业积压2种情况。 设全部作业的集合为N=1，2，n。SN是N的作业子 集。在一般情况下，机器M1开始加工S中作业时，机器M2还 在加工其它作业，要等时间t后才可利用。将这种情况下完成 S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最 优值为T(N,0)。46流水作业调度流水作业调度设是所给n个流水作业的一个最优调度，它所