第03章動態(tài)規(guī)劃

1、2022-5-101第3章 動態(tài)規(guī)劃2022-5-102 動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=算法總體思想2022-5-103 但是經(jīng)分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時，有些子問題被重復計算了許多次。算法總體思想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)2022-5

2、-104 如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。算法總體思想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)2022-5-105動態(tài)規(guī)劃基本步驟 找出最優(yōu)解的性質，并刻劃其結構特征。 遞歸地定義最優(yōu)值。 以自底向上的方式計算出最優(yōu)值。 根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。2022-5-106本章內(nèi)容 3.1 矩陣連乘問題 3.2 動態(tài)規(guī)劃算法的基本要素 3.3 最長公共子序列 3.4 凸多邊形最優(yōu)

3、三角剖分 3.5 多邊形游戲 3.6 圖像壓縮 3.7 電路布線 3.8 流水作業(yè)調度 3.9 0-1背包問題 3.10 最優(yōu)二叉搜索樹2022-5-1073.1 矩陣連乘問題n給定n個矩陣 ， 其中 與 是可乘的 ， 。考察這 n個矩陣的連乘積 n由于矩陣乘法滿足結合律，所以計算矩陣的連乘可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。n若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復調用2個矩陣相乘的標準算法計算出矩陣連乘積,.,21nAAAiA1iA1,.,2 , 1ninAAA.212022-5-108u完全加括號的矩陣連乘積可遞歸地

4、定義為：u設有四個矩陣 ，它們的維數(shù)分別是：u總共有五中完全加括號的方式完全加括號的矩陣連乘積（1）單個矩陣是完全加括號的；（2）矩陣連乘積 是完全加括號的，則 可 表示為2個完全加括號的矩陣連乘積 和 的乘積并加括號，即 AABC)(BCADCBA , , ,1050A4010B3040C530D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB16000, 10500, 36000, 87500, 345002022-5-109矩陣連乘問題 給定n個矩陣A1,A2,An，其中Ai與Ai+1是可乘的，i=1,2 ,n-1。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積

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

6、鏈斷開，ikj，則其相應完全加括號方式為).)(.(211jkkkiiAAAAAA計算量：Ai:k的計算量加上Ak+1:j的計算量，再加上Ai:k和Ak+1:j相乘的計算量2022-5-1011分析最優(yōu)解的結構 特征：計算Ai:j的最優(yōu)次序所包含的計算矩陣子鏈 Ai:k和Ak+1:j的次序也是最優(yōu)的。 矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質稱為最優(yōu)子結構性質。問題的最優(yōu)子結構性質是該問題可用動態(tài)規(guī)劃算法求解的顯著特征。2022-5-1012建立遞歸關系n設計算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mi,j，則原問題的最優(yōu)值為m1,n n當i=j時，Ai:j=Ai，因此，

7、mi,i=0，i=1,2,nn當ij時，n可以遞歸地定義mi,j為：jkipppjkmkimjim1, 1,這里 的維數(shù)為 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只有 種可能，全部遞歸計算需要指數(shù)計算時間。kij 2022-5-1013計算最優(yōu)值n對于1ijn不同的有序對(i,j)對應于不同的子問題。因此，不同子問題的個數(shù)最多只有n由此可見，在遞歸計算時，許多子問題被重復計算多次。這也是該問題可用動態(tài)規(guī)劃算法求解的又一顯著特征。n用動態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進行計算。在計算過程中，保存已解決的子問題答案。每個子問題只計算

8、一次，而在后面需要時只要簡單查一下，從而避免大量的重復計算，最終得到多項式時間的算法)(22nnn2022-5-1014用動態(tài)規(guī)劃法求最優(yōu)解public static void matrixChain(int p, int m, int s) int n=p.length-1; 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;

9、 k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t 0) return mij; if (i = j) return 0; int u = 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; 2022-5-1021本章內(nèi)容 3.1 矩陣連乘問題 3.2 動態(tài)

10、規(guī)劃算法的基本要素 3.3 最長公共子序列 3.4 凸多邊形最優(yōu)三角剖分 3.5 多邊形游戲 3.6 圖像壓縮 3.7 電路布線 3.8 流水作業(yè)調度 3.9 0-1背包問題 3.10 最優(yōu)二叉搜索樹2022-5-1022最長公共子序列 若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存在一個嚴格遞增下標序列i1,i2,ik使得對于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應的遞增下標序列為2，3，5，7。 給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共

11、子序列。 給定2個序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。 2022-5-1023最長公共子序列的結構設序列X=x1,x2,xm和Y=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)子結構性質。 2022-5-1024子問題的遞歸

