第3章 动态规划_jlwan12

1、1 第第3章章 动态规划动态规划（Dynamic Programming）3.1 动态规划的设计思想动态规划的设计思想3.2 动态规划的设计要素动态规划的设计要素3.3 动态规划算法动态规划算法的典型应用的典型应用 3.3.1 投资问题投资问题 3.3.2 背包问题背包问题 3.3.3 最长公共子序列最长公共子序列LCS 3.3.4 图像压缩图像压缩 3.3.5 最大子段和最大子段和 3.3.6 最优二分检索树最优二分检索树 3.3.7 生生物信息学中的动态规划算法物信息学中的动态规划算法 3.3.8 流水作业调度问题描述流水作业调度问题描述 动态规划法的实质也是将较大问题分解为较小的同类子问

2、题，这一点上它与分治法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解。3S1S2S3S4S5T1T2T3T4T5B1A1A2A3A4B2B3B4B5C1C2C3C464745943936241433433212525473716u,2d,3u,7u,1d,9u,8d,6u,7d,11u,5u,7d,5d,15u,13d,10d,11u,4u,103.1 动态规划的设计思想例例1 求从始点到终点的最短路径求从始点到终点的最短路径4解：判断序列解：判断序列

3、)(min)()(min)()(min)()min)(jjijikkjkjllklkmlmlAFASSFBFBAAFCFCBBFTCCF 优化函数的特点优化函数的特点：任何最短路径的子路径都是：任何最短路径的子路径都是相对于子路径始点和终点的最短路径相对于子路径始点和终点的最短路径 求解步骤：确定子问题的边界、从最小的子问求解步骤：确定子问题的边界、从最小的子问题开始进行多步判断题开始进行多步判断动态规划的基本思想指出，一个最优策略具有这样的性质，不论过去状态和决策如何，对于前面的决策所形成的状态而言，其余决策必定构成最优策略。这便是最优决策序列的最优子结构特性，即一个问题的最优解中包含了子问

4、题的最优解。 设计一个动态规划算法，通常可以按以下几个步骤进行： （1）刻画最优解的结构特性； （2）递归定义最优解值； （3）以自底向上方式计算最优解值； （4）根据计算得到的信息构造一个最优解。 其中，第（1）至（3）步是动态规划算法的基本步骤。最优解值是最优解的目标函数的值。 7优化原则：优化原则：一个最优决策序列的任何子序列本身一定是一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优的决策序列相对于子序列的初始和结束状态的最优的决策序列例例2 2 求总长模求总长模1010的最小路径的最小路径最优解：下、下、下、下最优解：下、下、下、下动态规划算法的解：下、上、上、

5、上动态规划算法的解：下、上、上、上不满足优化原则，不能使用动态规划设计技术不满足优化原则，不能使用动态规划设计技术22225555u,6u,4u,2d,1ST使用动态规划技术的条件:优化原则8例例3 矩阵乘法：矩阵乘法： 设设A1,A2,An为矩阵序列，为矩阵序列，Ai为为Pi-1 Pi阶阶 矩阵，矩阵，i = 1,2,n. 确定乘法顺序使得元素相乘的总确定乘法顺序使得元素相乘的总 次数最少次数最少. 输入：向量输入：向量 P = ，n个矩阵的行数、列数个矩阵的行数、列数实例：实例： P = A1: 10 100, A2: 100 5, A3: 5 50, 乘法次序乘法次序 (A1 A2)A3

6、: 10 100 5 + 10 5 50 = 7500 A1(A2 A3): 10 100 50 + 100 5 50 = 75000 3.2 算法设计要素9)/2()211()(2)(2)2(2211()!)!2(11()(2322121222212nnnnneeennnennennennnnnnnnWnnnnnnnnnnn 枚举算法：加枚举算法：加n对括号的方法有对括号的方法有 种，是种，是一个一个Catalan数，是指数级别数，是指数级别 nnn211搜索空间的规模10由由 i 和和 j 确定子问题的边界：输入确定子问题的边界：输入P= , Ai.j 表表示乘积示乘积AiAi+1Aj 的

7、结果，其最后一次相乘是的结果，其最后一次相乘是 Ai.j = Ai.k Ak+1.j 确定优化函数和递推方程：确定优化函数和递推方程：mi,j 表示得到表示得到 Ai.j 的最少的相乘次数，则递推方程和初值的最少的相乘次数，则递推方程和初值 jiPPPjkmkimjijimjkijki, 1,min0,1动态规划算法设立标记函数：为了确定加括号的次序，设计表设立标记函数：为了确定加括号的次序，设计表 si,j,记录求得最优时最后一次运算的划分位置。记录求得最优时最后一次运算的划分位置。11算法1：递归实现算法算法3.1 RecurMatrixChain(P,i,j) 1. mi,j 2. si

8、,ji 3. for ki to j 1 do 4. q RecurMatrixChain(P,i,k) + RecurMatrixChain(P,k+1,j) + pi 1 pk pj 5. if qmi,j 6. then mi,jq 7. si,jk 8. Return mi,j 这里没有写出算法的全部描述（进入递归调用的初值等）这里没有写出算法的全部描述（进入递归调用的初值等）12复杂性满足递推关系复杂性满足递推关系 11111111)(2)()()()()(1)1()()(1)1()(nknknknkkTnOknTkTnOnTnOknTkTnOnT 数学归纳法证明数学归纳法证明 T(

9、n) 2n 1 n=2,=2,显然为真显然为真假设对于任何小于假设对于任何小于n 的的 k 命题为真命题为真, , 则则11111112)12(2)(22)()(2)()( nnnkknknOnOkTnOnT递归实现的复杂性递归实现的复杂性13复杂性高的原因：子问题重复计算复杂性高的原因：子问题重复计算n=5，计算子问题：，计算子问题：81个个；不同的子问题：；不同的子问题：15个个子子问问题题1-1 2-2 3-3 4-4 5-5 1-2 2-3 3-4 4-5 1-3 2-4 3-5 1-4 2-5 1-5数数812141284554222111214 A1 A2 A3 A4 A5 A6

10、A7 A8 r=2r=3r=4r=5r=6r=7r=8n=8 的的迭代过程迭代过程15算法算法3.3.2 MatrixChain(P,n) 1令所有的令所有的 mi,j初值为初值为0 1 i j n 2for r 2 to n do / r为计算的矩阵链长度为计算的矩阵链长度 3 for i 1 to n r+1 do /n-r+1为最后为最后r链的始位置链的始位置 4 j i+r 1 / 计算链计算链ij 5 mi,j mi+1,j + pi 1*pi*pj / Ai(Ai+1.Aj) 6. si,j i /记录分割位置记录分割位置 7. for k i+1 to j 1 do 8. t m

11、i,k+mk+1,j+ pi 1*pk*pj /(Ai.Ak)(Ak+1.Aj) 9. if tmi,j 10. then mi,jt 11. si,jk 复杂性：行复杂性：行2,3,7循环进行都是循环进行都是O(n)，循环内为，循环内为O(1) W(n)=O(n3)算法算法2：迭代实现迭代实现实例实例r=1 m1,1=0m2,2=0m3,3=0m4,4=0m5,5=0r=2 m1,2=15750 m2,3=2625 m3,4=750m4,5=1000r=3 m1,3=7875m2,4=4375 m3,5=2500r=4 m1,4=9375m2,5=7125r=5 m1,5=11875备忘录备

12、忘录 r=2 s1,2=1s2,3=2s3,4=3s4,5=4r=3 s1,3=1s2,4=2s3,5=3r=4 s1,4=3s2,5=3r=5 s1,5=3输入输入 P= , n=5，矩阵链：矩阵链：A1 A2 A3 A4 A5，其中，其中 A1:3035，A2:3515，A3:155，A4:510，A5:102017两种实现的比较两种实现的比较递归算法：时间复杂性高，空间较小递归算法：时间复杂性高，空间较小非递归算法：时间复杂性较低，空间消耗多非递归算法：时间复杂性较低，空间消耗多时间复杂性不同的原因：时间复杂性不同的原因：递归动态规划算法的子问题被多次重复计算递归动态规划算法的子问题被多

13、次重复计算子问题计算次数呈指数增长子问题计算次数呈指数增长非递归动态规划算法每个子问题只计算一次非递归动态规划算法每个子问题只计算一次子问题的计算随问题规模成多项式增长子问题的计算随问题规模成多项式增长18动态规划算法设计步骤(1) 划分子问题划分子问题 用参数表达子问题的边界，将问题求解转用参数表达子问题的边界，将问题求解转 变成多步判断变成多步判断的过程的过程. (2) 确定优化函数确定优化函数 以该函数的极大以该函数的极大(或极小或极小)作为判断的依据，确定是否满足作为判断的依据，确定是否满足优化原则优化原则. (3) 列出关于优化函数的递推方程列出关于优化函数的递推方程 (或不等式或不

14、等式)和边界条件和边界条件 (4) 考虑是否需要设立标记函数考虑是否需要设立标记函数(5) 自底向上计算，以备忘录方法自底向上计算，以备忘录方法 (表格表格)存储中间结果存储中间结果 19m 元钱，元钱，n 项投资，项投资，fi (x): 将将 x 元投入第元投入第 i 项项目的效益项项目的效益目标函数目标函数 max f1(x1) + f2(x2) + + fn(xn) 约束条件约束条件 x1 + x2 + + xn = m，xi N实例：实例：5万元钱，万元钱，4个项目，效益函数如下表所示个项目，效益函数如下表所示 xf1(x)f2(x)f3(x)f4(x)0000011102202125

15、10213131030224141532235152040243.3.1 投资问题投资问题20设设Fk(x) 表示表示 x元钱投给前元钱投给前k 个项目的最大效益个项目的最大效益多步判断多步判断 假设知道假设知道 p 元钱（元钱（p x）投给前）投给前 k 1个项目的最大效个项目的最大效 益，决定益，决定 x 元钱投给前元钱投给前 k 个项目的分配方案个项目的分配方案递推方程和边界条件递推方程和边界条件)()(1)()(max)(1110 xfxFkxxFxfxFkkkkxxkk 子问题划分和优化函数子问题划分和优化函数21实例的计算实例的计算xF1(x) x1(x)F2(x) x2(x)F3

16、(x) x3(x)F4(x) x4(x)111 111 011 020 1212 212 013 131 1313 316 230 333 1414 421 341 350 1515 526 443 461 1解解 x1 =1, x2 =0, x3=3, x4 =1 F4(5) = 61 22表中有表中有 m 行行 n 列列, 共计共计 mn 项项 对第对第Fk(x)项项 (2 k n,1 x m) 需要需要 x+1次加法次加法, x 次比较次比较)()()1()1(21)3()1(21)1(22121nmOnWmmnxmmnxnkmxnkmx 比较次数比较次数加法次数加法次数)()(1)()

17、(max)(1110 xfxFkxxFxfxFkkkkxxkk 算法的复杂度分析算法的复杂度分析23一个旅行者准备随身携带一个背包一个旅行者准备随身携带一个背包. 可以放入背包的物品可以放入背包的物品有有n 种种, 每种物品的重量和价值分别为每种物品的重量和价值分别为 wj , vj . 如果背包的最如果背包的最大重量限制是大重量限制是 b, 怎样选择放入背包的物品以使得背包怎样选择放入背包的物品以使得背包的价值最大的价值最大?N,max11 jnjjjnjjjxbxwxv约约束束条条件件目目标标函函数数线性规划问题线性规划问题 由线性条件约束的线性函数取最大或最小的问题由线性条件约束的线性函

18、数取最大或最小的问题整数规划问题整数规划问题 线性规划问题的变量线性规划问题的变量 xj 都是非负整数都是非负整数3.3.2 背包问题背包问题 (Knapsack Problem)24Fk(y)：装前：装前 k 种物品种物品, 总重不超过总重不超过 y, 背包的最大价值背包的最大价值i(k,y)：装前：装前 k 种物品种物品, 总重不超过总重不超过 y, 背包达最大价值时背包达最大价值时 装入物品的最大标号装入物品的最大标号递推方程、边界条件、标记函数递推方程、边界条件、标记函数0)()(0, 0)0(,0, 0)()(),(max)(11101 yyFvwyyFnkFbyyFvwyFyFyF

19、kkkkkkk子问题划分、优化函数、标记函数子问题划分、优化函数、标记函数 kkkkkkkkkkVWyFyFkVWyFyFyiyi)()()()()()(11125 v1 = 1, v2 = 3, v3 = 5, v4 = 9, w1 = 2, w2 = 3, w3 = 4, w4 = 7, b = 10 Fk(y) 的计算表如下的计算表如下:k y1234567891010112233445201334667993013556810101140135569101012实例计算实例计算26在上例中在上例中, 求得求得 i4(10)=4 x4 1 i4(10w4)=i4(3)=2 x2 1，x4

20、=1, x3=0 i2(3w2)=i2(0)=0 x2 = 1，x1=0 解解 x1=0, x2=1, x3=0, x4=1k y1234567891010111111111201222222223012333333340123334344用标记函数追踪问题的解用标记函数追踪问题的解27算法算法3.3 TrackSolution输入：输入：ik(y)表，其中表，其中k=1,2,n，y=1,2,b输出：输出：x1, x2, , xn，n种物品的装入量种物品的装入量 1. for j=1 to n do 2. xj 0 3. y b, jn 4. j ij(y) 5. xj 1 6. y y wj

21、 7. while ij(y)=j do 8. y y wj 9. xj xj+1 10. if ij(y) 0 goto 4 追踪解追踪解 xj 的算法的算法28X 的子序列的子序列 Z ：设序列：设序列 X, Z, 若存在若存在 X 的元素构成的下标严格递增序列的元素构成的下标严格递增序列使得使得 ， 则称则称 Z 是是 X 的的子序列子序列X 与与 Y 的的公共子序列公共子序列 Z ：Z 是是 X 和和 Y 的子序列的子序列子序列的长度子序列的长度：子序列的元素个数：子序列的元素个数 kmzzzZxxxX,.,.,2121 kiiixxx,.,21kjxzjij,.,2 , 1, 相关概

22、念相关概念3.3.3 最长公共子序列最长公共子序列 LCS29给定序列给定序列 X=, Y=求求 X 和和 Y 的最长公共子序列的最长公共子序列实例实例蛮力算法：检查蛮力算法：检查 X 的每个子序列在的每个子序列在Y 中出现中出现每个子序列每个子序列 O(n) 时间，时间，X 有有 2m 个个 子序列，最坏情况下子序列，最坏情况下时间复杂度：时间复杂度：O(n2m)问题描述问题描述X: A B C B D A BY: B D C A B A一个最长公共子序列一个最长公共子序列: B C B A30子问题边界：子问题边界： X和和Y 起始位置为起始位置为1，X的终止位置是的终止位置是 i，Y 的

23、的终止位置是终止位置是 j，记作，记作 Xi=，Yj=依赖关系：依赖关系： X=, Y=, Z=， Z 为为 X 和和 Y 的的 LCS，那么，那么 (1) 若若xm=yn zk=xm=yn,且且Zk 1是是Xm 1与与Yn 1的的 LCS； (2) 若若xm yn, zk xm Z是是Xm 1与与Y 的的 LCS； (3) 若若xm yn, zk yn Z是是X与与Yn 1的的 LCS.满足优化原则和子问题重叠性满足优化原则和子问题重叠性子问题划分及依赖关系子问题划分及依赖关系31令令 X 与与 Y 的子序列的子序列 Xi = ， Yj = Ci,j： Xi 与与 Yj 的的 LCS 的长度

24、的长度递推方程递推方程标记函数：标记函数：Bi, j, 其值为字符其值为字符 、 ，分别表示分别表示Ci,j取得最大值时的三种情况取得最大值时的三种情况 jijiyxjijiCjiCyxjijiCjijiC, 0, 1,1,max, 0,1 1, 1000,若若若若或或若若递推方程、标记函数递推方程、标记函数32算法算法3.4 LCS(X,Y,m,n) 1. for i1 to m do /行行1-4边界情况边界情况 2. Ci,00 3. for i1 to n do 4. C0,i0 5. for i1 to m do 6 for j1 to n do 7. if Xi=Yj 8. the

25、n Ci,jCi 1,j 1+1 9. Bi,j 10. else if Ci 1,j Ci,j 1 11. then Ci,jCi 1,j 12. Bi,j 13. else Ci,jCi,j 1 14. Bi,j动态规划算法动态规划算法33算法的计算复杂度算法的计算复杂度计算优化函数和标记函数：时间为计算优化函数和标记函数：时间为O(mn)构造解：每一步至少缩小构造解：每一步至少缩小X 或或 Y 的长度，时间的长度，时间 (m+n）空间：空间： (mn) 利用标记函数构造解利用标记函数构造解算法算法3.5 Structure Sequence(B, i, j)输入：输入：Bi,j输出：输出

26、：X与与Y的最长公共子序列的最长公共子序列 1. if i=0 or j=0 then return /一个序列为空一个序列为空 2. if Bi,j =“ ” 3. then 输出输出Xi 4. Structure Sequence(B, i1, j1) 5. else if Bi,j=“ ” then Structure Sequence (B, i1, j) 6. else Structure Sequence (B, i, j1) 输入：输入：X=, Y=，标记函数：标记函数：解：解：X2,X3, X4, X6, 即即 B, C, B, A 实例实例1234561B1,1= B1,2=

27、 B1,3= B1,4= B1,5= B1,6= 2B2,1= B2,2= B2,3= B2,4= B2,5= B2,6= 3B3,1= B3,2= B3,3= B3,4= B3,5= B3,6= 4B4,1= B4,2= B4,3= B4,4= B4,5= B4,6= 5B5,1= B5,2= B5,3= B5,4= B5,5= B5,6= 6B6,1= B6,2= B6,3= B6,4= B6,5= B6,6= 7B7,1= B7,2= B7,3= B7,4= B7,5= B7,6= 35像素点灰度值像素点灰度值 : 0 255，表示为，表示为8位二进制数位二进制数像素点灰度值序列像素点灰

28、度值序列 : p1, p2, pn，pi为第为第i个像素点灰度值个像素点灰度值变位压缩存储格式变位压缩存储格式: 将将 p1, p2, pn分割分割 m 段段 S1, S2, ,Sm i 段有段有li个像素，每个像素个像素，每个像素 bi位位, hi 为为 该该 段最大像素的位数段最大像素的位数 ) 1maxlog(, 8kSpiiphibhik约束条件：约束条件：每段像素个数每段像素个数 li 256段头段头11位：位： bi的二进制表示的二进制表示(3 位位) + li的二进制表示的二进制表示(8位位)i 段占用空间：段占用空间：bili + 11 问题问题 ：给定像素序列：给定像素序列

29、p1, p2, , pn，确定最优分段，即，确定最优分段，即3.3.4 图像压缩图像压缩为分段为分段,.,),11(min211jjiTSSSTilib 36灰度值序列灰度值序列 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： 分成分成12组，每组一个数组，每组一个数存储空间存储空间 分法分法1：11 3+4 3+8 1+2 8=69 分法分法2：11 1+8 12=107 分法分法3：11 12+4 3

30、+8 1+1 5+2 3=163结论：分法结论：分法1是其中最优的分法是其中最优的分法实例实例37递推方程递推方程 设设si是像素序列是像素序列p1, p2, , pi的最优分段所需存储位数的最优分段所需存储位数111 , 1 1 8)1maxlog(, 111, 1min256,min1 bSpjjibijibjjiSiSkSpijmkj*bmax(i-j+1,i)P1 P2 Pi-j Pi-j+1 PiSi-j位位 j 个灰度个灰度算法设计算法设计38算法算法3.6 Compress (P,n) /计算最小位数计算最小位数Sn1. Lmax256; header11; S00 /最大段长最

31、大段长Lmax, 头头header2. for i1 to n do 3. bilength(Pi) /bi是第是第i个灰度个灰度Pi的二进制位数的二进制位数4. bmaxbi /3-6行分法的最后一段只有行分法的最后一段只有Pi自己自己5. SiSi 1+bmax 6. li1 7. for j2 to mini,Lmax do /最后段含最后段含 j 个像素个像素 8. if bmaxSi j+j*bmax 11. then SiSi j+j*bmax 12. lij 13. SiSi+header 时间复杂度时间复杂度 T(n)=O(n)算法算法实实例例P=. S1=15, S2=19,

32、 S3=23, S4=42, S5=50，l1=1, l2=2, l3=3, l4=1, l5=2 10 121525512 S5=50 121110 121525512 S4=42 221110 121525512 S3=23 381110 121525512 S2=19 481110 121525512 S1=15 581110 1215255126811追踪解追踪解算法算法3.7 Traceback(n,l) 输入：数组输入：数组l 输出：数组输出：数组C / Cj是从后向前追踪的第是从后向前追踪的第 j段的长度段的长度1. j1 / j为正在追踪的段数为正在追踪的段数2. while

33、n 0 do 3. Cjln 4. nnln 5. jj+1 时间复杂度：时间复杂度：O(n)41 jikknjia max,0max1实例：实例： (-2, 11, -4, 13, -5, -2)解：最大子段和解：最大子段和 a2+a3+a4= 20 算法算法1-顺序求和顺序求和+比较比较算法算法2-分治策略分治策略算法算法3-动态规划动态规划问题：给定问题：给定n 个整数（可以为负数）的序列个整数（可以为负数）的序列 (a1, a2, , an) 求求 3.3.5 最大子段和最大子段和42算法算法3.8 Enumerate输入：数组输入：数组A1.n输出：输出：sum, first, la

34、st 1. sum0 2. for i1 to n do / i为当前和的首位置为当前和的首位置 3. for ji to n do / j为当前和的末位置为当前和的末位置 4. thissum0 / thissum为为Ai到到Aj之和之和 5. for ki to j do 6. thissumthissum+Ak 7. if thissum sum 8. then sumthissum 9. firsti / 记录最大和的首位置记录最大和的首位置 10 lastj / 记录最大和的末位置记录最大和的末位置时间复杂度：时间复杂度：O(n3) 算法算法1 顺序求和顺序求和+比较比较43将序列分

35、成左右两半，中间分点将序列分成左右两半，中间分点center递归计算左段最大子段和递归计算左段最大子段和 leftsum递归计算右段最大子段和递归计算右段最大子段和 rightsum acentera1的最大和的最大和S1, acenter+1an的最大和的最大和S2max leftsum, rightsum, S1+S2 leftsumrightsumA1 Ak Ak+1 An S1+S2算法算法2 分治策略分治策略44算法算法3.9 MaxSubSum(A, left, right）输入：数组输入：数组A，left，right分别是分别是A的左、右边界的左、右边界输出：输出：A的最大子段和

36、的最大子段和sum及其子段的前后边界及其子段的前后边界 1if |A|=1 then 输出元素值（当值为负时输出输出元素值（当值为负时输出0） 2center(left+right)/2 3leftsumMaxSubSum(A,left,center) /子问题子问题A1 4righsumMaxSubSum(A,center+1,right) /子问题子问题A2 5S1A1left, center /从从center向左的最大和向左的最大和 6S2A2center+1,right /从从center+1向右的最大和向右的最大和 7sumS1+S2 8if leftsum sum then su

37、mleftsum 9if rightsum sum then sumrightsum 时间：时间：T(n)=2T(n/2)+O(n), T(c)=O(1) T(n)=O(nlogn)分治算法分治算法45令令Ci 是是 A1.i中必须包含元素中必须包含元素Ai的最大子段和的最大子段和 递推方程递推方程: Ci= maxCi1+Ai, Ai i=2，,n C1=A1 若若A10, 否则否则C1=0 解：解：A1 A2 A3 Ai-1 Ai An最大子段和最大子段和 Ci-1最大子段和最大子段和 Ci 算法算法3：动态规划：动态规划 max1 ikjikjAiCmax)(OPT1iCAni 46算法

38、算法3.10 MaxSum(A, n)输入：数组输入：数组A输出：最大子段和输出：最大子段和sum, 子段的最后位置子段的最后位置c 1. sum0 2b0 / b是前一个最大子段和是前一个最大子段和 3. for i1 to n do 4. if b0 5. then bb+Ai 6. else bAi 7. if bsum 8. then sumb 9. ci /记录最大和的末项标号记录最大和的末项标号 10. return sum，c 时间复杂度：时间复杂度：O(n), 空间复杂度：空间复杂度：O(n)算法算法 MaxSum47S= 1, 2, 3, 4, 5, 6设集合设集合 S 为排

39、序的为排序的 n 个元素个元素 x1x2xn，将这些元素存，将这些元素存储在一棵二叉树的结点上，以查找储在一棵二叉树的结点上，以查找 x 是否在这些数中是否在这些数中. 如如果果 x 不在，确定不在，确定 x 在那个空隙在那个空隙. 检索方法：检索方法：1. 初始，初始，x与根元素比较；与根元素比较；2. x根元素，递归进入右子树；根元素，递归进入右子树；4. x=根元素，算法停止，输出根元素，算法停止，输出x；5. x到达叶结点，算法停止，输到达叶结点，算法停止，输 出出x不在数组中不在数组中. 3.3.6 最优二叉检索树最优二叉检索树42 6 531 L0 L1 L2 L4 L5 L6 L

40、348空隙：空隙： (- , x1), (x1, x2), , (xn 1, xn), (xn,+ ) , x0= - , xn+1= 给定序列给定序列 S = , x 在在 xi 的概率为的概率为bi , x 在在 (xi , xi+1) 的概率为的概率为ai , S的存取概率分布如下：的存取概率分布如下： P = 实例实例S=1,2,3,4,5,6P=存取概率不等情况存取概率不等情况S=1,2,3,4,5,6P=m(T2)= 1*0.1+2*0.2+3*0.1+4*(0.2+0.05)+5*0.1+1*0.04+2*0.01+4*(0.05+0.02+0.04)+5*(0.02+0.07)

41、= 2.3+0.95=3.25 216354 L0 L1 L2 L4 L5 L6 L342 6 531 L0 L1 L2 L4 L5 L6 L3实例实例T1T2m(T1)=1*0.1+2*(0.2+0.05)+3*(0.1+0.2+0.1)+3*(0.04+0.01+0.05+0.02+0.02+0.07)+2*0.04= 1.8+0.71=2.5150问题：给定数据集问题：给定数据集 S 和相关存取概率分布和相关存取概率分布 P，求一棵最优的，求一棵最优的(即平均比较次数最少的即平均比较次数最少的) 二分检索树二分检索树. 数据集数据集 S 存取概率分布存取概率分布 P=结点结点 xi 在在

42、T 中的深度是中的深度是 d(xi), i=1,2,n，空隙空隙 Lj 的深度为的深度为 d(Lj), j=0,1,n，平均比较次数为：平均比较次数为： 问问 题题 ninjjjiiLdaxdbt10)()(1(51算法设计算法设计:子问题划分子问题划分Si,j = 是是S 以以 i 和和 j 作为边界的子数据集作为边界的子数据集Pi,j = 是对应是对应Si,j存取概率分布存取概率分布例例: S= P= S2,4= P2,4=子问题划分：以子问题划分：以 xk 作为根，划分成两个子问题：作为根，划分成两个子问题： Si,k 1, Pi,k 1 Sk+1,j, Pk+1,j 例例: 以以B为根

43、，划分成以下子问题：为根，划分成以下子问题： S1,1=，P1,1= S3,5=, P3,5=52递推方程递推方程设设 mi,j 是相对于输入是相对于输入 Si,j 和和 Pi,j 的最优二叉搜索树的最优二叉搜索树的平均比较次数，令的平均比较次数，令是是 Pi,j 中所有概率（包括数据元素与空隙）之和中所有概率（包括数据元素与空隙）之和递推方程：递推方程： jiqqjippbajiw1,niiimnjijiwjkmkimjimjki,.,2 , 1, 0 1,1, 1 1,min, 证证 明明mi,jk ：根为：根为 xk 时的二分检索树平均比较次数的最小值时的二分检索树平均比较次数的最小值平

44、均比较次数：在所有平均比较次数：在所有 k 的情况下的情况下 mi,jk 的最小值，的最小值，mi,j=minmi,jk | i k j, 1 1,), 1 1,()()(), 1 1,(), 1 1,(), 1 1,(1), 1, 1()1, 1,(,11111jiwjkmkimbajkmkimbabbajkmkimjkwbkiwjkmkimbjkwjkmkiwkimjimjiqqjippjkqqjkppkkiqqkippkkk 54 复杂性估计：复杂性估计： T(n)=O(n3) S(n)=O(n2) 04. 288. 016. 01)5 , 3() 1 , 1 (1)5 , 1() 1,

45、 1 (min1)5 , 1 (88. 0)(3,5,16. 0 1 , 1 4 , 3, 2 mmkmkmmmmk实例实例0 1,1, 1 1,min, iimnjijiwjkmkimjimjki B AEDC L0 L1 L2 L4 L5 L30.30.20.10.10.10.040.020.02 0.05 0.06 0.013.3.7生物信息学中的动态规划算法生物信息学中的动态规划算法 RNA二级结构预测二级结构预测一级结构：由一级结构：由字母字母 A,C,G,U 标记的核苷酸构成的一条链标记的核苷酸构成的一条链二级结构：核苷酸相互匹配构成二级结构（平面图）二级结构：核苷酸相互匹配构成二

46、级结构（平面图）匹配原则：匹配原则： (1) 配对配对U-A,C-G； (2) 末端不出现末端不出现“尖角尖角”，位置，位置i - j 配对，则配对，则 i j4； (3) 每个核苷酸只能参加一个配对；每个核苷酸只能参加一个配对； (4) 不允许交叉，即如果位置不允许交叉，即如果位置 i1, i2, j1, j2 满足满足i1i2j1j2， 不允许不允许 i1-j1, i2-j2配对配对. 但可以允许但可以允许i1-j2, i2-j1配对配对. i1i2j1j2实例：实例：4sRNA的二级结构的二级结构57问题与算法设计问题与算法设计令令Ci,j是序列是序列Si.j的最大匹配对数的最大匹配对数

47、 问题：给定问题：给定RNA的一级结构：由的一级结构：由A,U,C,G 构成的长为构成的长为 n 的序的序列，寻找具有最大匹配对数的二级结构列，寻找具有最大匹配对数的二级结构.ii+1k 1k+1 kj 1 j50, 11,1max,1,max,4 ijjiCjkCkiCjiCjiCjki算法时间复杂度是算法时间复杂度是O(n3)序列比对序列比对编辑距离：编辑距离：给定两个序列给定两个序列S1和和S2，通过一系列字符编辑（插，通过一系列字符编辑（插入、删除、替换）等操作，将入、删除、替换）等操作，将S1转变成转变成S2. 完成这种转换所完成这种转换所需要的最少的编辑操作个数称为需要的最少的编辑

48、操作个数称为S1和和S2的编辑距离的编辑距离. 实例实例：vintner 转变成转变成 writers，编辑距离编辑距离 6： vintner 删除删除v：-intner 插入插入w：wintner 插入插入r： wrintner 删除删除n： wri-tner 删除删除n： writ-er 插入插入s： writers 算法设计算法设计S11.n 和和 S21.m 表示两个子序列表示两个子序列子问题划分：子问题划分：S11.i 和和 S21.jCi,j： S11.i 和和 S21.j 的编辑距离的编辑距离算法的时间复杂度是算法的时间复杂度是O(nm)iiCjjCjSiSjSiSjitjitjiCjiCjiCjiC 0 , 010, 1, 1, 1 1, 1, 1min,212160小小 结结(1) 引入参数来界定子问题的边界引入参数来界定子问题的边界. (2) 判断该优化问题是否满足优化原则判断该优化问题是否满足优化原则. (3) 注意子问题的重叠程度注意子问题的重叠程度. (4) 给出带边界参数的优化函数定义与优化函数的递推关系给出带