第3章动态规划

1、1课程安排课程安排12345678910111213141516周二周二P PP PTTTTP PTTTTP PTTTTP PTTTTTTTTP P周四周四P PP PP PP PP PP PP PP PP PP PP PP PP PP P 端午端午考试考试TT3 理解理解动态规划动态规划算法的概念。算法的概念。 掌握掌握动态规划动态规划算法的基本要素算法的基本要素(1) 最优子结构性质最优子结构性质(2) 重叠子问题性质重叠子问题性质 掌握掌握设计设计动态规划算法的步骤。动态规划算法的步骤。(1) 找出最优解的性质，并刻划其结构特征。找出最优解的性质，并刻划其结构特征。(2) 递归地定义最优

2、值。递归地定义最优值。(3) 以自底向上的方式计算出最优值。以自底向上的方式计算出最优值。(4) 根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。学习要点学习要点:4(1) 矩阵连乘问题；矩阵连乘问题；(2) 最长公共子序列；最长公共子序列；(3) 最大子段和最大子段和;(4) 凸多边形最优三角剖分；凸多边形最优三角剖分；(5) 多边形游戏；多边形游戏； (6) 图像压缩；图像压缩；(7) 电路布线；电路布线；(8) 流水作业调度；流水作业调度；(9) 背包问题；背包问题；(10) 最优二叉搜索树。最优二叉搜索树。通过应用范例学习动态规划算法设计策略通过应用范例

3、学习动态规划算法设计策略5n 找出最优解的找出最优解的性质性质，并刻划其结构特征。，并刻划其结构特征。n 递归地定义递归地定义最优值。最优值。n 以以自底向上自底向上的方式计算出最优值。的方式计算出最优值。n 根据计算最优值时得到的信息，构造根据计算最优值时得到的信息，构造最优解最优解。13是动态规划算法最基本的步骤是动态规划算法最基本的步骤,若需要最优解若需要最优解, 则必须执行步骤则必须执行步骤46完全加括号的矩阵连乘积可递归地定义为：完全加括号的矩阵连乘积可递归地定义为：n 单个矩阵是完全加括号的；单个矩阵是完全加括号的；n 矩阵连乘积矩阵连乘积A是完全加括号的，则是完全加括号的，则A可

4、表示为可表示为2个完全加个完全加括号的矩阵连乘积括号的矩阵连乘积B和和C的乘积并加括号，即的乘积并加括号，即A=(BC) 设有四个矩阵设有四个矩阵A, B, C, D，总共有五种完全加括号的方式，总共有五种完全加括号的方式:(A(BC)D)(A(B(CD)(AB)(CD)(AB)C)D)(A(BC)D)7设有四个矩阵设有四个矩阵A, B, C, D，它们的维数分别是：，它们的维数分别是：A=5010, B=1040, C=4030, D=305矩阵矩阵A和和B可乘的条件是可乘的条件是: 矩阵矩阵A的列数等于矩阵的列数等于矩阵B的行数的行数.设设A是是pq的矩阵的矩阵, B是是qr的矩阵的矩阵,

5、 则乘积是则乘积是pr的矩阵的矩阵;计算量是计算量是pqr.上述上述5种完全加括号方式的计算工作量为种完全加括号方式的计算工作量为:(A(BC)D), (A(B(CD), (AB)(CD), (AB)C)D), (A(BC)D)16000, 10500, 36000, 87500, 34500BC: 104030 = 12000, (BC)D: 10305 = 1500,(A(BC)D): 50105 = 25008示例示例9示例示例10定义：定义：给定给定n n个矩阵个矩阵AA1 1,A,A2 2,A,An n ，其中，其中A Ai i与与A Ai+1i+1是可乘的，是可乘的，i=1,2,n

