(算法分析设计)第3章动态规划课件.ppt

1、12n动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=3n但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。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)计算计算Fibonacci数列的递归算法：数列的递归算法：int F(int n,int aN)if(n=

2、0)return 0;if(n=1)return 1;return F(n-1,a)+F(n-2,a);01234567890112358132134求解求解Fibonacci数数F(9)的填表过程的填表过程 如下：如下：由于计算由于计算F(n)是以计算它的两个重叠子问题是以计算它的两个重叠子问题 F(n-1)和和F(n-2)的形式来表达的，所以，可以设计一张表的形式来表达的，所以，可以设计一张表填入填入n+1个个F(n)的值的值(避免重复计算避免重复计算)。动态规划算法的基本思想 动态规划算法的基本思想动态规划算法的基本思想 其基本思想与分治算法的思想类似分而治之分而治之 对每个子问题都只计

3、算一次，不管该子问题以后是否会被用到，都将其保存到一张表中，避免每次遇到各个子问题都要重复计算答案。与分治法的不同之处 分治法子问题的个数往往是问题规模的指数函数；动态规划分解后的子问题往往不互相独立，不同的子问题的个数只是多项式量级 采用记录表的方法来保存所有已解决问题的答案 一个最优化多步决策问题适合用动态规划法求解有两个要素：动态规划算法的一般步骤动态规划算法的一般步骤动态规划算法的一般步骤找出最优解的性质，并刻画其结构特征；递归地定义最优值；以自底向上的方式计算出最优值；1.根据计算最优值时得到的信息，构造最优解；动态规划算法动态规划算法的基本步骤的基本步骤如只需要求出如只需要求出最优

