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

《《算法設(shè)計(jì)與分析》第07章v.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法設(shè)計(jì)與分析》第07章v.ppt（96頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、,算法設(shè)計(jì)與分析,DeSign and Analysis of Algorithms In C+,“十一五”國(guó)家級(jí)規(guī)劃教材,陳慧南 編著,電子工業(yè)出版社,第2部分 算法設(shè)計(jì)策略,第7章 動(dòng)態(tài)規(guī)劃法,7.1 一般方法和基本要素 7.2 每對(duì)結(jié)點(diǎn)間的最短路徑 7.3 矩陣連乘 7.4 最長(zhǎng)公共子序列 7.5 最優(yōu)二叉搜索樹 7.6 0/1背包 7.7 流水作業(yè)調(diào)度,7.1 一般方法和基本要素,7.1.3 多段圖問(wèn)題,例71 多段圖G=(V,E)是一個(gè)帶權(quán)有向圖，它具有如下特性：圖中的結(jié)點(diǎn)被劃分成k2個(gè)互不相交的子集Vi，1ik。其中V1和Vk分別只有一個(gè)結(jié)點(diǎn)，V1包含源點(diǎn)（source）s，Vk包

2、含匯點(diǎn)（sink）t。對(duì)所有邊E，多段圖要求若uVi，則vVi1，1ik，每條邊的權(quán)值為c(u,v)。從s到t的路徑長(zhǎng)度是這條路徑上邊的權(quán)值之和，多段圖問(wèn)題（multistage graph problem）是求從s到t的一條長(zhǎng)度最短的路徑。,子集Vi,多段圖問(wèn)題的特性,最優(yōu)子結(jié)構(gòu)特性 （s,v2,v3,vk-1,t) 與 (v2,v3,vk-1,t) 定義cost(i,j)， 1ik cost(k,t)=0 cost(i,j) = min c(j,p) + cost(i+1,p) 重疊子問(wèn)題特性,第i階段j狀態(tài)的最短路徑,1 k段圖的自后向前遞推求解,遞推關(guān)系式 cost(5,t)=0 co

3、st(4,8)=?，cost(4,9)，cost(4,10) cost (3,5)=?， cost(3,6)， cost(3,7),課堂練習(xí),用分治法思想求解K段圖問(wèn)題 與上述動(dòng)態(tài)規(guī)劃法進(jìn)行比較,【程序71】k段圖的（從后）向前遞推算法 template void Graph:FMultiGraph(int k,int *p) /采用程序68的鄰接表存儲(chǔ)圖G。對(duì)圖按階段順序標(biāo)號(hào) float *cost=new floatn; /各節(jié)點(diǎn)的最短路徑值 int q; int *d=new intn; /各結(jié)點(diǎn)開(kāi)始的最短路徑上的下一結(jié)點(diǎn) costn-1=0,dn-1=-1; /設(shè)置初值,for (in

4、t 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)=?,動(dòng)態(tài)規(guī)劃法的實(shí)質(zhì)也是將較大問(wèn)題分解為較小的同類子問(wèn)題，這一點(diǎn)上它與分治法和貪心法類似。但動(dòng)態(tài)規(guī)劃法有自己的特

5、點(diǎn)。分治法的子問(wèn)題相互獨(dú)立，相同的子問(wèn)題被重復(fù)計(jì)算，動(dòng)態(tài)規(guī)劃法解決這種子問(wèn)題重疊現(xiàn)象。貪心法要求針對(duì)問(wèn)題設(shè)計(jì)最優(yōu)量度標(biāo)準(zhǔn)，但這在很多情況下并不容易。動(dòng)態(tài)規(guī)劃法利用最優(yōu)子結(jié)構(gòu)，自底向上從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解，動(dòng)態(tài)規(guī)劃則可以處理不具備貪心準(zhǔn)則的問(wèn)題。,7.1.1 一般方法,最優(yōu)性原理指出，一個(gè)最優(yōu)策略具有這樣的性質(zhì)，不論過(guò)去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，其余決策對(duì)相應(yīng)的子問(wèn)題來(lái)說(shuō)，必定構(gòu)成最優(yōu)策略。這便是最優(yōu)決策序列的最優(yōu)子結(jié)構(gòu)特性。,設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，通?？梢园匆韵聨讉€(gè)步驟進(jìn)行： （1）刻畫最優(yōu)解的子結(jié)構(gòu)特性； （2）遞歸定義最優(yōu)解值； （3）以自底向上方

