計算機(jī)算法的動態(tài)規(guī)劃課件

1、12 學(xué)習(xí)要點學(xué)習(xí)要點:理解動態(tài)規(guī)劃算法的概念。掌握動態(tài)規(guī)劃算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）重疊子問題性質(zhì)掌握設(shè)計動態(tài)規(guī)劃算法的步驟。(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。(3)以自底向上的方式計算出最優(yōu)值。(4)根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。第三章.動態(tài)規(guī)劃(Dynamic Programming)適用問題: 具備最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性子問題重疊性的最優(yōu)化問題.將問題的求解過程化為多步選擇或決策的結(jié)果將問題的求解過程化為多步選擇或決策的結(jié)果, ,在每一步?jīng)Q策上在每一步?jīng)Q策上, ,列出各種可能的選擇列出各種可能的選擇( (各子問題的

2、可行解各子問題的可行解),),舍去那些肯定不能成為舍去那些肯定不能成為最優(yōu)解的局部解最優(yōu)解的局部解. .最后一步得到的解必是最優(yōu)解最后一步得到的解必是最優(yōu)解. .問題的整體的最優(yōu)解中包問題的整體的最優(yōu)解中包含著它的子問題的最優(yōu)解含著它的子問題的最優(yōu)解3.1 基本思想用以求解最優(yōu)化問題算法設(shè)計與分析算法設(shè)計與分析 動態(tài)規(guī)劃動態(tài)規(guī)劃與貪心算法比較與貪心算法比較:都是將問題的求解過程化為多步?jīng)Q策.區(qū)別是:貪心法每采用一次貪心策略便做出唯一決策,求解過程只產(chǎn)生一個決策序列;求解過程為自頂向下,不一定得到最優(yōu)解.動態(tài)規(guī)劃的求解過程產(chǎn)生多個決策序列, 下一步的選擇總是依賴上一步的結(jié)果.求解過程多為自底向上

3、.總能得到最優(yōu)解.第第i+1i+1步問題的求解中包含第步問題的求解中包含第i i步步子問題的最優(yōu)解子問題的最優(yōu)解, ,形成遞歸求解形成遞歸求解. .串形與樹形優(yōu)化系列算法設(shè)計與分析算法設(shè)計與分析 動態(tài)規(guī)劃動態(tài)規(guī)劃1).分析最優(yōu)解的結(jié)構(gòu).2).給出計算局部最優(yōu)解值的遞歸關(guān)系.3).自底向上計算局部最優(yōu)解的值.4).根據(jù)最優(yōu)解的值構(gòu)造最優(yōu)解.常見應(yīng)用:0-1背包問題,圖像壓縮,最短路徑,矩陣連乘,作業(yè)調(diào)度等等.算法的步驟算法的步驟注意0-1背包問題不能用貪心算法求解.優(yōu)化子問題優(yōu)化子問題最終不取作用最終不取作用的優(yōu)化子問題的優(yōu)化子問題貪心算法貪心算法動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法5n動態(tài)規(guī)劃算法與分治法

4、類似，其基本思想也是將待求解問題分解成若干個子問題nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=6n但是經(jīng)分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時，有些子問題被重復(fù)計算了許多次。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)7n如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計算，從而得到多項式時間算法。n=n/2T(n

5、/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)8（1）單個矩陣是完全加括號的；（2）矩陣連乘積 是完全加括號的，則 可 表示為2個完全加括號的矩陣連乘積 和 的乘積并加括號，即 AABC)(BCADCBA , , ,1050A4010B3040C530D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB16000, 10500, 36000, 87500, 34500u完全加括號的矩陣連乘積可遞歸地定義為：u設(shè)有四個矩陣 ，它們的維數(shù)分別是：u總共有五中完全加括號的方式9給定n

6、個矩陣A1,A2,An，其中Ai與Ai+1是可乘的，i=1，2，n-1。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。u窮舉法窮舉法：列舉出所有可能的計算次序，并計算出每一種計算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計算次序。 算法復(fù)雜度分析：算法復(fù)雜度分析：對于n個矩陣的連乘積，設(shè)其不同的計算次序為P(n)。由于每種加括號方式都可以分解為兩個子矩陣的加括號問題：(A1.Ak)(Ak+1An)可以得到關(guān)于P(n)的遞推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnk10u窮舉法窮舉法u動態(tài)規(guī)劃動態(tài)規(guī)劃將矩陣連乘積 簡記

7、為Ai:j ，這里ij jiiAAA.1考察計算Ai:j的最優(yōu)計算次序。設(shè)這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，ikj，則其相應(yīng)完全加括號方式為).)(.(211jkkkiiAAAAAA計算量：Ai:k的計算量加上Ak+1:j的計算量，再加上Ai:k和Ak+1:j相乘的計算量11n特征：計算Ai:j的最優(yōu)次序所包含的計算矩陣子鏈 Ai:k和Ak+1:j的次序也是最優(yōu)的。n矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法求解的顯著特征。12n設(shè)計算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mi,j

8、，則原問題的最優(yōu)值為m1,n n當(dāng)i=j時，Ai:j=Ai，因此，mi,i=0，i=1,2,nn當(dāng)ij時，n可以遞歸地定義mi,j為：jkipppjkmkimjim1, 1,這里 的維數(shù)為 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只有 種可能kij 13n對于1ijn不同的有序?qū)?i,j)對應(yīng)于不同的子問題。因此，不同子問題的個數(shù)最多只有n由此可見，在遞歸計算時，許多子問題被重復(fù)計算多次許多子問題被重復(fù)計算多次。這也是該問題可用動態(tài)規(guī)劃算法求解的又一顯著特征。n用動態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計算。在計算過程中，保存已解決

