第3 章 动态规划 动态规划(DynamicProgramming)技术已经广泛应用于许多组合优化问题的算法设计 中.例如,图的多起点与多终点的最短路径问题、矩阵链的乘法问题、最大效益投资问题、背 包问题、最长公共子序列问题、图像压缩问题、最大子段和问题、最优二分检索树问题、RNA 的最优二级结构问题等. 一般的组合优化问题都有对应的目标函数和约束条件.例如,第1章提到的货郎问题. 设C={c1,c2,…,cm }是城市集合,距离d(ci,cj )=d(cj,ci)∈Z+ ,1≤i给出,其中P0 是矩阵A1 的行ni. 1,n-既是矩阵Ai ,这说明有3个矩阵相乘,其中 A1:10×100, A2:100×5, A3:5×50 有两种乘法次序,即(A1A2)A3 和A1(A2A3).如果采用第一种次序,执行的基本运算次 数是: 10×100×5+10×5×50=7500 而采用第二种次序,执行的基本运算次数是: 10×100×50+100×5×50=75000 工作量相差达到10倍之多. 我们的问题是:给定向量P,确定一种乘法次序,使得基本运算的总次数达到最少. 一般的蛮力算法就是枚举所有可能的乘法次序,针对每种次序计算基本运算的次数,从 中找出具有最小运算次数的乘法次序.每一种乘法次序对应了一种在n 个项中加n-1对 括号的方法.根据组合数学的知识不难知道,加n 对括号的方法数是一个Catalan数,它的 值是1 n+1 2n n . è . . . ÷ .根据Stirling公式,即使对每种次序的计算工作量为常数,对规模为n+1 的输入使用蛮力算法的时间将是: W (n)=Ω 1 n +1 (2n)! n! n! . è . . . ÷ =Ω 1 n +1 2π2n 2n e . è . . . ÷ 2n 2πn ne . è . . . ÷ n 2πn ne . è . . . ÷ n . è .... . . ÷÷÷÷ =Ω 1 n +1 n1 222nn2nenen e2nn1 2nnn1 2nn . è . . . ÷ =Ω 22n/n32 ( ) 这是一个指数时间的算法.下面尝试动态规划的算法.我们将从子问题的划分、递推方 程的确定、递归和迭代的实现方法、复杂度分析等方面介绍动态规划算法的设计特征. 3.2.1 子问题的划分和递推方程 我们的优化目标是基本运算次数的最小化.如何界定子问题的边界? 令A1..n 表示输入 的矩阵链.如果从前向后划分,所产生的子问题只有后边界,是A1..i 的形式,i=1,2,…,n. 但是在计算子问题A1..j,j>i 时,我们不仅需要子问题A1..i的信息,也需要子问题A(i+1)..j的 信息.这说明子问题的划分需要前后两个边界.用Ai..j 定义矩阵链AiAi+1…Aj 相乘的子问 题,m [i,j]表示得到乘积Ai..j所用的最少基本运算次数.假定其最后一次相乘发生在矩阵 链Ai..k 和Ak+1..j之间,即 AiAi+1…Aj =(AiAi+1…Ak)(Ak+1Ak+2…Aj) k =i,i+1,…,j-1 那么子问题Ai..j的计算依赖于子问题Ai..k 和Ak+1..j的计算结果.换句话说,m [i,j]的值依赖 于m [i,k]和m [k+1,j]的值,具体的依赖关系可以表示为 m [i,j]= 0 i=j min i≤k,其中1≤i≤j≤n 输出:计算Ai..j 的所需最小乘法运算次数m [i,j]和最后一次运算的位置s[i,j] 1.ifi=j 2.thenm [i,j]←0;s[i,j]←i;returnm [i,j] 3.m [i,j]←∞ 4.s[i,j]←i 5.fork←itoj-1do //考虑所有可能的划分位置 6. q←RecurMatrixChain(P,i,k)+RecurMatrixChain(P,k+1,j)+Pi-1PkPj 7. ifq1 ì . í .. .. 经过化简得 T(n)≥Θ(n)+ Σn-1 k=1 T(k)+ Σn-1 k=1 T(n -k)=Θ(n)+2Σn-1 k=1 T(k) 3.1 当n>1时,T(n)=Ω(2n-1). 证 n=2,T(2)≥c=c122-1,c1=c/2为某个正数. 假设对于任何小于n 大于或等于2的k,T(k)≥c12k-1,则存在某个常数c',使得 算法设计与分析(第3版) 58 n-1 n-1 k-1 n)≥cn+2Σ k)≥cn+2Σ T('T('c12 k=1 k=2 n n-1 =c(') n+c1(2-4)≥c12 可以看到,通过使用动态规划的设计思想,该算法的时间复杂度比蛮力算法有所改进, 但是并没有得到多项式时间的高效算法.时间复杂度高的原因在于:在递归调用中同一个 子问题被多次重复计算.以矩阵链A1.5的计算为 例.图3. 4用一棵横放的树给出了递归计算的过 程.每个问题对应一个结点,树根是原始问题,记 作“1.5” .第1层的结点对应于原问题在 k=1,2,3,4的不同位置进行划分所得到的8个 子问题,每个子问题表示成原问题的儿子.第2 层对应这8个子问题进一步递归求解得到的新的 子问题,有24个.类似地,第3层有32个新的子 问题,第4层有16个新的子问题.在整个递归计 算中总计产生了 1+8+24+32+16=81 个子问题.但是,根据边界考查不同的子问题个 数:规模为1的子问题有5个,规模为2的有 4个,规模为3的有3个,规模为4的有2个,规 模为5的有1个,总计 5+4+3+2+1=15 个不同的子问题.这说明算法计算的81个子问 题中有许多是重复的,这就是递归实现动态规划 算法时间复杂度高的原因 . 2.动态规划算法的迭代实现 3.3 如果在计算中对每个子问题只计算一次,并 且把结果保存起来.等到后面计算其他子问题需 要这个值时,直接把它代入,这样就能够改善算法 的时间复杂度.这就是迭代实现动态规划算法的 思想.为了实现这个想法,需要解决以下两个 问题: (1)开辟一个存储空间,用表格的方式来存 储子问题的优化函数值和划分边界,通常把这些 图3.子问题 表格称为“备忘录” .这说明提高效率需要付出空 4 间的代价.对于规模大的实例,过大的空间需求 往往成为不能使用动态规划算法的主要因素 . (2)子问题的计算需要从底向上进行.每个子问题只计算一次.这就是说,从最小规模 的子问题开始,比如规模为1的所有子问题,然后是规模为2的所有子问题,接着是规模为 动态规划 3的所有子问题……直到规模为 n 的子问题(原始问题)为止.这样才能在前面的计算中准 备好后面计算要查找的数据 . 下面的伪码给出了矩阵链问题动态规划算法的迭代实现方法 . 算法3.n(n) 2 MatrixChiP, 输入:矩阵链A1.n 的输(a) 入为向量P= 输出:计算Ai. 的所需最小乘法运算次数m[和最后一次运算的位置s[j] , ji,j] i,1≤i≤j≤ n 1.令所有的m[i,i] s[j]初值为i, 初值为0,i,1≤i≤j≤ n 第 章 59 2.forr←2tondo 3. fori←1ton-r+1do 4. j←i+r-1 i,←m[j]+Pi 5. m[j]i+1,-1*Pi *Pj i, 6. s[j]← i 7. fork←i+1toj-1do 8. t←m[k]+m[j]+Pi-1*Pk *Pj i,k+1, i, 9. ift,n=5,相应的矩阵链是:A1,A2,A3,A4,A5, 其中, A1:30×35,A2:35×15,A3:15×5,A4:5×10,A5:10×20 计算开始,当子问题规模r=1时,所有的m[1,1],m[2,2],…,m[5,5]都等于0.然后 r=2,有4个子问题,计算结果是: m[1,2]=30×35×15=15750 m[2,3]=35×15×5=2625 m[3,4]=15×5×10=750 r=有3个子问题, m[4,5]=5×10×20=1000 接着,3, 计算结果是: m[1,3]=min{m[1,2]+30×15×5,m[2,3]+30×35×5}=7875,s[1,3]=1 m[2,4]=min{m[2,3]+35×5×10,m[3,4]+35×15×10}=4375,s[2,4]=3 m[3,5]=min{m[3,4]+15×10×20,m[4,5]+15×5×20}=2500,s[3,5]=3 接着,4, 计算结果是: r=有2个子问题, m[1,4]=min{m[2,4]+30×35×10,m[1,2]+m[3,4]+30×15×10, m[1,3]+30×5×10}=9375 m[2,5]=min{m[3,5]+35×15×20,m[2,3]+m[4,5]+35×5×20, 算法设计与分析(第3版) m[2,4]+35×10×20}=7125 ==3.r= 对应的划分位置分别是s[1,4]3和s[2,5]最后,5,就是原始问题,计算结果是: m[1,5]=min{m[2,5]+30×35×20,m[1,2]+m[3,5]+30×15×20, m[1,3]+m[4,5]+30×5×20,m[1,4]+30×10×20}=11875 s[1,5]=31和表3. 存储上述计算结果的备忘录和标记函数分别如表3.2所示 . 表3.优化函数值的备忘录 1 60 r= 1 m[1,1]=0 m[2,2]=0 m[3,3]=0 m[4,4]=0 m[5,5]=0 r= 2 m[1,2]=15750 m[2,3]=2625 m[3,4]=750 m[4,5]=1000 r= 3 m[1,3]=7875 m[2,4]=4375 m[3,5]=2500 r= 4 m[1,4]=9375 m[2,5]=7125 r= 5 m[1,5]=11875 表3.标记函数 2 r= 2 s[1,2]=1 s[2,3]=2 s[3,4]=3 s[4,5]=4 r= 3 s[1,3]=1 s[2,4]=3 s[3,5]=3 r= 4 s[1,4]=3 s[2,5]=3 r= 5 s[1,5]=3 根据备忘录可以知道最少运算次数是11875,根据s[1,5]=3知道最后一次划分在第三 个矩阵的后面,于是得到A1.5=A1.3A4.5.接着查找s[1,3]=1,于是得到A1.3=A1.1A2.3,从 而得到最佳的运算次序是: A1A2A3A4A5=(A1(A2A3))(A4A5) 通过矩阵链相乘的例子,我们可以总结动态规划算法的设计要素: (1)划分子问题,用参数表达子问题的边界,将问题求解转变成多步判断的过程 . (2)确定优化函数,以该函数的极大(或极小)值作为判断的依据,确定是否满足优化 原则 . (3)列出关于优化函数的递推方程(或不等式)和边界条件 . (4)考虑是否需要设立标记函数,以记录划分位置 . (5)自底向上计算,以备忘录方法(表格)存储中间结果 . (6)根据备忘录(和标记函数)通过追溯给出最优解 . 3.动态规划算法的典型应用 3 本节介绍动态规划算法的一些典型应用 . 3.1 投资问题 3. 例3.4 设有 m 元,函数fi(表示将 x 元投入第 i 项项目所产生的效益, n 项投资, x) 动态规划 1,2,…,问:如何分配这 m 元,使得投资的总效益最高? 假设钱数的分配都是非负整数,分配给第 i 个项目的钱数是xi,那么该问题可以描述为 目标函数max{f1(x1)+f2(x2) + …+fn (xn )} 约束条件x1+x2+ …+xn =m,xi ∈ N 一个简单的实例是:有5万元,4个项目, 以万元为单位)3所示 . i=n. 效益函数( 如表3. 表3.效益函数 3 x f1(x) f2(x) f3(x) f4(x) x f1(x) f2(x) f3(x) f4(x) 0 0 0 0 0 3 13 10 30 22 1 11 0 2 20 4 14 15 32 23 2 12 5 10 21 5 15 20 40 24 使用动态规划算法首先需要界定子问题的边界.可以是按项目划分成 n 个阶段,比如 先考虑对第1个项目的分配,接着考虑对前2个项目的分配,……, 直到考虑对 n 个项目的 分配.每阶段的问题都构成后面阶段的子问题.与前面的最短路径和矩阵链乘法的不同点 在于:这里每个阶段的子问题还存在另一个参数:投资的钱数.于是每个阶段的子问题还 可以按照钱数进行更细的划分.这里使用的是具有两个不同参数的优化函数.设Fk (x)表 示 x 万元投给前 k 个项目的最大效益,其中k=2,…,x=2,…,在第 k 步, 1,n;1,m. 钱数 为 x 万元时需要做的是:假设知道 p 万元(p≤x)投给前k-1个项目的最大效益,如何对 前 k 个项目分配 x 元以取得最大的效益.首先从 x 万元中分配xk (0≤xk ≤x)万元给第 k 个项目,那么剩下的x-xk 万元将分配给前k-1个项目,最佳分配方案已经在第k-1步 计算过.于是得到如下递推方程和边界条件: Fk (x) = max{fk (xk )+Fk-1(x-xk )},k=2,3,…, n 0≤xk ≤x F1(x)=f1(x),Fk (0)0,k=1,2,…, = n 这里需要设立标记函数xk (x), 它表示当Fk (x)取得最大值时应该分配给第 k 个项目 的钱数 . 不难验证这个问题满足优化原则.算法的伪码描述请读者自己给出.下面以上述实例 看看算法的运行过程 . 首先,计算F1(x). x 万元仅分配给第一个项目,这对应于递推关系的初值,可以直接 从效益函数表中查到,于是有 F1(1)=f1(1)=11,F1(2)=f1(2)=12,F1(3)=f1(3)=13, F1(4)=f1(4)=14,F1(5)=f1(5)=15,x1(x)=x,x=1,2,3,4,5 这些值存在备忘录的第一列,见表3.下面计算F2(首先计算F2(1), 总钱数1万元, 4.x) . 分配给第二个项目可能有两种结果:0万元或1万元.于是递推关系是: F2(1)=max{f2(0)+F1(1),f2(1)+F1(0)}=max{0+11,0+0}=11, x2(1)=0 其中,x2(1)=0表示取得最大效益11 万元时分配给第二个项目的钱数是0.类似地可以计 算F2(2),F2(3),F2(4),F2(5): 第 章 61 62 算法设计与分析(第3版) 2),1),0) } F2(3)x{0)+F1(f2(2),2)+F1( F2(2)=max{f2(0)+F1(f2(1)+F1(f2(2)+F1(=12,x2(2)=0 =maf2(3),1)+F1(f2(1), f2(3)+F1(0)}=16,x2(3)=2 F2(4)x{0)+F1(f2(3),2)+F1(f2(3)+F1(1), =maf2(4),1)+F1(f2(2), f2(4)+F1(0)}=21,x2(4)=3 5),4),3),2), F2(5)=max{f2(0)+F1(f2(1)+F1(f2(2)+F1(f2(3)+F1( f2(4)+F1(f2(0)}x2(4 1),5)+F1(26,5) == 这些值和相应的标记函数x2(x)存在备忘录的第2列.照此下去,继续计算F3(x)和 F4(x),1,3,5. 从表中F4(=投资5万元可以产 x=2,4,从而完成整个备忘录 . 5)61 可知, 生的最大效益是61 万元.那么能够达到这个效益的分配方案是什么呢? 这需要从表上的 标记函数从后向前追溯.首先查到x4(5)=1知道1万元分配给第4个项目.于是分配给前 三个项目的钱数为5-1=4万元.再查x3(4)=3,从而知道在4万元中又有3万元分配给 第三个项目.那么还剩下4-3=1 万元分配给前两个项目.最后查x2(1)=0,说明在这 1万元中分配给第二个项目的钱数是0,只能全部分配给第一个项目.经过这样的追溯,可 以得到问题的解,即 分配方案是:1,0,3, x1=x2=x3=x4= 1 最大效益是:F4(5)=61 对于解的追溯过程可以在表3. 4的灰色方格中看到 . 表3.解的追溯 4 xF1(x) x1(x) F2(x) x2(x) F3(x) x3(x) F4(x) x4(x) 1 11 1 11 0 11 0 20 1 2 12 2 12 0 13 1 31 1 3 13 3 16 2 30 3 33 1 4 14 4 21 3 41 3 50 1 5 15 5 26 4 43 4 61 1 最后,让我们看看这个算法的效率.假设给定的输入实例含有 n 个项目,钱数为m,那 么备忘录中有 m 行 n 列,共计mn 项.根据递推关系 Fk (x) = max{fk (xk )+Fk-1(x-xk )} 0≤xk ≤x F1(x)=f1(x) 除了k=1的初值以外,对项Fk (x)(2≤k≤n,1≤x≤m)的计算需要x+1 次加法和 x 次 比较.对 k 求和,于是算法执行的加法次数满足: = kΣ=2(n) xΣ=1(m) (x+1)21(n-1)m(m+3) 比较次数满足: k=2x=1 x= 2n-1)m(m+1) Σ(n) Σ(m) 1( 动态规划 第3章 6 3 于是该算法的时间复杂度是W (n,m )=O(nm2). 3.3.2 背包问题 背包问题(KnapsackProblem)是一个著名的NP难问题. 例3.5 一个旅行者准备随身携带一个背包.可以放入背包的物品有n 种,物品j 的 重量和价值分别为wj 和vj,j=1,2,…,n.如果背包的最大重量限制是b,怎样选择放入背 包的物品以使得背包的价值最大? 这是一个组合优化问题,设xj 表示装入背包的第j 种物品的数量,那么目标函数和约 束条件是: 目标函数 maxΣn j=1 vjxj 约束条件 Σn j=1 wjxj ≤b xj ∈ N { 如果组合优化问题的目标函数和约束条件都是线性函数,称为线性规划问题,如果线性 规划问题的变量xj 都是非负整数,则称为整数规划问题.背包问题就是整数规划问题.限 制所有的xj=0或xj=1时的背包问题称为0-1背包问题. 不难验证背包问题也满足优化原则,可以使用动态规划设计技术.与投资问题类似,背 包问题也有两个参数,物品种类和背包重量的限制.可以根据物品种类和背包的重量限制 进行子问题划分.设Fk(y)表示只允许装前k 种物品,背包总重不超过y 时背包的最大价 值,分两种情况考虑:不装第k 种物品或者至少装1件第k 种物品.如果不装第k 种物品, 那么只能用前k-1种物品装入背包,而背包的重量限制仍旧是y,在这种情况下,背包最大 价值是Fk-1(y).如果第k 种物品装了一件,那么背包的价值是vk,且重量是wk,剩下的物品 仍旧需要在前k 种物品中选择(因为最优的装法可能包含多个第k 种物品).于是问题归约为 在背包重量限制为y-wk 的情况下如何用前k 种物品装入背包以取得最大价值Fk(y-wk). 我们需要从这两种情况中取价值较大的作为最优选择.于是,得到递推关系与边界条件: Fk(y)=max{Fk-1(y),Fk(y -wk)+vk} F0(y)=0 0≤y ≤b Fk(0)=0 0≤k ≤n F1(y)= y w1 v1 Fk(y)=-∞ y <0 上面公式的初值比较多,F0(y)是背包不装物品的价值,显然等于0;Fk (0)是背包重量限制 为0时的最大价值,当然也等于0;F1(y)是只能用第一种物品背包重量限制为y 时的最大 价值,为了保证背包不超重,第一种物品至多能装.y/w1. 个,因此背包价值是.y/w1.v1.为 什么还需要设定当y<0时的初值呢? 因为在递推式中有Fk(y-wk),在递推过程中,某些 y-wk 可能得到负值,这意味着背包此刻能够承受的重量已经小于第k 种物品的重量,实 际上是不能装的.通过令Fk(y)=-∞(可以选机器中的最小数),使得这个值在与另一个 优化函数值比较时被淘汰,从而使得这种装法被排除. 64 算法设计与分析(第3版) 与投资问题相比较,背包问题的递推关系也可以使用与投资问题类似的表述,请读者给 出相关的表达式和初值 . 考虑下面的实例,其 中 v1=1,v2=3,v3=5,v4= 9 w1=2,w2=3,w3=4,w4= 7 b=10 则Fk (y)的计算表如表3.其中省略了所有Fk (0) 5所示, 的值 . 表3.5 优化函数Fk ( y) ky123456789101 0 1 1 2 2 3 3 4 4 5 2 0 1 3 3 4 6 6 7 9 9 3 0 1 3 5 5 6 8 10 10 11 4 0 1 3 5 5 6 9 10 10 12 表3.最后一项F4(=12,这就是背包的最大价 5只是计算了各个子问题的优化函数值, 10) 值.怎样选择物品可以得到这个价值呢? 可以像投资问题一样设立标记函数,记录得到这个值 时所装入的最大标号物品的个数.这里采用另一种标记方法.令ik (表示在计算优化函数值 y) 在计算Fk (时, 1( y 比 ) Fk (大, Fk (时所用到物品的最大标号 . yy) ) 如果Fk-y) y-wk )+vk 那 么此刻装入背包物品的最大标号与计算Fk-1(所用物品的最大标号一致;反之,选择标号 为 k 的物品装入背包才能使得背包价值达到最大,即ik (y)=k.于是ik (y)满足下述递推 关系: k (y)ik1(Fk1(y-wk )+vk -y) -y)>Fk ( i= k Fk-1(y)≤Fk (y-wk )+vk 不难看出,标记函数ik (y)不需要额外的计算,只需计算Fk (y)时把相关的ik (y)值填入一 个标记表就行了.标记表的格式如表3.其中省略了所有i0)=0的初值. 6所示, k ( 表3.标记函数iy) 6 k ( ky123456789101 0 1 1 1 1 1 1 1 1 1 2 0 1 2 2 2 2 2 2 2 2 3 0 1 2 3 3 3 3 3 3 3 4 0 1 2 3 3 3 4 3 4 4 根据表3.找到问题的解 . 10)=4可知4号物 6可以向前追踪, 具体追踪过程是:由i4( 品至少用1个,占用背包重量w4=7,背包剩余重量是10-7=3,于是继续检查i4(3).由于 i4(3)=2,即剩余物品的最大标号是2,这说明2号物品至少装1个,而不再装入第2个4号 动态规划 物品和3号物品.装入这个2号物品后,背包重量又增加了w2=3,剩余背包重量是0,于是 不能装任何物品了.用公式表示追踪解的过程是: i4(10)=4.x4≥1 i4(10-w4)i4(=x41,= =3)2.x2≥1,=x30 i2(3-w2)=i2(0)=0.x2=1,x1=0 最终得到该实例的解是:x1=0,x2=1,x3=0,x4=1.上述追踪过程也可以用伪码描述 . 算法3.3 TrackSolutio 输入:iy) 其中k=n;1, 2,…,2,…, k (表, 1,(n) y= b 输出:x2,…, n 种物品的装入 量 x1,xn , 1.forj←1tondo 2. xj ← 0 3.y←b, j← n 4.j←ij (y) 5.xj ← 1 6.y←y-wj 7.whileij (y)=jdo 8. y←y-wj 9. xj ←xj + 1 10.ifij (y)≠0thengoto4 最后考虑算法的时间复杂度.与投资问题类似,该算法的时间复杂度为O(nb).表面上 看,这是一个 n 和 b 为变量的多项式,但这个算法并不是多项式时间的算法.因为正整数 b 的输入规模是 b 在机器中占用的存储空间大小,因此问题的输入规模实际上是 n 和logb log.nog ( b 是 b 的二进制表示的位数)显然O(b)不是 n 和lb 的多项式函数,我们把这样的 算法称为伪多项式时间的算法.关于这个问题将在9. 3节进一步讨论 . 背包问题具有广泛的应用背景.许多任务调度、资源分配、轮船装载等问题都可以用背 包问题建模.背包问题也有许多变种,比如在原有背包问题的基础上增加体积约束条件,即 物品 i 不但有重量wi、价值vi,还有体积di,背包本身也有体积 D 的限制.作为典型的 NP 难问题,许多人对背包问题进行了深入的研究,特别对0-1背包问题已经得到了有效的 近似算法.这些将在第10 章介绍 . 3.3 最长公共子序列LCS 3. 在实际问题中经常需要对两个对象进行类比分析,找出它们之间的公共部分.最长公 共子序列问题就是这类问题的一种简单的抽象模型 . 定义3.1 设 X 和 Z 是两个序列,其中 X= x2,…, Z= z2,…, 如果存在 X 的元素构成的按下标严格递增序列,使得xij =zj ,1, xi2xij= 2,…, k,那么称 Z 是 X 的子序列. Z 含有的元素个数,称为子序列的(k) 长度 . 定义3.2 设 X 和 Y 是两个序列,如果 Z 既是 X 的子序列,也是 Y 的子序列,则称 第 章 65 66 算法设计与分析(第3版) Z 是 X 与 Y 的公共子序列 . 最长公共子序列问题 . 给定序 列 例3.6 x2,…,>,Y= y2,…, n 求 X 和 Y 的最长公共子序列 . 例如, X = C,D,B>,D,A,A>, 子序列是,长度是4.当然还有另一个最长公共子序列,即 . 我们的要求是求出一个最长的公共子序列.当最长公共子序列不唯一时,不同的算法的求 解结果可能不一样,但是它们的长度都相等 . 假设m≤n.蛮力算法可以这样做:找出 X 的每个子序列X' ,并且把X'和 Y 进行比 较,看看X'是否也是 Y 的子序列.如果是,那么X'就是 X 与 Y 的公共子序列.当所有的比 较完成后就找到了 X 与 Y 的最长公共子序列.在选择X'时,每个 X 的元素有两种可能的 选择:属于X'还是不属于X于是 X 有2m 如果检查Xn) 那 ' , 个子序列.'与 Y 需要O(时间, 么整个算法需要O(n2m )时间,这是一个指数时间的算法 . 考虑动态规划算法,首先需要思考如何界定子问题的边界.假设子问题的 X 和 Y 的起 始位置都从第一个元素开始, X 的终止位置是第i个元素,那么 Y 的终止位置是第 j 个元素, Xi=x2,…, ,Yj= y2,… , 就代表了由 i 和 j 共同界定的子问题的输入 . 下面分析子问题之间的依赖性质,这是设计递推关系的基础. 设 x2,…,y2,…,z2,… , Xi= ,Yj =,Zk = 如果Zk 为Xi 和Yj 的最长公共子序列,那 么 (1)若xi=yj ,则zk =xi =yj ,且Zk―1是Xi-1与Yj-1的最长公共子序列.如若不然, 一定存在Xi-1和Yj-1的最长公共子序列Z' ,|Z'|>|Zk-1|.在Z'后面加上zk 就得到一个 Xi 与Yj 的公共子序列,且它的长度为|Z'|+1>|Zk-1|+1=|Zk|,与Zk 是Xi 与Yj 的最 长公共子序列矛盾 . 如果xi 与yj 不等,或xi 不是zk ,或yj 不是zk.下面的(和(分别对应于这两种情况 . (2)若xi≠yj ,则Zk 是Xi-1与Yj 2) 3) zk ≠xi, 的最长公共子序列 . (3)若xi≠yj ,zk ≠yj ,则Zk 是Xi 与Yj-1的最长公共子序列 . 设C[i,j]表示Xi 与Yj 的最长公共子序列的长度.根据上述分析,得到优化函数的递 推关系如下: i-1,如果i,xi=yji,= C[j-1]+1 j >0, j]i, C[j-1],C[j]} 如果i, C[0,=C[0]=0 如果1≤ i ≤m,1≤ j ≤ n 上述的递推公式恰好反映了前面的三种情况.C[j]C[1,1]+1 对应于情况(1); C[i-j] i,则分别对应于情况(和( i, . = = i-j- 0时, C[j]max{i,i-1, j >0,xi ≠yj 1,与C[j-1] 2) 3)当i0或者j=两个序列中的一个 序列是空序列,那么公共子序列只能是空序列,因此C[0,j]=i,=0,这是递推关系的 C[0] 初值 . 根据这个递推关系和初值,不难给出算法迭代实现的伪码描述 . 动态规划 算法3.X,m, 4 LCS(Y,n) 输入:序列X,其中X[Y[1. n] Y, 1. m], 标记B[j] , 输出:最长公共子序列长度C[i,j], i,1≤i≤m,1≤j≤ n 1.fori←1tom do //第1~4行处理初值 i, 3.fori←1tondo 2. C[0]←0 0, 5.fori←1tom do 4. C[i]←0 6. forj←1tondo //X[与Y[ i]Y[i] 被选入公共子序列 7. ifX[=j] j] 8. tei,←C[-j hnC[j]i1,1]+1 i, 9. B[j]"↖" 10. esfC[-j]≥C[j leii1,(←) i,1] ←C[j] 11. thenC[i,j]i-1, i,← “ eC[i,j]i, 12. B[j]↑” 13. els←C[j-1] i,←“ 14. B[j]←” 上述算法计算了所有子问题的最长公共子序列的长度C[j]B[j] 记 i,.i,是标记函数, 录Xi 与Yj 的最长公共子序列的元素是怎样选取的.有三种标记:①用“↖”表示序列Xi 与Yj 的最后项xi=yj ,已被选入最长公共子序列;②用“↑”表示在Xi 与Yj 的最长公共 子序列选择时不考虑xi,它们的最长公共子序列就是Xi-1与Yj 的最长公共子序列;③用 “←”表示在Xi 与Yj 的最长公共子序列选择时不考虑yj ,它们的最长公共子序列就是Xi 与Yj-1的最长公共子序列.设立这些标记是为了追踪解.可以从后向前追踪这些标记,遇到 “↖”标记时,就把xi 加入最长公共子序列中.如果遇到其他两种标记,表示没有元素加入 最大公共子序列,这时仅需按照标记的指示向前继续追踪.追踪解的算法在下面给出 . 算法3.5 StcueSqune(i, 输入:B[ utreecB,j) i, j](r) 输出: X 与 Y 的最长公共子序 列 1.ifi=0orj=0thenreturn //一个序列为 空 2.ii,= ↖ fB[j]"" 3.then输出X[ i] 4. SuteSqecB,-j tcreune(i1,1) 5.elseii,="↑"thenStctreSqnce(i fB[(r) j](u) B,1,j) 6. estutreuni,e((u) (r) 1)(e) (u) (e) leSrcueSqecB,(u) j 回顾这个问题开始时所给出的实例: X= ,Y= 其中,m=n=算法LCS计算的C[j] i,分别如表37和表38所示.. 7,6.i,和B[j] ..在表38中 用连续的灰色表格表示追踪过程: B[7,6]→B[6,6]→B[5,5]→B[4,5]→B[3,4]→ B[3,3]→B[2,2]→B[2,1]→j=0 其中,B[6,6]=B[4,5]=B[3,3]=B[2,1]=“↖”,这就得到解Z== 第 章 67 68 算法设计与分析(第3版) . 最后我们分析这个算法的时间复杂度.算法LCS 的第1行和第2行是O(m)时间,第3 n) mn) 1) 行和第4行是O(时间,第5行和第6行的循环执行O(次,循环内部的运算是O( mn) . tructureSequencj=n 时间,于是算法的总时间是O(此外,追踪解的Se算法从i=m, i, 开始,每找到一个标记B[j], 算法执行常数操作,然后或者 i 和 j 同时减1,或者 i 减1,或 者 j 减1,总之i+ j 至少减1.由于初始i+j= m +n,因此至多 m + n 次在标记上的操作, 算法将结束,于是算法的时间是O(我们看到这个算法把蛮力算法的O( m )时间 降低到O(mn)时间. m +n).n2 表3.优化函数C[j] 7 i, 01234560 C[0,0]=0 C[0,1]=0 C[0,2]=0 C[0,3]=0 C[0,4]=0 C[0,5]=0 C[0,6]=0 1 C[1,0]=0 C[1,1]=0 C[1,2]=0 C[1,3]=0 C[1,4]=1 C[1,5]=1 C[1,6]=1 2 C[2,0]=0 C[2,1]=1 C[2,2]=1 C[2,3]=1 C[2,4]=1 C[2,5]=2 C[2,6]=2 3 C[3,0]=0 C[3,1]=1 C[3,2]=1 C[3,3]=2 C[3,4]=2 C[3,5]=2 C[3,6]=2 4 C[4,0]=0 C[4,1]=1 C[4,2]=1 C[4,3]=2 C[4,4]=2 C[4,5]=3 C[4,6]=3 5 C[5,0]=0 C[5,1]=1 C[5,2]=2 C[5,3]=2 C[5,4]=2 C[5,5]=3 C[5,6]=3 6 C[6,0]=0 C[6,1]=1 C[6,2]=2 C[6,3]=2 C[6,4]=3 C[6,5]=3 C[6,6]=4 7 C[7,0]=0 C[7,1]=1 C[7,2]=2 C[7,3]=2 C[7,4]=3 C[7,5]=4 C[7,6]=4 表3.标记函数B[ i, 8 j] 1234561 B[1,1]=↑ B[1,2]=↑ B[1,3]=↑ B[1,4]=↖ B[1,5]=← B[1,6]=↖ 2 B[2,1]=↖ B[2,2]=← B[2,3]=← B[2,4]=↑ B[2,5]=↖ B[2,6]=← 3 B[3,1]=↑ B[3,2]=↑ B[3,3]=↖ B[3,4]=← B[3,5]=↑ B[3,6]=↑ 4 B[4,1]=↖ B[4,2]=↑ B[4,3]=↑ B[4,4]=↑ B[4,5]=↖ B[4,6]=← 5 B[5,1]=↑ B[5,2]=↖ B[5,3]=↑ B[5,4]=↑ B[5,5]=↑ B[5,6]=↑ 6 B[6,1]=↑ B[6,2]=↑ B[6,3]=↑ B[6,4]=↖ B[6,5]=↑ B[6,6]=↖ 7 B[7,1]=↖ B[7,2]=↑ B[7,3]=↑ B[7,4]=↑ B[7,5]=↖ B[7,6]=↑ 3.4 图像压缩 3. 计算机中的图像由一系列像点构成,每个像点称为一个像素,图像分辨率越高,使用的 像素就越多.例如,Windows桌面的图片经常使用的像素设置是1024×768,大概达到106 量级.图像传输和视频处理有时在1秒内要处理几十帧图片,这些图片的像素就很可观了, 因此,图像处理常常需要大量的存储空间和高的处理速度,图像压缩问题就成了计算机科学 技术中的重要研究课题之一 . 动态规划 第 以黑白图像的处理来说明图像压缩中的问题.每幅黑白图像由像点构成,每个像点具 3 有灰度值,用0~255 的整数表示.如果每个整数都用相同的二进制位来表示,那么需要用8 章 个二进制位.假设一幅图像有 n 个像素,那么这 n 个像素的灰度值构成一个整数序列 P= 其中,pi 表示第 i 个像素的灰度.存储这幅图片时,可以像数组一样连续把这些整数存起 来,共需要8n 个二进制位 . 69 下面考虑一种图像压缩方法.一般来说,在一幅图片中许多连续区域中像点的灰度值 是接近的.例如,有些交通标志图片,大片的区域是白的,可能少量区域有颜色,而且是比较 单调的颜色.对这样的图片是否可以采用分段存储的方法:对灰度值较小的段的像素采用 比较少的位数,如2位;对灰度值较大的段的像素采用较多的位数,如8位,这样就可能减少 空间的占用.这就是变位压缩技术的基本想法.这种技术节省了空间,但在读取图像时带来 了新的问题.在每个像素8位的存储方法中,读取图像时每8位就是一个像素的灰度值,不 会出错.但是对于分段压缩的图像,看起来就是一个长长的0-1序列.当读取这个序列时, 怎么知道每段的划分位置及每段像素占用的二进制位数呢? 这里需要对段的划分和段中像 素使用的二进制位数(要求同一段内不同像素用的存储位数都一样)给出明确的信息.为 此,我们对每个段给出两个整数值,一个表示该段含有的像素个数,一个表示每个像素所占 用的二进制位数.比如第 i 段,有l个像素,每个像素用bi 位.由于某些技术要求,规定每 段像素总数不超过256,即li≤256.(i) 于是,可以用8位来表示li(8位二进制数恰好有256 个 值).此外,由于每个灰度值为0~255,表达每个灰度值所用二进制数的位数bi 不超过8,于 是记录bi 还需要三个二进制位.对每段来说,这额外的11 位作为段头信息.分段越多,每段 内部像素所占用的位数会减少,但过多的段头会消耗较多的二进制位;相反,分段越少,段内 像素的空间消耗会增加,但是段头消耗少 . 请看下面的例子.设输入的灰度值序列是: P=<10,12,15,255,1,2,1,1,2,2,1,1> 考虑下面三种分段方法: 分法1 S1=<10,12,15>,S2=<255>,S3=<1,2,1,1,2,2,1,1> 分法2 S1=<10,12,15,255,1,2,1,1,2,2,1,1> 分法3 S1=<10>,S2=<12>,S3=<15>,S4=<255>,S5=<1>, S6=<2>,S7=<1>,S8=<1>,S9=<2>,S10=<2>, S11=<1>,S12=<1> 分法1有3段,第1段3个像素,每个像素用4位;第2段1个像素,每个像素用8位; 第3段8个像素,每个像素用2位;加上3个段头,每个段头11 位,总计位数是: 4×3+8×1+2×8+3×11=69 分法2有1段,12 个像素,每个像素用8位,段头11 位,总计位数是: 8×12+11=107 分法3有12 段,前3段的像素用4位,第4段像素用8位,后面有5段像素用1位,3段 像素用2位,还有12 个段头,每个11 位,总计位数是: 4×3+8×1+1×5+2×3+11×12=163 看起来分法1占用的位数最少.我们的问题是寻找存储位数最少的分段方法 . 算法设计与分析(第3版) 例3.7图像压缩问题. 给定非负整数序列P=,其中pi 为第 i 个像素的灰度值,采用变位 以使得存储 P 占用的二进制位数达到最少? 使用动态规划算法.先考虑子问题的划分边界.这 个问题比较简单,每个子问题的输入都从p1 开始,第 i 个子问题的输入Pi 到第 i 个像素值pi 结束,即Pi= 图3.子问题的归约.如图3.如果最后一段的灰 5 5所示, 度值有 j 个,其中1≤j≤mii},那么剩余部分将归约为输入是Pip2,… , 的子问题 . 下面考虑子问题之间的依赖关系.设S[表示输入为Pi n{256,- j = i] 时按最优分段存储所使用的 二进制位数.假设最后一段是第 m 段,记作Sm ,且Sm 含有 j 个灰度值,即Sm =.存储Sm ij+1,它应该是用二进制表示 的每个灰度值需要的二进制位数记作b[-i] , Sm 中的最大灰度值所占用的位数,即 log(maxpk +1) i-i] pk ∈Sm 由于Sm 含有 j 个灰度值 b, [j+1,= ij+1,个二进制位 . 于是需要j×b[-i] ≤8 剩下就是考虑前ij 个 灰度值的最优分段所占用的位数,这恰好是子问题Pi-ji-.于是在最后一 段为 j 个灰度值时的最少的位数是: 的最优解S[j] i-i]+11S[i-j]+j×b[j+1,2,…,i256,中 其中11是该段段头的空间消耗.最后分段的灰度值个数 j 可以选择1,mn{i} 的每一个值,我们必须对所有可能的 j 值进行上述计算,并从中选出最小的位数值,这个最 小值就是S[根据上述分析,不难得到关于优化函数S[的递推关系: i].i] S[i] = i{S[j]+j×b[j+1, mn i-i-i]+11} 1≤j≤mii, n{256} S[0]=0 算法实现采用迭代方法,子问题的输入从P1,P2,…,最后达到Pn.对给定的输入Pi, 算法从最后分段开始考虑,依次处理像素数为1,直到mn{i} 用 2,…, i256,的分段结果 . S[i]保留对应于最优分段的最小位数, i] 并用了l[记录达到最少位数时最后一段的灰度值 个数.如果随着分段像素灰度值个数的增加,得到了比当前的位数更少的位数,那么就用新 的位数替换原来的位数,同时更新最后段的像素个数l[算法的伪码描述如下: i] . 算法3.omps(P,n) 6 Ce 输入:数组P[1.n](r) 输出:最小位数S[l[n] n],1. 1.Lmax←256;header←11;S[0]←0 //Lmax为最大段长,header为每个段头占用空间 2.fori←1tondo 3.b[i]←length(P[//表示第 i 个像素灰度的二进制位数 4. bmax←b[ i]) //第36行分法的最后一段只有P[一个像素 i]~i] 5. S[←S[-1]+bmax i] i 6.l[ 7. foi]←1 omn{i,Lmao //最后段含 j 个像素,2,…,ii, rj←2tix}dj=mn{256} 8. ixS[-x 11. tei]ij]+j*bma hnS[←S[-x i] i]←S[ 12. l[← j 13.S[i]+header 下面给出一个运行实例.设输入 P =<10,12,15,255,1,2>.假设S[1],S[2],…, S[5]已经计算完成,且 S[1]=15,S[2]=19,S[3]=23,S[4]=42,S[5]=50, l[1]=1,l[2]=2,l[3]=3,l[4]=1,l[5]=2 算法迭代计算的最后一个子问题,即对i=6的计算过程说明如下: 初始分段,最后段含有1个像素灰度(算法3.6的第3行到第6行), 即j=1,这时该像 素灰度值是2,占用位数bmax=b[6,6]=2,加上段头11 位①,于是得到 S[6]=S[5]+1×2+11=50+13=63,l[6]=1 接着j=2,最后段含有两个像素灰度值,这时bmax=b[5,6]=2,于是最后一段占用位数等 于2×2=4位,这个位数计算出是57,即 S[6]=S[4]+2×2+11=42+15=57,l[6]=2 57 比63 小,于是更新了S[和l[ . 3, 这时bmx b[4,6]=8, 6] 6]下一步j= =最后段含有3个像素灰度值, a= 于是最后一段占用位数等于3×824 位,计算结果是: S[3]+3×8+11=23+35=58 由于这个数比57 大,于是不再更新S[6]后面几步计算和这个过程类似,得到的最小位数 分别是62,66,它们都大于57, 终(.) 6]57,6]2. 6给出了整个 59, 因此最保留的S[=l[=图3. 计算步骤,灰色区域表示最后一段的范围 . 图3.一个实例 6 ① 把段头所占用的11 位加上,是为了与图3. 在算法3.不是每次划分后 6中不同划分占用的位数一致.6的伪码中, 都做1次加法,而是找到最优划分、确定了最后分段的位置之后才加段头的11 位.两种方法的最优划分和占用位数是一 样的,但这个过程比算法做的加法次数更多. 第 章 71