算法设计与分析-3-15

《算法设计与分析-3-15》由会员分享，可在线阅读，更多相关《算法设计与分析-3-15（175页珍藏版）》请在文档大全上搜索。

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

2、也是将待求解问题分解成若干个子问题;先求子问题解，然后合成原问题解nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=n大问题自上而下分解为子问题时，可以有多种分解方法。 e.g. 归并排序，矩阵连乘n如果不同分解方法对应的子问题及其解不同，并导致合并后的原问题解不同，则需要考虑各种可能的分解方法。此时，无法直接采用分治法求解：e.g. 矩阵连乘1. 分解得到的子问题往往不是互相独立的，用分治法求解，需要计算的子问题数目太多，时间复杂性指数级别2. 不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。 E.g. Fibonacci数列计算，见后与分治法区

3、别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)n解决方法： 保存已解决的子问题的答案，在需要时再找出已求得的答案，避免大量重复计算，得到多项式时间算法。 利用表来记录子问题的答案，表的大小为多项式量级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)示例：分治法 vs 动

4、态规划n算法1基于递归分治 F(n) 1. if (n = 1 return 1; 2. else return F(n-1)+ F(n-2); 问题：复杂性O(2n) 原因：自上而下的自上而下的递归计算过程中，一些子问题被多次重 复计算10( )11(1)(2)1nF nnF nF nnFibonacci数F(6)F(4)F(3)F(2)F(1)F(0)F(2)F(1)F(0)F(1)F(5)F(4)F(3)F(2)F(1)F(0)F(1)F(3)F(2)F(2)F(1)F(0)F(1)F(1)F(0)子问题子问题F(3)重复计算重复计算3次次子问题子问题F(2)重复计算重复计算5次次n算法

5、2：非递归的分治算法 保存子问题计算结果，只计算1次，以后碰到同样子问题时，直接调用已有结果F1(n) 0. 初始化数组 vi -1, 0 i n 1. if vn 0 then 2. vn F1(n-1) + F1(n-2) 3. return vn 数组vn: 存储子问题结果的数组， vi：表示子问题Fi的解， vi=-1：表示子问题Fi还没有被计算问题：自上而下的计算过程中，避免了多次计算同一子问题，但又多次函数调用。每次调用需要花费较多时间用于参数传递和动态链接n算法3自下而上的迭代算法：动态规划算法F2(n) 1. F(0) 1; 2. F(1) 1; 3. for i 2 to n

6、 do 4. Fi F1(i-1) + F1(i-2) /* 问题问题-子问题间的递归公式子问题间的递归公式 5. return Fn 特点： 1）时间复杂性 O(n) 2) 自下而上，迭代计算 3) 利用数组，保存中间（子问题）计算结果。每个子问题只计算一次n1.找出最优解的性质，刻划其结构特征-最优子结构特征n2. 递归地定义最优值： 刻画原问题解与子问题解间的（数值）关系: 表达式中存在寻优变量、最优目标值寻优变量、最优目标值n3. 以自底向上自底向上的方式计算出各个子问题、原问题的最优值，并避免子问题的重复计算（记录已计算的子问题解）n4. 根据计算最优值时得到的信息，构造最优解12（

7、1）矩阵连乘问题；乘法次数最少（2）最长公共子序列；公共子序列的长度最长 （3）最大子段和子段中的数字之和最大（4）凸多边形最优三角剖分；三角形上权之和为最小（6）图像压缩；（9）背包问题；（10）最优二叉搜索树。（7）电路布线；（8）流水作业调度；作业运行时间最短n（5）多边形游戏；u给定n个可连乘的矩阵A1, A2, ,An,连乘积A1A2, ,An 。u根据矩阵乘法结合律，可有多种不同计算次序，每种次序有不同的计算代价)数乘次数数乘次数（取决于各矩阵的行、列数和计算次序）u给定2个矩阵Api,pj,Bpj,pk, AB 为pi,pk矩阵，数乘次数pipjpku多个矩阵的连乘计算次序可用完

8、全加括号来确定见下页1050A4010B3040C530D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB这5种计算次序对应的计算代价分别为： 16000, 10500, 36000, 87500, 34500u设有四个矩阵A, B, C, D, 它们的维数分别是：u总共有五种完全加括号的方式举例(40*30*5) + 10*40*5 + 50*10*5CD40,5B(CD)10,5A(B(CD)50,5u完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 AABC)

9、(BCAn给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积 n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。n若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,.,21nAAAiA1iA1,.,2 , 1ninAAA.21给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次使得依此次序计算矩阵连乘积需要的数乘次数最少。序计算矩阵连乘积需要的数乘次数最少。u方法方法1：穷举法

10、：穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。 算法复杂度分析：算法复杂度分析： 对于n个矩阵的连乘积，设其不同的计算次序下的组合方式（即完全加括号的组合方式）为P(n)。 每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)，关于P(n)的递推式如下：)/4()(11)()(1)(2/ 311nnPnnknPkPnPnnk穷举法u 方法方法2：动态规划：动态规划 将矩阵连乘积 简记为Ai:j ，这里ij jiiAAA.1考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链

11、断开，ikj，则其相应完全加括号方式为).)(.(211jkkkiiAAAAAA计算量：Ai:k的计算量 + Ak+1:j的计算量 +Ai:k和Ak+1:j相乘的计算量n特征： 计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。即： 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质最优子结构性质。 问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。n设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n n当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,nn当ij时，n断开位置kn

12、可以递归地定义mi,j为：jkipppjkmkimjim1, 1,这里 的维数为 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只有 种可能kij n对于1ijn，不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有n由此可见，在递归计算时，许多子问题被重复计算多次许多子问题被重复计算多次 这也是该问题可用动态规划算法求解的又一显著特征。n用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算： 1）在计算过程中，保存已解决的子问题答案。每个子问题只计算一次 2）而在后面需要时只要简单查一下，从而避免大量的重复计算 最终得到多

13、项式时间的算法)(22nnn子问题Ai,i, 1i nvoid MatrixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) mii = 0; /*规模为1的子问题的最优解 for (int r = 2; r = n; r+) /*自下而上，从规模为r=2的子问题开始， 依次计算规模为2、3、n的子问题 for (int i = 1; i = n - r+1; i+) /*考察规模为r的共n-r+1个子问题 mi, j, j-i= r-1, int j=i+r-1; /* 子问题左端点i，右端点j, 规模r mij =0+

14、 mi+1j+ pi-1*pi*pj; /*设置子问题mi,j的初始最优值 sij = i; /*记录子问题最优值的初始断点位置 for (int k = i+1; k j; k+) /*依次考察不同断点，计算mi,j最优值 int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; 输入参数最优值断开位置子问题mi, j的递推比较矩阵维度1(.)iijA AA1n子问题规模r：2nr左端点i：1( 0) return mij; /* Ai,j 如果以前以计算过，则 mi,j0，直接返回计算结果， 避免重复计算 if (i =

15、j) return 0; /* Ai,j =Ai,i, 只有1个矩阵的最小规模子问题 /* 以下各步依次比较 k=i,j-1 等多种划分方法，求最优划分和最优值 int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj; sij = i; /*初始最佳划分点位置k=i for (int k = i+1; k j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u;Ai,i*

16、Ai+1,jAi,k*Ak+1,j 备忘录 vs 动态规划n备忘录方法采用自上而下的递归分解法n与动态规划法一样，避免子问题重复计算n但由于采用递归，需要多次函数调用和参数传递，计算时间仍然比动态规划要大若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xijE.g. 对序列X=A，B，C，B，D，A，B，子序列Z=B，C，D，B ，相应的递增下标序列为2，3，5，7。 应用：网络内容审查, 敏感字检查给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子

17、序列公共子序列。问题：给定2个序列X=x1, x2, xm和Y=y1,y2,yn，找出X和Y的最长最长公共子序列 nE.g. X=(A, B, C, B, D, A, B)Y=(B, D, C, A, B, A)子序列: Z1=(B, C, A), 长度3 Z2=(B,C, B, A)，长度4设序列X(m)=x1,x2,xm和Y(n)=y1,y2,yn的最长公共子序列为Z(k)=z1,z2,zk ，则(1)若xm=yn，则zk=xm=yn，且Z(k-1)=z1, z2,zk-1 是X(m-1)= x1,x2,xm-1和Y(n-1)=y1,y2,yn-1的最长公共子序列BCBAX(m) :CBA

18、Y(n) :BBCBX(m-1) :Y(n-1) : Z(k) :CBBA Z(k-1) :CBBCBB问题规模前缀前缀n问题归结：原问题 子问题(问题规模更小) 原问题: X(m), Y(n), 最优解:Z(k)X(m-1), Y(n-1)X(m-1), Y(n)X(m), Y(n-1)（1）（2）（3）子问题最优解： Z(k-1) Z(k) Z(k) 上述3种情况下，原问题最优解包括了子问题最优解！前缀前缀3种情况：(2)若xmyn且zkxm，则Z(k)是x(m-1)和Y(n)的最长公共子序列BCBACBABBCBCBBAX(m) :Y(n) :X(m-1) : Z(k) :问题规模前缀前

19、缀A(3)若xmyn且zkyn，则Z(k)是X(m)和y(n-1)的最长公共子序列BCBACBABCBBACBABX(m) :Y(n-1) :Y(n) : Z(k) :问题规模 前缀前缀由此可见，2个序列的最长公共子序列包含了这2个序列的前缀前缀(i.e. 子问题子问题)的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质最优子结构性质。 根据最优子结构性质，建立子问题最优值的递归关系。 cij：序列X(i)和Y(j)的最长公共子序列的长度，X(i)=x1,x2,xi；Y(j)=y1,y2,yj。 当i=0或j=0时，即其中1个序列为空，则空序列是Xi和Yj的最长公共子序列。故此时Ci

20、j=0。 其它情况下，由最优子结构性质可建立递归关系如下：00,0 11 1,0;max 1, 1 ,0;ijijijc ijc iji jxyc ijc iji jxy或3种情况 对X(m)和Y(n)，总共有(mn)个不同的子问题，用动态规划算法自底向上地计算最优值，以提高算法效率。void LCSLength(int m，int n，char *x，char *y，int *c， int *b)数组x*和y*：存储2个输入序列X(m)、Y(n)输出数组c：cij存储序列Xi、Yj的最长公共子序列的长度输出数组b： bij 记录cij的值是由哪个子问题得到的(3种情 况之一)，构造最长公共子

21、序列时用到X(i)=x1,x2,xi, 1i m；Y(j)=y1,y2,yj, 1j n；void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; /*初始化, Yj为空时 for (i = 1; i = n; i+) c0i = 0; /*初始化， Xi为空时 for (i = 1; i = m; i+) /*两重循环，自下而上， 计算子问题X(i), Y(j) for (j = 1; j =cij-1) /*情况2 cij=ci-1j; bij=2;

22、else cij=cij-1; /*情况3 bij=3; 每个数组单元的计算耗时O(1)，算法耗时：O(mn)算法LCSLength构造了数组bij，据此可递归构造出X(i)、Y(j)的最长公共子序列：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); coutxi; /*第1种情况下，X(i)和Y(j)的最长公共子序列由X(i-1)和 Y(j-1)的解LCS(i-1, j-1, x, b)，加上位于最后的，加上位于最后的Xi 组成组成 else if (bi

23、j= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b); /*其它2种情况下，原问题解 等于子问题解过程： 从bm,n开始，依其值在数组b中搜索。1） bi,j=1, Xi和Yj的最长公共子序列由Xi-1和Yj-1的最长公共子序列，在尾部加上xi得到2） bi,j=2, Xi和Yj的最长公共子序列与Xi-1和Yj的的最长公共子序列相同3） bi,j=3, Xi和Yj的最长公共子序列与Xi和Yj-1的的最长公共子序列相同算法中，每次递归调用使i或j减一，算法的计算时间为O(m+n)在算法lcsLength和lcs中，可进一步将数组b省去： 数组元素cij的值仅由ci-

24、1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组b而仅借助于c本身在O(1)时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少： 在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。最大子段和n给定n个整数组成的序列序列a1,a2,an，求该序列形如 ，1i、j n, 的子段和的最大值nE.g. -2, 11, -4, 13, -5, -2，最大

25、子段和 =20 子段的起点i、长度、终点j不固定jkk ia42kka一、简单算法 用数组a存储给定的n个整数a1,a2,an，注意到，采用2重循环，计算复杂性为O(n2)1jjkjkk ik iaaa int MaxSum(int n, int *a，int &besti, int &bestj) int sum=0 for (int i = 1; i = n; i+) int thissum=0; for (int j=i; i sum) sum=thissum; besti=i; bestj=j return sum i: 1nij: injjkk ia2重循环55n问题采用二维表述Ma

26、xSum(i, j)，算法两重循环，导致二次项复杂性O(n2)自上而下分治算法n目标：进一步改进算法复杂性n将序列a1:n分解为长度相等的2段a1:n/2和an/2+1:n，分别求出这2个子段的和，与a1:n的最大子段和相比，有三种情况1） a1:n/2与a1:n的最大子段和相同 最大子段落在前半部分2） an/2+1:n与a1:n的最大子段和相同 最大子段落在后半部分3） a1:n的最大子段和为 ，并且1i n/2, n/2+1 j n 最大子段横跨中点jkk ian对第3种情况，an/2和an/2+1 一定在最优子序列中：1) 在a1:n/2中计算出S1=2) 在an/2+1:n中计算出S

27、2=3) 最优值： S1+S2/21/2maxnki nk ia jkk iaan/2+1*an/2/2 1/2 1maxjknj nk na ijleftsleftsumrightsrightsum int MaxSubSum(int *a, int left, int right) 数组 子段左界 子段右界 int sum=0 if (left= =right) sum=aleft 0 ? aleft:0; else int center=(left+right)/2; 一分为二 int leftsum= MaxSubSum(a, left, center); 求左子段最优值 int ri

28、ghtsum=MaxSubSum(a, center+1, right,); 求右子段最优值 int s1=0; int lefts=0; for (int i=center; i = left; i-) /*假设为第3种情况， 求左子段中的最优子段和值s1，由中点开始，自右向左搜索 lefts+=aj; if (leftss1) s1=lefts; int s2=0; int rights=0; for (int i=center+1; i s2) s2=rights; sum=s1+s2; 与第1、第2种情况比较 if (sumleftsum) sum=leftsum; if (sum0时

29、，时，bj=bj-1+aj， 当当bj-1=0时时, bj=ajn故得到如下递归方程： max 1 , ,1b jb ja j a jjn问题：a1, a2, , aj-1, aj, 指标：bj 子问题: a1, a2, , aj-1, 指标: bj-1 子问题: aj, 指标: ajnint MaxSum(int n, int *a) /*计算长度为n的最大子段和 int sum=0; b=0; for (int i = 1; i 0) b+=ai; else b=ai; if (bsum) sum=b; return sum; 从序列左端第1个元素a1开始，自左向右，根据递归方程，逐步计算

30、bi, 1in。 算法时间、空间复杂性均为O(n)。-2, 11, -4, 13, -5, -2用多边形顶点的逆时针序列表示凸多边形，即P=v0,v1,vn-1表示具有n条边的凸多边形。若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形vi,vi+1,vj和vj,vj+1,vi。多边形的三角剖分多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T三角形顶点：凸多边形顶点，边：多边形边、弦。最优值？！：给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w（如欧氏距离）。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形

31、上权之和为最小 最优值。 示例： 利用三角剖分，计算GSM/CDMA网络小区覆盖范围Voronoi图矩阵连乘/表达式的完全加括号方式问题与三角剖分问题具有相似性对应于相同理论模型，可相互归结(reduction): 1）多个矩阵的排列顺序 对应于图中顶点排列顺序 2）序列中2个矩阵的加括号 (Ai Al) 对应于 顶点Ai 与Al间的边或弦表达式的完全加括号问题可以表示为一棵完全二叉树，称为表达式的语法树 e.g. 完全加括号的矩阵连乘积(A1(A2A3)(A4(A5A6)所相应的语法树如图 (a)所示。vk(A1(A2A3)(A4(A5A6)多出的一条边n个矩阵连乘A1,n对应于凸(n+1)

32、边形的三角剖分凸多边形v0,v1,vn-1的三角剖分也可以用语法树表示。例如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树表示：1） 树根节点对应V0V62）叶节点对应边Vi-1Vi3）非叶结点对应剖分多边形的弦边三角剖分与矩阵连乘积对应关系1. 矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。2. 三角剖分中的一条弦vivj，ij，对应于矩阵连乘积Ai+1:j。凸多边形的最优三角剖分问题有最优子结构性质： 根据顶点vk，将序列分为2部分v0,v1,vk、 vk+1,v1,vn-1 若凸(n+1)边形P=v0,v1,vn-1的最优三角剖分T包含三角形v0vk

33、vn，1kn-1，例如图(b)中的V3 ，则T的权为3个部分权的和：1）三角形v0vkvn的权， e.g. v0v3v62）子多边形v0,v1,vk权, e.g. v0v1v2v33) 子多边形vk,vk+1,vn权, e.g.v3v4v5v6子问题划分：一分为三可以断言： 由T所确定的这2个子多边形的三角剖分也是最优的。 因为若有v0,v1,vk或vk,vk+1,vn的更小权的三角剖分将导致T不是最优三角剖分的矛盾。 问题/子问题形式化表述： j-i+2个顶点组成的多边形Pvi-1,vi,vj, 1i j n问题/子问题最优化目标 tij，1ijn, 凸子多边形vi-1,vi,vj的最优三角

34、剖分所对应的权函数值。 为方便起见，设退化的多边形vi-1,vi具有权值0。原问题目标：凸(n+1)边形P的最优权值为t1n最小化72n问题归结：原问题 子问题(问题规模更小) 原问题: Pvi-1,vi,vj, 最优解:ti,jPvi-1,vi,vkTravi-1,vk,vjPvk,vk+1,vj（1）（2）（3）e.g. i=0, k=3, j=6vk(A1(A2A3)(A4(A5A6) 子问题最优解： tvi-1, vk wvi-1vkvj tvk+1, vj 73tij的值利用最优子结构性质递归地计算:1) 当j-i1时，凸子多边形至少有3个顶点。 /* vi-1,vi,vj2) 用顶

35、点vk, 进行子问题划分3）由最优子结构性质，tij的值应为tik的值加上tk+1j的值，再加上三角形vi-1vkvj的权值，其中ikj-1由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使tij值达到最小的位置由此，tij可递归地定义为：jijivvvwjktkitjitjkijki)(1min010606006min 0 16()kkijttkt kw v v vij e.g. void MinWeightTriangulation(int n，Type * t, int *s) for (int i = 1; i = n; i+) tii

36、= 0; for (int r = 2; r = n; r+) for (int i = 1; i = n-r+1; i+) int j= i + r 1 tii = ti+1j + w(i-1, i, j) sii =i; for (int k =i+1; k i+r-1; k+) int u=tik + tk+1j + W(i-1,k,j); if (u10,000，采用复杂性阶次较高的动态规划算法求解，运行时间过长，不具有实用性！nE.g. 见下页例子87Assume N = 100,000 and processor speed is 1,000,000,000 operations

37、per second(10亿次/秒，普通微机运算速度)FunctionRunning Time2N3.2 x 1030086 yearsN43171 yearsN311.6 daysN210 secondsN N0.032 secondsN log N0.0017 secondsN0.0001 seconds N3.2 x 10-7 secondslog N1.2 x 10-8 seconds88n假设单核微机 1. 主频为 F=3GHz=3 109次/每秒 2. 1个机器指令周期时长 t=1/F = (1/3) * 10-9 秒 3. 1条指令平均需要3个周期，则1条指令平均执行时间为 (3

38、/3) * 10-9 秒nCPU运算速度： 每秒执行的指令数目 = 1 / 1条指令平均执行时间 = (3/3) * 109 条/秒 = 10亿条指令/秒 n如果基于微机平台，采用动态规划三角剖分方法，如果基于微机平台，采用动态规划三角剖分方法，计算基站计算基站Voronoi图，当基站数目图，当基站数目n10,000时，运行时，运行时间时间2-3天，不可接受天，不可接受!89动态规划法的适用性动态规划法的适用性n需要结合实际问题背景，优化算法，降低算法复杂性 分析递归表达式，避免过度搜索子问题的各种组合，根据启发式信息，选取某一种或少数某几种组合由求解全局最优解（最小、最大），改为求解全局次优

39、解（比较小、比较大）nE.g. 三角剖分n不需要搜索、比较Pvi-1,vi,vj中的每个vk，而是按照一定启发式信息，优先选取某个剖分点vk，e.g. vk= v3，避免最内层循环，将算法复杂性由O(n3) 降为O(n2)jijivvvwjktkitjitjkijki)(1min01. 穷搜90void MinWeightTriangulation(int n，Type * t, int *s) for (int i = 1; i = n; i+) tii = 0; for (int r = 2; r = n; r+) /*第1层循环 for (int i = 1; i = n-r+1; i+

40、) /*第2层循环 int j= i + r 1 tii = ti+1j + w(i-1, i, j) sii =i; for (int k =i+1; k i+r-1; k+) int u=tik + tk+1j + W(i-1,k,j); if (utij) tij) =u; sij) =k; 利用启发式信息，在第2层循环内部，直接选取某个vk，避免第3层循环，算法时间复杂性降为O(n2)Z找到更好的划分，并记录结果t: 记录子问题最优值s：记录子问题最优划分点 子问题vi、vj, 子问题规模r=j-i+1自下而上，不同规模r的子问题ii+1j91动态规划法的适用性动态规划法的适用性nE.

41、g. 利用启发式（而非动态规划）三角剖分算法，得到以基站为顶点的Delaunay三角网有多种启发式构造方法n在此基础上转换为Voronoi图，计算全网基站覆盖范围n优点：算法运行时间可接受，e.g. 4小时左右n缺点： 1. 有可能无法完全满足三角剖分要求，极少部分的弦相交 2. Delaunay三角网上的各三角形边之和有可能非全局最小，而只是局部极小、比较小n实际问题中，从实用性、适用性角度，实际问题中，从实用性、适用性角度， tradeoff ! between 算法解质量算法解质量and 算法运行时间算法运行时间解质量：解质量：是否达到全局最大、最小是否达到全局最大、最小多边形游戏是一个

42、单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。游戏第1步，将一条边删除。随后n-1步按以下方式操作：(1)选择一条边E以及由E连接着的2个顶点V1和V2；(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。问题:对于给定的多边形，计算最高得分。102294153627v7v1v2v3v4v5v6+*1234567102294153627v7v1v2v3v4v

43、5v6+*234567Step1: 1022v7v1+1v7Step2: 1022v7v1+132v17102294153627v1v2v3v4v5v6+*234567Step2: 32v1794153627v2v3v4v5v6+*234567顶点减为6个Step3: v173294153627v2v3v4v5v6+*23567415v3v4+419v34Step3: v173293627v2v5v6+*2356719v34顶点减为5个n游戏的得分/最优值： 最后所剩顶点上的整数值n目标：最大化最后所剩顶点上的整数值n问题解的结构： 不同的删除边、合并顶点的顺序问题形式化表述问题形式化表述p(

44、i，j) ： 在所给多边形中，从顶点i(1in)开始，长度为j(链中有j个顶点)的顺时针链p(i，j) 可表示为： vi, opi+1, , opi+j-2, vi+j-1e.g. i=2, j=5 p(2,5): v2, *, v3, +, v4, *, v5, +, v6 op3+1=+,94153627v2v3v4v5v6+*3456如果这条链的最后一次合并运算最后一次合并运算在opi+s处发生(1sj-1)，则可在opi+s处将链p(i，j)分割为2个子链： 1）p(i,s) 2）p(i+s, j-s)E.g. 1) i=2, j=5 , s=2, opi+2=op4=op3+1=+2

45、) p(i,s)=p(2,2): v2, *, v33) p(i+s, j-s)=p(4, 3): v4, *, v5, +, v6 P(i, s) 与子链的关系与子链的关系由由2条子链合并而成条子链合并而成93627v2v5v6+*35619v3494153627v2v3v4v5v6+*3456p(i,s)=p(2,2) m1= 36p(i+s, j-s)=p(4, 3) m2=max(36+27)*15, 27+36*15设m1是对子链p(i，s)的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中得到的最小值和最大值。e.g. p(i,s)=p(2,2), m1=9*4=36m2

46、是p(i+s，j-s)的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。 e.g. p(i+s, j-s)=p(4, 3), 15*36 +27 m2 (27+36)*5 依此定义有am1b，cm2d 子链p(i，s)和p(i+s，j-s)的合并方式决定了p(i, j)在opi+s处断开后的合并方式，在opi+s处合并后其值为 m=(m1) opi+s (m2)e.g. opi+s =op2+2=op3+1=+,有以下性质：(1)当opi+s=+时，显然有a+cmb+d(2)当opi+s=*时，有minac，ad，bc，bdmmaxac，ad，bc，bd 换句话

47、说，主链的最大值和最小值可由子链的最大值换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。和最小值得到。 递归求解n需要同时求子链P(i, j)=vi, opi+1, , opi+j-2, vi+j-1合并的最大最小值n最优化目标： mi,j,0：p(i,j)合并的最小值 mi,j,1： p(i,j)合并的最大值合并的最大值n最优合并在opi+s处将p(i,j)分为2个长度小于j的子链p(i,s)和p(i+s, j-s)n记2个子链合并后的最大最小值为 a= mi, i+s, 0, b= mi, i+s, 1 c= mi+s, j-s, 0, d= mi+s, j-s, 1n将p(i

48、, j)在opi+s处断开后的最大值记为 maxf(i, j, s) , 最小值记为 minf(i, j, s) e.g. maxf(2, 5, 2)minf(i, j, s)= 1) a+c opi+s=+2) minac, ad, bc, bd, opi+s=*maxf(i, j, s)=1) b+d opi+s=+2) maxac, ad, bc, bd, opi+s=*最优断开位置s有1s j-1共j-1种情况，故有如下递归方程：1） m(i, j, 0) = min minf(i, j, s), 1s j, 1i, j n m(i, j, 1) = max maxf(i, j, s)

49、, 1s j, 1i, j n2）边界条件 m(i, 1, 0) = vi, 1i n; m(i, 1, 1) = vi, 1i n;方法：采用图像变位压缩存储格式1) 将所给的象素点序列p1, p2,pn, 0pi255, 分割成m个连续段S1,S2,Sm2) 第i个象素段Si中(1im)，有li个象素,且该段中每个象素都只用bi (8) 位表示 计算机中，一幅有n个像素点的图像用象素点灰度值序列p1, p2, pn表示, 整数pi, 1in, 表示图像中像素点i的灰度值, 范围在0255，1个像素点最多最多用8 bits表示，。 E.g. iPhone4：Retina屏幕， 3.5英寸64

50、0960像素, 点距0.007705cm，像素密度326像素/英寸(ppi)，1600万色目标：如何用更少的bits表示不同的像素点灰度值灰度值小，用的bits少方法：采用图像变位压缩存储格式1) 将所给的象素点序列p1, p2,pn, 0pi255, 分割成m个连续段S1,S2,Sm2) 第i个象素段Si中(1im)，有li个象素,且该段中每个象素都只用bi (8) 位表示0 1 7 3 5 9 13 11 15 33 35 41 44 51 39 219 241 180 209015，9个像素, 4bits3263，6个像素, 6bits128255，4个像素, 8bits等长存储: (9

51、 + 6 + 4)*8 = 152 bits;3段变长存储：9*4 + 6*6 + 4*8 = 104 bits2段划分设 ，表示前i-1个段的像素总数，则第i个象素段Si为11ikklit,1ilititippS, 1 i m， 见下页 一幅图像的邻近区域内的颜色一般相近，需要使用的表达颜色的bits相近S1S2S3p1pnS1S2SmSi第i段有li个象素，每个像素用bi bits表示前i-1个段的像素总数ti,1ilititippS第i段像素集合：Si-1前i-1个段像素为： p1,p2, , ptipti11ikklit对第Si段，设 ，表示该段像素值最大的像素所需灰度值存储位数，hi

52、=bi8。存储空间分析：需要表示出每段的段长、该段所用位数每段的段长、该段所用位数1）对Si段中每一个像素pi，其需要的灰度值存储需要一定的位数bi来存储, 需要3 bits表示bi的大小2）假设Si段中的像素总数li限制为1 li 255，需要用8bits表示li的数值3）第i个象素段所需的存储空间为li*bi+11位4）按此格式存储象素序列p1,p2,pn，分成m段，需要 bits 的存储空间。1maxlog1kilitkitiphmibilmi11*1位数bi=300000长度li=4011100第Si段有4个像素，每个像素占3bits总位数23 bits = 3 + 8 + 4*3 确

53、定象素序列p1, p2, pn的最优分段，使得依此分段所需的存储空间最少, 约束条件： 每个分段的长度不超过256，即每个分段中的像素总数不超过256优化变量：分段数目、每段段长目标：总存储空间极小化设li, bi, 1i m, 是p1,p2,pn的最优分段。 显而易见，见下页1) l1, b1是p1,pl1的最优分段 2) li, bi， 2i m, 是pl1+1,pn的最优分段 , 即图象压缩问题满足最优子结构性质。原问题: p1,p2,pn，解: m段，每段长li, 位数bi, 1i m子问题1: 第1段p1, pl1, 解: l1, b1子问题2: 剩余部分pl1+1 , , pn,

54、解: li, bi, 2i m p1pnS1S2SmSili个象素，每个像素用bi bits表示前i-1个段的像素总和ti,1ilititippS第i段像素集合：Si-1l1个象素，用b1 bits表示 设si，1in，是前i个象素序列p1,pi的最优分段所需的存储位数。由最优子结构性质易知：其中11), 1max(b*min256,min1ikikkisisik1maxlog),bmax(kjkipji1bmax(1, )logmax 1ki kk iikip 表示最后1段的长度、位数最后一段i-k+1像素所占位数p1pipi-k断点1k 256第2个子问题pi-k+1, pi, 1）长度k

55、，有k个像素。2）由于每段长度=256，因此断点k的位置最多有256个；再考虑到原问题的长度有可能小于256，因此断点位置: 1k min(256,i)3）最后一段pi-k+1, pi, 有k个像素，每个像素最多需要的存储位数原问题： p1, pi-k, pi-k+1,pi，长度i子问题1: p1, pi-k, 长度i-k子问题2:pi-k+1, pi, 长度k最优解si最优解si-k最后1段1bmax(1, )logmax 1ki kk iikip 算法复杂度分析：算法复杂度分析：由于算法compress中对k的循环次数不超这256，故对每一个确定的i，可在时间O(1)内完成的计算。因此整个

56、算法所需的计算时间为O(n)119 给定n种物品1, 2, 3, ,n和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。 问：应如何选择装入背包的物品，使得装入背包中装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题： 找出1个n元0-1向量(x1,x2,xn), xi0,1, 1in, 使得niiixv1maxnixCxwiniii1,1 , 01120n最优子结构性质 设(x1,x2,xn)是相对于n种物品1, 2, 3, ,n的1个最优解，则(x2,xn)是子问题2,3,4,n的1个最优解，即原问题最优解包括了子问题最优解证明：反证法2maxniiiv x20,

57、1,2niiiiw xCxin 121原问题：n种物品1, 2, 3, ,n子问题2：n-1种物品2, 3, ,n解: (x1,x2,xn)(最优)解: (x2,xn)(最优)子问题1：1解: (x1)122n问题的形式化表示： n个物品的背包问题的2个因素：1）物品1, 2, 3, , n2) 背包容量C将n个物品背包问题的不同子问题表示为：1）i：子问题i, i+1, , n的起点2）j: 子问题的背包容量12 i-1 i i+1 n-1 n原问题子问题原问题表示为123给定n个物品1,2,n, 其子问题定义为：nikkkxvmaxnkixjxwknikkk,1 , 0 子问题的最优值定义

58、为m(i, j)，即m(i, j)是背包容量为j，可选择物品为i, i+1, , n时0-1背包问题的最优值。 原问题的最优解可表示为m(1, c)124n根据最优子结构性质，可以建立计算m(i, j)的递归式: 1）边界条件：对于只有1个物品n、背包容量为j的子问题( , )00nnnjwvm n jjw容量j大于物品n的重量wn，n可放入背包，放入后价值为vn容量j小于物品n的重量wn，n无法放入背包，价值为01252）对子问题说明：考察子问题中的物品i, i+1, i+2, , n-1, n， i ) 如果第i种物品重量wi大于容量j，可以不考虑第i种物品，子问题缩减为规模更小的ii)如

59、果第i种物品重量wi小于容量j，第i种物品可以考虑放入，分为2种情况： *情况1：将第i种物品放入，对总价值的贡献为vi，剩余容量为jwi ，子问题缩减为规模更小的 *情况2：第i种物品不放入，背包容量仍为j ，子问题缩减为规模更小的(0,1) (1, ),(1,)( , )0(1, )maxiiiixim ij m ijwvjwm i jjwm ij126: i, i+1, i+2, , n-1, n: i+1, i+2, , n-1, nijwiwj是否放入物品i放入不放背包无法容纳物品i背包可以容纳物品i: i+1, i+2, , n-1, n: i+1, i+2, , n-1, nXi

60、=0Xi=0Xi=1127Knapsack算法：算法：p73算法复杂度分析：算法复杂度分析： 从m(i, j)的递归式容易看出，算法需要O(nc)计算时间 当背包容量c很大时，算法需要的计算时间较多。 例如，当c2n时，算法需要(n2n)计算时间。 128n说明： 子问题表示方法的设计是关键，不同子问题表示方法影响到问题分解/合成、递归方程、算法实现方法、效率E.g. 1. 矩阵连乘：Ai, j = O(n3)2. 最长公共子序列中的X(m)=x1,x2,xm和Y(n)=y1,y2,yn，Z(k), Cmn, O(m+n)3. 最大子段和:子问题: a1, a2, , aj, 指标bj, O(

61、n)4.最优三角剖分：凸子多边形vi-1,vi,vj，最优值tij，1ijn, 对应的权函数值, O(n3)5. 多边形游戏：从顶点i(1in)开始，长度为j(链中有j个顶点)的顺时针链p(i，j)，即vi, opi+1, , vi+j-1，mi,j,0, mi,j,1jiiAAA.11296.图像压缩：前i个象素序列p1,pi， Si, O(n)7. 背包问题中的子问题，指标mi, j, O(nc)8. 作业调度：作业子集SN=1, 2, 3, , n，T(N,0), T(S,t)9. 最优二叉搜索树：最优二叉搜索树Tij，平均路长为pij，130n设S=x1,x2,xn是有序集，且x1x2

62、 T(S,b(1)，设是作业集S在机器M2的等待时间为b(1)情况下的一个最优调度。 则(1)， (2)， (n)是N的一个调度，且该调度所需的时间为a(1)+T(S,b(1)a(1)+T。 这与是N的最优调度矛盾。 故TT(S,b(1)，从而T=T(S,b(1)，并有： T(N, 0) = a(1) + T( N-(1), b(1) 原问题N，子问题S=N-(1), 这就证明了流水作业调度问题具有最优子结构的性质这就证明了流水作业调度问题具有最优子结构的性质。递归方程：递归方程： 由流水作业调度问题的最优子结构性质可知，说明： 依次选取各个作业i，作为第1个处理的作业，从中选取所需处理时间最

63、短者. E.g.),(min)0 ,(1iinibiNTaNT13(1,2,3,0)min(1,2,3 ,)iiiTaTib 一般情况下，对作业子集S（见下图说明） e.g. )0 ,max,(min),(iiiSiatbiSTatST1,3111333(1,3, )min(1,3 ,max,0)min(3,max,0),(1,max,0)iiiiTtaTibtaaTbtaaTbtaM1M2a1a3a2b1b3b2tT(1,3, t)maxtai, 0的说明: 在机器M2上，作业i必须在maxt, ai之后才能在M2开始； 因此，在M1上完成作业i后，在机器M2上还需时间，才能完成对作业i的加

64、工E.g.1 考虑i=1, maxta1, 0, ta3 在M2上，作业3必须在maxt, a3= t=b1之后才能开始; 在M1上完成作业3后，M2还需 maxt, a3 a3 + b3 = b1 a3 + b3 , 才能完成对作业3的加工M1M2a1a3a2b1b3b2tT(3, t)b1 a3 + b3利用不等式，对算法进行优化简化。 设是作业集S在机器M2的等待时间为t时的任一最优调度，即T(S, t)最优。 若(i)=1, (j)=2，即最优调度(S)=i, j, 中的第1个作业为i，第2个作业为j，由动态规划递归式可得: T(S,t)= ai + T(S-i, bi+maxt-ai

65、,0) = ai + aj + T(S-i,j,tij)其中，表示对Si,j在M2上的等待时间maxmax,0,0maxmax,0,max,0max ,ijjiiijiijjijijijijiiijjjitbbtaabbataabbbbbaabata abtaaaE.g. S=1,2,3, (S)=2, 1,3, i=2, j=1; t=a2. T(S, t)= ai + T(S-i, bi+maxt-ai,0) = a2 + T(S-2, b2+maxt-a2,0) = a2 + T(1,3, b2+0) = ai + aj + T(S-i,j,tij) = a2 + a1 + T(3, t

66、21)M1M2a1a3a2b1b3b2tT(3, t21)T(1,3, b2)t212112211222111212121212212121121121212121221maxmax,0,0maxmax,0,0maxmax,0,maxmax,()max,0max,ijttbbtaabbaaabbbataabbbaaaabbbaabbbbata abbbaaa a21121221221212221221,0max ,max,bbbbaat aab abbaaa aab ab 如果作业i和j满足: minbi, aj minbj,ai ，则称作业i和j满足JohnsonJohnson不等式不等式。E.g. 对i=1, j=3 minb1, a3=b1 minb3,a1=b3M1M2a1a3a2b1b3b2M1M2a1a3a2b1b3b2T13T31交换作业1、3的调度顺序后，增加了调度时间对i执行在前、j执行在后的调度，如前所述，有： 交换作业i和作业j的加工顺序（j在前、i在后），得到作业集S的另一调度，它所需的加工时间为： T(S,t)=aj + ai + T(S-j,i,tji) 其