6、-1i=1,2,n-1。考察这。考察这n n个矩阵的连乘积个矩阵的连乘积A A1 1A A2 2AAn n。 由于矩阵乘法满足由于矩阵乘法满足结合律结合律，所以计算矩阵的连乘可以有许，所以计算矩阵的连乘可以有许多多不同的不同的计算次序。这种计算次序可以用计算次序。这种计算次序可以用加括号加括号的方式来的方式来确定。确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用积已完全加括号，则可以依此次序反复调用2 2个矩阵相乘个矩阵相乘的标准算法计算出矩阵连乘积的标准算法计算出矩阵连乘积11算法复杂度分析：算法

7、复杂度分析：对于对于n个矩阵的连乘积，设其不同的计算次序为个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于可以得到关于P(n)的递推式如下：的递推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnk给定给定n n个矩阵个矩阵A A1 1,A,A2 2,A,An n，其中，其中A Ai i与与A Ai+1i+1是可乘的，是可乘的，i=1i=1，22，n-1n-1。如何确定计算矩阵连乘积的计算次序，。如何确定计算矩阵连乘积的计

8、算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少？使得依此次序计算矩阵连乘积需要的数乘次数最少？穷举法：穷举法：列举出所有可能的计算次序，并计算出每一种计列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。的计算次序。12穷举法穷举法动态规划动态规划将矩阵连乘积将矩阵连乘积AiAi+1Aj 简记为简记为Ai:j, 这里这里ij;考察计算考察计算Ai:n的最优计算次序。的最优计算次序。设这个计算次序在矩阵设这个计算次序在矩阵Ak和和Ak+1之间将矩阵链断开，之间将矩阵链断开，1kn，则其相应

9、完全加括号方式为，则其相应完全加括号方式为(A1A2Ak)(Ak+1Ak+2An)计算量：计算量：A1:k的计算量加上的计算量加上Ak+1:n的计算量，再的计算量，再加上加上A1:k和和Ak+1:n相乘的计算量相乘的计算量13特征：计算特征：计算A1:n的最优次序所包含的计算矩阵子的最优次序所包含的计算矩阵子链链 A1:k和和Ak+1:n的次序也是最优的。的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其矩阵连乘计算次序问题的最优解包含着其子问题子问题的的最优解。最优解。这种性质称为这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算问题的最优子结构性质是该问题可用动态规

10、划算法求解的显著特征。法求解的显著特征。14设计算设计算Ai:j，1ijn，所需要的最少数乘次数，所需要的最少数乘次数mi,j，则，则原问题的最优值为原问题的最优值为m1,n 当当i=j时，时，Ai:j=Ai，因此，因此，mi,i=0，i=1,2,n当当ij 时，时，这里这里Ai的维数是的维数是Pi-1Pi可以递归地定义可以递归地定义mi,j为：为：jkipppjkmkimjim1, 1,jipppjkmkimjijimjki, 1,min0,1jki 的位置只有的位置只有 种种可能可能kij 15mij给出了最优值，最优断开位置为给出了最优值，最优断开位置为k：若将对应于若将对应于mi, j

11、的断开位置的断开位置k记为记为si, j, 在计算在计算出最优值出最优值mi, j后后,可递归的由可递归的由si, j构造出相应的构造出相应的最优解最优解.jkipppjkmkimjim1, 1,16)(22nnn对于对于1ijn不同的有序对不同的有序对(i,j)对应于不同的子对应于不同的子问题。因此，不同子问题的个数最多只有问题。因此，不同子问题的个数最多只有在递归计算时，在递归计算时，许多子问题被重复计算多次。这也。这也是该问题可用动态规划算法求解的又一显著特征。是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底用动态规划算法解此问题，可依据其递归式以

12、自底向上的方式进行计算。向上的方式进行计算。在计算过程中，保存已解决的子问题答案。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，在后面需要时只要简单查一下，每个子问题只计算一次，在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。从而避免大量的重复计算，最终得到多项式时间的算法。17void 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+)/变量变量i的跨度的跨度 for (int i = 1; i

13、= 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 mij) mij = t; sij = k; r18A1A2A3A4A5A630 3535 1515 55 1010 2020 25113752010350437555427125205351000262554 3213000201535250005322min52541531521pppmmpppmmpppmmmr19依据其递归式以自底向

