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

1、南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,算法設(shè)計(jì)與分析,DeSign and Analysis of Algorithms In C++,,,“十一五”國(guó)家級(jí)規(guī)劃教材,陳慧南 編著,電子工業(yè)出版社,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,第2部分 算法設(shè)計(jì)策略,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,第7章 動(dòng)態(tài)規(guī)劃法,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,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)度,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.1 一般方法和基本要素,

2、,,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,動(dòng)態(tài)規(guī)劃法的實(shí)質(zhì)也是將較大問(wèn)題分解為較小的同類子問(wèn)題，這一點(diǎn)上它與分治法和貪心法類似。但動(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)題。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.1.1 一般方法,最優(yōu)性原理指出，一個(gè)最優(yōu)策略具有這樣的性質(zhì)，不論過(guò)去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，其余決策必定構(gòu)成最

3、優(yōu)策略。這便是最優(yōu)決策序列的最優(yōu)子結(jié)構(gòu)特性。,,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，通?？梢园匆韵聨讉€(gè)步驟進(jìn)行： （1）刻畫最優(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ù)的值。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.1.2 基本要素,一個(gè)最優(yōu)化多步?jīng)Q策問(wèn)題適合用動(dòng)態(tài)規(guī)劃法求解有兩個(gè)要素：最優(yōu)子結(jié)構(gòu)特性和重疊子問(wèn)題。,,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.1.3 多段圖問(wèn)題,例71 多段圖G=(V,E

4、)是一個(gè)帶權(quán)有向圖，它具有如下特性：圖中的結(jié)點(diǎn)被劃分成k2個(gè)互不相交的子集Vi，1ik。其中V1和Vk分別只有一個(gè)結(jié)點(diǎn)，V1包含源點(diǎn)（source）s，Vk包含匯點(diǎn)（sink）t。對(duì)所有邊E，多段圖要求若uVi，則vVi1，1i

5、,int *p) //采用程序68的鄰接表存儲(chǔ)圖G。 float *cost=new floatn; int q,*d=new intn; costn-1=0,dn-1=-1;,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,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; for(j=1

6、;j<=k-2;j++) pj=dpj-1; delete cost;delete d; ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.1.4 資源分配問(wèn)題,【例72】 將n個(gè)資源分配給r個(gè)項(xiàng)目，已知如果把j個(gè)資源分配給第i個(gè)項(xiàng)目，可以收益N(i,j)，0jn，1ir。求總收益最大的資源分配方案。,,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.2 每對(duì)結(jié)點(diǎn)間的最短路徑,,,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.2.1 問(wèn)題描述,設(shè)G=(V,E)是一個(gè)有n個(gè)結(jié)點(diǎn)的帶權(quán)有向圖，w(i,j)是權(quán)函數(shù)， 每對(duì)結(jié)點(diǎn)間的最短路徑問(wèn)題是指求圖

7、中任意一對(duì)結(jié)點(diǎn)i和j之間的最短路徑。,,,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,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)槿舨蝗唬瑒t(i,j)代表的路徑就不是最短路徑。這表明每對(duì)結(jié)點(diǎn)之間的最短路徑問(wèn)題的最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性。,,,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,最優(yōu)解的遞推關(guān)系,,,重疊子問(wèn)題：為了計(jì)算dkij時(shí)，必須先計(jì)算 dk1ij、dk1ik和dk1ik，dk1