6、式計(jì)算最優(yōu)解值； （4）根據(jù)計(jì)算得到的信息構(gòu)造一個(gè)最優(yōu)解。 其中，第（1）至（3）步是動(dòng)態(tài)規(guī)劃算法的基本步驟。最優(yōu)解值是最優(yōu)解的目標(biāo)函數(shù)的值。,7.1.2 基本要素,一個(gè)最優(yōu)化多步?jīng)Q策問(wèn)題適合用動(dòng)態(tài)規(guī)劃法求解有兩個(gè)要素：最優(yōu)子結(jié)構(gòu)特性和重疊子問(wèn)題。,7.1.4 資源分配問(wèn)題,【例72】 將n個(gè)資源分配給r個(gè)項(xiàng)目，已知如果把j個(gè)資源分配給第i個(gè)項(xiàng)目，可以收益N(i,j)，0jn，1ir。求總收益最大的資源分配方案。 （這里假設(shè)，對(duì)同一個(gè)項(xiàng)目，獲得的資源越多，收益越多；不同的項(xiàng)目對(duì)資源的單位收益不一樣）,V(i,j)表示j個(gè)資源已經(jīng)分配給前i-1個(gè)項(xiàng)目 N(m,n)表示n個(gè)資源分配給第m個(gè)項(xiàng)目了,

7、4個(gè)資源、3個(gè)項(xiàng)目,7.1.4 資源分配問(wèn)題,向后遞推的動(dòng)態(tài)規(guī)劃算法？,7.1.5 關(guān)鍵路徑問(wèn)題（略）,工程安排 最短工期 關(guān)鍵路徑 關(guān)鍵活動(dòng) 在關(guān)鍵路徑上的活動(dòng) 注意結(jié)點(diǎn)的編號(hào),結(jié)點(diǎn)=事件（代表前一個(gè)活動(dòng)結(jié)束， 后一個(gè)活動(dòng)可開(kāi)始的狀態(tài)）,7.1.5 關(guān)鍵路徑問(wèn)題,最優(yōu)子結(jié)構(gòu)特性？ 子問(wèn)題重疊？,7.2 每對(duì)結(jié)點(diǎn)間的最短路徑,單源最短路徑問(wèn)題,單源最短路徑問(wèn)題是：給定帶權(quán)的有向圖G=(V,E)和圖中結(jié)點(diǎn)sV，求從s到其余各結(jié)點(diǎn)的最短路徑，其中，s稱為源點(diǎn)。,貪心法求解,迪杰斯特拉（Dijkstra） 算法 解視為向量（L1,L2,L3,Ln-1) ，分量Li表示s到結(jié)點(diǎn)i的最短路徑 首先求得長(zhǎng)

