《《算法設(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)二叉搜索樹(shù) 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)

2、（source）s，Vk包含匯點(diǎn)（sink）t。對(duì)所有邊E，多段圖要求若uVi，則vVi1，1i

3、圖的自后向前遞推求解,遞推關(guān)系式 cost(5,t)=0 cost(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)始的最短路徑上

4、的下一結(jié)點(diǎn) 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段圖的自前向后遞推求解

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

6、優(yōu)策略。這便是最優(yōu)決策序列的最優(yōu)子結(jié)構(gòu)特性。,,,,設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，通?？梢园匆韵聨讉€(gè)步驟進(jìn)行： （1）刻畫(huà)最優(yōu)解的子結(jié)構(gòu)特性； （2）遞歸定義最優(yōu)解值； （3）以自底向上方式計(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。求總收益最大的資源分配方

7、案。 （這里假設(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)目了,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)的有向圖

8、G=(V,E)和圖中結(jié)點(diǎn)sV，求從s到其余各結(jié)點(diǎn)的最短路徑，其中，s稱(chēng)為源點(diǎn)。,,,,貪心法求解,迪杰斯特拉（Dijkstra） 算法 解視為向量（L1,L2,L3,,Ln-1) ，分量Li表示s到結(jié)點(diǎn)i的最短路徑 首先求得長(zhǎng)度最短的一條最短路徑，再求得長(zhǎng)度次短的一條最短路徑，依此類(lèi)推，直到從源點(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 mS

9、ize); void Dijkstra(int s,T* ,,,,private: int Choose(int* d, bool* s); T**a; //鄰接矩陣 int n; ;,,template int MGraph::Choose(int* d, bool* s) //找出在下一條當(dāng)前最短路徑上的尾結(jié)點(diǎn) int i,minpos; T min; min=INFTY; minpos=-1; for (i=1;i

10、t s, T* ,,,,,,inSs=true; ds=0; for (i=1;i

11、,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í)，必須先計(jì)算 dk1ij、dk1ik和dk1ik，dk1的元素被多個(gè)dk的元素的計(jì)算共享。,dkij指在

12、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;k

13、 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ì)

14、算次序，使得按照這一次序計(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，i

15、j。于是矩陣連乘A0A1An-1可記作A0:n-1。將這一計(jì)算次序在矩陣Ak和Ak+1，0k

16、存矩陣連乘時(shí)所需的最少計(jì)算量。,注意：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)解

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

18、 sij=i; for (int k=i+1;k

19、cout<<(; //ak+1,ak+2,,aj加括號(hào) Traceback(sij+1,j); if(sij+1

20、子問(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 (int k=i+1;k

21、k; mij=u; return u; ,,int MatrixChain::LookupChain() return LookupChain(0,n-1); ,,7.5 最優(yōu)二叉搜索樹(shù),,,,,7.5.1 問(wèn)題描述,設(shè)有元素集合 a1,a2,,an，其中，a1

22、,,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)二叉搜索樹(shù)的代價(jià)，則,,一般地，c(i,j) ,ij 是元素值集合ai+1,,aj所構(gòu)造的最優(yōu)二叉搜索樹(shù)的代價(jià)，設(shè)r(i,j)=k為該樹(shù)的根，要求結(jié)點(diǎn)k滿足,,,例77 設(shè)n4且（a1,a2,a3,a4）=(Mon,Thu,Tue,Wed)。又設(shè)p(1:4)=(3,3,1,1)和q(0:4)(2

23、,3,1,1,1)。這里p和q都已乘了16。,,,,,,,,,,7.5.3 最優(yōu)二叉搜索樹(shù)算法,【程序77】構(gòu)造最優(yōu)二叉搜索樹(shù) 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)

24、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

25、 = k; ,,算法復(fù)雜度,,7.6 0/1背包,,,,,7.6.1 問(wèn)題描述,問(wèn)題 已知一個(gè)載重為M的背包和n件物品，物品編號(hào)從0到n-1。第i件物品的重量為 wi，如果將第i種物品裝入背包將獲益pi，這里，wi0，pi0，0i

26、1件物品，第i件物品的重量為 wi，效益pi，wi0，pi0，1i

27、1=(0,0)，函數(shù)f(-1,X)只有一個(gè)階躍點(diǎn)； S1j=(X,P)|(X-wj,P-pj)Sj1，也就是說(shuō)，由集合Sj-1中的每個(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背

28、包算法的粗略描述 void DKP(float *p,float *w,int n, float M, float ,,(X1,P1)=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.

29、1 問(wèn)題描述,,,,假定處理一個(gè)作業(yè)需要執(zhí)行若干項(xiàng)不同類(lèi)型的任務(wù)，每一類(lèi)任務(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ù)，其中第j個(gè)任務(wù)只能在第j臺(tái)設(shè)備上執(zhí)行，1jm。設(shè)第i個(gè)作業(yè)的第j項(xiàng)任務(wù)Tji所需時(shí)間為tji，1jm，0i

30、的所有任務(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í)間 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上加工，然后在

31、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)度方案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

32、. 對(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，則稱(chēng)作業(yè)i和j滿足Johnson不等式。 最優(yōu)調(diào)度方案中，只要有作業(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

33、是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))是最優(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，再考察

34、b2和a3，令(2)=3。 所以最優(yōu)解為：((0),(1),(2),(3)) （0,2,3,1）。,,7.7.3 Johnson算法,Johnson算法具體描述如下： 設(shè)ai和bi，0i

35、構(gòu) struct Triplet int operator <(Triplet b)const return t

36、logn) int left=0, right=n-1; //指示左右兩端首個(gè)空位 for (i=0;i