【精品】动态规划（可编辑.ppt

《【精品】动态规划（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】动态规划（可编辑.ppt（73页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

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

3、,An为为矩矩阵阵序列，序列，Ai为为Pi-1 Pi阶阶 矩矩阵阵，i=1,2,n.确定乘法确定乘法顺顺序使得元素相乘的序使得元素相乘的总总 次数最少次数最少.输输入：向量入：向量 P=，n个矩个矩阵阵的行数、列数的行数、列数实实例：例：P=A1:10 100,A2:100 5,A3:5 50,乘法次序乘法次序 (A1 A2)A3:10 100 5+10 5 50=7500 A1(A2 A3):10 100 50+100 5 50=75000 3.2 算法设计要素8枚举算法：加枚举算法：加n对括号的方法有对括号的方法有 种，是种，是一个一个Catalan数，是指数级别数，是指数级别搜索空间的规

4、模9由由 i 和和 j 确定子确定子问题问题的的边边界：界：输输入入P=,Ai.j 表表示乘示乘积积AiAi+1Aj 的的结结果，其最后一次相乘是果，其最后一次相乘是 Ai.j=Ai.k Ak+1.j 确定确定优优化函数和化函数和递递推方程：推方程：mi,j 表示得到表示得到 Ai.j 的最少的相乘次数，的最少的相乘次数，则递则递推方程和初推方程和初值值动态规划算法设立标记函数：为了确定加括号的次序，设计表设立标记函数：为了确定加括号的次序，设计表 si,j,记记录求得最优时最后一次运算的划分位置。录求得最优时最后一次运算的划分位置。10算法1：递归实现算法算法3.1 RecurMatrixC

5、hain(P,i,j)1.mi,j 2.si,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 这里没有写出算法的全部描述（进入递归调用的初值等）这里没有写出算法的全部描述（进入递归调用的初值等）11复复杂杂性性满满足足递递推关系推关系 数学数学归纳归纳法法证证明明 T(n)2n 1 n=2,=2,显然为真显然为真假设对于任何小于假设对于任何小于n 的的 k 命题为真命题为真,则则

6、递归实现的复杂性递归实现的复杂性12复杂性高的原因：子问题重复计算复杂性高的原因：子问题重复计算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数数81214128455422211121314A1 A2 A3 A4 A5 A6 A7 A8 r=2r=3r=4r=5r=6r=7r=8n=8 的的迭代过程迭代过程算法算法3.3.2 MatrixChain(P,n)1令所有的令所有的 mi,j初值为初值为0 1 i j n 2for r

7、 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 mi,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

8、(1)W(n)=O(n3)算法算法2：迭代实现迭代实现15实例实例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备备忘忘录录 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，其中，其中

9、A1:3035，A2:3515，A3:155，A4:510，A5:1020两种实现的比较两种实现的比较递归算法：时间复杂性高，空间较小递归算法：时间复杂性高，空间较小非递归算法：时间复杂性较低，空间消耗多非递归算法：时间复杂性较低，空间消耗多时间复杂性不同的原因：时间复杂性不同的原因：递归动态规划算法的子问题被多次重复计算递归动态规划算法的子问题被多次重复计算子问题计算次数呈指数增长子问题计算次数呈指数增长非递归动态规划算法每个子问题只计算一次非递归动态规划算法每个子问题只计算一次子问题的计算随问题规模成多项式增长子问题的计算随问题规模成多项式增长17动态规划算法设计步骤(1)划分子划分子问题

10、问题 用参数表达子用参数表达子问题问题的的边边界，将界，将问题问题求解求解转转 变变成多步判断成多步判断的的过过程程.(2)确定确定优优化函数化函数 以以该该函数的极大函数的极大(或极小或极小)作作为为判断的依据，确定是否判断的依据，确定是否满满足足优优化原化原则则.(3)列出关于列出关于优优化函数的化函数的递递推方程推方程(或不等式或不等式)和和边边界条件界条件(4)考考虑虑是否需要是否需要设设立立标记标记函数函数(5)自底向上自底向上计计算，以算，以备备忘忘录录方法方法(表格表格)存存储储中中间结间结果果 18m 元钱，元钱，n 项投资，项投资，fi(x):将将 x 元投入第元投入第 i

