《算法設(shè)計與分析》第07章v.ppt

,算法設(shè)計與分析,DeSign and Analysis of Algorithms In C+,“十一五”國家級規(guī)劃教材,陳慧南 編著,電子工業(yè)出版社,第2部分 算法設(shè)計策略,第7章 動態(tài)規(guī)劃法,7.1 一般方法和基本要素 7.2 每對結(jié)點間的最短路徑 7.3 矩陣連乘 7.4 最長公共子序列 7.5 最優(yōu)二叉搜索樹 7.6 0/1背包 7.7 流水作業(yè)調(diào)度,7.1 一般方法和基本要素,7.1.3 多段圖問題,例71 多段圖G=(V,E)是一個帶權(quán)有向圖，它具有如下特性：圖中的結(jié)點被劃分成k2個互不相交的子集Vi，1ik。其中V1和Vk分別只有一個結(jié)點，V1包含源點（source）s，Vk包含匯點（sink）t。對所有邊E，多段圖要求若uVi，則vVi1，1i<k，每條邊的權(quán)值為c(u,v)。從s到t的路徑長度是這條路徑上邊的權(quán)值之和，多段圖問題（multistage graph problem）是求從s到t的一條長度最短的路徑。,子集Vi,多段圖問題的特性,最優(yōu)子結(jié)構(gòu)特性 （s,v2,v3,vk-1,t) 與 (v2,v3,vk-1,t) 定義cost(i,j)， 1i<k cost(k,t)=0 cost(i,j) = min c(j,p) + cost(i+1,p) 重疊子問題特性,第i階段j狀態(tài)的最短路徑,1 k段圖的自后向前遞推求解,遞推關(guān)系式 cost(5,t)=0 cost(4,8)=?，cost(4,9)，cost(4,10) cost (3,5)=?， cost(3,6)， cost(3,7),課堂練習,用分治法思想求解K段圖問題 與上述動態(tài)規(guī)劃法進行比較,【程序71】k段圖的（從后）向前遞推算法 template void Graph:FMultiGraph(int k,int *p) /采用程序68的鄰接表存儲圖G。對圖按階段順序標號 float *cost=new floatn; /各節(jié)點的最短路徑值 int q; int *d=new intn; /各結(jié)點開始的最短路徑上的下一結(jié)點 costn-1=0,dn-1=-1; /設(shè)置初值,for (int j=n-2;j=0;j-) float min=INFTY; for (ENode *r=aj;r;r=r-nextArc) int v=r-adjVex; if (r-w+costvw+costv; q=v; costj=min;dj=q; p0=0; pk-1=n-1; /p記錄最短路徑 for(j=1;j<=k-2;j+) pj=dpj-1; delete cost; delete d; ,2 k段圖的自前向后遞推求解,遞推關(guān)系式 cost(1,s)=0 cost(i,j)=?,動態(tài)規(guī)劃法的實質(zhì)也是將較大問題分解為較小的同類子問題，這一點上它與分治法和貪心法類似。但動態(tài)規(guī)劃法有自己的特點。分治法的子問題相互獨立，相同的子問題被重復(fù)計算，動態(tài)規(guī)劃法解決這種子問題重疊現(xiàn)象。貪心法要求針對問題設(shè)計最優(yōu)量度標準，但這在很多情況下并不容易。動態(tài)規(guī)劃法利用最優(yōu)子結(jié)構(gòu)，自底向上從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解，動態(tài)規(guī)劃則可以處理不具備貪心準則的問題。,7.1.1 一般方法,最優(yōu)性原理指出，一個最優(yōu)策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，其余決策對相應(yīng)的子問題來說，必定構(gòu)成最優(yōu)策略。這便是最優(yōu)決策序列的最優(yōu)子結(jié)構(gòu)特性。,設(shè)計一個動態(tài)規(guī)劃算法，通常可以按以下幾個步驟進行： （1）刻畫最優(yōu)解的子結(jié)構(gòu)特性； （2）遞歸定義最優(yōu)解值； （3）以自底向上方式計算最優(yōu)解值； （4）根據(jù)計算得到的信息構(gòu)造一個最優(yōu)解。 其中，第（1）至（3）步是動態(tài)規(guī)劃算法的基本步驟。最優(yōu)解值是最優(yōu)解的目標函數(shù)的值。,7.1.2 基本要素,一個最優(yōu)化多步?jīng)Q策問題適合用動態(tài)規(guī)劃法求解有兩個要素：最優(yōu)子結(jié)構(gòu)特性和重疊子問題。,7.1.4 資源分配問題,【例72】 將n個資源分配給r個項目，已知如果把j個資源分配給第i個項目，可以收益N(i,j)，0jn，1ir。求總收益最大的資源分配方案。 （這里假設(shè)，對同一個項目，獲得的資源越多，收益越多；不同的項目對資源的單位收益不一樣）,V(i,j)表示j個資源已經(jīng)分配給前i-1個項目 N(m,n)表示n個資源分配給第m個項目了,4個資源、3個項目,7.1.4 資源分配問題,向后遞推的動態(tài)規(guī)劃算法？,7.1.5 關(guān)鍵路徑問題（略）,工程安排 最短工期 關(guān)鍵路徑 關(guān)鍵活動 在關(guān)鍵路徑上的活動 注意結(jié)點的編號,結(jié)點=事件（代表前一個活動結(jié)束， 后一個活動可開始的狀態(tài)）,7.1.5 關(guān)鍵路徑問題,最優(yōu)子結(jié)構(gòu)特性？ 子問題重疊？,7.2 每對結(jié)點間的最短路徑,單源最短路徑問題,單源最短路徑問題是：給定帶權(quán)的有向圖G=(V,E)和圖中結(jié)點sV，求從s到其余各結(jié)點的最短路徑，其中，s稱為源點。,貪心法求解,迪杰斯特拉（Dijkstra） 算法 解視為向量（L1,L2,L3,Ln-1) ，分量Li表示s到結(jié)點i的最短路徑 首先求得長度最短的一條最短路徑，再求得長度次短的一條最短路徑，依此類推，直到從源點到其它所有結(jié)點之間的最短路徑都已求得為止。 每步度量準則：當前最短路徑（增量最少的分量） 以求得最短路徑的結(jié)點集合記為S, 從其他結(jié)點找出當前最短的,6.6.3 迪杰斯特拉算法,【程序610】迪杰斯特拉算法 template class MGraph public: MGraph(int mSize); void Dijkstra(int s,T* ,private: int Choose(int* d, bool* s); T*a; /鄰接矩陣 int n; ;,template int MGraph:Choose(int* d, bool* s) /找出在下一條當前最短路徑上的尾結(jié)點 int i,minpos; T min; min=INFTY; minpos=-1; for (i=1;i<n;i+) if (di<min ,template void MGraph:Dijkstra(int s, T* ,inSs=true; ds=0; for (i=1;i<n-1;i+) /需要n-1步完成 k=Choose(d,inS); inSk=true; for (j=0; j<n; j+) /更新各結(jié)點的d和path if (!inSj ,時間復(fù)雜度？,7.2.1 結(jié)點對間最短路徑問題描述,設(shè)G=(V,E)是一個有n個結(jié)點的帶權(quán)有向圖，w(i,j)是權(quán)函數(shù)， 每對結(jié)點間的最短路徑問題是指求圖中任意一對結(jié)點i和j之間的最短路徑。,7.2.2 動態(tài)規(guī)劃法求解,最優(yōu)子結(jié)構(gòu) 設(shè)圖G=(V,E)是帶權(quán)有向圖，(i,j)是從結(jié)點i到結(jié)點j的最短路徑長度，k是這條路徑上的一個結(jié)點，(i,k) 和(k,j)分別是從i到k和從k到j(luò)的最短路徑長度，則必有(i,j)= (i,k)+(k,j)。因為若不然，則(i,j)代表的路徑就不是最短路徑。這表明每對結(jié)點之間的最短路徑問題的最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性。,定義dkij=i到j(luò)的路徑上，包含的結(jié)點編號 不超過k是的最短路徑長度,最優(yōu)解的遞推關(guān)系,重疊子問題：為了計算dkij時，必須先計算 dk1ij、dk1ik和dk1ik，dk1的元素被多個dk的元素的計算共享。,dkij指在i和j之間由編號不大于k的結(jié)點組成的最短路徑長度。k=-1時表示不包含其他結(jié)點,7.2.3弗洛伊德算法,弗洛伊德算法的基本思想是：令k=0,1,n-1，每次考察一個結(jié)點k。二維數(shù)組d用于保存各條最短路徑的長度，其中，dij存放從結(jié)點i到結(jié)點j的最短路徑的長度。在算法的第k步上應(yīng)作出決策：從i到j(luò)的最短路徑上是否包含結(jié)點k。,【程序72】弗洛伊德算法 template void MGraph:Floyd(T* ,for (k=0;k<n;k+) 總共n步完成 for (i=0;i<n;i+) for (j=0;j<n;j+) if (dik+dkj < dij ) dij=dik+dkj; pathij=pathkj; 弗洛伊德算法的時間復(fù)雜度也為O(n3),7.2.4 算法正確性,定理71 弗洛伊德算法得到的dij，0i,jn-1是從i到j(luò)的最短路徑。,結(jié)點對間最短路徑問題,弗洛伊德算法 N次迪杰斯特拉算法,7.3 矩陣連乘,7.3.1 問題描述,給定n個矩陣A0,A1,An1， 其中Ai，i=0,n-1的維數(shù)為pipi+1，并且Ai與Ai+1是可乘的?？疾爝@n個矩陣的連乘積A0A1An1，由于矩陣乘法滿足結(jié)合律，所以計算矩陣的連乘可有許多不同的計算次序。矩陣連乘問題是確定計算矩陣連乘積的計算次序，使得按照這一次序計算矩陣連乘積，需要的“數(shù)乘”次數(shù)最少。,(A0A1) A3)A4),(A0(A1 A3)A4),完全加括號的矩陣連乘積可遞歸地定義為： 單個矩陣是完全加括號的； 矩陣連乘積A是完全加括號的，則A可表示為兩個完全加括號的矩陣連乘積B和C的乘積并加括號，即A=(BC)。,A=(M0M1M3Mk),(Mk+1Mk+2Mn-1),A=M0M1M3M4Mn-1,B,C,例74 4個矩陣連乘積ABCD，設(shè)它們的維數(shù)分別為A:5010，B:1040, C:4030, D:305。,7.3.2 動態(tài)規(guī)劃法求解,最優(yōu)子結(jié)構(gòu) 矩陣連乘AiAi+1Aj簡記為Ai:j，ij。于是矩陣連乘A0A1An-1可記作A0:n-1。將這一計算次序在矩陣Ak和Ak+1，0k<n-1之間斷開，則其相應(yīng)的完全加括號形式為（A0A1Ak）（Ak+1Ak+2An1）?？上确謩e計算A0:k和Ak+1:n-1，然后將兩個連乘積再相乘得到A0:n-1。,矩陣連乘A0:n-1的最優(yōu)計算次序的計算量等于A0:k和Ak+1:n-1兩者的最優(yōu)計算次序的計算量之和，再加上A0:k和Ak+1:n-1相乘的計算量。如果兩個矩陣子序列的計算次序不是最優(yōu)的，則原矩陣的計算次序也不可能是最優(yōu)的。這就是說，矩陣連乘問題的最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性。,最優(yōu)解的遞推關(guān)系 先定義一個二維數(shù)組m，用來保存矩陣連乘時所需的最少計算量。,注意：N個矩陣的維數(shù)依序放在一維數(shù)組p中， 其中Ai的維數(shù)記為PiPi+1,求解過程,為避免重復(fù)計算，自底向上求解 mij mik, k=i,i+1,j-1 mk+1j, k=i+1,j-1,7.3.3矩陣連乘算法,【程序73】矩陣連乘算法 class MatrixChain public: MatrixChain(int mSize,int *p); int MChain(); / 基于動態(tài)規(guī)劃法 int LookupChain(); /基于備忘錄的分治法 void Traceback(); /輸出最優(yōu)解 ,private: void Traceback(int i,int j); int LookupChain(int i, int j); int *p,*m,*s, n; ;,int MatrixChain:MChain() /求A0:n-1的最優(yōu)解值 for (int i=0;i<n;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;k<j;k+) int t=mik +mk+1j+pi*pk+1*pj+1; if (t<mij) mij=t;sij=k; return m0n-1; ,void MatrixChain:Traceback(int i,int j) if(i=j) cout<<A<<i;return; if (i<sij) cout<<(; /ai,ai+1,ak加括號 Traceback(i,sij); if (i<sij) cout<<); if(sij+1<j) cout<<(; /ak+1,ak+2,aj加括號 Traceback(sij+1,j); if(sij+1<j) cout<<); void MatrixChain:Traceback() cout<<(; Traceback(0,n-1); cout<<); cout<<endl; ,例75 6個矩陣連乘積A0A1A2A3A4A5，設(shè)它們的維數(shù)分別為A:3035，B:3515 C:155 D:510，E:1020，F(xiàn):2025。,7.3.4 備忘錄方法,矩陣連乘的備忘錄方法 備忘錄方法為每個已經(jīng)計算的子問題建立備忘錄，即保存子問題的計算結(jié)果以備需要時引用，從而避免了相同子問題的重復(fù)求解。,【程序74】矩陣連乘的備忘錄方法 int MatrixChain:LookupChain(int i, int j) if (mij0) return mij; /子問題已解。 if(i=j) return 0; int u=LookupChain(i+1,j)+pi*pi+1*pj+1; sij=i; for (int k=i+1;k<j; k+) int t=LookupChain(i,k)+LookupChain(k+1,j) +pi*pk+1*pj+1; if (t<u) u=t; sij=k; mij=u; return u; ,int MatrixChain:LookupChain() return LookupChain(0,n-1); ,7.5 最優(yōu)二叉搜索樹,7.5.1 問題描述,設(shè)有元素集合 a1,a2,an，其中，a1<a2<<an，p(i) 是在集合中成功查找ai 的概率，1i n，q(i)是待查元素x值滿足 ai<x<ai+1的概率,0i n（假定a0= , an+1=+）。 最優(yōu)二叉搜索樹問題是指設(shè)法構(gòu)造一棵具有最小平均搜索時間的二叉搜索樹。,二叉搜索樹的代價,二叉搜索樹平均搜索時間 a1,an, E0,En cost(T)=,遞推關(guān)系,cost(T)= cost(L)+cost(R)+p1+pn +q0+q1+qn,L,R,T,=cost(L)+cost(R)+w(0,n),7.5.2動態(tài)規(guī)劃法求解,設(shè) c(0,n) 是由元素值集合a1,an所構(gòu)造的最優(yōu)二叉搜索樹的代價，則,一般地，c(i,j) ,ij 是元素值集合ai+1,aj所構(gòu)造的最優(yōu)二叉搜索樹的代價，設(shè)r(i,j)=k為該樹的根，要求結(jié)點k滿足,例77 設(shè)n4且（a1,a2,a3,a4）=(Mon,Thu,Tue,Wed)。又設(shè)p(1:4)=(3,3,1,1)和q(0:4)(2,3,1,1,1)。這里p和q都已乘了16。,7.5.3 最優(yōu)二叉搜索樹算法,【程序77】構(gòu)造最優(yōu)二叉搜索樹 int Find(int i, int j, int *r, float*c) /找出I,j之間使代價最小的根 float min=INFTY; int k; for (int m=i+1;m<=j;m+) if (cim-1+cmj)<min) min=cim-1+cmj;k=m; return k; ,void CreateOBST(float* p, float* q, float *c, int *r, float*w,int n) /初始化，主對角線，次主對角線 for (int i=0;i<=n-1;i+) wii=qi;cii=0.0;rii=0; wii+1=qi+qi+1+pi+1; cii+1=qi+qi+1+pi+1; rii+1=i+1; wnn=qn;cnn=0.0;rnn=0;,for (int m=2;m<=n;m+) for (i=0;i<=n-m;i+) int j=i+m; wij=wij-1+pj+qj; int k = Find(i,j,r,c); cij = wij + cik-1 + ckj; rij = k; ,算法復(fù)雜度,7.6 0/1背包,7.6.1 問題描述,問題 已知一個載重為M的背包和n件物品，物品編號從0到n-1。第i件物品的重量為 wi，如果將第i種物品裝入背包將獲益pi，這里，wi0，pi0，0i<n。所謂0/1背包問題是指在物品不能分割，只能整件裝入背包或不裝入的情況下，求一種最佳裝載方案使得總收益最大。,7.6.2 動態(tài)規(guī)劃法求解,最優(yōu)子結(jié)構(gòu) 0/1背包的最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性。設(shè) (x0, x1, , xn1)，xi0,1是0/1背包的最優(yōu)解，那么，(x1 ,x2, , xn1) 必然是0/1背包子問題的最優(yōu)解：背包載重Mw0 x0，共有n-1件物品，第i件物品的重量為 wi，效益pi，wi0，pi0，1i<n。,例78 設(shè)有0/1背包問題n=3，（w0,w1,w2）=（2,3,4），（p0,p1,p2）=（1,2,4）和M=6。,遞歸式,7.6.3 0/1背包算法框架,現(xiàn)用Sj表示函數(shù)曲線f(j,X)的全部階躍點的集合，Sj=(Xi,Pi)| 函數(shù)曲線f(j,X)的全部階躍點，-1jn-1，其中S-1=(0,0)。用S1j表示函數(shù)曲線f(j-1,X-wj)+pj的全部階躍點的集合，S1j=(Xj,Pj)| 函數(shù)曲線f(j-1,X-wj)+pj的全部階躍點，0j<n-1。,計算所有Sj和S1j的步驟如下： S-1=(0,0)，函數(shù)f(-1,X)只有一個階躍點； S1j=(X,P)|(X-wj,P-pj)Sj1，也就是說，由集合Sj-1中的每個階躍點（X,P），得到集合S1j中的一個階躍點（X+wj,P+pj）； Sj是合并集合Sj-1S1j，舍棄其中被支配的階躍點和所有XM的階躍點得到。,對于例78有 S1=(0,0)，S10=(2,1) S0=(0,0),(2,1)，S11=(3,2),(5,3) S1=(0,0),(2,1),(3,2),(5,3)， S12=(4,4),(6,5)，(7,6),(9,7) S2=(0,0),(2,1),(3,2),(4,4),(6,5),【程序79】0/1背包算法的粗略描述 void DKP(float *p,float *w,int n, float M, float ,(X1,P1)=Sn2中最后一個階躍點; (X2,P2)=(X+wn1,P+pn1)，其中(X,P)是Sn-1 中 使得 X+wn1M的最大的階躍點; PmaxP1,P2; If (P2P1) xn1=1; else xn1=0; 回溯確定xn2,xn-3,x0; ,7.6.5 性能分析,在最壞情況下，算法的空間復(fù)雜度是O(2n)。 在最壞情況下，算法的時間復(fù)雜度是O(2n)。,7.7 流水作業(yè)調(diào)度,7.7.1 問題描述,假定處理一個作業(yè)需要執(zhí)行若干項不同類型的任務(wù)，每一類任務(wù)只能在某一臺設(shè)備上執(zhí)行。設(shè)一條流水線上有n個作業(yè)J=J0,J1,Jn1和m臺設(shè)備P=P1,P2,Pm。每個作業(yè)需依次執(zhí)行m個任務(wù)，其中第j個任務(wù)只能在第j臺設(shè)備上執(zhí)行，1jm。設(shè)第i個作業(yè)的第j項任務(wù)Tji所需時間為tji，1jm，0i<n。如何將這nm個任務(wù)分配給這m臺設(shè)備，使得這n個作業(yè)都能順利完成。這就是流水線作業(yè)調(diào)度(flow shop schedule)問題。,例710 設(shè)有三臺設(shè)備兩個作業(yè)，每個作業(yè)包含三項任務(wù)。完成這些任務(wù)的時間由矩陣M給定。,作業(yè)i的完成時間fi(S)是指在調(diào)度方案S下，該作業(yè)的所有任務(wù)都已完成的時間。 完成時間F(S)是所有作業(yè)都完成的時間。 平均流動時間(mean flow time)MFT(S)定義為：,一組給定的作業(yè)的最優(yōu)完成時間是F(S)的最小值。 OFT表示指非搶先調(diào)度最優(yōu)完成時間 POFT表示搶先調(diào)度最優(yōu)完成時間。 OMFT表示非搶先調(diào)度最優(yōu)平均完成時間， POMFT表示搶先調(diào)度最優(yōu)平均完成時間。 本節(jié)只討論當m=2時獲得OFT的調(diào)度方案的算法，這就是雙機流水作業(yè)調(diào)度問題。,雙機流水作業(yè)調(diào)度描述為：設(shè)有n個作業(yè)的集合0，1，n-1，每個作業(yè)都有兩項任務(wù)要求在2臺設(shè)備P1和P2組成的流水線上完成加工。每個作業(yè)加工的順序總是先在P1上加工，然后在P2上加工。P1和P2加工作業(yè)i所需的時間分別為a i和bi。流水作業(yè)調(diào)度問題要求確定這n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在設(shè)備P1上開始加工，到最后一個作業(yè)在設(shè)備P2上加工完成所需的時間最少。即求使F(S)有最小值的調(diào)度方案S。,7.7.2 動態(tài)規(guī)劃法求解,重要結(jié)論（可證明）：在兩臺設(shè)備的情況下，存在一個最優(yōu)非搶先調(diào)度方案，使得在P1和P2上的作業(yè)完全以相同次序處理（若m2則不然）。,定理73 流水作業(yè)調(diào)度問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。 =(0),(1),(k-1) g (S, t) 遞推關(guān)系： g(N,0)=minai+g(N-i,bi; N=0,1,N-1, i屬于N. 對任意的集合S和I (i屬于S）： g(S,t)=ai+g(S-i,t), t=bi+maxt-ai,0,如果在調(diào)度方案的作業(yè)排列中，作業(yè)i和j滿足minbi,ajminbj,ai，則稱作業(yè)i和j滿足Johnson不等式。 最優(yōu)調(diào)度方案中，只要有作業(yè)i先于j處理，必然有： minbi, aj = min bj,ai 即滿足Johnson不等式,最優(yōu)調(diào)度求解方案,可以設(shè)計下列作業(yè)排列方法。這樣做能得到最優(yōu)調(diào)度方案 (1)如果mina0,a1,an1, b0,b1,bn1是ai，則ai應(yīng)是最優(yōu)排列的第一個作業(yè)； (2)如果mina0, a1, , an-1, b0, b1, bn1是bj，則bj應(yīng)是最優(yōu)排列的最后一個作業(yè)； (3) 繼續(xù)（1）和（2）的做法，直到完成所有作業(yè)的排列。,例711設(shè)n4，（a0,a1,a2,a3）=(3,4,8,10) （b0,b1,b2,b3）=(6,2,9,15)。 設(shè) =(0),(1),(2),(3)是最優(yōu)作業(yè)排列。 先將任務(wù)按處理時間的非減次序排列成： （b1,a0,a1,b0,a2,b2,a3,b3）=(2,3,4,6,8,9,10,15) 先選 b1，將其加在最優(yōu)作業(yè)排列的最后，故(3)=1 再選a0，應(yīng)加在最優(yōu)作業(yè)排列的最前面，故 (0)=0 考察a1和b0，因作業(yè)1和0已調(diào)度， 接著考察a2，應(yīng)有(1)=2，再考察b2和a3，令(2)=3。 所以最優(yōu)解為：(0),(1),(2),(3) （0,2,3,1）。,7.7.3 Johnson算法,Johnson算法具體描述如下： 設(shè)ai和bi，0i<n分別為作業(yè)i在兩臺設(shè)備上的處理時間。建立由三元組（作業(yè)號,處理時間,設(shè)備號）組成的三元組表d。 對三元組表按處理時間排序，得到排序后的三元組表d。 對三元組表的每一項di，0i<n，從左和右兩端生成最優(yōu)作業(yè)排列cj, 0j<n，cj是作業(yè)號。如果di的設(shè)備號為1，則按從左向右順序?qū)⒆鳂I(yè)i置于c的左端第一個空位，否則按從右向左的順序置于c的右端第一個空位。,【程序712】Johnson算法 /三元組結(jié)構(gòu) struct Triplet int operator <(Triplet b)const return t<b.t; int jobNo, t, ab; ;,void FlowShop(int n, int *a,int *b,int *c) Triplet dmSize=0,0,0; for(int i=0;i<n;i+) if(ai<bi) di.jobNo=i; di.ab=0; di.t=ai; else di.jobNo=i; di.ab=1; di.t=bi; Sort(d,n); /n個元素排序，O(nlogn) int left=0, right=n-1; /指示左右兩端首個空位 for (i=0;i<n;i+) if(di.ab=0) cleft+=di.jobNo; else cright-=di.jobNo; ,Johnson算法的時間取決于對作業(yè)集合的排序，因此，在最壞情況下算法的時間復(fù)雜度為O(nlogn)，所需的空間復(fù)雜度為O(n)。,（a0,a1,a2,a3）=(3,4,8,10) （b0,b1,b2,b3）=(6,2,9,15)。,動態(tài)規(guī)劃法 小結(jié),求最優(yōu)化問題 最優(yōu)子結(jié)構(gòu)原理 遞推關(guān)系 分析子問題的重疊性 自底向上計算（最優(yōu)解值） 構(gòu)造最優(yōu)解 與分治法、貪心法比較 備忘錄方法,