第3章动态规划ppt课件

1,第3章动态规划,2,要点,理解动态规划算法的概念掌握动态规划算法的基本要素掌握设计动态规划算法的设计策略,3,本章主要内容,矩阵连乘问题掌握动态规划算法的基本要素熟练掌握流水作业调度了解0-1背包问题熟练掌握最优二叉搜索树熟练掌握,4,1n=0F(n)=1n=1F(n-1)+F(n-2)n1,例31,Fibonacci数列问题,F(4),F(3),F(2),F(2),F(1),F(1),F(0),动态规划算法,F(1),F(0),5,动态规划算法,将待求解的问题分解成若干个子问题，先求解子问题，并存储子问题的解而避免计算重复的子问题，再由子问题的解得到原问题的解。,算法思想,6,动态规划与分治的联系区别,都是分解成子问题，由子问题的解得到原问题的解。分治中子问题相互独立，而动态规划中子问题互相有联系，且存在重复计算，即存在重叠子问题。,7,动态规划算法设计步骤,（1）找出最优解的性质，刻画其结构特征（2）递归地定义最优值（3）以自底向上的方式计算出最优值（4）根据计算最优值时得到的信息，构造一个最优解,8,3.1矩阵连乘问题,给定n个矩阵A1,A2,An，其中Ai是一个ri-1ri矩阵(1in)，即AiAi+1是可乘的，求出n个矩阵相乘的最优计算次序，使得计算量最小。,问题提出,设三个矩阵A1,A2,A3大小分别为10100，1005，550，考虑(A1(A2A3),(A1A2)A3的结果与相乘的次数。,9,矩阵相乘满足结合律，连乘积可以有许多不同的次序。这种次序可以用加括号的方式确定。考查两个矩阵相乘的情形：C=AB。如果矩阵A，B分别是pr和rq矩阵，则它们的乘积C将是pq矩阵，其(i,j)元素为则共需要pqr次数乘。,矩阵连乘问题,A1,A2,A3大小分别为10100，1005，550，(A1(A2A3),(A1A2)A3)的结果相同，都是1050的矩阵，计算量分别为75000，7500,10,完全加括号的矩阵连乘积单个矩阵是完全加括号的；矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。,考虑n=4的情况，此时矩阵运算A*B*C*D可按以下方式（顺序）计算(完全加括号方式)：A*(B*C)*D)，A*(B*(C*D)，(A*B)*(C*D)，(A*(B*C)*D,矩阵连乘问题,11,两个矩阵的乘法,voidMatrixMultiply(int*a,int*b,int*c,intra,intca,intrb,intcb)if(ca!=rb)error(“矩阵不可乘”)；for(inti=0;ira;i+)for(intj=0;jcb;j+)intsum=ai0*b0j;for(intk=1;kca;k+)sum+=aik*bkj;cij=sum;,矩阵连乘问题,12,穷举搜索法,对于n个矩阵的连乘积，设有p(n)个计算次序。我们可以在第k个和第k1个矩阵之间将原矩阵划分为两个子矩阵序列，然后分别对这两个矩阵子序列完全加括号，最后对所得的结果加括号，则其中P(n)=C(n-1)，,矩阵连乘问题,13,1.分析最优解的结构,设Ai:j为矩阵连乘积AiAi+1Aj计算A1:n的最优次序，设该次序在矩阵Ak和Ak1之间断开，1kn,则完全加括号方式为(A1Ak)(Ak+1An)总计算量为mi,j=mi,k+mk+1,j+A1:k和Ak+1:n相乘的计算量。,矩阵连乘问题,14,最优子结构特征,计算A1:n的一个最优次序所包含的计算矩阵子链A1:k和Ak+1:n的次序也是最优的矩阵连乘积计算次序问题的最优解包含着其子问题的最优解，也就是最优子结构性质。,矩阵连乘问题,考虑A1:k和Ak+1:n相乘所需的计算量，Ai:k和Ak+1:j相乘呢,A1:k的结果为r0*rk的矩阵，Ak+1:n的结果为rk*rn的矩阵，则它们相乘的计算量为p0*pk*pn,15,2.建立递归关系,设计算Ai:j所需的最少次数为mij,原问题的最优解为m1n。,矩阵连乘问题,16,采用递归方法计算,intRecurMatrixChain(inti,int,j,intp)if()return0;intu=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j,p)+pi-1*pi*pj;sij=i;for(intk=i+1;kj;k+)intt=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j,p)+pi-1*pi*pj;if(tu)u=t;sij=k;returnu;,参加运算矩阵链起始位置,矩阵链终止位置,i=j,取第一个断开位置时计算量,记录当前断开位置,循环取k的可取断开位置,矩阵连乘问题,17,递归树,14,11,24,12,34,13,44,22,34,23,44,11,22,33,44,11,23,12,33,33,44,22,33,22,33,11,22,矩阵连乘问题,18,可以证明该算法的计算时间T(n)有指数下界，设算法中判断语句和赋值语句花费常数时间，则由算法的递归部分可得关T(n)的递归不等式如下：,矩阵连乘问题,19,对于1ijn不同的有序对(i,j)对应于不同的子问题mij，因此，不同的子问题的个数最多只有用动态规划解此问题时，在计算过程中，保存已解决的子问题答案，每个子问题只计算一次，而在后面用到时简单地查一下，从而避免了大量的重复计算,矩阵连乘问题,20,24,22,34,12,33,44,11,14,13,23,矩阵连乘问题,3.计算最优值,21,3.计算最优值,对于m1n可以按照下面顺序构成m12m23m34m45mn-1nm13m24m35mn-2nm14m25m36mn-3nm1n-1m2nm1n,矩阵连乘问题,计算mij时，只用到已计算出的mik和mk+1j,22,3.计算最优值,置所有只有一个矩阵的矩阵链计算量为0，即mii=0，i=1,2,n。通过上一步的结果可以得到所有矩阵链长度为2的子问题的最优计算量。通过上两步的结果可以得到所有矩阵链长度为3的子问题的最优计算量,矩阵连乘问题,计算mij时，只用到已计算出的mik和mk+1j,23,A1A2A3A4A5A63035351515551010202025,例32,设要计算矩阵连乘积A1A2A3A4A5A6,其中各矩阵的维数分别为,123456,15750,2625,750,1000,5000,m11+m23+p0p1p3=7875m13=minm12+m33+p0p2p3=15750,9375,11875,15125,4375,7125,10500,2500,5375,3500,7875,i,j,24,计算过程,先计算出mii=0,i=1,2,n,然后，依次计算mii+1,i=1,2,n-1(矩阵长度为2)；mii+2,i=1,2,n-2,(矩阵链长度为3)；.每次计算只用到已计算出的mik和mk+1j计算顺序m11,m22,m33.mnnm12,m23,m34mn-1nm13,m24,m35mn-2nm1n-1,m2nm1n,矩阵连乘问题,25,3.计算最优值,voidMatrixChain(intp,intn,int*m,int*s)for(inti=1;i=n;i+)mii=;/单个矩阵的计算量for(intr=2;r=n;r+)/r为每次循环矩阵链的长度for(inti=1;i=;i+)intj=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(intk=i+1;kj;k+)intt=mik+mk+1j+;if(tmij)mij=t;sij=k;,矩阵连乘问题,0,nr+1,取第一个可取位置，即断开位置为i,循环取k的可取位置,pi-1*pk*pj,26,算法复杂度,算法MatrixChain的主要计算量取决于程序中对r,i和k的三重循环，循环体内的计算量为O(1)，三重循环的总次数是O(n3)，所以，算法的计算时间上界为O(n3)。,27,4.构造最优解,上述算法只是明确给出了矩阵最优连乘次序所用的数乘次数m1n，并未明确给出最优连乘次序，即完全加括号方法。但是以sij为元素的2维数组却给出了足够的信息。事实上，sij=k说明，计算连乘积Ai:j的最佳方式应该在矩阵Ak和Ak+1之间断开，即最优加括号方式为(Ai:k)(Ak+1:j)。,28,123456011333023330333045050,考虑计算A16时的顺序,S16,(A1A3)(A4A6),S13,A1(A2A3),S46,(A4A5)A6,S11=0,S23=0,A1(A2)(A3),S22=S33=0,S66=0,S45=0,(A4)(A5)A6,S44=S55=0,29,根据最优值算法构造最优解,VoidTraceback(inti,intj,int*s)if(i=j)return;Traceback(i,sij,s);Traceback(sij+1,j,s);cout“MultiplyA”i“,”sij;cout“andA”(sij+1)“,”j;endl;,调用Traceback(1,n,s)即可得到A1:n,30,作业1当A1A2A3A4A5分别为2025，2510，105，515，1520的矩阵时，填写相应的mij和sij，并给出最优计算次序。,31,3.2动态规划算法的基本要素,1最优子结构性质2重叠子问题性质,32,1.最优子结构,当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。分析最优子结构性质时，一般假设由问题的最优解导出的子问题不是最优的，然后再设法说明在这个假设下可以构造出一个比原问题更优解更好的解，从而导出矛盾。,动态规划算法的基本要素,33,2.重叠子问题,在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法对每个问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，用常数时间查看一下结果。因此，用动态规划算法通常只需要多项式时间。,动态规划算法的基本要素,34,3.备忘录方法,用一个表格来保存已解决的子问题的答案，用的时候查表即可。采用的递归方式是自顶向下，动态规划是自低向上控制结构与直接递归相同，区别在于备忘录方式为每个解过的子问题建立备忘录。初始化为每个子问题的记录存入一个特殊的值，表示并未求解。在求解过程中，查看相应记录如果是特殊值，表示未求解，否则只要取出该子问题的解答即可。,动态规划算法的基本要素,35,备忘录方法解矩阵乘,intMemoizedMatrixChain(intn,int*m,int*s)for(inti=1;i=n;i+)for(intj=i;j0)returnmij;if(i=j)return0;intu=LookupChain(i,i)+LookupChain(i+1,j)+pi-1*pk*pj;sij=i;for(intk=i+1;k0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？,41,考虑有三种物品,它们的重量为(w1,w2,w3)=(2,3,4),价值为(v1,v2,v3)=(1,2,5),当背包容量为c=6时，如何装背包总价值最大？,x1,x2,x3=1,0,1v1*x1+v2*x2+v3*x3=6,x1,x2,x3=0,0,01,0,00,1,00,0,11,1,01,0,1,42,给定c0,wi0,vi0,1in,要求找出一个n元向量(x1,x2,xn),xi0,1,1in,使得，而且达到最大，用knap(1,n,c)表示。,约束条件：背包容量限制,vixi,效益值最大化,43,1.最优子结构性质,证明0/1背包问题具有最优子结构性质即若背包容量为c时，(y1,y2,yn)为待选物品为1到n时knap(1,n,c)的最优解，则(y2,yn)将是物品1作出选择后的子问题的最优解,当第一个物品做出决策后，有两种状态y1=0，则背包容量没有影响，(y2,yn)是的最优解y1=1，则背包减少w1，价值增长v1，(y2,yn)是的最优解,x1,vixi,knap(2,n,c-w1*y1),knap(2,n,c),knap(2,n,cw1),44,证明：,因为，若(z2,zn)是下述子问题的一个最优解，而(y2,yn）不是它的最优解,这说明(y1,z2,zn)是所给问题的一个更优解，从而(y1,y2,yn)不是原问题的最优解，矛盾,则,因此,45,2.递归关系,设背包问题的子问题的最优值为m(i,j),即m(i,j)是背包容量为j，可选择物品为i，i1，,n时的最优值。当选择第i个物品时，。如果不选择第i个物品，则。由问题的最优子结构性质，我们可以建立计算m(i,j)的递归式如下：,m(i,j)=m(i+1,j-wi)+vi,m(i,j)=m(i+1,j),46,例:四个物品，背包容积为5，w4=2,1,3,2，v4=12,10,20,15，求最大价值m1c及选取的物品编号,4,3,2,1,4,3,2,1,0,5,0,0,0,0,0,10,15,15,15,15,15,15,20,20,35,35,30,25,37,i,j,x4X3X2X1,1,m15m25所以物品1被选,cw1=3,查看m23m33,1,jw2=2,查看m32=m42,0,查看m420,1,47,3.算法描述,templatevoidKnapsack(Typev,intw,intc,intn,Type*m)intjMax=min(wn-1,c);for(intj=0;j1;i-)jMax=min(wi-1,c);for(intj=0;j=w1)m1c=max(m1c,m2c-w1+v1);,0,vn,mi+1j,m2c,初始化mnj,只剩下第一个物品时，如果剩余背包容积大于w1时，要进行选择,48,m15m25,4,3,2,1,4,3,2,1,0,5,0,0,0,0,0,10,10,15,15,15,15,15,20,20,35,35,30,25,37,i,j,构造最优解,x1=1c=5-w1=3,m23m33,x2=1c=3-w2=2,m32=m42,x3=0c=2,m420,x4=1,49,构造最优解,TemplateVoidTraceback(Type*m,intw,intc,intn,intx)for(inti=1;i2n时，算法需要(n2n),n=3,(w1,w2,w3)=(2,3,4),v1,v2,v3=(1,2,5),c=5,51,设有n种不同面值的硬币，各硬币的面值存于数组T1:n中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数不限。(1)当只用硬币面值T1,T2,Ti时，可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值，找不出钱数j时，记C(i,j)=。给出C(i,j)的递归表达式及初始条件。1in,1jL。(2)设计一个动态规划算法，对1jL，计算出所有的C(n,j)。算法中只允许使用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂性。,52,3.5最优二叉搜索树OptimalBinarySearchTrees,53,二叉搜索树最优二叉搜索树最优二叉搜索树问题描述最优子结构证明递归计算最优值算法,54,是一棵空树或者满足以下的性质：每个结点作为搜索对象，它的关键字是互不相同的。对于树上的所有结点，如果它有左子树，那么左子树上所有结点的关键字都小于该结点的关键字。对于树上的所有结点，如果它有右子树，那么右子树上所有结点的关键字都大于该结点的关键字,1、二叉搜索树定义,55,搜索过程：从根结点开始，如果根为空，则搜索不成功；否则使用待搜索值与根结点比较，如果待搜索值等于根结点关键字，则搜索成功返回，如果小于根结点，则向左子树搜索；如果大于根结点，则向右子树搜索。,1、二叉搜索树,56,构造不同的二叉搜索树就有不同的性能特征。二叉搜索树a在最坏情况下找一个标识符需要4次比较，而b表示的二分检索树最坏情况下只需3次比较。假设只作成功的检索并且检索每个标识符的概率相同，则两棵二分检索树在平均情况下各需要12/5和11/5次比较。,1、二叉搜索树,57,2、最优二叉搜索树,存在的两个问题1在实际中也会遇到不成功检索的情况。2在实际中，不同标识符会有不同的检索概率。对给定的标识符集合，希望给出构造二分搜索树的方法，使得所构造的二分搜索树具有最优的性能。,最优二叉搜索树,58,扩充二叉树：当二叉树里出现空的子树时，就增加新的、特殊的结点空树叶。对于原来二叉树里度数为1的分支结点，在它下面增加一个空树叶；对于原来二叉树的树叶，在它下面增加两个空树叶。扩充二叉树是满二叉树，新增加的空树叶（以下称外部结点）的个数等于原来二叉树的结点（以下称内部结点）个数加1,在实际中也会遇到不成功检索的情况。,最优二叉搜索树,59,A,A代表其值处于wim和wul之间的可能关键码集合,最优二叉搜索树,60,设S=x1,x2,xn是一个有序集合，且x1,x2,xn表示有序集合的二叉搜索树利用二叉树的顶点存储有序集中的元素，而且具有性质：存储于每个顶点中的元素x大于其左子树中任一个顶点中存储的元素，小于其右子树中任意顶点中存储的元素。二叉树中的叶顶点是形如(xi,xi+1)的开区间。,在二叉搜索树中搜索一个元素x,(1)在二叉树的内部顶点处找到：x=xi(2)在二叉树的叶顶点中确定：x(xi,xi+1),最优二叉搜索树,61,在实际中，不同标识符会有不同的检索概率。,设Pi是对ai检索的概率，设qi是对满足aiXai+1,0in的标识符X检索的概率，(假定a0=-且an+1=)。,a1,Q(0),E0,P(1),a2,E1,Q(1),P(2),ai,P(i),ai+1,Ei,Q(i),P(i+1),an,P(n),En,Q(n),最优二叉搜索树,62,例标识符集1,2,3do,if,stop可能的二分检索树为,(a),(b),(c),(e),设每个内、外结点检索的概率相同：pi=qi=1/7求每棵树的平均比较次数（成本）。若P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05求每棵树的平均比较次数（成本）。,63,例：,P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05,考虑平均搜索次数，也叫做平均路长,Pa(n)=1p1+2p2+3p3+1q0+2q1+3(q2+q3)=10.5+20.1+30.05+10.05+20.1+3(0.05+0.05)=1.5,最优二叉搜索树,64,分析,对于图的内结点而言，第0层需要比较操作次数为1，第1层需要比较2次，第2层需要3次Pb(n)=1p1+2p3+3p2+1q0+3(q2+q3)=10.5+20.05+30.1+10.15+20.05+3(0.05+0.05)=1.6Pc(n)=1p2+2(p1+p3)+2(q0+q1+q2+q3)=10.1+2(0.5+0.05)+2(0.15+0.1+0.05+0.05)=1.9Pd(n)=1p3+2p1+3p2+1q3+2q0+3(q1+q2)=10.05+20.5+30.1+10.05+20.15+3(0.1+0.05)=2.15Pd(n)=1p3+2p1+3p2+1q3+2q0+3(q1+q2)=10.05+20.5+30.1+10.05+20.15+3(0.1+0.05)=2.15,最优二叉搜索树,65,找到元素x=xi的概率为bi；确定x(xi,xi+1)的概率为ai。其中约定x0=,xn+1=+,有,最优二叉搜索树,66,在一个表示S的二叉树T中，设存储元素xi的结点深度为ci；叶结点（xj，xj1）的结点深度为dj,表示在二叉搜索树T中作一次搜索所需的平均比较次数。P又称为二叉搜索树T的平均路长，在一般情况下，不同的二叉搜索树的平均路长是不同的。,最优二叉搜索树,67,3、最优二叉搜索树问题,对于有序集S及其存取概率分布（a0,b1,a1,bn,an），在所有表示有序集S的二叉搜索树中找出一棵具有最小平均路长的二叉搜索树。结点在二叉搜索树中的层次越深，需要比较的次数就越多，因此要构造一棵最小二叉树，一般尽量把搜索概率较高的结点放在较高的层次。,最优二叉搜索树问题,68,4、最优子结构性质,假设选择k为树根，则1,2,k-1和a0,a1,ak-1都将位于左子树L上，其余结点(k+1,n和ak,ak+1,an)位于右子树R上。,k,L,R,1,2,k-1a0,a1,ak-1,k+1,nak,ak+1,an,最优子结构性质,69,最优子结构性质,70,最优子结构性质,71,设COST(L)和COST(R)分别是二分检索树T的左子树和右子树的成本则检索树T的成本是：P(k)+COST(L)+COST(R)若T是最优的，则上式及COST(L)和COST(R)必定都取最小值。,最优子结构性质,72,4、最优子结构性质,二叉搜索树T的一棵含有顶点xi,xj和叶顶点(xi-1,xi),(xj,xj+1)的子树可以看作是有序集xi,xj关于全集为xi-1,xj1的一棵二叉搜索树（T自身可以看作是有序集)。根据S的存取分布概率，在子树的顶点处被搜索到的概率是,最优子结构性质,73,左子树的搜索概率,右子树的搜索概率,设Tij是有序集xi,xj关于存储概率分布为ai-1,bi,bj,aj的一棵最优二叉搜索树Pij：平均路长xm：Tij的根顶点存储的元素pl和pr:左子树Tl和右子树Tr的平均路长,74,构造最优二叉搜索树时，可以选择先构造其左右子树，使其左右子树最优，然后构造整棵树,最优子结构性质,75,5、递归计算最优值,最优二叉搜索树Tij的平均路长为pij，则所求的最优值为p1,n。由二叉树的花费公式根据最优二叉搜索树问题的最优子结构性质可建立计算pij的递归式如下,初始时,递归计算最优值,76,记wi,jpi,j为m(i,j),递归计算最优值,77,根据该公式，计算树Tij的花费只用到了Tik-1，Tk+1j,可得到具体求解过程如下：1）构造只有1个内部结点的最优二叉搜索树T11,T22,Tnn，可以求得mii同时可以用一个数组存做根结点元素为：s11=1,s22=2snn=n2)构造具有2个内部结点的最优二叉搜索树,78,例,给出标识符集1,2,3do,if,stop存取概率若P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05构造一棵最优二叉搜索树,递归计算最优值,79,P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05,T12,w12=0.9m12=0.9+m11+m32=1.65,w12=0.9m12=0.9+m10+m22=1.15,80,P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05,T12,w12=0.9m12=0.9+m11+m32=1.65,w12=0.9m12=0.9+m10+m22=1.15,T23w23=0.5,m23=0.5,m23=0.6,81,P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05,T12,w12=0.9m12=0.9+m11+m32=1.65,w12=0.9m12=0.9+m10+m22=1.15,T23w23=0.5,m23=0.5,m23=0.6,82,P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05,T12m12=1.15,T23m23=0.5,T13W13=1,m13=1.5,m13=1.9,m13=2.15,83,P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05,T12m12=1.15,T23m23=0.5,2,3,q2,q3,1,q0,q1,T13W13=1,m13=1.5,2,3,q2,q3,1,q0,q1,m13=1.9,2,3,q2,q3,1,q0,q1,m13=2.15,84,P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05,0,1,2,3,1,2,3,0,0,0,0,4,0123,1234,W(i,j),0123,1234,0,0,0,0,0.15,0.1,0.05,0.05,0.75,0.75,1,0.25,0.15,0.25,0.15,2,3,0.9,1.15,1,0.35,1,0.5,2,1.5,1,m(i,j),s(i,j),85,具体求解过程,递归出口，没有内部节点时，构造T10T21,T32，Tn+1n2)构造具有2个、3个、n个内部结点的最优二叉搜索树r（起止下标的差）0T11,T22,，Tnn，1T12,T23,，Tn-1n，2T13,T24,，Tn-2n，rT1r+1,T2r+2,，Tii+r，Tn-rnn-1T1n,86,voidOBST(inta,intb,intn,int*m,int*s,int*w),for(inti=0;i=n;i+)wi+1i=ai;mi+1i=0;/初始化，构造没有内部节点时的情况for(intr=0;rn;r+)for(inti=1;i=n-r;i+)intj=j+r;构造Tij，填写wij,mij,sij,87,构造Tij,Tij表示用第i到第j个内部节点构造的树，做根的结点可以是第i，i+1,j中任意一个。1)首选i作为根，其左子树空，右子树为结点i+1,i+2j构成即Ti+1j。mij=wij+0+mi+1jsij=i2)不选i做根，设k为其根，则k=i+1,j,左子树为结点i,i+1,k-1,右子树为k+1,k+2,jt=wij+mik-1+mk+1jif(tmij)mij=t;sij=k;3)k=k+1,跳回2,88,voidOptimalBinar