動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)

1、動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò) 學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn):n理解動(dòng)態(tài)規(guī)劃算法的概念。n掌握動(dòng)態(tài)規(guī)劃算法的基本要素n（1）最優(yōu)子結(jié)構(gòu)性質(zhì)n（2）重疊子問(wèn)題性質(zhì)n掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟。n(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。n(2)遞歸地定義最優(yōu)值。n(3)以自底向上的方式計(jì)算出最優(yōu)值。n(4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。2通過(guò)應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略。（1）矩陣連乘問(wèn)題；（2）最長(zhǎng)公共子序列；（3）最大子段和（4）凸多邊形最優(yōu)三角剖分；（5）多邊形游戲； （6）圖像壓縮；（7）電路布線；（8）流水作業(yè)調(diào)度；（9）背包問(wèn)題；（10）最優(yōu)二叉搜索樹(shù)。3n動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將

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

3、n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)6n找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。n遞歸地定義最優(yōu)值。n以自底向上的方式計(jì)算出最優(yōu)值。n根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。7u完全加括號(hào)的矩陣連乘積可遞歸地定義為： （1）單個(gè)矩陣是完全加括號(hào)的； （2）矩陣連乘積A是完全加括號(hào)的，則A可表示為2個(gè)完全加括號(hào)的矩陣連乘積B和C的乘積并加括號(hào)，即 A=(BC) 。u設(shè)有四個(gè)矩陣A,B,C,D ，它們的維數(shù)分別是： A=5010，B=1040，C=4030，D=305 總共有五中完全加括號(hào)的方式： (AB)C)D)，(A(BC)D)，(A(B(CD)，(AB)(

4、CD)，(A(BC)D) 計(jì)算量分別為87500, 16000, 10500, 36000, 345008n給定n個(gè)矩陣 ， 其中 與 是可乘的， 。考察這n個(gè)矩陣的連乘積 n由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。n若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積,.,21nAAAiA1iA1,.,2 , 1ninAAA.219給定n個(gè)矩陣A1,A2,An，其中Ai與Ai+1是可乘的，i=1，2，n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序

5、計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。u窮舉法窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。 算法復(fù)雜度分析：算法復(fù)雜度分析：對(duì)于n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問(wèn)題：(A1.Ak)(Ak+1An)可以得到關(guān)于P(n)的遞推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnk10u窮舉法窮舉法u動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃將矩陣連乘積 簡(jiǎn)記為Ai:j ，這里ij jiiAAA.1考察計(jì)算Ai:j的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈

6、斷開(kāi)，ikj，則其相應(yīng)完全加括號(hào)方式為).)(.(211jkkkiiAAAAAA計(jì)算量：Ai:k的計(jì)算量加上Ak+1:j的計(jì)算量，再加上Ai:k和Ak+1:j相乘的計(jì)算量11n特征：計(jì)算Ai:j的最優(yōu)次序所包含的計(jì)算矩陣子鏈 Ai:k和Ak+1:j的次序也是最優(yōu)的。n矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。12n設(shè)計(jì)算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mi,j，則原問(wèn)題的最優(yōu)值為m1,n n當(dāng)i=j時(shí)，Ai:j=Ai，因此，mi,i=0，i=1,2,nn當(dāng)ij時(shí)，n可以遞歸地

7、定義mi,j為：jkipppjkmkimjim1, 1,這里 的維數(shù)為 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只有 種可能kij 13n對(duì)于1ijn不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問(wèn)題。因此，不同子問(wèn)題的個(gè)數(shù)最多只有n由此可見(jiàn)，在遞歸計(jì)算時(shí)，許多子問(wèn)題被重復(fù)計(jì)算多次許多子問(wèn)題被重復(fù)計(jì)算多次。這也是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。n用動(dòng)態(tài)規(guī)劃算法解此問(wèn)題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過(guò)程中，保存已解決的子問(wèn)題答案。每個(gè)子問(wèn)題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法)(

8、22nnn14void 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+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t 0) return mij; if (i = j) return 0; in

9、t 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*pj; if (t u) u = t; sij = k; mij = u; return u;18若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對(duì)于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=

10、A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列公共子序列。給定2個(gè)序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長(zhǎng)公共子序列。 19設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長(zhǎng)公共子序列為Z=z1,z2,zk ，則(1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長(zhǎng)公共子序列。(2)若xmyn且zkxm，則Z是xm-1和Y的最長(zhǎng)公共子序列。(3)若xmyn且zkyn，則Z是X和yn-1的最長(zhǎng)公共子序列。由此可見(jiàn)，2個(gè)序列的最長(zhǎng)公

11、共子序列包含了這2個(gè)序列的前綴的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。 20由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。用cij記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)Cij=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 11021由于在所考慮的子問(wèn)題空間中，總共有(mn)個(gè)不同的子問(wèn)題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提

12、高算法的效率。 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; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 構(gòu)造最長(zhǎng)公共子序列構(gòu)造最長(zhǎng)公共子序列void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) retu