8、度最短的一條最短路徑，再求得長(zhǎng)度次短的一條最短路徑，依此類推，直到從源點(diǎn)到其它所有結(jié)點(diǎn)之間的最短路徑都已求得為止。 每步度量準(zhǔn)則：當(dāng)前最短路徑（增量最少的分量） 以求得最短路徑的結(jié)點(diǎn)集合記為S, 從其他結(jié)點(diǎn)找出當(dāng)前最短的,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(in

9、t* d, bool* s) /找出在下一條當(dāng)前最短路徑上的尾結(jié)點(diǎn) int i,minpos; T min; min=INFTY; minpos=-1; for (i=1;in;i+) if (dimin ,template void MGraph:Dijkstra(int s, T* ,inSs=true; ds=0; for (i=1;in-1;i+) /需要n-1步完成 k=Choose(d,inS); inSk=true; for (j=0; jn; j+) /更新各結(jié)點(diǎn)的d和path if (!inSj ,時(shí)間復(fù)雜度？,7.2.1 結(jié)點(diǎn)對(duì)間最短路徑問(wèn)題描述,設(shè)G=(V,E)是一個(gè)有n

10、個(gè)結(jié)點(diǎn)的帶權(quán)有向圖，w(i,j)是權(quán)函數(shù)， 每對(duì)結(jié)點(diǎn)間的最短路徑問(wèn)題是指求圖中任意一對(duì)結(jié)點(diǎn)i和j之間的最短路徑。,7.2.2 動(dòng)態(tài)規(guī)劃法求解,最優(yōu)子結(jié)構(gòu) 設(shè)圖G=(V,E)是帶權(quán)有向圖，(i,j)是從結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑長(zhǎng)度，k是這條路徑上的一個(gè)結(jié)點(diǎn)，(i,k) 和(k,j)分別是從i到k和從k到j(luò)的最短路徑長(zhǎng)度，則必有(i,j)= (i,k)+(k,j)。因?yàn)槿舨蝗?，則(i,j)代表的路徑就不是最短路徑。這表明每對(duì)結(jié)點(diǎn)之間的最短路徑問(wèn)題的最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性。,定義dkij=i到j(luò)的路徑上，包含的結(jié)點(diǎn)編號(hào) 不超過(guò)k是的最短路徑長(zhǎng)度,最優(yōu)解的遞推關(guān)系,重疊子問(wèn)題：為了計(jì)算dkij時(shí)，必

11、須先計(jì)算 dk1ij、dk1ik和dk1ik，dk1的元素被多個(gè)dk的元素的計(jì)算共享。,dkij指在i和j之間由編號(hào)不大于k的結(jié)點(diǎn)組成的最短路徑長(zhǎng)度。k=-1時(shí)表示不包含其他結(jié)點(diǎn),7.2.3弗洛伊德算法,弗洛伊德算法的基本思想是：令k=0,1,n-1，每次考察一個(gè)結(jié)點(diǎn)k。二維數(shù)組d用于保存各條最短路徑的長(zhǎng)度，其中，dij存放從結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑的長(zhǎng)度。在算法的第k步上應(yīng)作出決策：從i到j(luò)的最短路徑上是否包含結(jié)點(diǎn)k。,【程序72】弗洛伊德算法 template void MGraph:Floyd(T* ,for (k=0;kn;k+) 總共n步完成 for (i=0;in;i+) for

12、(j=0;jn;j+) if (dik+dkj dij ) dij=dik+dkj; pathij=pathkj; 弗洛伊德算法的時(shí)間復(fù)雜度也為O(n3),7.2.4 算法正確性,定理71 弗洛伊德算法得到的dij，0i,jn-1是從i到j(luò)的最短路徑。,結(jié)點(diǎn)對(duì)間最短路徑問(wèn)題,弗洛伊德算法 N次迪杰斯特拉算法,7.3 矩陣連乘,7.3.1 問(wèn)題描述,給定n個(gè)矩陣A0,A1,An1， 其中Ai，i=0,n-1的維數(shù)為pipi+1，并且Ai與Ai+1是可乘的?？疾爝@n個(gè)矩陣的連乘積A0A1An1，由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可有許多不同的計(jì)算次序。矩陣連乘問(wèn)題是確定計(jì)算矩陣連乘積的計(jì)算

13、次序，使得按照這一次序計(jì)算矩陣連乘積，需要的“數(shù)乘”次數(shù)最少。,(A0A1) A3)A4),(A0(A1 A3)A4),完全加括號(hào)的矩陣連乘積可遞歸地定義為： 單個(gè)矩陣是完全加括號(hào)的； 矩陣連乘積A是完全加括號(hào)的，則A可表示為兩個(gè)完全加括號(hào)的矩陣連乘積B和C的乘積并加括號(hào)，即A=(BC)。,A=(M0M1M3Mk),(Mk+1Mk+2Mn-1),A=M0M1M3M4Mn-1,B,C,例74 4個(gè)矩陣連乘積ABCD，設(shè)它們的維數(shù)分別為A:5010，B:1040, C:4030, D:305。,7.3.2 動(dòng)態(tài)規(guī)劃法求解,最優(yōu)子結(jié)構(gòu) 矩陣連乘AiAi+1Aj簡(jiǎn)記為Ai:j，ij。于是矩陣連乘A0A

14、1An-1可記作A0:n-1。將這一計(jì)算次序在矩陣Ak和Ak+1，0kn-1之間斷開(kāi)，則其相應(yīng)的完全加括號(hào)形式為（A0A1Ak）（Ak+1Ak+2An1）?？上确謩e計(jì)算A0:k和Ak+1:n-1，然后將兩個(gè)連乘積再相乘得到A0:n-1。,矩陣連乘A0:n-1的最優(yōu)計(jì)算次序的計(jì)算量等于A0:k和Ak+1:n-1兩者的最優(yōu)計(jì)算次序的計(jì)算量之和，再加上A0:k和Ak+1:n-1相乘的計(jì)算量。如果兩個(gè)矩陣子序列的計(jì)算次序不是最優(yōu)的，則原矩陣的計(jì)算次序也不可能是最優(yōu)的。這就是說(shuō)，矩陣連乘問(wèn)題的最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性。,最優(yōu)解的遞推關(guān)系 先定義一個(gè)二維數(shù)組m，用來(lái)保存矩陣連乘時(shí)所需的最少計(jì)算量。,注意：

15、N個(gè)矩陣的維數(shù)依序放在一維數(shù)組p中， 其中Ai的維數(shù)記為PiPi+1,求解過(guò)程,為避免重復(fù)計(jì)算，自底向上求解 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(); / 基于動(dòng)態(tài)規(guī)劃法 int LookupChain(); /基于備忘錄的分治法 void Traceback(); /輸出最優(yōu)解 ,private: void Traceback(int i,int j); int Loo

16、kupChain(int i, int j); int *p,*m,*s, n; ;,int MatrixChain:MChain() /求A0:n-1的最優(yōu)解值 for (int i=0;in;i+) mii=0; /主對(duì)角線,for (int r=2; r=n;r+) /和主對(duì)角線平行的其他次對(duì)角線 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; retu

17、rn m0n-1; ,void MatrixChain:Traceback(int i,int j) if(i=j) coutAi;return; if (isij) cout(; /ai,ai+1,ak加括號(hào) Traceback(i,sij); if (isij) cout); if(sij+1j) cout(; /ak+1,ak+2,aj加括號(hào) Traceback(sij+1,j); if(sij+1j) cout); void MatrixChain:Traceback() cout(; Traceback(0,n-1); cout); coutendl; ,例75 6個(gè)矩陣連乘積A0A

18、1A2A3A4A5，設(shè)它們的維數(shù)分別為A:3035，B:3515 C:155 D:510，E:1020，F(xiàn):2025。,7.3.4 備忘錄方法,矩陣連乘的備忘錄方法 備忘錄方法為每個(gè)已經(jīng)計(jì)算的子問(wèn)題建立備忘錄，即保存子問(wèn)題的計(jì)算結(jié)果以備需要時(shí)引用，從而避免了相同子問(wèn)題的重復(fù)求解。,【程序74】矩陣連乘的備忘錄方法 int MatrixChain:LookupChain(int i, int j) if (mij0) return mij; /子問(wèn)題已解。 if(i=j) return 0; int u=LookupChain(i+1,j)+pi*pi+1*pj+1; sij=i; for (i

19、nt k=i+1;kj; k+) int t=LookupChain(i,k)+LookupChain(k+1,j) +pi*pk+1*pj+1; if (tu) u=t; sij=k; mij=u; return u; ,int MatrixChain:LookupChain() return LookupChain(0,n-1); ,7.5 最優(yōu)二叉搜索樹,7.5.1 問(wèn)題描述,設(shè)有元素集合 a1,a2,an，其中，a1a2an，p(i) 是在集合中成功查找ai 的概率，1i n，q(i)是待查元素x值滿足 aixai+1的概率,0i n（假定a0= , an+1=+）。 最優(yōu)二叉搜索樹問(wèn)

20、題是指設(shè)法構(gòu)造一棵具有最小平均搜索時(shí)間的二叉搜索樹。,二叉搜索樹的代價(jià),二叉搜索樹平均搜索時(shí)間 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動(dòng)態(tài)規(guī)劃法求解,設(shè) c(0,n) 是由元素值集合a1,an所構(gòu)造的最優(yōu)二叉搜索樹的代價(jià)，則,一般地，c(i,j) ,ij 是元素值集合ai+1,aj所構(gòu)造的最優(yōu)二叉搜索樹的代價(jià)，設(shè)r(i,j)=k為該樹的根，要求結(jié)點(diǎn)k滿足,例77 設(shè)n4且（a1,a2,a3,a4）=(Mon,Thu,Tue,We

21、d)。又設(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之間使代價(jià)最小的根 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,i

22、nt n) /初始化，主對(duì)角線，次主對(duì)角線 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 問(wèn)題描述,問(wèn)題 已知一個(gè)

23、載重為M的背包和n件物品，物品編號(hào)從0到n-1。第i件物品的重量為 wi，如果將第i種物品裝入背包將獲益pi，這里，wi0，pi0，0in。所謂0/1背包問(wèn)題是指在物品不能分割，只能整件裝入背包或不裝入的情況下，求一種最佳裝載方案使得總收益最大。,7.6.2 動(dòng)態(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背包子問(wèn)題的最優(yōu)解：背包載重Mw0 x0，共有n-1件物品，第i件物品的重量為 wi，效益pi，wi0，pi0，1in。,例78 設(shè)有0/1背包問(wèn)題n=3，

24、（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)的全部階躍點(diǎn)的集合，Sj=(Xi,Pi)| 函數(shù)曲線f(j,X)的全部階躍點(diǎn)，-1jn-1，其中S-1=(0,0)。用S1j表示函數(shù)曲線f(j-1,X-wj)+pj的全部階躍點(diǎn)的集合，S1j=(Xj,Pj)| 函數(shù)曲線f(j-1,X-wj)+pj的全部階躍點(diǎn)，0jn-1。,計(jì)算所有Sj和S1j的步驟如下： S-1=(0,0)，函數(shù)f(-1,X)只有一個(gè)階躍點(diǎn)； S1j=(X,P)|(X-wj,P-pj)Sj1，也就是說(shuō)，由集合Sj-1中的

25、每個(gè)階躍點(diǎn)（X,P），得到集合S1j中的一個(gè)階躍點(diǎn)（X+wj,P+pj）； Sj是合并集合Sj-1S1j，舍棄其中被支配的階躍點(diǎn)和所有XM的階躍點(diǎn)得到。,對(duì)于例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)=