14、上的方式进行计算。依据其递归式以自底向上的方式进行计算。在计算过程中在计算过程中 , , 保存已解决的子问题答案。保存已解决的子问题答案。每个子问题只计算一次每个子问题只计算一次 , , 而在后面需要时只要简单查而在后面需要时只要简单查一下一下 , ,从而避免大量的重复计算从而避免大量的重复计算, , 最终得到多项式时间最终得到多项式时间的算法。的算法。r20void 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

15、= 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 mij) mij = t; sij = k; 算法复杂度分析：算法复杂度分析：n 算法算法matrixChain的的主要计算量取决于算主要计算量取决于算法中对法中对r，i和和k的的3重重循环。循环。n 循环体内的计算量为循环体内的计算量为O(1)。n 3重循环的总次数为重循环的总次数为O(n3)。因此算法的计算因此算法的计算时

16、间时间上界为上界为O(nO(n3 3) )。1.1. 算法所占用的算法所占用的空间空间显显然为然为O(nO(n2 2) )。21sij已经存储了构造最优解所需要的足够的信息。已经存储了构造最优解所需要的足够的信息。每个部分的最优加括号方式可以根据数组每个部分的最优加括号方式可以根据数组s的相应元素得的相应元素得出。照此递推下去，最终可以确定出。照此递推下去，最终可以确定A1:n的最优完全加括的最优完全加括号方式，即构造出问题的一个最优解。号方式，即构造出问题的一个最优解。 void TraceBack(int i,int j) if(i=j) return; TraceBack(i,sij);

17、 TraceBack(sij+1,j); printf(Multiply A%d,%d and A%d,%dn,i,sij,sij+1,j); 22一、最优子结构一、最优子结构矩阵连乘计算次序问题的最优解包含着其子问题的最优解。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为这种性质称为最优子结构性质最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更然后再设法说

18、明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。好的解，从而导致矛盾。 23一、最优子结构一、最优子结构利用问题的最优子结构性质，以自底向上的方式递归地从子利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的问题的最优解逐步构造出整个问题的最优解。最优解。最优子结构是问题能用动态规划算法求解的最优子结构是问题能用动态规划算法求解的前提前提。同一个问题可以有多种同一个问题可以有多种方式刻划它的最优子结构，有些表示方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）方法的求解速度更快（空间占用小，问题的维度低）24r二、重叠子问

19、题二、重叠子问题递归算法求解问题时，每次产生的子问题并不总是新问递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。题，有些子问题被反复计算多次。这种性质称为这种性质称为子问题的子问题的重叠性质重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间个表格中，当再次需要解此子问题时，只是简单地用常数时间查查看一下看一下结果。结果。 通常不同的子问题个数随问题的大小呈通常不同的子问题个数随问题的大小呈多项式多项式增长。因此用动态增长。因此用动态规划算法