9、的子問題答案。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而避免大量的重復(fù)計算，最終得到多項式時間的算法)(22nnnvoid MatrixChain(int p, int n, int * m, int * s) for (int i= 1; i = n; i +) mii =0; for (int r= 2; r = n; r+) /r/r子鏈長度子鏈長度 for (int i= 1; i= n-r+l; i+) /i/i子鏈開始位置子鏈開始位置 int j= i+r-1; /j/j子鏈結(jié)束位置子鏈結(jié)束位置 mij = mi+1j + pi-1 * pi* pj; /初始化初始化

10、 sij = i; /初始化初始化 for(int k = i+1; k j;k+) /循環(huán)搜索循環(huán)搜索 int t = mik + mk+1j + pi- 1 * pk * pj; if ( t 動態(tài)規(guī)劃動態(tài)規(guī)劃 矩陣乘法鏈矩陣乘法鏈矩陣乘法鏈動態(tài)規(guī)劃算法算法設(shè)計與分析算法設(shè)計與分析 動態(tài)規(guī)劃動態(tài)規(guī)劃 矩陣乘法鏈矩陣乘法鏈s25=316矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)

11、致矛盾。 利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提。同一個問題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問題的維度低）17遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)子問題的重疊性質(zhì)。動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。 通常不同的子問題個數(shù)隨問題的大小呈多項式增長。因此用動態(tài)規(guī)劃算法只需要多項式時間，從而獲得較高的解題效

12、率。 18備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復(fù)求解。int LookupChain(int i，int j) if (mij 0) return mij; if (i = j) return 0; int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk

13、*pj; if (t u) u = t; sij = k; mij = u; return u;19若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存在一個嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。給定2個序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列公共子序列。給定2個序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。 20設(shè)序列X=x1,x2,xm和Y=

14、y1,y2,yn的最長公共子序列為Z=z1,z2,zk ，則(1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長公共子序列。(2)若xmyn且zkxm，則Z是xm-1和Y的最長公共子序列。(3)若xmyn且zkyn，則Z是X和yn-1的最長公共子序列。由此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)最優(yōu)子結(jié)構(gòu)性質(zhì)構(gòu)性質(zhì)。 21由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用cij記錄序列和的最長公共子序列的長度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當(dāng)i=0或j=0時，空序

15、列是Xi和Yj的最長公共子序列。故此時Cij=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 11022由于在所考慮的子問題空間中，總共有(mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。 void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1

16、; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 構(gòu)造最長公共子序列構(gòu)造最長公共子序列void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b);23在算法lcsLength和lcs中，可進(jìn)一步將數(shù)組b省去。事實上，數(shù)組元素cij的值僅由ci-1j-1，