13、rn; 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);22在算法lcsLength和lcs中，可進(jìn)一步將數(shù)組b省去。事實(shí)上，數(shù)組元素cij的值僅由ci-1j-1，ci-1j和cij-1這3個(gè)數(shù)組元素的值所確定。對(duì)于給定的數(shù)組元素cij，可以不借助于數(shù)組b而僅借助于c本身在時(shí)間內(nèi)確定cij的值是由ci-1j-1，ci-1j和cij-1中哪一個(gè)值所確定的。如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求可大大減少。事實(shí)上，在計(jì)算cij時(shí)，只用到數(shù)組c的第i行和

14、第i-1行。因此，用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。進(jìn)一步的分析還可將空間需求減至O(min(m,n)。23用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即P=v0,v1,vn-1表示具有n條邊的凸多邊形。若vi與vj是多邊形上不相鄰的2個(gè)頂點(diǎn)，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成2個(gè)多邊形vi,vi+1,vj和vj,vj+1,vi。多邊形的三角剖分多邊形的三角剖分是將多邊形分割成互不相交的三角形的弦的集合T。給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權(quán)之和為最小。 24一個(gè)表達(dá)式的完全加

15、括號(hào)方式相應(yīng)于一棵完全二叉樹(shù)，稱為表達(dá)式的語(yǔ)法樹(shù)。例如，完全加括號(hào)的矩陣連乘積(A1(A2A3)(A4(A5A6)所相應(yīng)的語(yǔ)法樹(shù)如圖 (a)所示。凸多邊形v0,v1,vn-1的三角剖分也可以用語(yǔ)法樹(shù)表示。例如，圖 (b)中凸多邊形的三角剖分可用圖 (a)所示的語(yǔ)法樹(shù)表示。 矩陣連乘積中的每個(gè)矩陣Ai對(duì)應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，ij，對(duì)應(yīng)于矩陣連乘積Ai+1:j。25凸多邊形的最優(yōu)三角剖分問(wèn)題有最優(yōu)子結(jié)構(gòu)性質(zhì)。事實(shí)上，若凸(n+1)邊形P=v0,v1,vn-1的最優(yōu)三角剖分T包含三角形v0vkvn，1kn-1，則T的權(quán)為3個(gè)部分權(quán)的和：三角形v0vk

16、vn的權(quán)，子多邊形v0,v1,vk和vk,vk+1,vn的權(quán)之和?？梢詳嘌?，由T所確定的這2個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲衯0,v1,vk或vk,vk+1,vn的更小權(quán)的三角剖分將導(dǎo)致T不是最優(yōu)三角剖分的矛盾。 26定義tij，1ijn為凸子多邊形vi-1,vi,vj的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值。為方便起見(jiàn)，設(shè)退化的多邊形vi-1,vi具有權(quán)值0。據(jù)此定義，要計(jì)算的凸(n+1)邊形P的最優(yōu)權(quán)值為t1n。tij的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算。當(dāng)j-i1時(shí)，凸子多邊形至少有3個(gè)頂點(diǎn)。由最優(yōu)子結(jié)構(gòu)性質(zhì)，tij的值應(yīng)為tik的值加上tk+1j的值，再加上三角形vi-1vk

17、vj的權(quán)值，其中ikj-1。由于在計(jì)算時(shí)還不知道k的確切位置，而k的所有可能位置只有j-i個(gè)，因此可以在這j-i個(gè)位置中選出使tij值達(dá)到最小的位置。由此，tij可遞歸地定義為：jijivvvwjktkitjitjkijki)(1min0127多邊形游戲是一個(gè)單人玩的游戲，開(kāi)始時(shí)有一個(gè)由n個(gè)頂點(diǎn)構(gòu)成的多邊形。每個(gè)頂點(diǎn)被賦予一個(gè)整數(shù)值，每條邊被賦予一個(gè)運(yùn)算符“+”或“*”。所有邊依次用整數(shù)從1到n編號(hào)。游戲第1步，將一條邊刪除。隨后n-1步按以下方式操作：(1)選擇一條邊E以及由E連接著的2個(gè)頂點(diǎn)V1和V2；(2)用一個(gè)新的頂點(diǎn)取代邊E以及由E連接著的2個(gè)頂點(diǎn)V1和V2。將由頂點(diǎn)V1和V2的整數(shù)

18、值通過(guò)邊E上的運(yùn)算得到的結(jié)果賦予新頂點(diǎn)。最后，所有邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點(diǎn)上的整數(shù)值。問(wèn)題:對(duì)于給定的多邊形，計(jì)算最高得分。28在所給多邊形中，從頂點(diǎn)i(1in)開(kāi)始，長(zhǎng)度為j(鏈中有j個(gè)頂點(diǎn))的順時(shí)針鏈p(i，j) 可表示為vi，opi+1，vi+j-1。如果這條鏈的最后一次合并運(yùn)算在opi+s處發(fā)生(1sj-1)，則可在opi+s處將鏈分割為2個(gè)子鏈p(i，s)和p(i+s，j-s)。設(shè)m1是對(duì)子鏈p(i，s)的任意一種合并方式得到的值，而a和b分別是在所有可能的合并中得到的最小值和最大值。m2是p(i+s，j-s)的任意一種合并方式得到的值，而c和d分別是在所有可能的

19、合并中得到的最小值和最大值。依此定義有am1b，cm2d(1)當(dāng)opi+s=+時(shí)，顯然有a+cmb+d(2)當(dāng)opi+s=*時(shí)，有minac，ad，bc，bdmmaxac，ad，bc，bd 換句話說(shuō)，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。 29圖象的變位壓縮存儲(chǔ)格式將所給的象素點(diǎn)序列p1,p2,pn,0pi255分割成m個(gè)連續(xù)段S1,S2,Sm。第i個(gè)象素段Si中(1im)，有l(wèi)i個(gè)象素,且該段中每個(gè)象素都只用bi位表示。設(shè) 則第i個(gè)象素段Si為設(shè) ，則hibi8。因此需要用3位表示bi,如果限制1li255，則需要用8位表示li。因此，第i個(gè)象素段所需的存儲(chǔ)空間為li*bi+11

20、位。按此格式存儲(chǔ)象素序列p1,p2,pn，需要 位的存儲(chǔ)空間。 圖象壓縮問(wèn)題要求確定象素序列p1,p2,pn的最優(yōu)分段，使得依此分段所需的存儲(chǔ)空間最少。每個(gè)分段的長(zhǎng)度不超過(guò)256位。11ikklit,1ilititippS1maxlog1kilitkitiphmibilmi11*130設(shè)li，bi (1i m )，是p1,p2,pn的最優(yōu)分段。顯而易見(jiàn)，l1，b1是p1,pl1的最優(yōu)分段，且li，bi (2i m ) ，是pl1+1,pn的最優(yōu)分段。即圖象壓縮問(wèn)題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。設(shè)si，1in，是象素序列p1,pn的最優(yōu)分段所需的存儲(chǔ)位數(shù)。由最優(yōu)子結(jié)構(gòu)性質(zhì)易知：其中11), 1max(b*

21、min256,min1ikikkisisik1maxlog),bmax(kjkipji算法復(fù)雜度分析：算法復(fù)雜度分析：由于算法compress中對(duì)k的循環(huán)次數(shù)不超這256，故對(duì)每一個(gè)確定的i，可在時(shí)間O(1)內(nèi)完成的計(jì)算。因此整個(gè)算法所需的計(jì)算時(shí)間為O(n)。 31在一塊電路板的上、下2端分別有n個(gè)接線柱。根據(jù)電路設(shè)計(jì)，要求用導(dǎo)線(i,(i)將上端接線柱與下端接線柱相連，如圖所示。其中(i)是1,2,n的一個(gè)排列。導(dǎo)線(i,(i)稱為該電路板上的第i條連線。對(duì)于任何1i(j)。電路布線問(wèn)題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說(shuō)，該問(wèn)題要求確定導(dǎo)線集Nets=(i,

22、(i),1in的最大不相交子集。 32記 。N(i,j)的最大不相交子集為MNS(i,j)。Size(i,j)=|MNS(i,j)|。(1)當(dāng)i=1時(shí)，(2)當(dāng)i1時(shí)，2.1 j(i)。此時(shí)， 。故在這種情況下，N(i,j)=N(i-1,j)，從而Size(i,j)=Size(i-1,j)。2.2 j(i)，(i,(i)MNS(i,j) 。 則對(duì)任意(t,(t) MNS(i,j)有ti且(t)(i)。在這種情況下MNS(i,j)-(i,(i)是N(i-1,(i)-1)的最大不相交子集。 2.3 若 ，則對(duì)任意(t,(t) MNS(i,j)有 t1時(shí)) 1 (1) 1 (0), 1 (jjjSi

23、ze)()(1) 1)(, 1(), 1(max), 1(),(ijijiiSizejiSizejiSizejiSize33n個(gè)作業(yè)1，2，n要在由2臺(tái)機(jī)器M1和M2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時(shí)間分別為ai和bi。流水作業(yè)調(diào)度問(wèn)題要求確定這n個(gè)作業(yè)的最優(yōu)加工順序，使得從第一個(gè)作業(yè)在機(jī)器M1上開(kāi)始加工，到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少。分析：分析：直觀上，一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器M1沒(méi)有空閑時(shí)間，且機(jī)器M2的空閑時(shí)間最少。在一般情況下，機(jī)器M2上會(huì)有機(jī)器空閑和作業(yè)積壓2種情況。設(shè)全部作業(yè)的集合為N=1，2

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

25、的時(shí)間為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)度問(wèn)題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。由流水作業(yè)調(diào)度問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，),(min)0 ,(1iinibiNTaNT)0 ,max,(min),(iiiSiatbiSTatST35對(duì)遞歸式的深入分析表明，算法可進(jìn)一步得到簡(jiǎn)化。設(shè)是作業(yè)集S在機(jī)器M2的等待時(shí)間為t時(shí)的任一最優(yōu)調(diào)度。若(1)=i, (2)=j。則由動(dòng)態(tài)規(guī)劃遞歸式可得:T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)其中，,max0 ,max,0 ,

26、maxmax0 ,0 ,maxmaxiijiijijijijijijijijjiijijabaataabbbaatabbbaatabbaatbbt如果作業(yè)i和j滿足minbi,ajminbj,ai，則稱作業(yè)i和j滿足JohnsonJohnson不等式不等式。36交換作業(yè)i和作業(yè)j的加工順序，得到作業(yè)集S的另一調(diào)度，它所需的加工時(shí)間為T(S,t)=ai+aj+T(S-i,j,tji)其中，當(dāng)作業(yè)i和j滿足Johnson不等式時(shí)，有由此可見(jiàn)當(dāng)作業(yè)i和作業(yè)j不滿足Johnson不等式時(shí)，交換它們的加工順序后，不增加加工時(shí)間。對(duì)于流水作業(yè)調(diào)度問(wèn)題，必存在最優(yōu)調(diào)度 ，使得作業(yè)(i)和(i+1)滿足Joh

27、nson不等式。進(jìn)一步還可以證明，調(diào)度滿足Johnson法則當(dāng)且僅當(dāng)對(duì)任意i2n時(shí)，算法需要(n2n)計(jì)算時(shí)間。 40由m(i,j)的遞歸式容易證明，在一般情況下，對(duì)每一個(gè)確定的i(1in)，函數(shù)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是這一類函數(shù)的描述特征。在一般情況下，函數(shù)m(i,j)由其全部跳躍點(diǎn)唯一確定。如圖所示。對(duì)每一個(gè)確定的i(1in)，用一個(gè)表pi存儲(chǔ)函數(shù)m(i，j)的全部跳躍點(diǎn)。表pi可依計(jì)算m(i，j)的遞歸式遞歸地由表pi+1計(jì)算，初始時(shí)pn+1=(0，0)。 41n=3，c=6，w=4，3，2，v=5，2，1。x(0,0)m(4,x)x(2,1)m(4,x-2

28、)+1x(0,0)(2,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0, 0)(2, 1)m(1,x)(3,2)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)42函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-wi)+vi作max運(yùn)算得到的。因此，函數(shù)m(i,j)的全部跳躍點(diǎn)包含于函數(shù)m(i+1，j)的跳躍點(diǎn)集pi+1與函數(shù)m(i+1，j-wi)+vi的跳躍

29、點(diǎn)集qi+1的并集中。易知，(s,t)qi+1當(dāng)且僅當(dāng)wisc且(s-wi,t-vi)pi+1。因此，容易由pi+1確定跳躍點(diǎn)集qi+1如下qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1 另一方面，設(shè)(a，b)和(c，d)是pi+1qi+1中的2個(gè)跳躍點(diǎn)，則當(dāng)ca且db時(shí)，(c，d)受控于(a，b)，從而(c，d)不是pi中的跳躍點(diǎn)。除受控跳躍點(diǎn)外，pi+1qi+1中的其它跳躍點(diǎn)均為pi中的跳躍點(diǎn)。由此可見(jiàn)，在遞歸地由表pi+1計(jì)算表pi時(shí)，可先由pi+1計(jì)算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控跳躍點(diǎn)得到表pi。43n=5

30、，c=10，w=2，2，6，5，4，v=6，3，5，4，6。初始時(shí)p6=(0,0)，(w5,v5)=(4,6)。因此，q6=p6(w5,v5)=(4,6)。p5=(0,0),(4,6)。q5=p5(w4,v4)=(5,4),(9,10)。從跳躍點(diǎn)集p5與q5的并集p5q5=(0,0),(4,6),(5,4),(9,10)中看到跳躍點(diǎn)(5,4)受控于跳躍點(diǎn)(4,6)。將受控跳躍點(diǎn)(5,4)清除后，得到p4=(0,0),(4,6),(9,10)q4=p4(6，5)=(6，5)，(10，11)p3=(0，0)，(4，6)，(9，10)，(10，11)q3=p3(2，3)=(2，3)，(6，9)p2=(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)q2=p2(2，6)=(2，6)，(4，9)，(6，12)，(8，15)p1=(0，0)，(2，6)，(4，9)，(6，12)，(8，15)p1的最后的那個(gè)跳躍點(diǎn)(8,15)給出所求的最優(yōu)值為m(1,c)=15。44上述算法的主要計(jì)算量在于計(jì)算跳躍點(diǎn)集pi(1in)。由于qi+1=pi+1(wi，vi)，故計(jì)算qi+1需要O(|pi+1|)計(jì)算時(shí)間。合并pi+1和qi+1并清除受控跳躍點(diǎn)也需要O(|pi+1|)計(jì)算時(shí)間。從跳躍點(diǎn)集pi的定義可以看出，pi中的跳躍點(diǎn)相應(yīng)于xi,xn的0/1賦值。