26、Sn2中最后一個(gè)階躍點(diǎn); (X2,P2)=(X+wn1,P+pn1)，其中(X,P)是Sn-1 中 使得 X+wn1M的最大的階躍點(diǎn); PmaxP1,P2; If (P2P1) xn1=1; else xn1=0; 回溯確定xn2,xn-3,x0; ,7.6.5 性能分析,在最壞情況下，算法的空間復(fù)雜度是O(2n)。 在最壞情況下，算法的時(shí)間復(fù)雜度是O(2n)。,7.7 流水作業(yè)調(diào)度,7.7.1 問(wèn)題描述,假定處理一個(gè)作業(yè)需要執(zhí)行若干項(xiàng)不同類型的任務(wù)，每一類任務(wù)只能在某一臺(tái)設(shè)備上執(zhí)行。設(shè)一條流水線上有n個(gè)作業(yè)J=J0,J1,Jn1和m臺(tái)設(shè)備P=P1,P2,Pm。每個(gè)作業(yè)需依次執(zhí)行m個(gè)任務(wù)，其中

27、第j個(gè)任務(wù)只能在第j臺(tái)設(shè)備上執(zhí)行，1jm。設(shè)第i個(gè)作業(yè)的第j項(xiàng)任務(wù)Tji所需時(shí)間為tji，1jm，0in。如何將這nm個(gè)任務(wù)分配給這m臺(tái)設(shè)備，使得這n個(gè)作業(yè)都能順利完成。這就是流水線作業(yè)調(diào)度(flow shop schedule)問(wèn)題。,例710 設(shè)有三臺(tái)設(shè)備兩個(gè)作業(yè)，每個(gè)作業(yè)包含三項(xiàng)任務(wù)。完成這些任務(wù)的時(shí)間由矩陣M給定。,作業(yè)i的完成時(shí)間fi(S)是指在調(diào)度方案S下，該作業(yè)的所有任務(wù)都已完成的時(shí)間。 完成時(shí)間F(S)是所有作業(yè)都完成的時(shí)間。 平均流動(dòng)時(shí)間(mean flow time)MFT(S)定義為：,一組給定的作業(yè)的最優(yōu)完成時(shí)間是F(S)的最小值。 OFT表示指非搶先調(diào)度最優(yōu)完成時(shí)間