20、只需要多项式时间，从而获得较高的解题效率。规划算法只需要多项式时间，从而获得较高的解题效率。 jipppjkmkimjijimjki, 1,min0,1jki25矩阵连乘积的递归式计算矩阵连乘积的递归式计算:int RecurChain(int i，int j) if (i = j) return 0; int u = RecurChain(i，i) + RecurChain(i+1，j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = RecurChain(i，k) + RecurChain(k+1，j) + pi-1*pk

21、*pj; if (t 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*pj; if (t u) u = t; sij = k; mij = u; return u;三、备忘录方法三、备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相同，备忘录方法的控制结构与直接递归

22、方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了区别在于备忘录方法为每个解过的子问题建立了备忘录备忘录以以备需要时查看，避免了相同子问题的重复求解。备需要时查看，避免了相同子问题的重复求解。27若给定序列若给定序列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，

23、7。给定给定2个序列个序列X和和Y，当另一序列，当另一序列Z既是既是X的子序列又是的子序列又是Y的的子序列时，称子序列时，称Z是序列是序列X和和Y的的公共子序列公共子序列。给定给定2个序列个序列X=x1,x2,xm和和Y=y1,y2,yn，找出，找出X和和Y的最长公共子序列。的最长公共子序列。 282个序列的最长公共子序列包含了这个序列的最长公共子序列包含了这2个序列的个序列的前缀的最长公共子序列前缀的最长公共子序列。最长公共子序列问题具有最长公共子序列问题具有最优子结构性质最优子结构性质。 设序列设序列X=x1,x2,xm和和Y=y1,y2,yn的最长公共子序的最长公共子序列为列为Z=z1,

24、z2,zk ，则，则q 若若xm=yn，则，则zk=xm=yn，且，且zk-1是是xm-1和和yn-1的最长公共的最长公共子序列。子序列。q 若若xmyn且且zkxm，则，则Z是是xm-1和和Y的最长公共子序列。的最长公共子序列。q 若若xmyn且且zkyn，则，则Z是是X和和yn-1的最长公共子序列。的最长公共子序列。29jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110由最长公共子序列问题的最优子结构性质建立子问题最优由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。值的递归关系。用用cij记录序列和的最长公共子序列的长度。记录

25、序列和的最长公共子序列的长度。 Xi=x1,x2,xi；Yj=y1,y2,yj。当当i=0或或j=0时，空序列是时，空序列是Xi和和Yj的最长公共子序列。的最长公共子序列。故此时故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：其它情况下，由最优子结构性质可建立递归关系如下：30void 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+

26、) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 由于在所考虑的子问题空间中，总共有由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，个不同的子问题，用动态规划算法自底向上地计算最优值能提高算法的效率。用动态规划算法自底向上地计算最优值能提高算法的效率。01234.n000000 010203040 m 0ij31void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0;

27、 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; 0123456yiBDCABA0 xi00000001A00001112B01111223C01122224B01122335D01222336A01223347B0122344ij32由数组由数组b构造最长公共子序列构造最长公共子序列void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if

28、 (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);0123456yiBDCABA0 xi00000001A00001112B01111223C01122224B01122335D01222336A01223347B0122344ij0123456yiBDCABA0 xi1A 2B 3C 4B 5D 6A 7B ij33在算法在算法lcsLength和和lcs中，可进一步将数组中，可进一步将数组b省去。省去。数组元素数组元素cij的值仅由的值仅由ci-1j-1，ci-1

29、j和和cij-1这这3个数组元素的值所确定。个数组元素的值所确定。对于给定的数组元素对于给定的数组元素cij，可以不借助于数组，可以不借助于数组b而仅借而仅借助于助于c本身在本身在O(1)时间内确定时间内确定cij的值是由的值是由ci-1j-1，ci-1j和和cij-1中中哪一个值哪一个值所确定的。所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。求可大大减少。在计算在计算cij时，只用到数组时，只用到数组c的第的第i行和第行和第i-1行。行。因此，用因此，用2行的数组空间就可以计算出最长公共子序列行的数组空间就可以计算

30、出最长公共子序列的长度。的长度。进一步的分析还可将空间需求减至进一步的分析还可将空间需求减至O(min(m,n)。34最大子段和最大子段和问题描述：问题描述：给定由给定由n个整数（包含负整数）组成的序列个整数（包含负整数）组成的序列a1,a2,.,an，求该序列子段和的最大值。当所有整数均为负值时定义求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为其最大子段和为0。依此定义，所求的最优值为：依此定义，所求的最优值为： 例如，当例如，当(a1,a2, a3, a4, a5,a6)=( -2,11,-4,13,-5,-2 )时，最时，最大子段和为：大子段和为： jikknjia1ma

31、x, 0max201341142kka351. 一个简单算法一个简单算法int MaxSum(int n, int *a, int &besti, int &bestj)int sum=0;for(i=1;i=n;i+)for(j=i;j=n;j+)int thissum=0;for(k=i;ksum)sum=thissum;besti=i;Bestj=j;return sum;算法有算法有3重循环，复杂性为重循环，复杂性为O(n3)。361. 一个简单算法一个简单算法一个简单算法：一个简单算法：int MaxSum(int n, int *a, int &besti,

32、 int &bestj)int sum=0;for(i=1;i=n;i+)for(j=i;j=n;j+)int thissum=0;for(k=i;ksum)sum=thissum;besti=i;Bestj=j;return sum;算法有算法有3重循环，复杂性为重循环，复杂性为O(n3)。由于有：由于有：算法可作如下改进：算法可作如下改进：int MaxSum(int n, int *a, int &besti, int &bestj)int sum=0;for(i=1;i=n;i+)int thissum=0;for(j=i;jsum)sum=thissum;be

33、sti=i;bestj=j;改进后的算法复杂性为改进后的算法复杂性为O(n2) 。1jikkjjikkaaa37inkkninnikknijikkasasnjnniaC121222211maxmax12,21 ,.2. 分治方法求解分治方法求解从问题的解的结构可以看出，它适合于用分治策略求解：从问题的解的结构可以看出，它适合于用分治策略求解：如果将所给的序列如果将所给的序列a1:n分为长度相等的两段分为长度相等的两段a1:n/1和和an/2+1:n，分别求出这两段的最大子段和，则，分别求出这两段的最大子段和，则a1:n的最大子的最大子段和有三种情形：段和有三种情形：a1:n的最大子段和与的最大

34、子段和与a1:n/2的最大子段和相同；的最大子段和相同；a1:n的最大子段和与的最大子段和与an/2+1:n的最大子段和相同；的最大子段和相同；A. a1:n的最大子段和为下面的形式。的最大子段和为下面的形式。1nn/2ijs1s2382. 分治方法求解分治方法求解int MaxSubSum(int a , int left, int right) int sum=0; if (left=right)sum=aleft0?aleft:0; elseint center=(left+right)/2; int leftsum=MaxSubSum(a,left,center); int right

35、sum=MaxSubSum(a,center+1,right); int s1=0;leftsum=0; for (int i=center;i=left;i-) leftsum+=ai; if (leftsums1) s1=leftsum; int s2=0;rightsum=0; for (int i=center+1;is2) s2=rightsum; sum=s1+s2; if (sumleftsum) sum=leftsum; if (sum0时时bj=bj-1+aj，否则，否则bj=aj。则计算则计算bj的动态规划递归式的动态规划递归式bj=maxbj-1+aj，aj，1jn。jn

36、jjikkjinjjkknjijikkjijbaanjab111111maxmaxmaxmax1max为，则所求的最大子段和，若记123456ai-211-413-5-2b(初值初值=0)-2117201513sum01111202020403. 动态规划方法求解动态规划方法求解据此，可设计出求最大子段和的动态规划算法如下：据此，可设计出求最大子段和的动态规划算法如下：int MaxSum(int n, int a)int sum=0; /sum是是bj(1jn)的最大值的最大值int b=0;for (int i=1;i0) b+=ai; else b=ai;if (bsum) sum=b;

37、return sum;显然该算法的计算时间为显然该算法的计算时间为O(n)。123456ai-211-413-5-2b(初值初值=0)-2117201513sum01111202020414. 算法的推广算法的推广最大矩阵和问题，最大矩阵和问题，略略最大最大m子段和问题，子段和问题，略略42n个作业个作业1，2，n要在由要在由2台机器台机器M1和和M2组成的流水线上组成的流水线上完成加工。完成加工。每个作业加工的顺序都是先在每个作业加工的顺序都是先在M1上加工，然后在上加工，然后在M2上加工。上加工。M1和和M2加工加工作业作业i所需的时间分别为所需的时间分别为ai和和bi。流水作业调度问题要

38、求确定这流水作业调度问题要求确定这n个作业的最优加工顺序，使得从个作业的最优加工顺序，使得从第一个作业在机器第一个作业在机器M1上开始加工，到最后一个作业在机器上开始加工，到最后一个作业在机器M2上上加工完成所需的加工完成所需的时间最少时间最少。123456A2571052B384113443直观上，一个最优调度应使机器直观上，一个最优调度应使机器M1没有空闲时间，没有空闲时间，且机器且机器M2的空闲时间最少。在一般情况下，机器的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压上会有机器空闲和作业积压2种情况。种情况。设全部作业的集合为设全部作业的集合为N=1，2，n。S N是是N

39、的的作业子集作业子集。在一般情况下，机器在一般情况下，机器M M1 1开始加工开始加工S S中作业时，机器中作业时，机器M M2 2还在还在加工其它作业，要等时间加工其它作业，要等时间t t后才可利用。后才可利用。将这种情况下完成将这种情况下完成S S中作业所需的最短时间记为中作业所需的最短时间记为T(S,t)T(S,t)。流水作业调度问题的最优值为流水作业调度问题的最优值为T(N,0)。44设设是所给是所给n个流水作业的一个最优调度个流水作业的一个最优调度，它所需的加工时，它所需的加工时间为间为 a(1) +T。其中其中TT是在机器是在机器M M2 2的等待时间为的等待时间为b b(1)(1

40、)时，安排作业时，安排作业(2)(2)， (n)(n)所需的时间。所需的时间。记记S=N-(1)，则有，则有T=T(S, b(1) )。 (1) (2) (3) (n)Aa (1)a (2)a (3)a (n)Bb (1)b (2)b (3)b (n)45ABa (1)b (1) (1)S=N-(1)T=T(S, b(1) )T46由流水作业调度问题的最优子结构性质可知，由流水作业调度问题的最优子结构性质可知，推广到一般情形下推广到一般情形下,有有:),(min)0 ,(1iinibiNTaNT)0 ,max,(min),(iiiSiatbiSTatST0 ,maxiiatbtM1M247推广

41、到一般情形下推广到一般情形下,有有:)0 ,max,(min),(iiiSiatbiSTatST48,max0 ,max,0 ,maxmax0 ,0 ,maxmaxiijiijijijijijijijijjiijijabaataabbbaatabbbaatabbaatbbt对递归式的深入分析表明，算法可进一步得到简化。对递归式的深入分析表明，算法可进一步得到简化。设设 是作业集是作业集S在机器在机器M2的等待时间为的等待时间为t时的任一最优调度。时的任一最优调度。若若 (1)=i, (2)=j。则由动态规划递归式可得。则由动态规划递归式可得:T(S,t)=ai+T(S-i,bi+maxt-ai

42、,0)=ai+aj+T(S-i,j,tij)49,max0 ,max,0 ,maxmax0 ,0 ,maxmaxiijiijijijijijijijijjiijijabaataabbbaatabbbaatabbaatbbt对递归式的深入分析表明，算法可进一步得到简化。对递归式的深入分析表明，算法可进一步得到简化。设设 是作业集是作业集S在机器在机器M2的等待时间为的等待时间为t时的任一最优调度。时的任一最优调度。若若 (1)=i, (2)=j。则由动态规划递归式可得。则由动态规划递归式可得:T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)50对递

43、归式的深入分析表明，算法可进一步得到简化。对递归式的深入分析表明，算法可进一步得到简化。设设 是作业集是作业集S在机器在机器M2的等待时间为的等待时间为t时的任一最优调度。时的任一最优调度。若若 (1)=i, (2)=j。则由动态规划递归式可得。则由动态规划递归式可得:T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)如果作业i和j满足minbi,ajminbj,ai，则称作业i和j满足JohnsonJohnson不等式不等式。51,maxjjjiijijjiabaataabbt,maxiijiijijijabaataabbt,max,max,ma

44、x,max,max,max,max,maxjjjiiijijjjiiijiijjijijiijjiabaatabaatabaaabaaabaaabaaabab交换作业交换作业i和作业和作业j的加工顺序，得到作业集的加工顺序，得到作业集S的另一调度，的另一调度，它所需的加工时间为它所需的加工时间为T(S,t)=ai+aj+T(S-i,j,tji)其中，其中，当作业当作业i和和j满足满足Johnson不等式时，有不等式时，有如果作业i和j满足minbi,ajminbj,ai，则称作业i和j满足JohnsonJohnson不等式不等式。52由此可见当作业由此可见当作业i和作业和作业j不满足不满足Jo

45、hnson不等式时，交换不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度问题，必存在最优调度 ，使得作业，使得作业 (i)和和 (i+1)满足满足Johnson不等式。进一步还可以证明，调度满足不等式。进一步还可以证明，调度满足Johnson法则当且仅当对任意法则当且仅当对任意ij有有由此可知，由此可知，所有满足所有满足Johnson法则的调度均为最优调度。法则的调度均为最优调度。 ,maxjjjiijijjiabaataabbt,maxiijiijijijabaataabbt,max,maxjjjiiiji

46、abaatabaat,min,min)()()()(ijjiabab53如果作业如果作业i和和j满足满足minbi,ajminbj,ai，则称作业则称作业i和和j满足满足Johnson不等式。不等式。若作业若作业i和作业和作业j不满足不满足Johnson不等式，则交换它们的不等式，则交换它们的加工顺序后，满足加工顺序后，满足Johnson不等式。不等式。对于流水作业调度问题，必存在最优调度对于流水作业调度问题，必存在最优调度 ，使得作业，使得作业 (i)和和 (i+1)满足满足Johnson不等式。进一步还可以证明，不等式。进一步还可以证明，调度满足调度满足Johnson法则当且仅当对任意法则

47、当且仅当对任意ij有有:所有满足所有满足Johnson法则的调度均为最优调度。法则的调度均为最优调度。 ,min,min)()()()(ijjiabab54流水作业调度问题的流水作业调度问题的Johnson算法算法(1) 令令(2) 将将N1中作业依中作业依ai的非减序排序；的非减序排序； 将将N2中作业依中作业依bi的非增序排序；的非增序排序；(3) N1中作业接中作业接N2中作业构成满足中作业构成满足Johnson法则的最优调度。法则的最优调度。;|,|21iiiibaiNbaiNN1中作业依中作业依ai的非减序排序的非减序排序N2中作业依中作业依bi的非增序排序的非增序排序123456A

48、2571052B384113455算法复杂度分析：算法复杂度分析：算法的主要计算时间花在对作业集的排序。算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为因此，在最坏情况下算法所需的计算时间为O(nlogn)。所需的空间为所需的空间为O(n)。123456A2571052B384113456int FlowShop(int n, int *a, int *b, int *c) class Jobtype public: int operator= (Jobtype a) const /排序重载函数排序重载函数 return key=a.key; int key; in

49、t index; bool job; ; Jobtype *d=new Jobtypen; for(int i=0; ibi?bi:ai; di.job = ai=bi; di.index = i; sort(d,n);012345A2571052B3841134key2541032jobTTFTFTindex01234557int j=0, k=n-1; for(int i=0; in; i+) if(di.job) cj+ = di.index; else ck- - = di.index; j = ac0; k = j+bc0; for(int i=1; in; i+) j += aci;k = jk ? k+bci : j+bci; delete d; return k; /最优加工时间最优加工时间 012345A2571052B3841134排序之后排序之后:key2234510jobTTFFTTindex