11、项项目的效益项项目的效益目标函数目标函数 max f1(x1)+f2(x2)+fn(xn)约束条件约束条件 x1+x2+xn=m，xi N实例：实例：5万元钱，万元钱，4个项目，效益函数如下表所示个项目，效益函数如下表所示xf1(x)f2(x)f3(x)f4(x)000001110220212510213131030224141532235152040243.3.1 投资问题投资问题19设设Fk(x)表示表示 x元钱投给前元钱投给前k 个项目的最大效益个项目的最大效益多步判断多步判断 假设知道假设知道 p 元钱（元钱（p x）投给前）投给前 k 1个项目的最大个项目的最大效效 益，决定益，决定

12、 x 元钱投给前元钱投给前 k 个项目的分配方案个项目的分配方案递推方程和边界条件递推方程和边界条件子问题划分和优化函数子问题划分和优化函数20实例的计算实例的计算xF1(x)x1(x)F2(x)x2(x)F3(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 21表中有表中有 m 行行 n 列列,共计共计 mn 项项 对第对第Fk(x)项项(2 k n,1 x m)需要需要 x

13、+1次加法次加法,x 次比较次比较算法的复杂度分析算法的复杂度分析22一个旅行者准备随身携带一个背包一个旅行者准备随身携带一个背包.可以放入背包的物品可以放入背包的物品有有n 种种,每种物品的重量和价值分别为每种物品的重量和价值分别为 wj,vj.如果背包的最如果背包的最大重量限制是大重量限制是 b,怎样选择放入背包的物品以使得背包怎样选择放入背包的物品以使得背包的价值最大的价值最大?线性规划问题线性规划问题 由线性条件约束的线性函数取最大或最小的问题由线性条件约束的线性函数取最大或最小的问题整数规划问题整数规划问题 线性规划问题的变量线性规划问题的变量 xj 都是非负整数都是非负整数3.3.

14、2 背包问题背包问题 (Knapsack Problem)23Fk(y)：装前：装前 k 种物品种物品,总重不超过总重不超过 y,背包的最大价值背包的最大价值i(k,y)：装前：装前 k 种物品种物品,总重不超过总重不超过 y,背包达最大价值时背包达最大价值时 装入物品的最大标号装入物品的最大标号递推方程、边界条件、标记函数递推方程、边界条件、标记函数子问题划分、优化函数、标记函数子问题划分、优化函数、标记函数24v1=1,v2=3,v3=5,v4=9,w1=2,w2=3,w3=4,w4=7,b=10 Fk(y)的计算表如下的计算表如下:k y1234567891010112233445201

15、334667993013556810101140135569101012实例计算实例计算25在上例中在上例中,求得求得 i4(10)=4 x4 1 i4(10w4)=i4(3)=2 x2 1，x4=1,x3=0 i2(3w2)=i2(0)=0 x2=1，x1=0 解解 x1=0,x2=1,x3=0,x4=1k y1234567891010111111111201222222223012333333340123334344用标记函数追踪问题的解用标记函数追踪问题的解26算法算法3.3 TrackSolution输输入：入：ik(y)表，其中表，其中k=1,2,n，y=1,2,b输输出：出：x1,

16、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 7.while ij(y)=j do 8.y y wj 9.xj xj+1 10.if ij(y)0 goto 4 追踪解追踪解 xj 的算法的算法27X 的子序列的子序列 Z ：设序列：设序列 X,Z,若存在若存在 X 的元素构成的下标严格递增序列的元素构成的下标严格递增序列使得使得 ，则称则称 Z 是是 X 的的子序列子序列X 与与 Y 的的公共子序列公共子序列 Z：Z 是是 X 和和 Y 的子序列的子序列子序列的长度子序列的长度

17、：子序列的元素个数：子序列的元素个数相关概念相关概念3.3.3 最长公共子序列最长公共子序列 LCS28给定序列给定序列 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 A29子问题边界：子问题边界：X和和Y 起始位置起始位置为为1，X的的终

18、终止位置是止位置是 i，Y 的的终终止位置是止位置是 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.满足优化原则和子问题重叠性满足优化原则和子问题重叠性子问题划分及依赖关系子问题划分及依赖关系30令令 X 与与 Y 的子序列的子序列 Xi=，Yj=Ci,j：Xi 与与 Yj 的的 LCS 的长度的长度

19、递推方程递推方程标记函数：标记函数：Bi,j,其值为字符其值为字符、，分别表示分别表示Ci,j取取得最大得最大值时值时的三种情况的三种情况递推方程、标记函数递推方程、标记函数31算法算法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.then 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

20、13.else Ci,jCi,j 1 14.Bi,j动态规动态规划算法划算法32算法的计算复杂度算法的计算复杂度计算优化函数和标记函数：时间为计算优化函数和标记函数：时间为O(mn)构造解：每一步至少缩小构造解：每一步至少缩小X 或或 Y 的长度，时间的长度，时间(m+n）空间：空间：(mn)利用标记函数构造解利用标记函数构造解算法算法3.5 Structure Sequence(B,i,j)输输入：入：Bi,j输输出：出：X与与Y的最的最长长公共子序列公共子序列 1.if i=0 or j=0 then return /一个序列一个序列为为空空 2.if Bi,j=“”3.then 输输出出

21、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)33输输入：入：X=,Y=，标记标记函数：函数：解：解：X2,X3,X4,X6,即即 B,C,B,A 实例实例1234561B1,1=B1,2=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=5B

22、5,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=像素点灰度值像素点灰度值:0 255，表示为，表示为8位二进制数位二进制数像素点灰度值序列像素点灰度值序列:p1,p2,pn，pi为第为第i个像素点灰度值个像素点灰度值变位压缩存储格式变位压缩存储格式:将将 p1,p2,pn分割分割 m 段段 S1,S2,Sm i 段有段有li个像素，每个像素个像素，每个像素 bi位位,hi 为为 该该 段最大像素的位数段最大像素的位数约束条件：约束条件：每段像素个数每段像素个数

23、li 256段头段头11位：位：bi的二进制表示的二进制表示(3 位位)+li的二进制表示的二进制表示(8位位)i 段占用空间：段占用空间：bili+11 问题问题：给定像素序列：给定像素序列 p1,p2,pn，确定最优分段，即，确定最优分段，即3.3.4 图像压缩图像压缩35灰度值序列灰度值序列 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

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

25、.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)算法算法38实实例例P=.S1=15,S2=19,S3=23,S4=42,S5=50，l1=1,l2=2,l