28、POFT表示搶先調(diào)度最優(yōu)完成時(shí)間。 OMFT表示非搶先調(diào)度最優(yōu)平均完成時(shí)間， POMFT表示搶先調(diào)度最優(yōu)平均完成時(shí)間。 本節(jié)只討論當(dāng)m=2時(shí)獲得OFT的調(diào)度方案的算法，這就是雙機(jī)流水作業(yè)調(diào)度問(wèn)題。,雙機(jī)流水作業(yè)調(diào)度描述為：設(shè)有n個(gè)作業(yè)的集合0，1，n-1，每個(gè)作業(yè)都有兩項(xiàng)任務(wù)要求在2臺(tái)設(shè)備P1和P2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序總是先在P1上加工，然后在P2上加工。P1和P2加工作業(yè)i所需的時(shí)間分別為a i和bi。流水作業(yè)調(diào)度問(wèn)題要求確定這n個(gè)作業(yè)的最優(yōu)加工順序，使得從第一個(gè)作業(yè)在設(shè)備P1上開(kāi)始加工，到最后一個(gè)作業(yè)在設(shè)備P2上加工完成所需的時(shí)間最少。即求使F(S)有最小值的調(diào)度方案

29、S。,7.7.2 動(dòng)態(tài)規(guī)劃法求解,重要結(jié)論（可證明）：在兩臺(tái)設(shè)備的情況下，存在一個(gè)最優(yōu)非搶先調(diào)度方案，使得在P1和P2上的作業(yè)完全以相同次序處理（若m2則不然）。,定理73 流水作業(yè)調(diào)度問(wèn)題具有最優(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. 對(duì)任意的集合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)度方案中，只要有