17、ci-1j和cij-1這3個數(shù)組元素的值所確定。對于給定的數(shù)組元素cij，可以不借助于數(shù)組b而僅借助于c本身在時間內(nèi)確定cij的值是由ci-1j-1，ci-1j和cij-1中哪一個值所確定的。如果只需要計算最長公共子序列的長度，則算法的空間需求可大大減少。事實上，在計算cij時，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計算出最長公共子序列的長度。進(jìn)一步的分析還可將空間需求減至O(min(m,n)。24用多邊形頂點的逆時針序列表示凸多邊形，即P=v0,v1,vn-1表示具有n條邊的凸多邊形。若vi與vj是多邊形上不相鄰的2個頂點，則線段vivj稱為多邊形的一條弦。弦將多邊形

18、分割成2個多邊形vi,vi+1,vj和vj,vj+1,vi。多邊形的三角剖分多邊形的三角剖分是將多邊形分割成互不相交的三角形的弦的集合T。給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權(quán)之和為最小。 25一個表達(dá)式的完全加括號方式相應(yīng)于一棵完全二叉樹，稱為表達(dá)式的語法樹。例如，完全加括號的矩陣連乘積(A1(A2A3)(A4(A5A6)所相應(yīng)的語法樹如圖 (a)所示。凸多邊形v0,v1,vn-1的三角剖分也可以用語法樹表示。例如，圖 (b)中凸多邊形的三角剖分可用圖 (a)所示的語法樹表示。 矩陣連乘積中的每個矩陣A

19、i對應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，ij，對應(yīng)于矩陣連乘積Ai+1:j。26凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子結(jié)構(gòu)性質(zhì)。事實上，若凸(n+1)邊形P=v0,v1,vn的最優(yōu)三角剖分T包含三角形v0vkvn，1kn-1，則T的權(quán)為3個部分權(quán)的和：三角形v0vkvn的權(quán)，子多邊形v0,v1,vk和vk,vk+1,vn的權(quán)之和?？梢詳嘌?，由T所確定的這2個子多邊形的三角剖分也是最優(yōu)的。因為若有v0,v1,vk或vk,vk+1,vn的更小權(quán)的三角剖分將導(dǎo)致T不是最優(yōu)三角剖分的矛盾。 27定義tij，1i 動態(tài)規(guī)劃動態(tài)規(guī)劃問題陳述:數(shù)字化圖像是nn的像素陣列. 假

20、定每個像素有一個0255的灰度值, 因此存儲一個像素至多需8位. 為了減少存儲空間, 采用變長模式, 即不同像素用不同位數(shù)來存儲, 步驟如下. 1) 圖像線性化:將n n維圖像轉(zhuǎn)換為1 n2向量 p1,p2,.pn23.7 圖像壓縮 2) 分段: 將像素分成連續(xù)的m段s1,s2,.sm,使每段中的像素存儲位數(shù) 相同. 每個段是相鄰像素的集合且每段最多含256個像素, 若相同 位數(shù)的像素超過 256個的話, 則用兩個以上段表示。3) 創(chuàng)建三個表 l: li存放第i段長度, 表中各項均為8位長 B: bi存放第i段中像素的存儲位數(shù),表中各項均為3位長. P: p1,.p n2以變長格式存儲的像素的

21、二進(jìn)制串。 設(shè)產(chǎn)生了m個段,則存儲第i段像素所需要的空間為:li*bi+11 總存儲空間為 11m+ li*bi ； 問題要求找到一個最優(yōu)分段。使存儲空間最少小灰度象素用短位數(shù)記錄小灰度象素用短位數(shù)記錄算法設(shè)計與分析算法設(shè)計與分析 動態(tài)規(guī)劃動態(tài)規(guī)劃libili+1bi+18位3位bi+1位li+1個單元431101010101010100011172110 010 010 100 011 011 011 011例例 題題算法設(shè)計與分析算法設(shè)計與分析 動態(tài)規(guī)劃動態(tài)規(guī)劃分段: 10, 9, 12, 40, 50, 35, 15, 12, 8, 10, 9, 15, 11, 130, 160, 24

22、0 L=2，2， 6，2；B=3，5，3，7；/為了用3位能存8,少算一個.計算時加1 P包含16個灰度值，其中頭三個各用4位存儲，接下來三個各用6位再接下來的七個各用4位，最后三個各用8位存儲。 1010 1001 1100 111000 110010 100011 .三個表需要存儲空間分別為: L:32位 B:12位 P:82位 例: 考察44圖像灰 度 值 10 9 12 40 50 35 15 12 8 10 9 15 11 130 160 240像素位數(shù) 4 4 4 6 6 6 4 4 4 4 4 4 4 8 8 8 10912 4012 1535 50810915240 16013