8、的元素被多個(gè)dk的元素的計(jì)算共享。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,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。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,【程序72】弗洛伊德算法 template void MGraph::Floyd(T** ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,for (k=0;k

9、0;j

10、乘的?？疾爝@n個(gè)矩陣的連乘積A0A1An1，由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可有許多不同的計(jì)算次序。矩陣連乘問(wèn)題是確定計(jì)算矩陣連乘積的計(jì)算次序，使得按照這一次序計(jì)算矩陣連乘積，需要的“數(shù)乘”次數(shù)最少。,,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,完全加括號(hào)的矩陣連乘積可遞歸地定義為： 單個(gè)矩陣是完全加括號(hào)的； 矩陣連乘積A是完全加括號(hào)的，則A可表示為兩個(gè)完全加括號(hào)的矩陣連乘積B和C的乘積并加括號(hào)，即A=(BC)。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,例74 4個(gè)矩陣連乘積ABCD，設(shè)它們的維數(shù)分別為A:5010，B:1040, C:4030, D:305。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院

11、 2008年3月,7.3.2 動(dòng)態(tài)規(guī)劃法求解,最優(yōu)子結(jié)構(gòu) 矩陣連乘AiAi+1Aj簡(jiǎn)記為Ai:j，ij。于是矩陣連乘A0A1An-1可記作A0:n-1。將這一計(jì)算次序在矩陣Ak和Ak+1，0k

12、則原矩陣的計(jì)算次序也不可能是最優(yōu)的。這就是說(shuō)，矩陣連乘問(wèn)題的最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,,最優(yōu)解的遞推關(guān)系 先定義一個(gè)二維數(shù)組m，用來(lái)保存矩陣連乘時(shí)所需的最少計(jì)算量。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.3.3矩陣連乘算法,【程序73】矩陣連乘算法 class MatrixChain public: MatrixChain(int mSize,int *q); int MChain(); int LookupChain(); void Traceback(); ,,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 200

13、8年3月,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

14、 for (int k=i+1;k

15、(; Traceback(sij+1,j);if(sij+1

16、要時(shí)引用，從而避免了相同子問(wèn)題的重復(fù)求解。,,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,,【程序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

17、if (t

18、n+1=+）。 最優(yōu)二叉搜索樹(shù)問(wèn)題是指設(shè)法構(gòu)造一棵具有最小平均搜索時(shí)間的二叉搜索樹(shù)。,,,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.5.2動(dòng)態(tài)規(guī)劃法求解,,,,設(shè) c(0,n) 是由元素值集合a1,,an所構(gòu)造的最優(yōu)二叉搜索樹(shù)的代價(jià)，則,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,一般地，c(i,j) ,ij 是元素值集合ai+1,,aj所構(gòu)造的最優(yōu)二叉搜索樹(shù)的代價(jià)，設(shè)r(i,j)=k為該樹(shù)的根，要求結(jié)點(diǎn)k滿足,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,例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

19、,1,1)。這里p和q都已乘了16。,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.5.3 最優(yōu)二叉搜索樹(shù)算法,【程序77】構(gòu)造最優(yōu)二叉搜索樹(shù) int Find(int i,int j,int **r,float**c) float min=INFTY; int k; for (int m=i+1;m<=j;m++) if ((cim-1+cmj)

20、 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;,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,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 = Fi

21、nd(i,j,r,c); cij = wij + cik-1 + ckj; rij = k; ,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.6 0/1背包,,,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.6.1 問(wèn)題描述,問(wèn)題 已知一個(gè)載重為M的背包和n件物品，物品編號(hào)從0到n-1。第i件物品的重量為 wi，如果將第i種物品裝入背包將獲益pi，這里，wi0，pi0，0i

22、的最優(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，1i

23、現(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)，0j

24、并集合Sj-1S1j，舍棄其中被支配的階躍點(diǎn)和所有XM的階躍點(diǎn)得到。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,對(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),南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,【程序79】0/1背包算法的粗略描述 void DKP(float *p,float *w,int n, float M, float

25、,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,(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; ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.6.5 性能分析,,,,,在最壞情況下，算法的空間復(fù)雜度是O(2n)。 在最壞情況下，算法的時(shí)間復(fù)雜度是O(2n)。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.7 流水作業(yè)調(diào)度,,,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年

26、3月,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ù)，其中第j個(gè)任務(wù)只能在第j臺(tái)設(shè)備上執(zhí)行，1jm。設(shè)第i個(gè)作業(yè)的第j項(xiàng)任務(wù)Tji所需時(shí)間為tji，1jm，0i

27、京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,作業(yè)i的完成時(shí)間fi(S)是指在調(diào)度方案S下，該作業(yè)的所有任務(wù)都已完成的時(shí)間。 完成時(shí)間F(S)是所有作業(yè)都完成的時(shí)間。 平均流動(dòng)時(shí)間(mean flow time)MFT(S)定義為：,,,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,一組給定的作業(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)題。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,雙機(jī)流

28、水作業(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)度方案S。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,7.7.2 動(dòng)態(tài)規(guī)劃法求解,在兩臺(tái)設(shè)備的情況下，存在一個(gè)最優(yōu)非搶先調(diào)度方案，使得在P1和P2上的作業(yè)完全以相同次序處理（若m2則不然）。,,,,南京郵電大學(xué)

29、計(jì)算機(jī)學(xué)院 2008年3月,定理73 流水作業(yè)調(diào)度問(wèn)題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,如果在調(diào)度方案的作業(yè)排列中，作業(yè)i和j滿足minbi,ajminbj,ai，則稱作業(yè)i和j滿足Johnson不等式。 可以設(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è)的排列。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月,例71

30、1設(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，再考察b2和a3，令(2)=3。 所以最優(yōu)解為：((0),(1),(2),(3)) （0,2,3,1）。,南京郵電大學(xué)

31、計(jì)算機(jī)學(xué)院 2008年3月,7.7.3 Johnson算法,Johnson算法具體描述如下： 設(shè)ai和bi，0i

32、b)const return t