4、值最优值，则步骤，则步骤4可省略；可省略；如需要求解问题的如需要求解问题的最优解最优解，则必须执行步骤，则必须执行步骤4通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）多边形游戏；（6）图像压缩；（7）电路布线；（8）流水作业调度；（9）背包问题；（10）最优二叉搜索树。矩阵连乘问题矩阵连乘问题矩阵连乘问题。连乘积个矩阵的察这。矩阵连乘问题就是考是可乘的，与，其中，个矩阵给定矩阵连乘问题niinAAAnniAAAAAn.1,.,2,1.21121Ai的列数的列数=Ai+1的行数的行数)43(2(1()4)32(1

5、()43)(21()4)32(1()432(1(4321AAAAAAAAAAAAAAAAAAAAAAAA矩阵连乘满足结合律两个矩阵的相乘问题 两个矩阵的相乘问题两个矩阵的相乘问题 A为p*q的矩阵 B为q*r的矩阵 C=AB为p*r的矩阵计算C的标准算法，共需要p*q*r次数乘找不到切入点找不到切入点考察A1,A2,A3三个矩阵连乘 假定：假定：A1为为10*100的矩阵的矩阵 A2为为100*5的矩阵的矩阵 A3为为5*50的矩阵的矩阵 切入点切入点 考察不同计算次序下的计算量考察不同计算次序下的计算量不同计算次序下的计算量 计算次序一：（A1A2）A3 计算量=10*100*5+10*5*

6、50=7500次数乘次数乘 计算次序二：A1（A2A3）计算量=10*5*50+10*100*50=75000次数乘次数乘矩阵的计算量与矩阵的计算量与计算次序有关计算次序有关例例 有有4个矩阵个矩阵A,B,C,D，它们的维数分别是，它们的维数分别是:A=5010，B=1040，C=4030，D=305 连乘积连乘积ABCD共有五种加括号的方式共有五种加括号的方式(AB)C)D87500(AB)(CD)36000A(B(CD)10500(A(BC)D34500A(BC)D)16000矩阵连乘积的最优计算次序问题。所需要的数乘次数最少计算次序，矩阵连乘积该的计算次序，使得按照如何确定矩阵连乘积题：

7、矩阵连乘的最优次序问的维数为个矩阵对于给定的相继niiinAAAnippAAAAn.,.,2,1,.,21121方案1：穷举搜索法 穷举搜索法穷举搜索法 列举出所有可能的计算次序，选取其中数乘最小的计算次序；一定可以找到最优计算次序 P(n)随n的增长呈指数增长)4(211)()1()(1)()(11)(2/311nnnnnCnCnPnknPkPnnPnnk其中天天 啊啊用动态规划法求解用动态规划法求解分析最优解的结构分析最优解的结构建立递归关系建立递归关系计算最优值计算最优值构造最优解构造最优解求解步骤 分析最优解的结构分析最优解的结构 建立递归关系 计算最优值 构造最优解分析最优解的结构

8、将矩阵连乘积AiAi+1Aj记作Ai:j 把问题转化成考察把问题转化成考察A1:n的最优计算次序问题的最优计算次序问题 设计算次序在设计算次序在Ak处将矩阵断开最优，则总计处将矩阵断开最优，则总计算量为：算量为：A1:k 的计算量加上的计算量加上Ak+1:n的计算的计算量，再加上量，再加上A1:k 和和Ak+1:n相乘的计算量。相乘的计算量。l关键特征关键特征lA1:n的最优计算次序所包含的计算矩阵子链A1:k和Ak+1:n的次序也是最优的。（可用反证法证明）问题的最优解包含了其子问题的最优解问题的最优解包含了其子问题的最优解，这种性质称为最优子结构性质最优子结构性质。最优子结构性质是该问题可

9、用动态规划算法求解的第一个标志最优子结构性质是该问题可用动态规划算法求解的第一个标志A1(A2A3)|A4(A5A6)最优解：A1:6=A1:3+A4:6+A1:3*A4:6 A1:3与A4:6也必分别为最优解（计算总量最少），因为其无关；若有A1:3小于A1:3,由后两项不改变，则A1:6不是最小，故与前提矛盾；对矩阵：A1A2A3A4A5A6，可能的最优解求解步骤 分析最优解的结构 建立递归关系建立递归关系 计算最优值 构造最优解建立递归关系 递归地定义最优值。设计算Ai:j,1ij n，所需的最少数乘次数为mij则原问题的最优解为m1n 考察两种情况考察两种情况 i=j;i=j;ij;i

10、j;niiimAjiAjii,.,2,1,0:为单一矩阵时，当当i=j时当ij时jkipppjkmkimjimjimji11算时，利用最优子结构计当问题：问题：如何确定如何确定k？分析：分析：因为，因为，ikj，所以，所以k的位置只有的位置只有j-i种可能，即种可能，即ki,i+1,ji,i+1,jk k是这是这j-ij-i个位置中使计算量达到最小的位置。个位置中使计算量达到最小的位置。jipppjkmkimjijimjkijki1min01sij=ksij=kjkippp1为为Ai:k 和和Ak+1:j相乘的计算量相乘的计算量 各各mij的值给出了子问题最优解的代价。为的值给出了子问题最优解

11、的代价。为了帮助跟踪构造最优解，定义了帮助跟踪构造最优解，定义sij为使为使mij取最优值时对应的取最优值时对应的k值值。mij=0+mi+1j+pi-1*pi*pj;for(k=i+1;k j;k+)t=mik+mk+1j+pi-1*pk*pj;if(t m12,m23,m34,m45,m56 m13,m24,m35,m46 m14,m25,m36 m15,m26 m16A1A2A3A4A5A63035351515551010202025113752010350437555427125205351000262554 3213000201535250005322min52541531521pp

12、pmmpppmmpppmmm计算矩阵连乘积计算矩阵连乘积A1A2A3A4A5A6712531 2 3 4 5 6 123456ij0 15750 7875 9375 11875 15125 0 2625 4375 7125 10500 0 750 2500 53750 1000 3500 0 5000 0mij123456ij1 2 3 4 5 6 0 1 1 3 3 3 0 2 3 3 3 0 3 3 3 0 4 5 0 5 0sij计算结果void MatrixChain(int*p，int n，int*m，int*s)for(j=2;j=1;i-)mij=mi+1j+pi-1*pi*pj

13、;sij=i;for(k=i+1;k j;k+)t=mik+mk+1j+pi-1*pk*pj;if(t mij)mij=t;sij=k;/算法的计算时间上界为算法的计算时间上界为O(n3)*p 存放存放Ai的维数；的维数；*m 存放最优值；存放最优值；*s 存放断开位置，用于递归地构造存放断开位置，用于递归地构造相应的最优解。相应的最优解。算法复杂性分析优于穷举搜索方法算法的占用空间为算法的计算时间上界为。重循环的总次数为，循环体内的计算量为重循环。的和于对算法的主要计算量取决)()()(3)1(3,233nOnOnkir求解步骤 分析最优解的结构 建立递归关系 计算最优值 构造最优解构造最优

14、解构造最优解 构造最优解构造最优解 利用算法实现过程中保存在sij中的分割点信息来重构最优解 sij中的数k表明计算矩阵Ai:j的最佳方式应在矩阵Ak和Ak+1断开，即最优加括号方式为(Ai:k)(Ak+1:j)(Ai:k)(Ak+1:j)/根据计算出的断点矩阵根据计算出的断点矩阵s指示的加括号方式，指示的加括号方式，输出计算输出计算Ai:j的最优先次序。的最优先次序。void Traceback(int i,int j,int*s)if(i=j)return;Traceback(i,sij,s);Traceback(sij+1,j,s);coutisij“;”sij+10)return mi

15、j;if(i=j)return 0;mij=LookupChain(i+1,j)+pi-1*pi*pj;sij=i;for(k=i+1;kj;k+)t=LookupChain(i,k)+LookupChain(k+1,j)+pi-1*pk*pj;if(tmij)mij=t;sij=k;mij=u;return u;备忘录方法的复杂性分析。其子问题规模为仍为性备忘录方法的算法复杂同动态规划算法相似，)(),(23nnO两种方法应用方面的考虑 当一个问题的所有子问题都至少要解一次所有子问题都至少要解一次时，建议使用动态规划算法建议使用动态规划算法 动态规划算法没有任何多余计算 当子问题空间中的部分

16、子问题不需要求解部分子问题不需要求解时，建议使用备忘录方法建议使用备忘录方法 从其控制结构可以看出，该方法只求解那些需要求解的子问题最长公共子序列最长公共子序列51破译密码时，往往需要对比不同密码串的共同序列；在生物学中，常常要比对不同有机体的DNA序列。有机体的DNA可以表示为四种碱基A,C,T,G的字符序列，可以通过序列直接的相似性来推断不同物种之间的进化关系。相似度概念可以形式化为最长公共子序列问题。公共子序列越长，相似度可以认为越高。DNA序列比对的应用：亲子鉴定；犯罪认定；52若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk是X的子序列是指存在一个严格递增下标序列i1,

17、i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列公共子序列。给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。找出一个而不是“唯一的”；公共子序列在原序列中不一定是连续的 举例举例X=A,B,C,B,D,A,B.Y=B,D,C,A,B,A.Z=B.C.AZ是是X和和Y的一个公共子序列（长度为的一个公共子序列（长度为3）*Z不是不是X和和Y的最长公共子序列的

18、最长公共子序列B,C,B,A是是X和和Y的最长公共子序列（长度为的最长公共子序列（长度为4）穷举法求解LCS LCS：longest common sequence 需要指数时间：对X的所有子序列，检查它是否是Y的子序列，并记录最长的公共序列；若X长m，X有2m个子序列；对每条子序列，检查是否是Y的子序列，需要O(n)时间，从而需要O(n2m)，即指数时间来搜索。54动态规划算法求解LCS 简化算法 从最长公共子序列的长度入手。让公共子序列不断增长，使其自己成长为最长公共子序列。定义序列s的长度为|s|。策略：考虑X、Y的前缀 定义cik=|LCS(X1i,Y1,k)|，找其前缀的最长公共子序

19、列。则有cmn=|LCS(X1m,Y1n)|=|LCS(X,Y)|。5556设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk，则(1)若xm=yn，则zk=xm=yn，且zk-1是X1m-1 和Y1n-1的最长公共子序列。(2)若xmyn且zkxm，则Z是X1m-1和Y的最长公共子序列。(3)若xmyn且zkyn，则Z是X和y1n-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结最优子结构性质构性质。子问题的递归结构分析的递归计算过程：的最长公共子序列问题，求解YXyyyYx

20、xxXnm,.,.,2121的最长公共子序列。、，就可以得到加上后在其尾部的最长公共子序列，然、时，找出当YXyxYXyxnmnmnm)(11的最长公共子序列、长者为这两个公共子序列中较；的一个最长公共子序列、）找出（；的一个最长公共子序列、）找出（题：时，需要求解两个子问当YXYXYXyxnmnm1121公共子问题：公共子问题：计算计算Xm-1、Yn-1的最长公共子序列的最长公共子序列 定义LCS的递归解 为LCS(xm-1,y)和LCS(x,yn-1)都包含了寻找LCS(xm-1,yn-1)的子问题。LCS问题的解涉及求解最优解的值的递归式。5859由最长公共子序列问题的最优子结构性质建立

21、子问题最优值的递归关系。用cik记录序列Xi和Yj的最长公共子序列的长度。其中，Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或k=0时，空序列是Xi和Yj的最长公共子序列。故此时Cik=0。其它情况下，由最优子结构性质可建立递归关系如下：jijiyxjiyxjijijicjicjicjic;0,;0,0,01,1max1 110/bij记录记录cij的值属于哪类子问题的值属于哪类子问题LCSLength(int m,int n,char*x,char*y,int*c,int*b)for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;bij=2;else

22、cij=cij-1;bij=3;/时间复杂度为时间复杂度为O(mn)xm=yn，找Xm-1、Yn-1的最长公共子序列xmyn且zk xm，找Xm-1、Yn的最长公共子序列xmyn且zk yn，找Xm、Yn-1的最长公共子序列构造最长公共子序列 构造构造k长公共子序列长公共子序列利用bij 11.i1.j1.i 11.j 1 21.i1.j1.i 11.j 31.i1.j1.iib ijXYXYxb ijXYXYb ijXYX如果表示、的最长公共子序列是由、的最长公共子序列在尾部加上 所得到的子序列；如果表示、的最长公共子序列同、的最长公共子序列相同；如果表示、的最长公共子序列同1.j 1Y、的

23、最长公共子序列相同；62构造最长公共子序列构造最长公共子序列void LCS(int i，int j，char*x，int*b)/根据bij的值向回搜索;/在递归返回时打印LCS中的元素 if(i=0|j=0)return;if(bij=1)LCS(i-1，j-1，x，b);coutxi;else if(bij=2)LCS(i-1，j，x，b);else LCS(i，j-1，x，b);/时间复杂度为时间复杂度为O(m+n)最长子序列必定在x中，不需y凸多边形最优凸多边形最优三角剖分三角剖分凸多边形的性质一个凸七边形一个凸七边形凹多边形凹多边形n凸多边形的性质凸多边形的性质q多边形k平面上一条分

24、段线性闭合曲线q用多边形顶点的逆时针序列表示：P=V0,V1,Vn-1 表示具有n条边的凸多边形，n由一系列首尾相接的直线段组成。q凸多边形性质凸多边形性质n凸多边形边界上或内部的任意两点，其所连成的直线段上所有点都在该凸多边形的内部或边界上。v1v2v3v4v5v6v0v1v2v3v4v5v6v0一个凸七边形的两种三角剖分凸多边形最优三角剖分问题点的欧式距离。到为其中，如：权函数有很多定义方法上权之和为最小。三角剖分中各个三角形剖分所对应的权，即该三角剖分，使得该三角要求确定该凸多边形的。三角形上的权函数多边形的边和弦组成的，以及定义在由给定凸多边形jijiikkjjikjinvvvvvvv

25、vvvvvvwwvvvP|,|)(,.,110周长一个有趣的发现矩阵连乘问题矩阵连乘问题凸多边形最优凸多边形最优三角剖分问题三角剖分问题类似问题类似问题可能吗？可能吗？矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的特殊情形。表达式语法树 表达式语法树表达式语法树 一个表达式的完全加括号方式相应于一个完全二叉树，称为表达式的语法树。树中每一个叶结点表示表达式中的一个原子。有n个原子的完全加括号表达式对应于惟一的一个有n个叶结点的语法树，反之亦然。矩阵连乘积最优次序解矩阵连乘积最优次序解:(A1(A2A3)(A4(A5A6)(A1(A2A3)(A4(A5A6)凸多边形三角剖分问题的语法树

26、表示语法树的根结点语法树的根结点一般情况下，凸n边形的三角剖分对应于一个有n-1个叶结点的语法树，也可以根据一个有n-1个叶结点的语法树产生一个凸n边形的三角剖分凸凸n边形的边形的三角剖分三角剖分一个有一个有n-1个叶个叶结点的语法树结点的语法树凸凸n边形的边形的三角剖分三角剖分一个有一个有n-1个叶个叶结点的语法树结点的语法树n个矩阵的个矩阵的完全加括号完全加括号乘积乘积有有n个叶结点的个叶结点的语法树语法树n个矩阵的个矩阵的完全加括号完全加括号乘积乘积凸凸n+1边形的边形的三角剖分三角剖分v1v2v3v4v5v6v0A3A1A2A4A5A6A1A2A3A4A5A6表达式语法树与三角剖分的对

27、应表达式语法树与三角剖分的对应(a)(b):1)1(.121jiAjivvvvnAAAAjiiiin，对应于矩阵连乘积，三角剖分中的一条弦。边形中的一条边对应于凸中的每个矩阵矩阵连乘积。上的权函数值为：三角形，则定义如果矩阵维数为一一对应。多边形的边与凸，使得矩阵边形凸，定义与之相应的对于给定的矩阵链形。三角剖分问题的特殊情优次序问题是凸多边形最矩阵连乘积的最优计算kjikjikjiiiiiinnpppvvvwvvvnippvvAvvvPnAAA1111021)(,.,2,1,.,)1(.根据此定义，凸多边形P的最优三角剖分所对应的语法树给出矩阵链A1A2An的最优完全加括号方式。求解凸多边形

28、最优三角剖分问题 最优子结构性质最优子结构性质 最优三角剖分的递归结构 计算最优值 构造最优解最优子结构性质的。形的三角剖分也是最优所确定的这两个子多边由的权之和。和的权，子多边形三角形：的权为三个部分权的和，则包含三角形的最优三角剖分边形如果凸的最优子结构性质凸多边形三角剖分问题TvvvvvvvvvTnkvvvTvvvPnnkkknknkn,.,.,11,.,)1(1100021求解凸多边形最优三角剖分问题 最优子结构性质 最优三角剖分的递归结构最优三角剖分的递归结构 计算最优值 构造最优解最优三角剖分的递归结构jivvvwjktkitjijitniiitvvvvvnnjijitjkijki

29、iijii)(1min0,.,2,1,00,.,1,111序问题参考矩阵连乘积最优次。的权值设退化的多边形的权函数值。的最优三角剖分所对应凸子多边形为设算法可由矩阵连乘算法获得求解凸多边形最优三角剖分问题 最优子结构性质 最优三角剖分的递归结构 计算最优值计算最优值 构造最优解计算最优值 计算最优值计算最优值 参考参考矩阵连乘积最优次序解矩阵连乘积最优次序解 权函数的定义权函数的定义 算法实现请参看教材算法实现请参看教材 算法复杂性分析算法复杂性分析 空间复杂性：空间复杂性：O(n2)时间复杂性：时间复杂性：O(n3)求解凸多边形最优三角剖分问题 最优子结构性质 最优三角剖分的递归结构 计算最

30、优值 构造最优解构造最优解构造最优解分中的所有三角形。时间构造出最优三角剖可以用顶点的位置个一起构成三角形的第和记录了与三角形信息。中的所有中记录的最优三角剖分利用数组)(31nOvvjissji图象压缩图象压缩 一幅数字图像是点或图像元素的m行n列的矩形数组。m x n是图像的分辨率(resolution)，而这些点称为像素(pixel)。图像压缩：指以较少的比特有损或无损地表示原来的像素矩阵的技术。也称图像编码。图像数据的冗余主要表现为：图像中相邻像素间的相关性引起的空间冗余；图像序列中不同帧之间存在相关性引起的时间冗余；不同彩色平面或频谱带的相关性引起的频谱冗余。图像压缩方法：无损压缩

31、有损压缩：通过牺牲图像的准确率来达到加大压缩率的目的。如果我们容忍解压缩后的结果中有一定的误差，那么压缩率可以显著提高 有损压缩方法的压缩比：在图像压缩比大于30:1时，仍然能够重构图像；在图像压缩比为10:1到20:1时，重构图像与原图几乎没有差别；无损压缩的压缩比很少有能超过3:1图像压缩-标量量化 每像素8位的图像，可用标量量化将各像素的低4位删除来压缩，这样可以获得0.5的压缩比，同时颜色从256种变为只有16种。图象压缩 常见图象：常见图象：RGB彩色图与灰度图彩色图与灰度图 图象压缩：灰度图点取值图象压缩：灰度图点取值0-255 出发点：出发点：不同的点的灰度值可以用不同长度的二进

32、制编码表示，比如“166”可以用8位，而“5”只要用3位。因此可以根据图象中点的灰度值不同，将其分割成不同的子段，每个子段中灰度值的二进制编码都一致（比如分段中所有点的灰度值都在015之间，那么统一采用用4位编码即可），从而将原先采用8位编码的图象转变成根据分段中图象点的灰度范围灵活设定码长的图象，压缩了存储空间。图象的变位压缩存储方式)1(,.,1)1(,.,.,1112121mippSimiklitibilmiSiSSSmpppilititiikimn个像素段第，设位表示。用且该段中每个像素都只个像素，有中个像素段，第个连续段，分割成将图象中的像素点序列前前i-1个像素段所个像素段所占用的

33、位数占用的位数图象的变位压缩存储方式。，位表示只要用）即段的长度如果限定，位表示只要用之间的整数，为设miilmiilmiibibhpphikkilitkiti181,255(255113825501maxlog(1minmibilpppibili12111*,.,38*位的存储空间。需要，按此格式存储像素序列位间为个像素段需要的存储空第恢复信息恢复信息:li与与bi占的二进制位数占的二进制位数第第i段中段中,描述每个描述每个象素的灰度值所需象素的灰度值所需要的最大比特位数要的最大比特位数第第i段象素个数段象素个数分段中像素个数与每分段中像素个数与每个像素的位数乘积个像素的位数乘积图象压缩问题

34、。每个分段的长度其中，空间最少。按此分段所需要的存储的最优分段，使得列问题描述：确定像素序图象压缩问题2551,2550,.,21nippppin89实例分段信息所占长度最优子结构性质子结构性质。图象压缩问题满足最优的最优分段。是且的最优分段，是显然，的最优分段。是设,.,2,.,1,1,.,1,111121nllnppmiibilppblpppmiibil递归计算最优值1maxlog),max(,11),1max(*min,.,1,1255,min121kjkikipjibikibkkisispppniis其中由最优子结构性质：所需要的存储位数。的最优分段是像素序列设li，像素段i的长度即b

35、i，灰度值的二进制编码位数，表示从i到k中选择像素灰度值pi最大的值，加1后取对数再取整k简化处理)i前i-k个存储的位数加上后k个的存储空间 si的图形表示为：图像压缩的原问题（规模为n）为：9211),1max(*min255,min1nknbkknsnsnkvoid Compress(int n,int p)Lmax=256,header=11,s0=0;for(i=1;i=n;i+)bi=length(pi);bmax=bi;si=si-1+bmax;li=1;for(j=2;j=i&j=Lmax;j+)if(bmaxsi-j+j*bmax)si=si-j+j*bmax;li=j;si

36、+=header;pi对应的二进制编码长度将分段中的最后一段只分配一个像素点取对应的二进制编码长度较长的为bmax在li,bili,bi中记录最优分段所需要的信息从尾部开始计算最优分段方法获得的结果并记录void Traceback(int n,int&i)if(n=0)return;Traceback(n-ln,i);si+=n-ln;/算法的计算时间为算法的计算时间为O(n)构造最优解 构造最优解构造最优解li,bili,bi中记录最优分段所需要的信息 ln:最优分段最后一段的段长度 bn:最优分段最后一段的像素位数 其前一段的段长度和像素位数分别存储在ln-ln和bn-ln中 对j的循环

37、最多不超过256，故对确定的i，compress可以在O(n)时间内构造出最优解*整个算法的计算复杂性整个算法的计算复杂性O(n)(n)实例9611+2*4=1915+51=6619+43=62电路布线电路布线98在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,X(i)将上端接线柱与下端接线柱相连，如图所示。其中X(i)是1,2,n的一个排列。导线(i,X(i)称为该电路板上的第i条连线。对于任何1iX(k)。连线的最大不相交子集。要求确定导线集线。该层上有尽可能多的连安排在第一层上，使得定将哪些连线交。电路布线问题要确在同一层上的连线不相缘层上，条连线分布到若干个绝将

38、这在制作电路板时，要求。条连线相交的充要条件条连线和第那么第，如果电路布线问题1),(,()()(1niiXiNetsnjXiXjinji最优子结构性质。的最大不相交子集位|),(|),(),(),()(,)(,(),(jiMNSjiSizejiMNSjiNjtXitNetstXtjiNN(3,9)=(1,8),(2,7),(3,4).MNS(3,9)=(1,8),Size(3,9)=1.N(6,9)=(1,8),(2,7),(3,4),(4,2),(5,5),(6,1).MNS(6,9)=(4,2),(5,5)Size(6,9)=2.MNS(6,9)=(3,4)(5,5)最优子结构性质)1(

39、)1(,1()1(),1(),1(1XjXXjjNjMNSi时当N(1,1)=N(1,9)=(1,8).MNS(1,9)=(1,8),Size(1,9)=1.),1(),(),1(),(),()(,()(11jiSizejiSizejiNjiNjiNiXiiXji）（时当不存在(i,X(i)这么一条连线N(5,4)=(3,4),(4,2).(5,5)不属于N(5,4)N(5,4)=N(4,4.并且size(5,4)=size(4,4=1103),1(),(),1(),(),(),1(),1(),(),1(),(),()(,(),()(,(1)1,1(),(),(),(),()(,)1)(,1(

40、)1)(,1()(,(),()(,()(,()()(),()(,(),()(,()()2(jiSizejiSizejiSizejiSizejiNjiMNSjiSizejiSizejiNjiMNSitjiMNStXtjiMNSiXijiSizejiSizejiMNSjiMNSjiNiXiiXiMNSiXiNiXijiMNSiXitXtiXtXitjiMNStXtjiMNSiXiiXj。有，则对任意如果定义矛盾更大的不相交子集，与是比否则，子集的最大不相交子集。是相交。与；否则且有，则对任意如果电路布线问题满足最优子结构性质电路布线问题满足最优子结构性质(i,X(i)加上MNS(i-1,j-1)递

41、归计算最优值)(1)1)(,1(),1(max)(),1(),(1)2()1(1)1(0),1(11),(iXjiXiSizejiSizeiXjjiSizejiSizeiXjXjjSizeinnSize时当时）当（值为设电路布线问题的最优MNS()int pN+1,cN+1=0;for(i=1;icpi)cpi=cpi-1+1;for(j=pi;jcj+1)cj+1=cj;cout0;i-)jMax=min(wi-1,c);for(j=0;j=jMax;j+)mij=mi+1j;for(j=jMax+1;j=c;j+)mij=max(mi+1j,mi+1j-wi+vi);算法复杂性分析 算法复杂性分析算法复杂性分析 算法复杂性为O(Cn)存在的问题存在的问题 wi为整数；当背包容量较大时，计算时间消耗较多算法分析题算法实现题P79 3-2 3-3P84-85 3-14 3-17 图像压缩问题