23、0 11共需126位。將段1,2合并，則l=5, 6, 2 ; b=5, 3, 7 ; 合并后P的第一段為001010 001001 001100 111000 110010 100011其余不變.三個表需要存儲空間分別為: L:24位 B:9位 P:88位 (共121位。)12+18+28+24例例 題題算法設(shè)計與分析算法設(shè)計與分析 動態(tài)規(guī)劃動態(tài)規(guī)劃si= si-k+ k*bmax(i-k+1,i) +111)最優(yōu)解結(jié)構(gòu) :設(shè)n個像素的最優(yōu)分段是C, 若在C中,第n像素與 n-1,n-2,.n-k+1像素為一段, 則像素1, 2,.n-k的分段也必是最優(yōu)的. 最優(yōu)分段C所需要的空間消耗為:

24、=像素1, 2,.n-k的最優(yōu)分段空間+k*bmax(n-k+1,n)+11 其中 bmax(a, b)=max ba,., bb 25611) ), ,( (m inm inikilsumik算法思路算法思路: 化為多步?jīng)Q策, 先求有一個像素時的最優(yōu)分段,再求有2個像素時的最優(yōu)分段,有3個像素時的最優(yōu)分段.3)構(gòu)造最優(yōu)解:記ki為si取得最小值時k的值, 可由k的值構(gòu)造相應(yīng) 的最優(yōu)解.2) 遞推關(guān)系:令si為前i個像素最優(yōu)分段的存儲位數(shù),則算法設(shè)計與分析算法設(shè)計與分析 動態(tài)規(guī)劃動態(tài)規(guī)劃#define HEADER=11void Compress(int p, int s, int l, in

25、t b) int n=p.length-1; s0=0; for(int i=1; i=n; i+) bi=length(pi); int bmax=bi; si=si-1+bmax; li=1; for(int j=2; j=i & j=256; j+) if(bmaxsi-j+j*bmax) si=si-j+j*bmax; li=j; si+=HEADER; ij最后一段:ln,bn倒數(shù)第二段:ln-ln,bn-ln計算復(fù)雜性 O(n)/固定循環(huán)長度算法設(shè)計與分析算法設(shè)計與分析 動態(tài)規(guī)劃動態(tài)規(guī)劃 38 電路布線電路布線 問題陳述問題陳述:在一塊電路板的上、下兩端分別有n個接線柱,