12、結構由最長公共子序列問題的最優(yōu)子結構性質建立子問題最優(yōu)值的遞歸關系。用cij記錄序列和的最長公共子序列的長度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時Cij=0。其他情況下，由最優(yōu)子結構性質可建立遞歸關系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 1102022-5-1025計算最優(yōu)值由于在所考慮的子問題空間中，總共有(mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。 Algorithm lcsLength(x,y,b)1: mx.

13、length-1;2: ny.length-1;3: ci0=0; c0i=0;4: for (int i = 1; i = m; i+)5: for (int j = 1; j =cij-1) 10: cij=ci-1j;11: bij=2;12: else 13: cij=cij-1;14: bij=3;構造最長公共子序列構造最長公共子序列Algorithm 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); System.out.print(xi); else if (bi

14、j= 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b); 2022-5-1026算法的改進在算法lcsLength和lcs中，可進一步將數(shù)組b省去。事實上，數(shù)組元素cij的值僅由ci-1j-1，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ù)組空間就可以計算出最長公共子序列的長度。進一步的

15、分析還可將空間需求減至O(min(m,n)。2022-5-1027本章內(nèi)容 3.1 矩陣連乘問題 3.2 動態(tài)規(guī)劃算法的基本要素 3.3 最長公共子序列 3.4 凸多邊形最優(yōu)三角剖分 3.5 多邊形游戲 3.6 圖像壓縮 3.7 電路布線 3.8 流水作業(yè)調度 3.9 0-1背包問題 3.10 最優(yōu)二叉搜索樹2022-5-10283.4 凸多邊形最優(yōu)三角剖分用多邊形頂點的逆時針序列表示凸多邊形，即P=v0,v1,vn-1表示具有n條邊的凸多邊形。若vi與vj是多邊形上不相鄰的2個頂點，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成2個多邊形vi,vi+1,vj和vj,vj+1,vi。多邊形

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

17、中的一條邊vi-1vi。三角剖分中的一條弦vivj，ij，對應于矩陣連乘積Ai+1:j。2022-5-1030最優(yōu)子結構性質凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子結構性質。事實上，若凸(n+1)邊形P=v0,v1,vn-1的最優(yōu)三角剖分T包含三角形v0vkvn，1kn-1，則T的權為3個部分權的和：三角形v0vkvn的權，子多邊形v0,v1,vk和vk,vk+1,vn的權之和?？梢詳嘌?，由T所確定的這2個子多邊形的三角剖分也是最優(yōu)的。因為若有v0,v1,vk或vk,vk+1,vn的更小權的三角剖分將導致T不是最優(yōu)三角剖分的矛盾。 2022-5-1031最優(yōu)三角剖分的遞歸結構定義tij，1ijn為凸

18、子多邊形vi-1,vi,vj的最優(yōu)三角剖分所對應的權函數(shù)值，即其最優(yōu)值。為方便起見，設退化的多邊形vi-1,vi具有權值0。據(jù)此定義，要計算的凸(n+1)邊形P的最優(yōu)權值為t1n。tij的值可以利用最優(yōu)子結構性質遞歸地計算。當j-i1時，凸子多邊形至少有3個頂點。由最優(yōu)子結構性質，tij的值應為tik的值加上tk+1j的值，再加上三角形vi-1vkvj的權值，其中ikj-1。由于在計算時還不知道k的確切位置，而k的所有可能位置只有j-i個，因此可以在這j-i個位置中選出使tij值達到最小的位置。由此，tij可遞歸地定義為：jijivvvwjktkitjitjkijki)(1min012022-

19、5-1032本章內(nèi)容 3.1 矩陣連乘問題 3.2 動態(tài)規(guī)劃算法的基本要素 3.3 最長公共子序列 3.4 凸多邊形最優(yōu)三角剖分 3.5 多邊形游戲 3.6 圖像壓縮 3.7 電路布線 3.8 流水作業(yè)調度 3.9 0-1背包問題 3.10 最優(yōu)二叉搜索樹2022-5-1033多邊形游戲是一個單人玩的游戲，開始時有一個由n個頂點構成的多邊形。每個頂點被賦予一個整數(shù)值，每條邊被賦予一個運算符“+”或“*”。所有邊依次用整數(shù)從1到n編號。游戲第1步，將一條邊刪除。隨后n-1步按以下方式操作：(1)選擇一條邊E以及由E連接著的2個頂點V1和V2；(2)用一個新的頂點取代邊E以及由E連接著的2個頂點V

20、1和V2。將由頂點V1和V2的整數(shù)值通過邊E上的運算得到的結果賦予新頂點。最后，所有邊都被刪除，游戲結束。游戲的得分就是所剩頂點上的整數(shù)值。問題:對于給定的多邊形，計算最高得分。2022-5-1034最優(yōu)子結構性質在所給多邊形中，從頂點i(1in)開始，長度為j(鏈中有j個頂點)的順時針鏈p(i，j) 可表示為vi，opi+1，vi+j-1。如果這條鏈的最后一次合并運算在opi+s處發(fā)生(1sj-1)，則可在opi+s處將鏈分割為2個子鏈p(i，s)和p(i+s，j-s)。設m1是對子鏈p(i，s)的任意一種合并方式得到的值，而a和b分別是在所有可能的合并中得到的最小值和最大值。m2是p(i+

21、s，j-s)的任意一種合并方式得到的值，而c和d分別是在所有可能的合并中得到的最小值和最大值。依此定義有am1b，cm2d(1)當opi+s=+時，顯然有a+cmb+d(2)當opi+s=*時，有minac，ad，bc，bdmmaxac，ad，bc，bd 換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。 2022-5-1035本章內(nèi)容 3.1 矩陣連乘問題 3.2 動態(tài)規(guī)劃算法的基本要素 3.3 最長公共子序列 3.4 凸多邊形最優(yōu)三角剖分 3.5 多邊形游戲 3.6 圖像壓縮 3.7 電路布線 3.8 流水作業(yè)調度 3.9 0-1背包問題 3.10 最優(yōu)二叉搜索樹2022-5-1

22、0363.6 圖像壓縮圖像的變位壓縮存儲格式將所給的象素點序列p1,p2,pn,0pi255分割成m個連續(xù)段S1,S2,Sm。第i個象素段Si中(1im)，有l(wèi)i個象素,且該段中每個象素都只用bi位表示。設 則第i個象素段Si為11ikklitmippSilititi1 ,12022-5-1037圖像壓縮 設 ，則hibi8。因此 需要用3位表示bi,如果限制1li255，則需要用8位表示li。因此，第i個象素段所需的存儲空間為li*bi+11位。按此格式存儲象素序列p1,p2,pn，需要 位的存儲空間。 圖像壓縮問題要求確定象素序列p1,p2,pn的最優(yōu)分段，使得依此分段所需的存儲空間最少。

23、每個分段的長度不超過256位。1maxlog1kilitkitiphmibilmi11*12022-5-1038圖像壓縮設li，bi，是p1,p2,pn的最優(yōu)分段。顯而易見，l1，b1是p1,pl1的最優(yōu)分段，且li，bi，是pl1+1,pn的最優(yōu)分段。即圖像壓縮問題滿足最優(yōu)子結構性質。設si，1in，是象素序列p1,pn的最優(yōu)分段所需的存儲位數(shù)。由最優(yōu)子結構性質易知：2022-5-1039圖像壓縮11), 1max(b*min256,min1ikikkisisik1maxlog),bmax(kjkipji其中：算法復雜度分析：算法復雜度分析：由于算法compress中對k的循環(huán)次數(shù)不超這25

24、6，故對每一個確定的i，可在時間O(1)內(nèi)完成的計算。因此整個算法所需的計算時間為O(n)。 2022-5-1040本章內(nèi)容 3.1 矩陣連乘問題 3.2 動態(tài)規(guī)劃算法的基本要素 3.3 最長公共子序列 3.4 凸多邊形最優(yōu)三角剖分 3.5 多邊形游戲 3.6 圖像壓縮 3.7 電路布線 3.8 流水作業(yè)調度 3.9 0-1背包問題 3.10 最優(yōu)二叉搜索樹2022-5-10413.7 電路布線 在一塊電路板的上、下兩端分別有n個接線柱。根據(jù)電路設計，要求用導線(i,(i)將上端接線柱與下端接線柱相連，如圖所示。其中(i)是1,2,n的一個排列。導線(i,(i)稱為該電路板上的第i條連線。對于

25、任何1i(j)。 電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，該問題要求確定導線集Nets=(i,(i),1in的最大不相交子集。2022-5-1042 記 。N(i,j)的最大不相交子集為MNS(i,j)。Size(i,j)=|MNS(i,j)|。 1 當i=1時，電路布線)(,)(,( |),(jtitNetstttjiN) 1 ()1 (, 1() 1 (), 1 (), 1 (jjjNjMNS2022-5-1043電路布線2. 當i1時，(1) j(i)。此時， 。故在這種情況下，N(i,j)=N(i-1,j)，故 MNS(i,j)=MNS (i-

26、1,j)，從而 Size(i,j)=Size(i-1,j)。),()(,(jiNiii(i)jN(i,j)2022-5-1044電路布線(2) j(i) 若(i,(i)MNS(i,j) ，則 對任意(t,(t) MNS(i,j)有ti且(t)(i)，否則(t,(t) 和(i,(i) 相交； MNS(i,j)-(i,(i)是N(i-1,(i)-1)的最大不相交子集，否則N(i-1,(i)-1)的最大不相交子集MNS(i-1,(i)-1)并上 (i,(i) （包含于）是N(i,j) 中比MNS(i,j )更大的不相交子集。與MNS(i,j )的定義矛盾。 所以， Size(i,j)=Size(i-

27、1, (i)-1)1i(i)jN(i,j)i-1(i)-12022-5-1045電路布線 若 ，則 對任意(t,(t) MNS(i,j)有 t1時(3) Size(i,0)=0) 1 (1) 1 (0), 1 (jjjSize)()( 1) 1)(, 1(), 1(max), 1(), (ijijiiSizejiSizejiSizejiSize2022-5-1047實例說明 對應關系為：(1,8), (2,7), (3,4), (4,2), (5,5), (6,1), (7,9), (8,3), (9,10), (10,6)2022-5-1048i=1,(1)=8Size12345678910

28、1000000011123456789102022-5-1049i=2,(2)=7Size1234567891010000000111200000011113456789102022-5-1050i=3,(3)=4Size12345678910100000001112000000111130001111111456789102022-5-1051i=4,(4)=2Size123456789101000000011120000001111300011111114011111111156789102022-5-1052i=5,(5)=5Size123456789101000000011120000

29、0011113000111111140111111111501112222226789102022-5-1053i=6,(6)=1, size(5,0)=0Size12345678910100000001112000000111130001111111401111111115011122222261111222222789102022-5-1054i=7,(7)=9Size123456789101000000011120000001111300011111114011111111150111222222611112222227111122223389102022-5-1055i=8,(8)=3

30、Size1234567891010000000111200000011113000111111140111111111501112222226111122222271111222233811222222339102022-5-1056i=9,(9)=10Size12345678910100000001112000000111130001111111401111111115011122222261111222222711112222338112222223391122222234102022-5-1057i=10,(10)=6Size1234567891010000000111200000011

31、11300011111114011111111150111222222611112222227111122223381122222233911222222341011222333342022-5-1058最優(yōu)解的構造Size123456789101000000011120000001111300011111114011111111150111222222611112222227111122223381122222233911222222341011222333342022-5-1059本章內(nèi)容 3.1 矩陣連乘問題 3.2 動態(tài)規(guī)劃算法的基本要素 3.3 最長公共子序列 3.4 凸多邊形最優(yōu)三

32、角剖分 3.5 多邊形游戲 3.6 圖像壓縮 3.7 電路布線 3.8 流水作業(yè)調度 3.9 0-1背包問題 3.10 最優(yōu)二叉搜索樹2022-5-10603.8 流水作業(yè)調度537264536584824547212022-5-10613.8 流水作業(yè)調度n個作業(yè)1，2，n要在由2臺機器M1和M2組成的流水線上完成加工。每個作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時間分別為ai和bi。流水作業(yè)調度問題要求確定這n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機器M1上開始加工，到最后一個作業(yè)在機器M2上加工完成所需的時間最少。2022-5-1062分析 直觀上

33、，一個最優(yōu)調度應使機器M1沒有空閑時間，且機器M2的空閑時間最少。在一般情況下，機器M2上會有機器空閑和作業(yè)積壓2種情況。 設全部作業(yè)的集合為N=1，2，n。SN是N的作業(yè)子集。在一般情況下，機器M1開始加工S中作業(yè)時，機器M2還在加工其他作業(yè)，要等時間t后才可利用。將這種情況下完成S中作業(yè)所需的最短時間記為T(S,t)。流水作業(yè)調度問題的最優(yōu)值為T(N,0)。2022-5-1063流水作業(yè)調度設是所給n個流水作業(yè)的一個最優(yōu)調度，它所需的加工時間為 a(1)+T。其中T是在機器M2的等待時間為b(1)時，安排作業(yè)(2)，(n)所需的時間。記S=N-(1)，則有T=T(S,b(1)。2022-5

34、-1064流水作業(yè)調度證明：證明：事實上，由T的定義知TT(S,b(1)。若TT(S,b(1)，設是作業(yè)集S在機器M2的等待時間為b(1)情況下的一個最優(yōu)調度。則(1)， (2)， (n)是N的一個調度，且該調度所需的時間為a(1)+T(S,b(1)a(1)+T。這與是N的最優(yōu)調度矛盾。故TT(S,b(1)。從而T=T(S,b(1)。這就證明了流水作業(yè)調度問題具有最優(yōu)子結構的性質。 由流水作業(yè)調度問題的最優(yōu)子結構性質可知：),(min)0 ,(1iinibiNTaNT)0 ,max,(min),(iiiSiatbiSTatST2022-5-1065Johnson不等式對遞歸式的深入分析表明，算

35、法可進一步得到簡化。設是作業(yè)集S在機器M2的等待時間為t時的任一最優(yōu)調度。若(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滿足Johnson不等式不等式。2022-5-1066流水作業(yè)調度的Johnson法則交換作業(yè)i和作業(yè)j的加工順序，得到作業(yè)集S的另

36、一調度，它所需的加工時間為T(S,t)=ai+aj+T(S-i,j,tji)其中，當作業(yè)i和j滿足Johnson不等式時，有,maxjjjiijijjiabaataabbt,maxiijiijijijabaataabbt,max,max,max,max,max,max,max,maxjjjiiijijjjiiijiijjijijiijjiabaatabaatabaaabaaabaaabaaabab2022-5-1067流水作業(yè)調度的Johnson法則 由此可見當作業(yè)i和作業(yè)j不滿足Johnson不等式時，交換它們的加工順序后，不增加加工時間。對于流水作業(yè)調度問題，必存在最優(yōu)調度 ，使得作業(yè)(i

37、)和(i+1)滿足Johnson不等式。進一步還可以證明，調度滿足Johnson法則當且僅當對任意i2n時，算法需要(n2n)計算時間。 2022-5-1074算法改進由m(i,j)的遞歸式容易證明，在一般情況下，對每一個確定的i(1in)，函數(shù)m(i,j)是關于變量j的階梯狀單調不減函數(shù)。跳躍點是這一類函數(shù)的描述特征。在一般情況下，函數(shù)m(i,j)由其全部跳躍點惟一確定。如圖所示。對每一個確定的i(1in)，用一個表pi存儲函數(shù)m(i，j)的全部跳躍點。表pi可依計算m(i，j)的遞歸式遞歸地由表pi+1計算，初始時pn+1=(0，0)。 2022-5-1075典型例子（一）n=3，c=6，

38、w=4，3，2，v=5，2，1。x(0,0)m(4,x)x(2,1)m(4,x-2)+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)2022-5-1076算法改進函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-wi)+vi作max運算得到的。因此，函數(shù)

39、m(i,j)的全部跳躍點包含于函數(shù)m(i+1，j)的跳躍點集pi+1與函數(shù)m(i+1，j-wi)+vi的跳躍點集qi+1的并集中。易知，(s,t)qi+1當且僅當wisc且(s-wi,t-vi)pi+1。因此，容易由pi+1確定跳躍點集qi+1如下qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1 另一方面，設(a，b)和(c，d)是pi+1qi+1中的2個跳躍點，則當ca且db時，(c，d)受控于(a，b)，從而(c，d)不是pi中的跳躍點。除受控跳躍點外，pi+1qi+1中的其他跳躍點均為pi中的跳躍點。由此可見，在遞歸地由表pi+1計算表pi時

40、，可先由pi+1計算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控跳躍點得到表pi。2022-5-1077典型例子（二）n=5，c=10，w=2，2，6，5，4，v=6，3，5，4，6。初始時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)。從跳躍點集p5與q5的并集p5q5=(0,0),(4,6),(5,4),(9,10)中看到跳躍點(5,4)受控于跳躍點(4,6)。將受控跳躍點(5,4)清除后，得到p4=(0,0),(4,6),(9,10)q4=p4(6，

41、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的最后的那個跳躍點(8,15)給出所求的最優(yōu)值為m(1,c)=15。2022-5-1078算法復雜度分析 上述算法的主要計算量在于計算跳躍點集pi(1in)。由于qi+1=pi+1(wi，vi)，故計算qi+1需要O(|pi+1|)計算時間。合并