算法设计与分析05动态规划课件.ppt

1、nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=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)n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)Those who cannot remember the past are doomed to repeat it.George Santay

2、ana,The life of Reason,Book I:Introduction and Reason in Common Sense(1905)12345678910111297324327111181456356425V1V2V3V4V55段图段图即，是v2 v3,.,vk-1t构成从v2至t的最短路径11,1,111111rrOPTjjpj就一个特定的r1,j1而言s0r1,1r1,2.r1,p1sn1,j11,11,21p1kkjkjkpkjrrOPTkkk,1就一个特定的就一个特定的rk,jk而言而言s0 s1 s2.sk-1rk,1rk,2.rk,pksnk,jkk,1k,2k

3、pk),1(),(min),(),(1liCOSTljcjiCOSTEljvliEtj,l1l2.lpi+1tjViVi+112345678910111297324227111181456356425V1V2V3V4V55段图段图)(en),(),1(min),(),(1jlcliCOSTjiBCOSTEjlvliEj ,112345678910111297324227111181456356425V1V2V3V4V55段图段图),(max0prNjnp指向汇点的边指向汇点的边注，并不是分给注，并不是分给的资源越多，得的资源越多，得到的净利就越大到的净利就越大jikknjia1max,0max

4、201341142kka1jikkjjikkaaannkkninnikknijikkasasnjnniaC121222211maxmax12,21,.int MaxSubSum(int a,int left,int right)int MaxSubSum(int a,int left,int right)int sum=0;int sum=0;if(left=right)sum=aleft0?aleft:0;if(left=right)sum=aleft0?aleft:0;elseint center=(left+right)/2;elseint center=(left+right)/2;i

5、nt leftsum=MaxSubSum(a,left,center);int leftsum=MaxSubSum(a,left,center);int rightsum=MaxSubSum(a,center+1,right);int rightsum=MaxSubSum(a,center+1,right);int s1=0;lefts=0;int s1=0;lefts=0;for(int i=center;i=left;i-)for(int i=center;i=left;i-)lefts+=ai;lefts+=ai;if(leftss1)s1=lefts;if(leftss1)s1=lef

6、ts;int s2=0;rights=0;int s2=0;rights=0;for(int i=center+1;i=right;i+)for(int i=center+1;is2)s2=rights;if(rightss2)s2=rights;sum=s1+s2;sum=s1+s2;if(sumleftsum)sum=leftsum;if(sumleftsum)sum=leftsum;if(sumsightsum)sum=rightsum;if(sumsightsum)sum=rightsum;return sum;return sum;nnOnTcnnOnTcnOnTlog221复杂性分

7、析：jnjjikkjinjjkknjijikkjijbaanjab111111maxmaxmaxmax1max为，则所求的最大子段和，若记E(G),ji(i,j)(i,k)(k,j)(k,k)ik且且kj,则有则有Ak(i,j)minAk-1(i,j),Ak(i,k)+Ak-1(k,j)在第在第i-1到第到第i次的迭代次的迭代过程中，过程中，A的第的第k行、行、第第k列元素不变列元素不变ki且且jk,则有则有Ak(i,j)minAk-1(i,j),Ak-1(i,k)+Ak(k,j)(k,k)(k,j)(i,k)(i,j)(k,j)(k,k)(i,j)(i,k)ki且且kj,则有则有Ak(i,j

8、)minAk-1(i,j),Ak(i,k)+Ak(k,j)642 113v1v2v3)(3n 2/31/42111111nnnnnCnCnPnknPkPnnPnnk，其中，jipppjkmkimjijimjkijki1,1,min0,22nnnclass MatrixChainpublic:MatrixChain(int mSize,int*q);int MChain();int LookupChain();void Traceback();private:void Traceback(int i,int j);int LookupChain(int i,int j);int*p,*m,*s,

9、n;int MatrixChain:MChain()/求求A0:n-1的最优解值的最优解值 for(int i=0;in;i+)mii=0;for(int r=2;r=n;r+)for(int i=0;i=n-r;i+)int j=i+r-1;mij=mi+1j+pi*pi+1*pj+1;sij=i;for(int k=i+1;kj;k+)int t=mik +mk+1j+pi*pk+1*pj+1;if(tmij)mij=t;sij=k;return m0n-1;void MatrixChain:Traceback(int i,int j)if(i=j)coutAi;return;if(isi

10、j)cout(;Traceback(i,sij);if(isij)cout);if(sij+1j)cout(;Traceback(sij+1,j);if(sij+1j)cout);void MatrixChain:Traceback()cout(;Traceback(0,n-1);cout);coutendl;113752010350437555427125205351000262554 3213000201535250005322min52541531521pppmmpppmmpppmmmjijiyxjijicjicyxjijicjijic;0,1,1max;0,1 110,00 对于一个给

11、定的对于一个给定的标识符标识符集合，可能有集合，可能有若干棵若干棵不同的二不同的二分检索树分检索树:不同形态的二分检索树对标识符的不同形态的二分检索树对标识符的检索性能检索性能是是不同不同的。的。ifforwhilerepeatloopifforrepeatloopwhile1223412233Avg=(1+2+2+3+4)/5=2.4Avg=(1+2+2+3+3)/5=2.2nii1)(Pnii0)(Q1Q(i)P(i)ni0ni1 不成功检索：不成功检索：不成功检索的每一种情况定义了一个不成功检索的每一种情况定义了一个等价类等价类，共有，共有n+1个个 这样的等价类这样的等价类Ei(0in

12、)。其中，。其中，E0=X|Xa0 Ei=X|aiXai+1(1in)En=X|Xan 若若Ei处于第处于第l级，则算法需作级，则算法需作l-1次迭代次迭代即元素的比较运即元素的比较运算在算在Ei的的上一级上一级就结束了。则，第就结束了。则，第l级上的外部结点级上的外部结点Ei在平均在平均成本中的成本中的成本分担额成本分担额为：为：Q(i)*(level(Ei)-1)则预期成本公式表示如下：则预期成本公式表示如下：)1)(*Q(i)(*P(i)ni0ni1iiElevelalevelstopdoifdoifstopstopifdoifdostopdostopif(a)(b)(c)(d)(e)i

13、fdostopdostopif(b)(c)ak由由ak1,ak+2,an及及Ek,Ek+1,En构构成的二分检索树成的二分检索树由由a1,a2,ak-1及及E0,E1,Ek-1构成构成的二分检索树的二分检索树kiikiiEleveliQaleveliPLCOST01)1(*)()(*)()(nikinikiEleveliQaleveliPRCOST)1(*)()(*)()(左子树的预期成本右子树的预期成本jilPlQiQjiW1)()()(),(左子树“成本差额”右子树“成本差额”),()1,0()(),()1,0(min),0(1nkWkWkPnkCkCnCnk),()1,()(),()1,

14、(min),(jkWkiWkPjkCkiCjiCjki),(),()1,(minjiWjkCkiCjkiW(0,n)仅有一个内结点jiifdoreadwhile)()(312nmnmnmjiiixp1jiwpxXxwiiijiii1,0,0,101或尽管X0,但还不足以装下w1i:fi-1(x-wi)+pii=0:函数不存在函数不存在1 2 3 4 5 6 7012i1:f0(x-w1)+p1x1 2 3 4 5 6 7012i2:f1(x-w2)+p23x1 2 3 4 5 6 7012f1(x)x1 2 3 4 5 6 7012f0(x)=0 x1 2 3 4 5 6 70123xf2(x

15、)12345670678x1234589i3:f2(x-w3)+p312345670678x1234589f3(x)10注：注：fi-1(X-wi)+pi曲线的构造：将曲线的构造：将fi-1(X)的曲线在的曲线在X轴上右移轴上右移wi个单位，然后个单位，然后上移上移pi个单位而得到；个单位而得到；fi(X)曲线的构造：由曲线的构造：由fi-1(X)和和fi-1(X-wi)+pi的曲线按的曲线按X相同时相同时f取大值取大值的的规则归并而成规则归并而成fi是关于是关于X的阶跃函数的阶跃函数),(|),(11iiiiSwWpPWPSiS1iS1iS111S21S31SiS1iS1iS1iS1iS1i

16、S1iS1iS1iS1iS1iS1此时W(next-1)ww这些序偶的W(k)wwiS1i1S122|1010nniiniiSi1Si1S|)S(|1-i)2(|101nniiSijjpP0|ijjipS0|1|,|min1|0MwSijji至少有一个（0,0）),|,2(min1nMpnniinnjijp11S21S31S41S51S)0,max,(min),(),(min)0,(1iiiSiiiniatbiSTatSTbiNTaNT,max0,max,0,maxmax0,0,maxmaxiijiijijijijijijijijjiijijabaataabbbaatabbbaatabbaat

17、bbt,maxjjjiijijjiabaataabbt,max,max,max,max,max,max,max,maxjjjiiijijjjiiijiijjijijiijjiabaatabaatabaaabaaabaaabaaabab,min,min)()()()(ijjiabab 设设ai和和bi，0 in分别为作业分别为作业i在两台设备上在两台设备上的处理时间。建立由三元组（作业号的处理时间。建立由三元组（作业号,处理时间处理时间,设备号）组成的三元组表设备号）组成的三元组表d。对三元组表按处理时间排序，得到排序后的三元对三元组表按处理时间排序，得到排序后的三元组表组表d。对三元组表的每一

18、项对三元组表的每一项di，0 in，从左和右两，从左和右两端生成最优作业排列端生成最优作业排列cj,0 jn，cj是作业号。是作业号。如果如果di的设备号为的设备号为1，则将作业，则将作业i置于置于c的左端末的左端末尾，否则置于尾，否则置于c的右端末尾。的右端末尾。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)。