30、作業(yè)i先于j處理，必然有： minbi, aj = min bj,ai 即滿足Johnson不等式,最優(yōu)調(diào)度求解方案,可以設(shè)計(jì)下列作業(yè)排列方法。這樣做能得到最優(yōu)調(diào)度方案 (1)如果mina0,a1,an1, b0,b1,bn1是ai，則ai應(yīng)是最優(yōu)排列的第一個(gè)作業(yè)； (2)如果mina0, a1, , an-1, b0, b1, bn1是bj，則bj應(yīng)是最優(yōu)排列的最后一個(gè)作業(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)是最

31、優(yōu)作業(yè)排列。 先將任務(wù)按處理時(shí)間的非減次序排列成： （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，0in分別為作業(yè)i在兩臺(tái)設(shè)備上的處理時(shí)間。建立由三元組（作業(yè)號(hào),處理時(shí)間,設(shè)備號(hào)）組成的三元組表d

32、。 對(duì)三元組表按處理時(shí)間排序，得到排序后的三元組表d。 對(duì)三元組表的每一項(xiàng)di，0in，從左和右兩端生成最優(yōu)作業(yè)排列cj, 0jn，cj是作業(yè)號(hào)。如果di的設(shè)備號(hào)為1，則按從左向右順序?qū)⒆鳂I(yè)i置于c的左端第一個(gè)空位，否則按從右向左的順序置于c的右端第一個(gè)空位。,【程序712】Johnson算法 /三元組結(jié)構(gòu) 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; fo

33、r(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); /n個(gè)元素排序，O(nlogn) int left=0, right=n-1; /指示左右兩端首個(gè)空位 for (i=0;in;i+) if(di.ab=0) cleft+=di.jobNo; else cright-=di.jobNo; ,Johnson算法的時(shí)間取決于對(duì)作業(yè)集合的排序，因此，在最壞情況下算法的時(shí)間復(fù)雜度為O(nlogn)，所需的空間復(fù)雜度為O(n)。,（a0,a1,a2,a3）=(3,4,8,10) （b0,b1,b2,b3）=(6,2,9,15)。,動(dòng)態(tài)規(guī)劃法 小結(jié),求最優(yōu)化問(wèn)題 最優(yōu)子結(jié)構(gòu)原理 遞推關(guān)系 分析子問(wèn)題的重疊性 自底向上計(jì)算（最優(yōu)解值） 構(gòu)造最優(yōu)解 與分治法、貪心法比較 備忘錄方法,