26、3=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 n 0 do 3.Cjln 4.nnln 5.jj+1 时间时间复复杂杂度：度：O

27、(n)实实例：例：(-2,11,-4,13,-5,-2)解：最大子段和解：最大子段和 a2+a3+a4=20 算法算法1-顺顺序求和序求和+比比较较算法算法2-分治策略分治策略算法算法3-动态规动态规划划问题：给定问题：给定n 个整数（可以为负数）的序列个整数（可以为负数）的序列 (a1,a2,an)求求 3.3.5 最大子段和最大子段和41算法算法3.8 Enumerate输输入：数入：数组组A1.n输输出：出：sum,first,last 1.sum0 2.for i1 to n do /i为为当前和的首位置当前和的首位置 3.for ji to n do /j为为当前和的末位置当前和的末

28、位置 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 顺序求和顺序求和+比较比较42将序列分成左右两半，中间分点将序列分成左右两半，中间分点center递归计算左段最大子段和递归计算左段最大子段和 leftsum递归计算右段最大子段和递归计算右段最大子段和 rightsum ac

29、entera1的最大和的最大和S1,acenter+1an的最大和的最大和S2max leftsum,rightsum,S1+S2 leftsumrightsumA1 Ak Ak+1 An S1+S2算法算法2 分治策略分治策略43算法算法3.9 MaxSubSum(A,left,right）输输入：数入：数组组A，left，right分分别别是是A的左、右的左、右边边界界输输出：出：A的最大子段和的最大子段和sum及其子段的前后及其子段的前后边边界界 1if|A|=1 then 输输出元素出元素值值（当（当值为负时输值为负时输出出0）2center(left+right)/2 3leftsu

30、mMaxSubSum(A,left,center)/子子问题问题A1 4righsumMaxSubSum(A,center+1,right)/子子问题问题A2 5S1A1left,center /从从center向左的最大和向左的最大和 6S2A2center+1,right /从从center+1向右的最大和向右的最大和 7sumS1+S2 8if leftsum sum then sumleftsum 9if rightsum sum then sumrightsum时间：时间：T(n)=2T(n/2)+O(n),T(c)=O(1)T(n)=O(nlogn)分治算法分治算法44令令Ci 是

31、是 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：动态规划：动态规划45算法算法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

32、bAi 7.if bsum 8.then sumb 9.ci /记录记录最大和的末最大和的末项标项标号号 10.return sum，c 时间复杂度：时间复杂度：O(n),空间复杂度：空间复杂度：O(n)算法算法 MaxSum46S=1,2,3,4,5,6设集合设集合 S 为排序的为排序的 n 个元素个元素 x1x2xn，将这些元素存，将这些元素存储在一棵二叉树的结点上，以查找储在一棵二叉树的结点上，以查找 x 是否在这些数中是否在这些数中.如如果果 x 不在，确定不在，确定 x 在那个空隙在那个空隙.检索方法：检索方法：1.初始，初始，x与根元素比较；与根元素比较；2.x根元素，递归进入右子

33、树；根元素，递归进入右子树；4.x=根元素，算法停止，输出根元素，算法停止，输出x；5.x到达叶结点，算法停止，输到达叶结点，算法停止，输 出出x不在数组中不在数组中.3.3.6 最优二叉检索树最优二叉检索树42 6 531 L0 L1 L2 L4 L5 L6 L347空隙：空隙：(-,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=存取概率不等情况存取概率不等情况48S=

34、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)=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.51问题：给定数据集问题：给定数据集 S 和相关存取

35、概率分布和相关存取概率分布 P，求一棵最优，求一棵最优的的(即平均比较次数最少的即平均比较次数最少的)二分检索树二分检索树.数据集数据集 S 存取概率分布存取概率分布 P=结结点点 xi 在在T 中的深度是中的深度是 d(xi),i=1,2,n，空隙空隙 Lj 的深度的深度为为 d(Lj),j=0,1,n，平均比平均比较较次数次数为为：问问 题题50算法设计算法设计:子问题划分子问题划分Si,j=是是S 以以 i 和和 j 作为边界的子数据集作为边界的子数据集Pi,j=是对应是对应Si,j存取概率分布存取概率分布例例:S=P=S2,4=P2,4=子问题划分：以子问题划分：以 xk 作为根，划分

36、成两个子问题：作为根，划分成两个子问题：Si,k 1,Pi,k 1 Sk+1,j,Pk+1,j 例例:以以B为根，划分成以下子问题：为根，划分成以下子问题：S1,1=，P1,1=S3,5=,P3,5=51递推方程递推方程设设 mi,j 是相对于输入是相对于输入 Si,j 和和 Pi,j 的最优二叉搜索树的最优二叉搜索树的平均比较次数，令的平均比较次数，令是是 Pi,j 中所有概率（包括数据元素与空隙）之和中所有概率（包括数据元素与空隙）之和递推方程：递推方程：52证证 明明mi,jk：根：根为为 xk 时时的二分的二分检检索索树树平均比平均比较较次数次数的最小的最小值值平均比平均比较较次数：在

37、所有次数：在所有 k 的情况下的情况下 mi,jk 的最的最小小值值，mi,j=minmi,jk|i k j 复杂性估计：复杂性估计：T(n)=O(n3)S(n)=O(n2)实例实例 B AEDC L0 L1 L2 L4 L5 L30.30.20.10.10.10.040.020.02 0.05 0.06 0.01543.3.7生物信息学中的动态规划算法生物信息学中的动态规划算法 RNA二二级结级结构构预测预测一一级结级结构：由构：由字母字母 A,C,G,U 标记的核苷酸构成的一条链标记的核苷酸构成的一条链二二级结级结构：核苷酸相互匹配构成二构：核苷酸相互匹配构成二级结级结构（平面构（平面图图

38、）匹配原匹配原则则：(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的二级结构的二级结构问题与算法设计问题与算法设计令令Ci,j是序列是序列Si.j的最大匹配对数的最大匹配对数 问题：给定问题：给定RNA的一级结构：由的一级结构：由A,

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

40、 删除删除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)小小 结结(1)引入参数来界定子引入参数来界定子问题问题的的边边界界.(2)判断判断该优该优化化问题问题是否是否满满足足优优化原化原则则.(3)注意子注意子问题问题的重叠程度的重叠程度.(4)给

41、给出出带边带边界参数的界参数的优优化函数定化函数定义义与与优优化函数的化函数的递递推关系推关系 考考虑标记虑标记函数函数.找到找到递递推关系的初推关系的初值值.(5)采用自底向上的采用自底向上的实现实现技技术术，从最小的子，从最小的子问题问题开始迭代开始迭代计计 算，算，计计算中用算中用备备忘忘录录保留保留优优化函数和化函数和标记标记函数的函数的值值.(6)利用利用备备忘忘录录和和标记标记函数通函数通过过回溯得到最回溯得到最优优解解.(7)动态规动态规划算法的划算法的时间时间复复杂杂度是度是对对所有子所有子问题问题的的计计算工作算工作 量求和量求和.(8)动态规动态规划算法一般使用划算法一般使

42、用较较多的存多的存储储空空间间，这这往往成往往成为为限限 制制动态规动态规划算法使用的瓶划算法使用的瓶颈颈因素因素.603.3.8 流水作业调度问题描述 假定处理一个作业需要执行若干项不同类型的任务，每一类任务只能在某一台设备上执行。设一条流水线上有n个作业J=J0,J1,Jn1和m台设备P=P1,P2,Pm。每个作业需依次执行m个任务，其中第j个任务只能在第j台设备上执行，1jm。设第i个作业的第j项任务Tji所需时间为tji，1jm，0i2则不然）。定理定理定理定理 流水作业调度问题具有最优子结构的性质。流水作业调度问题具有最优子结构的性质。如果在调度方案的作业排列中，作业i和j满足min

43、bi,ajminbj,ai，则称作业i和j满足JohnsonJohnson不等式。不等式。可以设计下列作业排列方法。这样做能得到最优调度方案 (1)如果mina0,a1,an1,b0,b1,bn1是ai，则ai应是最优排列的第一个作业；(2)如果mina0,a1,an-1,b0,b1,bn1是bj，则bj应是最优排列的最后一个作业；(3)继续（1）和（2）的做法，直到完成所有作业的排列。例例2 21111设n4，（a0,a1,a2,a3）=(3,4,8,10)（b0,b1,b2,b3）=(6,2,9,15)。设=(0),(1),(2),(3)是最优作业排列。先将任务按处理时间的非减次序排列成：

44、（b1,a0,a1,b0,a2,b2,a3,b3）=(2,3,4,6,8,9,10,15)先选 b1，将其加在最优作业排列的最后，故(3)=1再选a0，应加在最优作业排列的最前面，故(0)=0考察a1和b0，因作业1和0已调度，接着考察a2，应有(1)=2，再考察b2和a3，令(2)=3。所以最优解为：(0),(1),(2),(3)（0,2,3,1）。Johnson算法Johnson算法具体描述如下：设ai和bi，0in分别为作业i在两台设备上的处理时间。建立由三元组（作业号,处理时间,设备号）组成的三元组表d。对三元组表按处理时间排序，得到排序后的三元组表d。对三元组表的每一项di，0in，

45、从左和右两端生成最优作业排列cj,0jn，cj是作业号。如果di的设备号为1，则将作业i置于c的左端末尾，否则置于c的右端末尾。程序程序程序程序JohnsonJohnsonJohnsonJohnson算法算法算法算法struct Triplet int operator(Triplet b)const return tb.t;int jobNo,t,ab;void FlowShop(int n,int*a,int*b,int*c)Triplet dmSize=0,0,0;for(int i=0;in;i+)if(aibi)di.jobNo=i;di.ab=0;di.t=ai;else di.jobNo=i;di.ab=1;di.t=bi;Sort(d,n);int left=0,right=n-1;for(i=0;in;i+)if(di.ab=0)cleft+=di.jobNo;else cright-=di.jobNo;Johnson算法的时间取决于对作业集合的排序，因此，在最坏情况下算法的时间复杂度为O(nlogn)，所需的空间复杂度为O(n)。