26、要求用導(dǎo)線(i, (i)將上端接線柱i與下端接線柱(i)相連. 對于任何1i(j)在制作電路板時，要求將這n條連線分布到若干個絕緣層上。在同一層上的連線不相交.電路布線問題就是要確定將哪些連線安排在第一層(優(yōu)先層)上, 使得該層上有盡可能多的連線。即確定導(dǎo)線集Nets=(i, (i), 1in 的最大不相交子集MNS.上圖中 MNS=(3, 4), (5, 5), (7, 9), (9, 10) 算法設(shè)計與分析算法設(shè)計與分析 動態(tài)規(guī)劃動態(tài)規(guī)劃1)最優(yōu)解結(jié)構(gòu): 設(shè)nets(i, j) =(t, (t) | t i; (t) j nets, MNS(i, j)為nets(i, j)的最大不相交子集

27、, 則所求即為MNS(n,n), 且 MNS(i, j) MNS(n,n).算法思路算法思路: 化為多步?jīng)Q策,自底向上,先求出只有一條連線的最大不相交子集,再求有2條連線的最大不相交子集. 例如例如MNS(7, 6) = (3, 4) ,(5, 5) , Size (7, 6) =2 MNS(10, 10)=MNS= (3, 4), (5, 5), (7, 9), (9, 10) nets(7, 6)= (3, 4), (4, 2), (5, 5), (6, 1) 算法設(shè)計與分析算法設(shè)計與分析 動態(tài)規(guī)劃動態(tài)規(guī)劃 當(dāng)i=1時, nets(1, j)=(1, (1), MNS(1, j) = (1

28、,(1) j (1) j l時, 若j(i), 則有(i, (i) MNS(i, j),此時MNS(i, j)=MNS(i-1, j), Size(i, j)=Size(i-1, j);(i)jSize(i,j)=Size(i-1,j)ii-1 若j(i),則(i,(i)可在也可不在MNS(i, j)中: 若(i, (i) MNS(i, j), 則對任意(t, (t)MNS(i, j), 有t 動態(tài)規(guī)劃動態(tài)規(guī)劃Size(i, j)=01j (1)Size(i, j)=Size(i-1, j)max Size(i-1, j), Size(i-1, (i)-1)+1j (i) (2)當(dāng)il時(1)

29、當(dāng)i=1時 當(dāng)i=1時, nets(1, j)=(1, (1), MNS(1, j) = (1,(1) j (1) j l時 1)若j(i), 則有(i, (i) MNS(i, j), 此時MNS(i, j)=MNS(i-1, j), Size(i, j)=Size(i-1, j); 2)若j(i),則(i,(i)可在也可不在MNS(i, j)中: 若(i,(i) MNS(i, j), 對(t, (t)MNS(i, j) 有t i; (t) (i) 此時MNS(i, j)=MNS(i-1, j-1)(i,(i), Size(i, j)= Size(i-1,(i)-1)+1; 若(i, (i)

30、MNS(i, j), 則對任意(t, (t)MNS(i, j), 有t 動態(tài)規(guī)劃動態(tài)規(guī)劃void MNS(int C，int n，int *size)/初始化size1*for(int j=0；jCl；j+) sizel j=0；for(j=C1；j=n ; j+) size1j=1；/計算sizei*，1infor(int i=2；in；i+) for(int j=0；jCi；j+) sizeij=sizei-1j； for(j=Ci；i1；i-) /i號net在MNS中? if (sizeij!=sizei-1j /在MNS中 Netm+=i； j=Ci-1；/Ci已使用 /1號網(wǎng)組在MN

31、S中? if (j=C1) Netm+=1；/在MNS中算法復(fù)雜性算法復(fù)雜性:(n2)求最大無交叉子集算法算法設(shè)計與分析算法設(shè)計與分析 動態(tài)規(guī)劃動態(tài)規(guī)劃9-107-95-53-4MNS包含4條邊,按i, j 的倒序搜索,在數(shù)字增加處即是邊號.43n個作業(yè)1，2，n要在由2臺機(jī)器M1和M2組成的流水線上完成加工。每個作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時間分別為ai和bi。流水作業(yè)調(diào)度問題要求確定這n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機(jī)器M1上開始加工，到最后一個作業(yè)在機(jī)器M2上加工完成所需的時間最少。分析：分析：直觀上，一個最優(yōu)調(diào)度應(yīng)使機(jī)器M1沒

32、有空閑時間，且機(jī)器M2的空閑時間最少。在一般情況下，機(jī)器M2上會有機(jī)器空閑和作業(yè)積壓2種情況。設(shè)全部作業(yè)的集合為N=1，2，n。SN是N的作業(yè)子集。在一般情況下，機(jī)器M1開始加工S中作業(yè)時，機(jī)器M2還在加工其它作業(yè)，要等時間t后才可利用。將這種情況下完成S中作業(yè)所需的最短時間記為T(S,t)。流水作業(yè)調(diào)度問題的最優(yōu)值為T(N,0)。44設(shè)是所給n個流水作業(yè)的一個最優(yōu)調(diào)度，它所需的加工時間為 a(1)+T。其中T是在機(jī)器M2的等待時間為b(1)時，安排作業(yè)(2)，(n)所需的時間。記S=N-(1)，則有T=T(S,b(1)。證明：證明：事實上，由T的定義知TT(S,b(1)。若TT(S,b(1)

33、，設(shè)是作業(yè)集S在機(jī)器M2的等待時間為b(1)情況下的一個最優(yōu)調(diào)度。則(1)， (2)， (n)是N的一個調(diào)度，且該調(diào)度所需的時間為a(1)+T(S,b(1)a(1)+T。這與是N的最優(yōu)調(diào)度矛盾。故TT(S,b(1)。從而T=T(S,b(1)。這就證明了流水作業(yè)調(diào)度問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。由流水作業(yè)調(diào)度問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，),(min)0 ,(1iinibiNTaNT)0 ,max,(min),(iiiSiatbiSTatST45對遞歸式的深入分析表明，算法可進(jìn)一步得到簡化。設(shè)是作業(yè)集S在機(jī)器M2的等待時間為t時的任一最優(yōu)調(diào)度。若(1)=i, (2)=j。則由動態(tài)規(guī)劃遞歸式可得:T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)其中，,max0 ,max,0 ,maxmax0 ,0 ,maxmaxiijiijijijijijijijijjiijijabaataabbbaatabbbaatabbaatbbt如果作業(yè)i和j滿足minbi,ajminbj,ai，則稱作業(yè)i和j滿足JohnsonJohnson不等式不等式。46交換作業(yè)i和作業(yè)j的加工順序，得到作業(yè)集S的另一調(diào)度，它所需