算法设计与分析(霍红卫)-第3章-动态规划教学讲义课件

算法设计与分析(霍红卫)_第3章动态规划3.1用表代替递归图3-1是利用递归算法计算斐波那契数F7时的递归结构，由此可见，重复计算的子问题数导致了指数级的复杂度。图3-1表明，为了计算F7，递归算法进行了多次重叠子问题的递归调用,而这些重叠子问题导致了指数级的算法。在这个例子中，在第二次调用中忽略了前次调用所做的计算。计算F6=8的递归调用如图3-2所示。树中每一个节点代表所计算的斐波那契数。由于多重递归，导致了大量重复计算。图3-1计算斐波那契数算法的递归结构（n=7）利用自底向上的动态规划设计策略，我们可以将计算斐波那契数的递归算法(例2-1)变成以下的C语言函数：intF(intn){intf,f1,f2,k,t;

if(n<2)returnn;

else{f1=f2=1;

for(k=2;k<n;k++){f=f1+f2;f2=f1;f1=f;}}returnf;}自顶向下的动态规划(topdowndynamicprogramming)方法甚至是更简单的一种技术，它执行递归函数的运行时间与自底向上的动态规划的运行时间相同，有时更少。我们跟踪递归程序，存储它计算的每一个值，并检查计算的值，以避免重复计算。这种自顶向下的技术也称为备忘录(memoization)方法。利用自顶向下的动态规划设计策略，我们可以将计算斐波那契数的递归算法(例2-1)变成以下的C语言函数：intfibarr［1000］={0};intMEMOIZED-F(intn){intt;

if(fibarr［n］!=0returnfibarr［n］;

if(n==0)t=0;

if(n==1)t=1;

if(n>1)t=MEMOIZED-F(n-1)+MEMOIZED-F(n-2);

returnfibarr［n］=t;}图3-3计算斐波那契数的自顶向下的动态规划示例(n=7)算法将数组fibarr初始化为0，算法执行完成后，数组fibarr中的值如下所示：比较图3-1与图3-3可得，自顶向下的动态规划方法大大减少了递归调用的次数，使得算法的复杂度从指数级降到线性级。这种方法将已经计算过的子问题存储在数组fibarr中，可避免重复计算。3.20-1背包问题对于更复杂的例子，考虑0-1背包问题(knapsackproblem)。某商店有n个物品，第i个物品价值为vi，重量(或称权值)为wi，其中vi和wi为非负数。背包的容量为W，W为一非负数。目标是如何选择装入背包的物品，使装入背包的物品总价值最大。可将这个问题形式描述如下：(3.1)约束条件为(3.2)图3-40-1背包问题示例(1)刻画0-1背包问题最优解的结构。我们可以将背包问题的求解过程看做是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包。如果问题的一个最优解x1,x2,…,xn包含物品n，即xn=1，那么其余决策x1,x2,…,xn-1一定构成子问题1,2,…,n-1在容量为W-wn时的最优解。我们可以利用“切割—粘贴”方法证明：如果存在子问题1,2,…,n-1在容量为W-wn时的更大价值的解x1′,x2′,…,xn-1′

，我们可以构造问题的一个新解x1′,x2′,…,xn-1′，xn。这个解比x1,x2,…,xn的总价值更大，这与x1,x2,…,xn是问题最优解相矛盾。如果这个最优解不包含物品n，即xn=0，那么这个最优解一定包含子问题1,2,…,n-1在容量为W时的最优解。证明过程类似上述情形。(2)递归定义最优解的值。根据子问题的最优解递归地定义问题最优解的开销。设c［i,w］表示背包容量为w时，i个物品导致的最优解的总价值。显然，问题的最优价值为c［n,W］。由(1)中分析可得，c［i,w］递归定义如下：i=0或w=0wi>w

i>0且wi≤w

(3.3)(3)计算背包问题最优解的值。基于上述计算c［i,w］的递归方程，我们很容易写一个递归算法RECURKNAP，计算背包容量为W时n个物品的最优价值。然而，这个算法为指数时间复杂度O(2n)，并不比穷举法好。RECUR-KNAP(w)1max←02for(i←1to

n)3doif(space←(w-wi)≥0)4thenif((t←RECUR-KNAP(space)+vi)>max

5thenmax←t

6return

max这个递归过程初始调用为RECUR-KNAP(W)。我们不是直接计算递归方程的解，而是利用一个表格，以自底向上的方式计算最优价值。过程KNAPSACK-DP以物品权值〈w1，w2,…,wn〉，物品价值〈v1,v2，…,vn〉，物品个数n，背包容量W作为输入，并将c［i,w］的值存储在辅助表c［0..n,0..W］中，以行为主序从左到右计算表c中的元素。同时维持辅助表s［1..n,1..W］，以简化最优解的构造。为简单起见，我们只将物品个数及背包容量在参数表中列出。KNAPSACK-DP(n,W)1for

w←0to

W

2do

c［0,w］←03fori←1ton4do

c［i,0］←05for

w←1to

W

6doif

w［i］≤w

7thenif

v［i］+c［i-1,w-w［i］］>c［i-1,w］8then

c［i,w］←v［i］+c［i-1,w-w［i］］9else

c［i,w］←c［i-1,w］10else

c［i,w］←c［i-1,w］由算法KNAPSACK-DP的嵌套循环结构可得，算法的运行时间为O(nW)。对于(w1,w2,w3,w4,w5)=(3,4,7,8,9)，(v1,v2,v3,v4,v5)=(4,5,10,11,13)，W=17。图3-5给出了由算法KNAPSACK-DP计算表c［i,w］的过程。图3-5算法KNAPSACK-DP示例(4)根据计算的结果，构造问题最优解。KNAPSACK-DP返回的c可用于快速构造背包问题的一个最优解。如果c［i,w］=c［i-1,w］，表明xi=0，然后考察c［i-1，w］；否则xi=1，接着考察c［i-1，w-wi］。这个过程初始调用为OUTPUT-SACK(c,W)。OUTPUTSACK(c,w)1for

i←n

downto22doif

c［i,w］=c［i-1,w］3then

xi←04 else

xi←15 w←w-vi

6x1←c［1,w］?1:07return

x

3.3矩阵链乘问题通过上述的两个实例表明，动态规划算法的研制可由4步组成：(1)刻画最优解的结构。(2)递归定义最优解的值。(3)以自底向上(或自顶向下)的方式计算最优解的值。(4)根据计算的结果，构造问题最优解。我们给矩阵加上括号的方式会对矩阵的计算开销产生巨大影响。首先考虑两个矩阵的乘积。标准计算两个矩阵乘积的算法MATRIX-MULTIPLY描述如下，其中rows和columns分别表示矩阵的行数和列数。MATRIXMULTIPLY(A,B)1ifcolumns［A］≠rows［B］2thenerror“incompatibledomensions”3elsefor

i←1torows［A］4doforj←1to-columns［B］5doC［i,j］←06fork←1tocolumns［A］7doC［i,j］←C［i,j］+A［i,k］·B［k,j］8returnC如果矩阵A的列数等于矩阵B的行数，则两个矩阵A和B是可相乘的,即如果矩阵A是p×q的矩阵，B是q×r的矩阵，那么，它们乘积的结果矩阵C是p×r。我们首先给出一个例子，来说明括号加在矩阵不同位置对计算量所产生的影响。考虑三个矩阵〈A1，A2，A3〉链乘的情况。这三个矩阵的维数分别为10×100，100×5和5×50。如果我们按照((A1A2)A3)方式计算，则计算A1A2需要10×100×5=5000次乘法,计算其结果与A3的乘积需要10×5×50=2500次乘法,共需7500次数乘。如果我们按照(A1(A2A3))方式计算，则计算A2A3需要100×5×50=25000次乘法,计算A1与其结果的乘积需要10×100×50=50000次乘法，共需75000次数乘。矩阵链乘问题阐述如下：给定n个矩阵〈A1，A2，…，An〉，矩阵Ai的维数为pi-1×pi，i=1,2,…,n，如何给矩阵链乘A1×A2×…×An完全加上括号，使得矩阵链乘中数乘次数最少。值得注意的是，在矩阵链乘问题中，我们实际上并不做矩阵相乘。我们的目标是决定具有最少乘法次数的矩阵相乘的次序。一般而言，决定这个最优次序的开销可以由以后计算节省的开销补偿。在用动态规划求解矩阵链乘问题之前，我们先讨论穷举法求解该问题的算法。假设P(n)表示n个矩阵序列的加括号的数目。当n=1时，只有一个矩阵，完全加括号的方式只有一种。当n≥2时，完全加括号矩阵乘积等于两个完全加括号的子矩阵的乘积。而两个子矩阵间分割的位置可在第k个矩阵以及第k+1个矩阵之间，其中k=1,2,…,n-1。因此，可得递归方程n=1n≥2这个递归方程的解为Catalan数由此可见，矩阵链乘完全加上括号的个数为n的指数次幂，因此，穷举法不是一个有效的方法。以下研究如何用动态规划解该问题。研制一个动态规划算法的步骤如下：(1)刻画矩阵链乘问题的最优结构。动态规划范型的第一步是刻画问题的最优结构，通过子问题的最优解构造原问题的最优解。为简便起见，我们用Ai..j表示矩阵乘积AiAi+1…Aj的结果，其中i≤j。如果问题是非平凡的，即i<j，那么乘积AiAi+1…Aj一定在Ak与Ak+1之间被分裂，i≤k<j，即对于某些k值，首先要计算Aj..k与Ak+1..j，然后计算它们的乘积，得到最终结果Ai..j。问题AiAi+1…Aj被完全加上括号的开销等于计算矩阵Ai..k与计算矩阵Ak+1..j的开销，再加上它们结果相乘的开销。问题的最优子结构刻画如下：假定问题AiAi+1…Aj被完全加上括号的最优方式是在Ak与Ak+1处分裂，那么分裂之后，最优解AiAi+1…Aj中的子链AiAi+1…Ak一定是问题AiAi+1…Ak的最优加括号方式。我们用反证法证明这一点。如果问题AiAi+1…Ak存在更小开销的加括号方式，我们可以用这个更小开销的加括号方式代替问题AiAi+1…Aj中的子问题AiAi+1…Ak的加括号方式,这样就产生问题AiAi+1…Aj的另一种具有更小开销的加括号方式,这与问题AiAi+1…Aj具有最优解(具有最小开销)矛盾。可用类似方法证明，最优解AiAi+1…Aj中的子链Ak+1Ak+2…Aj一定也是问题Ak+1Ak+2…Aj的最优加括号方式。现在，我们利用最优子结构构造问题的最优解。正如已经表明的那样，非平凡矩阵链乘问题都会对矩阵进行分割，而分割的位置是未定的，需要我们确定，使得问题的最优解一定包含子问题的最优解，我们称这个性质为问题的最优子结构(optimalsubstructure)。由此，我们可以建立矩阵链乘问题的递归解。(2)递归定义矩阵链乘问题最优解的值。根据子问题的最优解递归地定义问题最优解的开销。设m［i,j］表示计算Ai..j所需的最少乘法次数，对于原问题，计算A1..n的最少开销则为m［1,n］。m［i,j］递归定义如下:如果i=j，则为平凡问题。子问题中只有一个矩阵，即Ai..i=Ai，不需数乘。因此，对于i=1，2，…，n，m［i,i］=0。如果i<j，可以利用第一步中得出的最优解结构，构造问题的最优解。假设最优加括号方式将乘积AiAi+1…Aj分裂为AiAi+1…Ak和Ak+1Ak+2…Aj，其中i≤k<j，则m［i,j］等于计算子乘积Ai..k和Ak+1..j的最小开销，再加上将这两个结果矩阵相乘的开销。由前定义，矩阵Ai的维数为pi-1×pi，因此计算矩阵乘积Ai..k×Ak+1..j需要pi-1pkpj次数乘。所以，m［i,j］=m［i,k］+m［k+1,j］+pi-1pkpj因为k有j-i种选择，即k=i，i+1，…，j-1。最优加括号方式一定利用某个k值，我们只需逐个检查，找出最优的。因此，矩阵乘积AiAi+1…Aj加括号的最小开销的递归定义变为i=j

i<j

(3.4)m［i,j］给出了子问题最优解的值。为了记录构造最优解的过程，设s［i,j］表示将AiAi+1…Aj分裂产生最优解时k的位置，即s［i,j］等于值k，满足m［i,j］=m［i,k］+m［k+1,j］+pi-1pkpj。(3)计算矩阵链乘最优解的值。为了正确实现自底向上方法，我们必须决定m表中的哪个元素用于计算m［i,j］。式(3.4)表明，计算j-i+1个矩阵乘积的开销m［i,j］只取决于计算矩阵Ai..k与Ak+1..j的开销，其中k=i，k+1，…，j-1。因此，我们可以按照矩阵链长度增加的方式填充表格。1n←length［p］-12for

i←1to

n

3do

m［i,i］←04for

l←2to

n

5dofor

i←1to

n-l+16do

j←i+l-17m［i,j］←∞8for

k←i

toj-19 do

q←m［i,k］+m［k+1,j］+pi-1pkpj

10 Ifq<m［i,j］11 then

m［i,j］←q

12 s［i,j］←k

13return

mands

首先，对于i=1，2，…，n，算法MATRIX-CHAIN-ORDER计算出m［i,i］=0，即链长度为1的最小开销。然后，在第4~12行循环的第一次执行中，利用递归方程(3.3)计算m［i,i+1］，i=1，2，…，n-1，即链长度为2的最小开销。第二次执行中，计算m［i,i+2］，i=1，2，…，n-2，即链长度为3的最小开销，依次类推。在每一步计算m［i,j］时，只需要表m［i,k］和m［k+1,j］中已计算出的值。计算m［i,j］的次序如图3-6所示。图3-6m［i,j］的计算次序注意,矩阵Ai的维数为pi-1×pi。给定n=6，p=〈p0,p1,…,pn〉=〈30,35,15,5,10,20,25〉。首先设m［i,i］=0，然后依次计算j-i=1，j-i=2，…，j-i=n-1时m［i,j］的值。我们按照如下步骤计算问题的最优解的值：(a)m［i,i］=0，i=1，2，…，6,如图3-7(a)所示。(b)当j-i=1时，m［1,2］，m［2,3］，m［3,4］，m［4,5］和m［5,6］的计算结果及其对应的s表如图3-7(b)所示。(c)当j-i=2时，m［1,3］，m［2,4］，m［3,5］和m［4,6］的计算结果及其对应的s表如图3-7(c)所示。(d)当j-i=3时，m［1,4］，m［2,5］和m［3,6］的计算结果及其对应的s表如图3-7(d)所示。(e)当j-i=4时，m［1,5］和m［2,6］的计算结果及其对应的s表如图3-7(e)所示。(f)当j-i=5时，m［1,6］的计算结果及其对应的s表如图3-7(f)所示。在m表中，利用表的主对角线和下三角部分。而在s表中，只利用表的下三角部分。6个矩阵相乘的最少数乘次数为m［1,6］=15125。在计算m［2,4］时，要用到已计算出的m［2,2］，m［2,3］，m［3,4］和m［4,4］：且s［2,4］=k=3由算法MATRIX-CHAIN-ORDER的嵌套循环结构可得，算法的复杂度为O(n3)。算法第2~3行需要O(n)时间单位，第4~12行的三层嵌套循环需要O(n3)时间单位，因为每个循环下标l，i和k至多取n-1个值。算法存储m表和s表需要的空间为Θ(n2)。因此，自底向上的动态规划要比穷举法的动态规划算法有效得多。图3-7算法MATRIX-CHAIN-ORDER计算m［i,j］和s［i,j］的值图3-7算法MATRIX-CHAIN-ORDER计算m［i,j］和s［i,j］的值图3-7算法MATRIX-CHAIN-ORDER计算m［i,j］和s［i,j］的值(4)构造矩阵链乘问题的最优解。尽管算法给出了计算矩阵乘积的最优数乘次数(最优解的值)，但我们仍然不知道这些矩阵相乘的次序。从存储在s表中的信息不难构造问题的一个最优解。s［i,j］中的每个元素记录着AiAi+1…Aj最优分裂的位置，即k值。由于s［1,n］是A1..n的最优分裂位置，通过这个位置s［1,n］，我们考虑这两个子问题A1..s［1,n］和As［1,n］+1..n，而s［1,s［1,n］］记录问题A1..s［1,n］最优分裂的位置，s［s［1,n］+1,n］记录问题As［1,n］+1..n最优分裂的位置，因此，以下过程OUTPUT-OPTIMAL-PARENS输出〈Ai，Ai+1，…，Aj〉的最优加括号方法，其中s表作为已知条件输入，并给定下标i和j。初始时，调用OUTPUT-OPTIMAL-PARENS(s,1,n)。OUTPUT-OPTIMAL-PARENS(s,i,j)1if

i=j

2thenoutput“A”i

3elseoutput“(”4OUTPUT-OPTIMAL-PARENS(s,i,s［i,j］)OUTPUT-OPTIMALPARENS(s,s［i,j］+1,j)OUTPUT“)”

上述例子调用OUTPUT-OPTIMAL-PARENS-(s,1,6)之后，产生输出结果((A1(A2A3))((A4A5)A6))。3.4动态规划的基本元素

1.最优子结构

动态规划应用于组合优化问题的第一个特征是问题自身具有最优子结构。在前面所讨论的问题中，如果问题的最优解包含子问题的最优解，则问题展示了最优子结构。只要问题展示最优子结构，就为应用动态规划提供了可能性。在动态规划中，我们通过子问题的最优解建立问题的最优解。因此，我们必须仔细考虑以保证子问题的范围包括在最优解中。我们详细讨论0-1背包问题、矩阵链乘问题的最优子结构。在3.2节中，i个物品在背包容量为w时的最优解，一定包括前i-1个物品的最优解。在3.3节中，AiAi+1…Aj在Ak与Ak+1处最优分裂，所产生的子问题AiAi+1…Ak和Ak+1Ak+2…Aj，一定分别是这两个子问题的最优加括号方式。因此，在寻找问题的最优子结构时，问题具有以下公共结构：(1)问题的解由一系列决策组成。在背包问题中，是选择一个物品是否放在背包中；在矩阵链乘问题中，是选择分裂矩阵的一个下标。(2)对于给定的问题，假定已知一个选择导致最优解。你不需关心如何做出这个选择,只需假定它是已知的。(3)给定这个决策，你来决定哪些子问题最好地刻画子问题的其余空间。(4)证明在问题最优解中所用到的子问题的解，通过使用“切割—粘贴”技术，一定是最优的。这可以通过假定子问题的解不是最优的，然后导出与问题最优解相矛盾的结论。在证明过程中，把不是子问题最优解的解切割出去，粘贴上子问题的最优解，就可以得到比原问题更好的一个解，这与初始时假定原问题具有最优解相矛盾。如果有多个子问题，明的过程十分相似，只需做少量修改。为了刻画子问题的空间，一个好的原则是尽可能保持这个空间简单，然后在需要的时候扩展它。例如，0-1背包问题的子空间就是空间为w时前i个物品的最优装包方式。相反，假定我们试图将矩阵链乘问题的子空间限制到形如A1A2…Aj的形式，如前所述，最优的加括号方式一定将这个乘积在Ak与Ak+1处分裂，1≤k<j。除非我们能够保证k总是等于j-1，否则我们就会得到形如A1A2…Ak和Ak+1Ak+2…Aj的子问题，而后者不是形如A1A2…Aj的子问题。因此，对于矩阵链乘问题，子问题需要在两端都可变化，即在子问题AiAi+1…Aj的两端i和j处都可改变。最优子结构随问题域的变化有两种方式：(1)原问题的最优解中，利用了多少个子问题？(2)决定最优解中使用哪些子问题需做多少次决策？在0-1背包问题中，子问题为i个物品在背包容量为w时的最优解，它一定包括前i-1个物品的最优解。最优解利用两个子问题，每个子问题需要做w(1≤w≤W)次决策，以便决定一个最优解。为了找到子问题c［i,

w］的最优装包方式，我们或者利用子问题c［i-1,w］的最优装包方式，或者利用子问题c［i-1,w-wi］的最优装包方式。不论使用哪一个子问题，都表示要最优解决那个子问题。动态规划算法的运行时间取决于两个因素的乘积：所有子问题的数目以及对于每个子问题需要做出多少次决策。在0-1背包问题中，共有Θ(n)个子问题，每个子问题至多需要做出W次决策，即需要检查W次才能确定子问题的最优解，因此，运行时间为O(nW)。对于矩阵链乘问题，共有Θ(n2)个子问题，每个子问题至多需要做出n-1次决策，因此运行时间为O(n3)。当我们应用动态规划技术时，需要关注遇见的如下问题。当问题的最优子结构不存在时，就不能假设应用最优子结构。考虑如下两个问题，在这两个问题中，给定有向图G=(V,E)和顶点u，v∈V。一个问题是最短路径问题：找一条从u到v包含最少边的简单路径。另一个问题是最长简单路径问题：找一条从u到v包含最多边的简单路径。我们要求路径是简单的，原因是一旦路径中包含回路，则可以多次遍历这个回路，使得这条路径上具有无限多条边。下面来分析这两个问题最优子结构的存在性。最短路径问题展示了最优子结构。假定u≠v，问题是非平凡的。从u到v的任何路径p包含一定包含中间结点，这个中间结点称为w，这里w可能为u或v。因此我们可将这条路径分为两条子路径 。显然，p中边数等于子路径p1与p2中的边数之和。因此，我们可以声称，如果p是一条从u到v的最优路径，即最短路径，那么，p1一定是一条从u到w的最优路径。这是因为，我们可以利用“切割—粘贴”方法证明：如果存在一条从u到w的具有更少边的路径p1′，我们可以将路径p1切除，并将这条更短路径p1′粘贴进来，则得一条具有更少条边的路径 。这与路径p是最优路径相矛盾。类似地，可证明p2一定是一条从w到v的最优路径。因此，求从u到v的最优路径可以通过考察所有中间结点w来完成，即求从u到w的最优路径和从w到v的最优路径，并选择导致最短路径的中间结点w。图3-8给出了一个例子。图3-8有向图示例

2.重叠子问题动态规划应用于组合优化问题的第二个特征是问题自身具有重叠子问题。这些子问题的空间可以足够小，以至于问题的递归算法可以多次解相同子问题,并且不同子问题的个数是问题规模的多项式函数。当递归算法反复重新访问相同问题时，我们说优化问题具有重叠子问题。而用分治方法所解的问题，通常在递归的每一步产生新的子问题。动态规划算法只计算一次子问题，并将它们存储在一张表中，当需要时直接查找这张表。查表时间为常量时间。我们以矩阵链乘问题为例，详细说明重叠子问题的性质。参照图3-9，在解更大一层子问题时，算法MATRIX-CHAIN-ORDER不断检查更小一层子问题的解。例如，在计算m［2,4］、m［1,4］、m［3,5］和m［3,6］时，元素m［3,4］共被调用4次。如果每次m［3,4］都被重新计算，而不是查找，那么运行时间上的增加将会是急剧上升的。为了更清楚地看清这一点，考虑以下效率不太高的计算m［i,j］的递归过程RECURSIVE-MATRIX-CHAIN，m［i,j］表示计算矩阵乘积Ai..j=AiAi+1…Aj所需的最少数乘次数。图3-9RECURSIVE-MATRIX-CHAIN(p,1,4)的递归树RECURSIVE-MATRIX-CHAIN(p,i,j)1ifi=j2thenreturn03m［i,j］←∞4for

k←i

to

j-15do

q←RECURSIVE-MATRIX-CHAIN(p,i,k) +RECURSIVE-MATRIX-CHAIN(p,k+1,j)+pi-1pkpj

6ifq<m［i,j］7thenm［i,j］←q8returnm［i,j］图3-9显示调用RECURSIVE-MATRIX-CHAIN(p,1,4)所产生的递归树。树中的每个结点标以参数i和j的值。由图可见，许多参数对在图中出现多次。事实上，我们可以证明，这个递归过程计算m［1,n］的时间至少为n的指数时间。设T(n)表示RECURSIVE-MATRIX-CHAIN计算n个矩阵链乘的最优加括号方式的时间。如果假设1、2行和6、7行每个至少执行一个单位时间,那么，

T(i)(i=1,2,:,n-1)在T(k)和T(n-k)中各出现一次。重写递归方程，可得利用替换方法，可以证明T(n)=Ω(2n)。尤其是证明n≥1时，T(n)≥2n-1。基础为T(1)≥1=20，对于n≥2，可得证毕。由此可得，RECURSIVEMATRIXCHAIN算法的时间复杂度至少为n的指数函数。比较这个自顶向下的递归算法与自底向上的动态规划算法，可见后者更有效，因为它充分利用了重叠子问题的性质，只有Θ(n2)个不同子问题，并且动态规划算法只解这些子问题一次。只要是在递归树中遇见的子问题，递归算法都进行求解。当问题的自然递归树中包含相同子问题且不同子问题数目少时，可以考虑用动态规划方法求解。我们常常将对子问题做出的选择存储在一张表中，以便可以利用这个信息得到问题的最优解。在矩阵链乘问题中，当重构最优解时，表s［i,j］存储了重要信息。假定我们没有维持s［i,j］表，而只填充了包含子问题最优开销的表m［i,j］。在求AiAi+1…Aj的最优加括号方式时，我们有j-i种选择，来决定哪些子问题使AiAi+1…Aj的乘积达到最优。(j-i不是常量。)因此，如果我们将AiAi+1…Aj分裂处的下标存储在表s［i,j］中，那么我们只需O(1)时间就可重构每次选择。3.5备忘录方法备忘录递归算法将每个子问题的计算结果存放在表中。表中的每个输入用一个特殊值进行初始化，这个特殊值表明这个输入需要被计算并填充。当递归算法在执行中，首次遇见该位置处的子问题时，就计算该子问题，并将计算结果存储在表中该位置处。当在以后遇见这个子问题时，通过查表返回该值。这种方法预示着已知了所有子问题的参量集合，并且表位置和子问题之间的关系已经确立。另一种记录的方法是利用子问题参数作为哈希函数关键字的方法。以下是矩阵链乘问题的备忘录算法。MEMOIZED-MATRIX-CHAIN(p)1n←length［p］-12for

i←1to

n

3dofor

j←i

to

n

4do

m［i,j］←∞5returnLOOKUP-CHAIN(p,1,n)LOOKUPCHAIN(p,1,n)1if

m［i,j］<∞2thenreturn

m［i,j］3if

i=j

4then

m［i,j］←05elsefor

k←i

to

j-1do

q←LOOKUP-CHAIN(p,i,k)+LOOKUP-CHAIN(p,k+1,j)+pi-1pkpj

7if

q<m［i,j］8then

m［i,j］←q9return

m［i,j］我们仍以p=〈p0,p1,…,pn〉=〈30,35,15,5,10,20,25〉为例说明备忘录算法的计算过程。在初始化m［i,j］后(执行算法MEMOIZED-MATRIX-CHAIN后)，m［i,j］中的所有元素初始化为∞。算法返回LOOKUP-CHAIN(p,1,6)。为简便起见，我们省略过程中参数p。图3-10说明了LOOKUP-CHAIN(p,1,6)的计算过程。其中，每张表中浅色阴影部分表示更新，深色阴影表示查表直接返回该处结果。在图3-10(a)中，初始化m［i,j］←∞，其中i，j=1，2，…，6。图3-10LOOKUP-CHAIN(p,1,6)的计算过程图3-10LOOKUP-CHAIN(p,1,6)的计算过程在图3-10(c)中，q=LOOKUP-CHAIN(1,2)+LOOKUP-CHAIN(3,6)+p0p2p6

且q<m［1,6］,执行更新操作m［1,6］←q。其中需要计算m［1,2］，如浅色阴影所示。而m［3,6］可查表直接返回结果，如深色阴影所示。在图3-10(d)中，q=LOOKUP-CHAIN(1,3)+LOOKUP-CHAIN(4,6)+p0p3p6=7875+3500+30×5×25=15125LOOKUP-CHAIN(1,3)=min{LOOKUP-CHAIN(1,1)+LOOKUP- CHAIN(2,3)+p0p1p3,LOOKUP- CHAIN(1,2)+LOOKUP-HAIN(3,3)+p0p2p3} =min{7875,18000}=7875且q<m［1,6］,执行更新操作m［1,6］←q。其中需要计算m［1,3］，m［2,3］，如浅色阴影所示。而m［1,2］，m［4,6］可查表直接返回结果，如深色阴影所示。在图3-10(e)中，q=LOOKUP-CHAIN(1,4)+LOOKUP-CHAIN(5,6)+p0p4p6=9375+5000+30×10×25=21875LOOKUP-CHAIN(1,4)=min{LOOKUP-CHAIN(1,1)+LOOKUP- CHAIN(2,4)+p0p1p4,=LOOKUP- CHAIN(1,2)+LOOKUP-CHAIN(3,5) +p0p2p4,=LOOKUP-HAIN(1,3)+LOOKUP- CHAIN(4,4)+p0p3p4} =min{14875,21000,9375}=9375且q>m［1,6］,不执行更新操作m［1,6］←q。其中需要计算m［1,4］，m［2,4］，m［3,4］，如浅色阴影所示。而m［1,2］，m［1,3］，m［2,3］，m［5,6］可查表直接返回结果，如深色阴影所示。在图3-10(f)中，q=LOOKUP-CHAIN(1,5)+LOOKUP-CHAIN-(6,6)+p0p5p6

=11875+30×20×25=26875LOOKUP-CHAIN(1,5)=min{LOOKUP-CHAIN(1,1)+LOOKUP- CHAIN(2,5)+p0p1p5, LOOKUP-CHAIN(1,2)+LOOKUP- CHAIN(3,5)+p0p2p5, LOOKUP-CHAIN(1,3)+LOOKUP- CHAIN(4,5)+p0p3p5}LOOKUP- CHAIN(1,4)+LOOKUP-CHAIN(5,5)+p0p4p5} =min{28125,24750,11875,15375}=11875图3-11背包算法的递归结构图3-11表示背包容余量为14时的背包算法的递归结构。typedefstruct{intweight;intval;}Item;intRECURKNAP(intX){inti,space,max,t;

for(i=0,max=0;i<n;i++)

if((space=X-items［i］.weight)>=0))

if((t=RECURKNAP(space)+items［i］.val)>maxmax=t;returnmax;}图3-12背包问题的动态规划算法结构intTopDown-KNAP(intW){inti,space,max,maxi,t;

if(maxKnown［W］![KG-*3]=unknown)returnmaxKnown［W］;//可用一个观察哨表示unknown的值

for(i=0,max=0;i<N;i++)

if((space=W-items［i］.weight)>=0)

if((t=TopDown-KNAP(space)+items［i］.val)>max){max=t;maxi=i;}maxKnown［W］=max;itemKnown［W］=items［maxi］;

returnmax;}改进后的算法TopDown-KNAP将复杂度从指数级降到线性级(当W不为n的指数级函数时)，即运行时间与nW成正比。在程序中，简单地存储已计算过的函数值。当进行递归调用时，查找存储函数值的表，若表中存在该值，则返回该值，否则进行递归调用。在表中将所有值初始化为观察哨，然后存储物品的下标，当计算完成后，可以重构背包内的物品。如果物品itemKnown［W］在背包中，其余的物品在背包容量为W-itemKnown［W］.weight的背包中产生最优解,那么itemKnown［W-item［W］.weight］在背包中，依次类推。在自顶向下的动态规划技术中，我们存储已知的值。在自底向上的动态规划技术中，我们预先进行计算。自顶向下的动态规划方法具有如下特点：·它是一种对自然问题求解的机械转换。·方法自身可以确定计算子问题的顺序。·可能不需要计算出所有子问题的解。3.6装配线调度问题如图3-13所示，某公司在生产汽车过程中使用两条装配线。当汽车底盘进入每条装配线时，在许多站点装配零件。在每条线结束时，自动完成下线工作。每条装配线有n个站点，标号为j=1，2，…，n。我们用Si,j表示第i条装配线上第j个站点，其中i=1，2。第1条装配线上的第j个站点S1,j与第2条装配线上的第j个站点S2,j的作用相同。由于站点建立的时间及技术不同，因此每个站点所需的时间不同，即使在两条不同装配线对应的同一站点，也会不同。用bi,j表示在Si,j处所需的装配时间，ei表示进入装配线i的进入时间，oi表示退出装配线i的退出时间。图3-13寻找以最快方式通过工厂的制造问题在一般情况下，当一个底盘进入某条装配线时，它只通过那条装配线，在同一条装配线上从一个站点到下一个站点的时间可忽略不计；有时候，当特殊情况订购出现时，顾客希望汽车尽可能快地制造出来。此时，底盘仍然按照次序通过每一站点，但是工厂主可能将部分完成的汽车从一条装配线切换到另一条装配线。假设通过站点Si,

j后，底盘离开装配线i的转移时间为ti,j，其中i=1，2和j=1，2，…，n-1。问题是要决定通过哪些站点完成一辆汽车的装配，使得装配时间达到最小。如果采用穷举法解决这个问题，那么最小化装配时间是不可行的。这是因为在每个站点上我们都有两种选择，所以有2n种选择站点的方式。因此，通过枚举所有可能的路线，计算所需时间为Ω(2n)。当n较大时，这是不可行的。我们仍然用动态规划解决这个问题。(1)分析装配线调度问题最优解的结构。动态规划的第一步是分析问题最优解的结构。对于装配线调度问题，考虑一个底盘从开始点到通过站点S1,j的最快方式，如果j=1，只有惟一一种方式通过S1,j。对于j=2，3，…，n，则有两种选择：一种方式是底盘从S1,j-1直接到S1,j，同一条线上从站点j-1到站点j的时间可忽略不计，另一种方式是底盘从S2,j-1经转移到S1,j，转移时间为t2,j-1。我们分别考虑这两种情形。首先，假定通过S1,j-1以最快方式到达S1,j，那么，底盘一定以最快的方式从开始点达到S1,j-1。这是因为，如果存在通过S1,j-1的更快方式，我们可以用这条更快方式得到一条通过S1,j的更快方式，这与S1,j是最快方式相矛盾。同样，假定通过S2,j-1以最快方式到达S1,j，那么，底盘一定以最快的方式从开始点到达S2,j-1。原因是相同的。这是因为，如果存在通过S2,j-1的更快方式，则可以用这条更快方式得到一条通过S1,j的更快方式，这与S1,j是最快通过方式相矛盾。更一般地说，对于装配线调度问题(assemblylineschedulingproblem)，问题的一个最优解(找出通过S1,j的最优解)包含子问题的最优解(找出通过S1,j-1的最优解或找出通过S2,j-1的最优解)，装配线调度问题具有最优子结构。问题的最优子结构表明，我们可以通过子问题的最优解构造问题的最优解。对于装配线调度问题，推理如下：考虑最快通过站点S1,j的方式，它一定通过装配线1或者装配线2的站点S1,j-1。因此，最快通过站点S1,j的方式或者通过站点S1,j-1并直接通过站点S1,j，或者通过站点S2,j-1并从装配线2转移到装配线1，然后通过站点S1,j。由对称性可得，通过站点S2,j的方式或者通过站点S2,j-1并直接通过站点S2,j，或者通过站点S1,j-1并从装配线1转移到装配线2，然后通过站点S1,j。(2)递归定义装配线调度问题最优解的值。设fi［j］表示从开始点到通过站点Si,j的最快时间，f*表示底盘从开始点经过工厂所有最优站点到输出的最快时间，则有f*=min{f1［n］+o1,f2［n］+o2}显然，f1［1］=e1+b1,1f2［1］=e2+b2,1

(3.6)(3.7)(3.5)以下推导fi［j］的计算过程，其中j=2，3，…，n；i=1，2。先看f1［j］的计算。经过上述讨论，得知最快通过S1,j的方式或者通过站点S1,j-1并直接通过站点S1,j，或者通过站点S2,j-1并从装配线2转移到装配线1，然后通过站点S1,j。在前一种情形下，f1［j］=f1［j-1］+b1,j

在后一种情形下，f1［j］=f2［j-1］+t2,j-1+b1,j

因此，f1［j］=min{f1［j-1］+b1,j，f2［j-1］+t2,j-1+b1,j}，j=2，3，…，n由对称性，可得f2［j］=min{f2［j-1］+b2,j，f1［j-1］+t1,j-1+b2,j}，j=2，3，…，n因此，j=1j≥2(3.8)j=1j≥2(3.9)图3-14装配线调度问题示例

fi［j］的值给出了子问题最优解的值。为了记录如何构造一个最优解，我们用li［j］表示装配线号，其值为1或2，表示最快通过Si,j的站点j-1所在的装配线。这里，j=2，3，…，n；i=1，2。这里不定义li［1］的原因是，无论是哪一条线，在它之前都没有站点。用l*表示最快通过站点n所在的装配线。

f*=38表示最快通过工厂所用时间。f1［3］=min{f1［2］+b1,3，f2［2］+t2,2+b1,3}=min{18+3，16+1+3}=20，对应的l1［3］=2，表示通过装配线1的第3个站点时，是从装配线2转移到装配线1得到的。借助li［j］的值可以求得最快通过工厂的方式，即经过哪条装配线、哪些站点。由l*=1可得，表示从第一条装配线站点S1,n下线。然后看l1［6］=2，表示通过站点S2,5(装配线2)转移到站点S1,6(装配线1)。下一个考察l2［5］，为2，表示通过站点S2,4(装配线2)直接到站点S2,5。l2［4］=1，表示通过站点S1,3(装配线1)转移到站点S2,4(装配线2)。l1［3］=2，表示通过站点S2,2(装配线2)转移到站点S1,3(装配线1)。l2［2］=1，表示通过站点S1,1(装配线1)转移到站点S2,2(装配线2)。(3)计算装配线调度问题的最快时间。根据式(3.4)、式(3.5)和式(3.6)，很容易写一个递归算法。但是这样的递归算法，它的运行时间为n的指数级。以下做出分析。设ri(j)表示递归算法中调用fi［j］的数目，由式(3.4)可得r1(n)=r2(n)=1(3.10)由式(3.7)和式(3.8)可得r1(j)=r2(j)=r1(j+1)+r2(j+1)，j=1,2,…,n-1(3.11)如果我们按照不同于递归调用的次序计算fi［j］，则可以做得更好。观察可见，对于j≥2，每个fi［j］的值只依赖于f1［j-1］和f2［j-1］。按照站点号j递增的次序计算fi［j］的值，即按从左到右的次序计算，此时运行时间为Θ(n)。过程以bi,j、ti,j、ei、oi和n作为输入。FASTEST-WAY(b,t,e,o,n)1f1［1］←e1+b1,1

2f2［1］←e2+b2,1

3for

j←2to

n

4doif

f1［j-1］+b1,j≤f2［j-1］+t2,j-1+b1,j5then

f1［j］←f1［j-1］+b1,j

6l1［j］←17elsef1［j］←f2［j-1］+t2,j-1+b1,j

8l1［j］←29if

f2［j-1］+b2,j≤f1［j-1］+t1,j-1+b2,j

10then

f2［j］←f2［j-1］+b2,j

11l2［j］←212else

f2［j］←f1［j-1］+t1,j-1+b2,j

13l2［j］←114if

f1［n］+o1≤f2［n］+o2

15then

f*=f1［n］+o1

16l*=117else

f*=f2［n］+o2

18l*=2(4)构造装配线调度的最优解。计算出fi［j］、li［j］、f*和l*之后，我们可以构造出最快方式通过哪些站点。过程OUTPUT-STATION按照站点号递增的次序输出。OUTPUT-STATION(l,i,j)1if

j=0thenreturn

2OUTPUT-STATION(l,li［j］,j-1)3print“line”i“,station”j

如要输出所有站点，需调用OUTPUT-STATION(l,l*,n)。在图3-13的示例中，OUTPUT-STATION将产生如下输出：line1,station1line2,station2line1,station3line2,station4line2,station5line1,station63.7最长公共子序列(1)刻画LCS问题的最优子结构。如果利用穷举法解LCS问题，列举出X的所有子序列，检查每个子序列是否是Y的一个子序列，记录所找到的最长子序列，X的每个子序列与X的下标集{1,2,…,n}的一个子集对应，X共有2m个子序列，因而，这种方法具有指数级的复杂度。因此，对于长序列，这种方法不可行。借助图3-15，定理3.1证明了LCS问题具有最优子结构性质。给定序列X=〈x1,x2,…,xm〉，定义Xi=〈x1,x2,…,xi〉为X的第i个前缀，其中i=0,1,…,m。例如，如果X=〈B,A,C,A,D,A,B〉，X3=〈B,A,C〉，X0为空序列。图3-15LCS问题的最优子结构

定理3.1LCS的最优子结构。设X=〈x1,x2,…,xm〉和Y=〈y1,y2,…,yn〉是两条序列，Z=〈z1,z2,…,zk〉是X和Y的任一LCS。(i)如果xm=yn，那么zk=xm=yn，且Zk-1是Xm-1和Yn-1的一条最长公共子序列。(ii)如果xm≠yn，那么zk≠xm，蕴含着Z是Xm-1和Y的一条最长公共子序列。(iii)如果xm≠yn，那么zk≠yn，蕴含着Z是X和Yn-1的一条最长公共子序列。证明：(i)如果zk≠xm，那么，我们可以将xm=yn添加到序列Z后，得到X和Y的一条长度为k+1的公共子序列，这与Z是X和Y的最长公共子序列矛盾。因此，一定会有zk=xm=yn。现在，前缀Zk-1是Xm-1和Yn-1的长度为k-1的公共子序列。我们要证明，这条子序列是最长公共子序列。假定存在Xm-1和Yn-1的长度大于k-1的公共子序列W，则将xm=yn添加到序列W后，产生X和Y的长度大于k的公共子序列，这与k是最长公共子序列的长度相矛盾。(ii)如果zk≠xm，则Z是Xm-1和Y的一条公共子序列。如果存在Xm-1和Yn-1的长度大于k的公共子序列W，那么W也会是Xm和Y的公共子序列，这与Z是X和Y的LCS的假设相矛盾。(iii)如果zk≠yn，则Z是X和Yn-1的一条公共子序列。如果存在Xm-1和Yn-1的长度大于k的公共子序列W，那么W也会是X和Yn的公共子序列，这与Z是X和Y的LCS的假设相矛盾。证毕。定理3.1表明，两条序列的LCS包含两条序列前缀的LCS。因此，LCS问题具有最优子结构性质，其递归解具有重叠子问题性质。(2)递归定义LCS问题最优解的值。定理3.1表明，当求X=〈x1,x2,…,xm〉和Y=〈y1,y2,…,yn〉的一条最长公共子序列时，需要考察一个或两个子问题。如果xm=yn，我们一定要找Xm-1和Yn-1的LCS。将xm=yn添加到这条LCS之后，就得到X和Y的LCS。如果xm≠yn，则必须解两个子问题，这就是求Xm-1和Y以及X和Yn-1这两个子问题的解。这两个子问题中较长的LCS就是X和Y的LCS。因为这些情形已经穷举了所有可能性，我们知道其中的最优子问题一定是X和Y的一条LCS。我们可以容易地表明，LCS问题具有重叠子问题性质。要求出X和Y的LCS，必须求出Xm-1和Y以及X和Yn-1这两个子问题的LCS。但这两个子问题都以Xm-1和Yn-1的LCS作为子问题。许多其他子问题共享子问题。设l［i,j］表示序列Xi和Yj的LCS的长度，如果i=0或j=0，则其中有一个序列长度为0，因此，LCS长度为0。由LCS问题的最优子结构可导出以下递归公式：i=0或j=0i,j>0且xi=yj

i,j>0且xi≠yj

(3.12)(3)计算LCS最优解的值。基于方程(3.12)，我们可以容易地写一个计算两个序列长度LCS值的指数级算法。因为只有Θ(mn)个不同的子问题，我们可以利用自底向上的动态规划求解这一问题。过程LCS-LENGTH(X,Y)以X=〈x1,x2,…,xm〉和Y=〈y1,y2,…,yn〉作为输入，并将l［i,j］的值存储在表l［0..m,0..n］中，以行为主序从左到右计算表l中的元素，同时维持表b［1..m,1..n］，以简化最优解的构造。当计算l［i,j］时，用b［i,j］记录使得l［i,j］取最优值的最优子问题。LCSLENGTH(X,Y)1m←length［X］2n←length［Y］3for

i←1tom4dol［i,0］←05for

j←1to

n

6do

l［0,j］←07for

i←1tom8dofor

j←1to

n

9doif

xi=yj

10then

l［i,j］←l［i-1,j-1］+111b［i,j］←“”12elseif

l［i-1,j］←l［i,j-1］13then