动态规划.doc

算法设计与分析结课作业动态规划和分治算法一样，动态规划(dynamic programming)是通过组合子问题的解而解决整个问题的。从第2章已经知道，分治算法是指将整个问题划分成一些独立的子问题，递归地求解各子问题，然后合并子问题的解而得到原问题的解。与此不同，动态规划使用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。在这种情况下，若用分治法则会做许多不必要的工作，及重复的求解公共的子子问题。动态规划算法对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。动态规划通常应用于最优化问题。此类问题可能有很多种可行解。每个解有一个值，而我们希望找出一个具有最优(最大或最小)值的解。称这样的解为该问题的“一个”最优解(而不是“确定”的最优解) ，因为可能存在多个取最优值的解。动态规划算法的设计可以分为如下4个步骤：1） 描述最优解的结构。2） 递归定义最优解的值。3） 按自底向上的方式计算最优解的值。4） 由计算出的结果构造一个最优解。第13步构成问题的动态规划解的基础。第4步在只要求计算最优解的值时可以略去。如果的确做了第4步，则有时要在第3步的计算中记录一些最优化问题，使构造一个最优解变得容易。接下来的各节利用动态规划方法来求解一些最优化问题。15.1节分析包括两个汽车装配线的调度问题，在经过每个装配站后，组装中的汽车可以留在同一条装配线上，或者移动到另外一条装配线。15.2节讨论如何做一连串的矩阵乘法，使得所作的标量乘法总次数最少。在给出这些动态规划的例子之后，15.3节讨论为使动态规划成为可行的求解技术，一个问题必须具备的两个关键特征。然后，15.4节介绍如何找出两个序列的最长公共子序列。最后，15.5节介绍在已知待搜索的关键字分布的情况下，如何利用动态规划构造最优的二叉查找树。15.1装配线调度第一个动态规划的例子是求解一个制造问题。Colonel汽车公司在有两条装配线的工厂内生产汽车，如图15-1所示。一个汽车底盘在进入每一条装配线后，在一些装配站中会在底盘上安装部件，然后，完成的汽车在装配线的末端离开。每一条装配线上有n个装配站，编号为j=1, 2, , n。将装配线i(i为1或2)的第j个装配站表示为。装配线1的第j个站()和装配线2的第j个站()执行相同的功能。然而，这些装配站是在不同的时间建造的，并且采用了不同的技术。因此，每个站上所需的时间是不同的，即使是在两条不同装配线相同位置的装配站上也是这样。我们把在装配站上所需的装配时间记为。如图15.1所示，一个汽车底盘进入其中一条装配线，然后从每一站进行到下一站。底盘进入装配线i的进入时间为，装配完的汽车离开装配线i的离开时间为。在正常情况下，一旦一个底盘进入一条装配线后，它只会经过该条装配线。在相同的装配线中，从一个装配站到下一个装配站所花的时间可以忽略。偶尔会来一个特别急的订单，客户要求尽可能快地制造这些汽车。对这些加急的订单，底盘仍然依序经过n个装配站，但是工厂经理可以将部分完成的汽车在任何装配站上从一条装配线移到另一条装配线上。把已经通过装配站的一个底盘从装配线i移走所花的时间为，其中i=1,2，而j=1,2, , n-1(因为在第n个装配后，装配已经完成)。问题是要确定在装配线1内选择哪些站以及在装配线2内选择哪些站，以使汽车通过工厂的总时间最小。在图15-2a所示的例子中，最快的总时间是选择装配线1的装配站1，3和6，以及装配线2的装配站2，4和5。图15-1 一个找出通过工厂装配线的最快方式的制造问题。共有两条装配线，每条有n个装配站；装配线i的第j个装配站表示为，在该站的装配时间是。一个汽车底盘进入工厂，然后进入装配线i(i为l或2)，花费时间。在通过一条线的第j个装配站后，这个底盘来到任一条线的第(j+1)个装配站。如果它留在相同的装配线，则没有移动的开销；但是，如果在装配站后，它移动到了另一条线上则花费时间。在离开一条线的第n个装配站后，完成的汽车花费时间离开工厂。待求解的问题是确定应该在装配线1内选择哪些站、在装配线2内选择些站，才能使汽车通过工厂的总时间量小显然，当有很多个装配站时，用强力法(brute force)来极小化通过工厂装配线的时间是不可行的。如果给定一个序列，在装配线1上使用哪些站，在装配线2上使用哪些站，则可以在时间内，很容易计算出一个底盘通过工厂装配线要花的时间。不幸的是，选择装配站的可能方式有2n中：可以把装配线1内使用的装配站集合看作1, 2, , n的一个子集，并注意到有2n个这样的子集。因此，要通过穷举所有可能的方式，然后计算每种方式花费的时间来确定最快通过工厂的路线，需要时间，这在n很大时是不可行的。图15-2 a)一个装配问题的实例，代价标为、以及。深阴影的路径表示通过工厂的最快方式 b) a)中的fij，f*，lij以及l*的实例的值步骤1：通过工厂最快路线的结构动态规划方法的第一个步骤是描述最优解的结构的特征。对于 装配线调度问题，可以如下执行。考虑底盘从起始点到装配站的最快可能路线。如果j=1，则底盘能走的只有一条路线，所以很容易就可以确定它的装配站花费了多少时间。对于j=2, 3, , n，则有两种选择：这个底盘可能是从装配站直接到装配站，在相同的装配线上，从装配站j-1到j的时间是可以忽略的。或者，这个底盘可能来自装配站，然后再移动到装配站，移动的代价是。我们将分别考虑这两种可能性，后面可以看到，它们之间其实是有很多共性的。首先，假设通过装配站的最快路线通过了装配站。关键的一点是这个底盘必定是利用了最快的路线从开始点到装配站的。这是为什呢？如果存在一条更快的路线通过，我们就可以采用这条更快的路线，从而得到通过装配站的更快的路线：这就形成了矛盾。类似地，假设通过装配站的最快路线就是通过装配站。现在，我们注意到这个底盘必定是利用了最快的路线从开始点到装配站的。理由是相同的：如果有一条更快的通过装配站的路线，就可以采用这条更快的路线，从而得到通过装配站的更快的路线，这是一个矛盾。更一般地，对于装配线调度问题，一个问题的（找出通过装配站的最快路线）最优解包含了子问题（找出通过和的最快路线）的一个最优解。我们称这个性质为最优子结构，这是是否可以应用动态规划方法标志之一，具体会在15.3节中看到。下面利用最优子结构来说明，可以利用子问题的最优解来构造原问题的一个最优解。对于装配线调度问题，推理如下。观察一条通过装配站的最快路线，会发现它必定是经过装配线1或2上的装配站j-1。因此，通过装配站的最快路线只能是以下二者之一：通过装配站的最快路线，然后直接通过装配站；通过装配站的最快路线，从装配线2移动到装配线1，然后通过装配站。利用对称的推理是想，通过装配站的最快路线也只能是以下二者之一：通过装配站的最快路线，然后直接通过装配站；通过装配站的最快路线，从装配线1移动到装配线2，然后通过装配站。为了解决这个问题，即寻找通过任一条装配线上的装配站j的最快路线，我们解决它的子问题，即寻找通过两条装配线上的装配站j-1的最快路线。所以，对于装配线调度问题，通过建立子问题的最优解，就可以建议原问题某个实例的一个最优解了。步骤2：一个递归的解在动态规划方法中，第二个步骤是利用子问题的最优解来递归定义一个最优解的值。对于装配线的调度问题，我们选择在两条装配线上通过装配站j的最快路线的问题来作为子问题，j=1,2，n。令fij表示一个底盘从起点到装配站的最快可能时间。我们的最终目标是确定底盘通过工厂的所有路线的最快时间，记为f*。底盘必须一路通过装配线1或2通过装配站n，然后到达工厂的出口。由于这些路线的较快者就是通过整个工厂的最快路线，有：(15-1)要对f11和f21进行推理也是很容易的。不管在哪一条装配线上通过装配站1，底盘都是直接到达该装配站的。于是，(15-2)(15-3)现在来考虑如何计算fij，其中j=2,3，n(i=l, 2)。先来看一看f1j前面说过，通过装配站的最快路线或者是通过装配站，然后直接通过装配站的最快路线，或者是通过装配站，从装配线2移动到装配线1然后通过装配站的最快路线。在第一种情况中，有f2j = f1j-1+ ，而在后一种情况中，f1j = f2j-1+ +。所以：(15-4)其中j=2, 3, , n。对称地，有：(15-5)其中j=2, 3, , n。合并公式(15.2)公式(15.5)，得到递归公式：(15-6)(15-7)图15-2b示出了图15 -2a例子中的由等式(15.6)和等式(15.7)计算出的fij值，以及f*的值。fij的值就是子问题最优解的值。为了有助于跟踪最优解的构造过程，我们定义lij为装配线的编号（1或2），其中的装配站j-l被通过装配站的最快路线所使用。这里，i=l，2且j=2,3,n。（我们避免定义li1，因为在任一条装配线上都没有一个装配站在站l前面）。此外，还定义l*为这样的装配线，其内的装配站n被通过整个工厂的最快路线所使用。lij的值可以帮助找到一个最快的路线。利用图15-2b中所示的l*的值和lij，可以如下找到如图15-2a所示通过工厂的一条最快路线。从l*=l开始，使用装配站。现在看到l16值为2，所以使用装配站。接着，可以看到l25=2（使用装配站），l24 =1(装配站)l13=2（装配站），以及l22=1（装配站）。步骤3：计算最快时间此时，写出一个递归算法来计算通过工厂的最快路线是一件简单的事情，它基于公式(15.1)以及递归式(15.6)和式(15.7)。这种递归算法有一个问题：它的执行时间是关于n的指数形式。要知道为什么，令ri (j)为递归算法中引用fij的次数。由公式(15.1)，有(15.8)由递归式(15.6)和式(15.7)得到(15.9)其中j=1, 2, , n-l。练习15. 1-2会要求读者证明rij=2n-j。这样，单是f11就被引用了2n-1次！如练习15.1-3要求读者证明的那样，引用所有fij值的总次数为。如果在递归的方式中以不同的顺序来计算fij的值，能做得更好。注意对于，fij的每一个值仅依赖于f1j-1和f2j-1的值。通过以递增装配站编号j的顺序来计算fij的值，即在图15-2b中从左到右，可以在时间内计算出通过工厂的最快路线，以及其所花的时间。FASTEST-WAY程序以值，和，以及在每条装配线中装配站的数目n作为输入。FASTEST-WAY(a, t, e, x, n)1 f11 e1 + a1,1 2 f21 e2 + a2,1 3 for j 2 to n 4 do if f1j - 1 + a1,j f2j - 1 + t2,j-1 + a1,j 5 then f1j f1j - 1 + a1, j 6 l1j 1 7 else f1j f2j - 1 + t2,j-1 + a1,j 8 l1j 2 9 if f2j - 1 + a2,j f1j - 1 + t1,j-1 + a2,j10 then f2j f2j - 1 + a2,j11 l2j 212 else f2j f1j - 1 + t1,j-1 + a2,j13 l2j 114 if f1n + x1 f2n + x215 then f* = f1n + x116 l* = 117 else f* = f2n + x218 l* = 2FASTEST-WAY的工作方式如下。第12行利用公式(15.2)和公式(15.3)来计算f11和f21。然后第313行的for循环计算fij和lij，i=l, 2，且j=2, 3, , n。第48行利用公式(15-4)来计算f1j和l1j，而第913行利用公式(15.5)来计算f2j和l2j。最后，第1418行利用公式(15.1)来计算f*和l*。因为第12行与第1418行花费常数时间，而且第313行的for循环的n-l次迭代中的每一个也花费常数时间，所以整个过程花费时间。观察fij和lij值的计算过程的一种方式是在表格中填入记录。在图15. 2b中，我们在表格内从左到右填入fij和lij的数值(在每一列中从上到下)。要填入一个记录fij，需要f1j-1和f2j-1的值，由于已经计算并保存了它们，只需简单地查表来确定它们的值。步骤4：构造通过工厂的最快路线计算出fij，f*，lij，l*的值之后，需要构造在通过工厂的最快路线中使用的装配站的序列。我们在上面已经讨论了如何在图15-2的例子中做到这一点。下面的过程以站号的递减顺序，输出所使用的各个装配站。练习15. 1-1要求读者修改这个过程，使它按站号的递增顺序输出各个装配站。PRINT-STATIONS(l, l*, n)1 i l*2 print line i , station n3 for j n downto 24 do i lij5 print line i , station j - 1在图152的例子中，PRINT-STATIONS将产生以下的输出：line 1, station 6line 2, station 5line 2, station 4line 1, station 3line 2, station 2line 1, station 1练习15. 1-1说明应如何修改程序PRINT-STATIONS，让它以站号的递增顺序输出各装配站。(提示：利用递归。)15. 1-2利用公式(15. 8)、(15. 9)及替换法来证明：在递归算法中引用fij的次数ri(j)等于2n-j。15. 1-3利用练习15. 1-2的结果，证明所有引用fij的总次数(即)等于2n+1-2。15. 1-4包含fij和lij值的表格共含有4n-2个表项。说明如何把空间需求缩减到共2n+2个表项，仍然能够计算出f*，并且仍然能够输出通过工厂的最快路线上的所有装配站。15. 1-5 Canty教授猜测存在着某些，以及的值，使得FASTEST-WAY程序在某个装配站j上，产生出满足l1j=2且l2j=l的lij值。假设所有的移动代价是非负值，说明Canty教授的猜测是不正确的。15.2 矩阵链乘法我们用来说明动态规划的下一个例子是解决矩阵链相乘问题的一个算法。给定由n个要相乘的矩阵构成的序列（链）。要计算乘积A1 A2An(15. 10)为计算式(15. 10)，可将两个矩阵相乘的标准算法作为一个子程序，根据括号给出的计算顺序做全部的矩阵乘法。一组矩阵的乘积是加全部括号的(fully parenthesized)，如果它是单个的矩阵，或是两个加全部括号的矩阵的乘积外加括号而成。矩阵的乘法满足结合率，故无论怎样加括号都会产生相同的结果。例如，如果矩阵链为，乘积A1A2A3A4可用五种不同方式加全部括号： (A1 (A2 (A3 A4) ,(A1 (A2 A3) A4) ,(A1 A2) (A3 A4) ,(A1 (A2 A3) A4) ,(A1 A2) A3) A4). 矩阵链加括号的顺序对求积运算的代价有很大的影响。先来看看两个矩阵相乘的代价。标准的算法由下面的伪代码给出。属性rows和columns表示矩阵的行数和列数。MATRIX-MULTIPLY(A, B)1 if columnsA rowsB2 then error incompatible dimensions3 else for i 1 to rowsA4 do for j 1 to columnsB5 do Ci, j 06 for k 1 to columnsA7 do Ci, j Ci, j + Ai, k Bk, j8 return C仅当两个矩阵A和B相容（即A的列数等于B的行数）时，才可以进行相乘运算。如果A是个pq矩阵，B是个qr矩阵，则结果矩阵C是一个pr矩阵。计算C的时间由第7行中标量乘法运算的次数决定，这个次数等于pqr。接下来对运行时间的分析都将以标量乘法次数来表示。为说明由不同的加全部括号顺序所带来的矩阵乘积的代价不同，考虑三个矩阵的链的问题。假设三个矩阵的维数分别为10100，1005，550。如果按(A1A2)A3)规定的次序来做乘法，求105的矩阵乘积A1A2，要做101005=5000次的标量乘法运算，再乘上A3还要做10550=2 500次标量乘法，总共7500次标量乘法运算。如果按(A1(A2A3)的次序来计算，则为求10050的矩阵乘积A2A3要做100550=25 000次标量乘法运算，再乘上A1还要101 0050=50 000次标量乘法，总共75 000次标量乘法运算。因此，按第一种运算次序进行计算就要快到10倍。矩阵链乘法问题可表述如下：给定n个矩阵构成的一个链，其中i=1, 2, , n。矩阵Ai的维数为pi-1pi，对乘积A1A2An以一种最小化标量乘法次数的方式进行加全部括号。注意在矩阵链乘法问题中，实际上并没有把矩阵相乘。目的仅是确定一个具有最小代价的矩阵相乘顺序。通常，与真正在执行矩阵乘法时所节省的时间相比，在确定最优顺序上花费的时间会得到更多的回报(例如只做7500次标量乘法而不是75 000次)。计算全部括号的重数在利用动态规划来解矩阵链乘法问题之前，应认识到靠穷尽所有可能的加全部括号方案不会得到一个有效的算法。设P(n)表示一串n个矩阵可能的加全部括号方案数。当n=1时，只有一个矩阵，因此只有一种方式来加全部括号矩阵乘积。当时，一个加全部括号的矩阵乘积，就是两个加全部括号的矩阵子乘积的乘积，而且这两个子乘积之间的分裂可能发生在第k个和第(k+1)个矩阵之间，其中k =1，2，n-l。因此，可得递归式(15-11)思考题12-4曾要求读者证明一个类似递归式的解是Catalan数序列，其增长的形式为。一个较简单的练习(参见练习15.23)将证明递归式(15. 11)的解为。所以解的个数是行的指数形式，而且对确定矩阵链的最优加全部括号来说，穷尽搜索不是一个好的策略。步骤1：最优加全部括号的结构动态规划方法的第一步是寻找最优的子结构，然后，利用这一子结构，就可以根据子问题的最优解构造出原问题的一个最优解。对于矩阵链乘法问题，可以如下执行这个步骤。为方便起见，用记号Ai.j，表示对乘积AiAi+1Aj求值的结果，其中。注意如果这个问题是非平凡的，即，则对乘积AiAi+1Aj的任何加全部括号形式都将乘积在Ak与Ak+l之间分开，此处k是范围1kj之内的一个整数。这就是说，对某个k值，首先计算矩阵Ai.k和Ak+1.j，然后把它们相乘就得到最终乘积Ai.j。这样，加全部括号的代价就是计算Ai.k和Ak+1.j的代价之和，再加上两者相乘的代价。这个问题的最优子结构如下。假设AiAi+1Aj的一个最优加全部括号把乘积在Ak与Ak+1之间分开，则对AiAi+1Aj最优加全部括号的“前缀”子链AiAi+1Ak的加全部括号必须是AiAi+1Ak的一个最优加全部括号。为什么呢？如果AiAi+1Ak有一个代价更小的加全部括号那么把它替换到AiAi+1Aj的最优加全部括号中去就会产生AiAi+1Aj的另一种加全部括号，而它的代价小于最优代价，产生了矛盾。类似的观察也成立，即AiAi+1Aj的最优加全部括号的子链Ak+1Ak+2Aj的加全部括号：必须是Ak+1Ak+2Aj的一个最优加全部括号。现在，就可以利用所得到的最优子结构，来说明能够根据子问题的最优解来构造原问题的一个最优解。已经看到，一个矩阵链乘法问题的非平凡实例的任何解法都需要分割乘积，而且任何最优解都包含了子问题实例的最优解。所以，可以把问题分割为两个子问题（最优加全部括号AiAi+1Ak和Ak+1Ak+2Aj），寻找子问题实例的最优解，然后合并这些子问题的最优解，来构造一个矩阵链乘法问题实例的一个最优解。必须保证在寻找一个正确的位置来分割乘积时，我们已经考虑过所有可能的位置，从而确保已检查过了最优的一个。步骤2：一个递归解接下来，根据子问题的最优解来递归定义一个最优解的代价。对于矩阵链乘法问题，子问题即确定AiAi+1Aj的加全部括号的最小代价问题，此处。设mi, j为计算矩阵Ai.j所需的标量乘法运算次数的最小值；对整个问题，计算A1.n的最小代价就是m1, n。我们这样来递归定义mi, j。如果i=j，则问题是平凡的；矩阵链只包含一个矩阵Ai. i=Ai，故无需做任何标量乘法来计算乘积。因此mi, i=0对i=1，2，n。当ij时，为计算mi, j，可以利用步骤1中得出的最优解的结构。假设最优加全部括号将乘积AiAi+1Aj从Ak和Ak+1之间分开，其中。因此mi, j就等于计算子乘积Ai.k和Ak+1.j的代价，再加上这两个矩阵相乘的代价的最小值。回忆起每个矩阵Ai是pi-1pi的，可以看出，计算Ai.k Ak+1.j要做pi-lpkpj次标量乘法。所以得到： mi, j = mi, k + mk+1, j + pi-lpkpj 这个递归公式假设我们已知k的值，而实际上我们并不知道。但是，k只有j-i个可能的值，即k=i, i+l, , j-1。最优加全部括号必然要用到其中之一的k值，故只需逐个检查这些值以找到最佳值。这样关于对乘积AiA i+1Aj的加全部括号的最小代价的递归定义为(15. 12)各mi, j的值给出了子问题的最优解的代价。为了有助于跟踪如何构造一个最优解，定义si, j为这样的一个k值：在该处分裂乘积AiAi+1Aj后可得一个最优加全部括号。亦即si, j等于使mi, j= mi, k+ mk+1, j+ pi-lpkpj的k值。步骤3：计算最优代价现在，可以很容易地根据递归式(15. 12)，来写一个计算乘积A1A2An的最小代价m1, n的递归算法。然而，在15.3节中可以看到，这个算法具有指数时间，它与检查每一种加全部括号乘积的强力法差不多。可以注意到原问题只有相当少的子问题：每一对满足的i和j对应一个问题，总共 。一个递归算法在其递归树的不同分支中可能会多次遇到同一个子问题。子问题重叠这一性质是是否可以采用动态规划的第二个标志（第一个标志是最优子结构）。我们不是递归地解递归式(15. 12)而是执行动态规划方法的第三个步骤，使用自底向上的表格法来计算最优代价。下面的伪代码假设矩阵Ai的维数是pi-1pi，i=l, 2, , n。输入是一个序列p= 。其中lengthp=n+1。此程序使用个辅助表ml.n,1.n来保存mi, j的代价。使用个辅助表sl.n,1.n来记录计算mi, j时取得最优代价处k的值。我们将利用表格s来构造一个最优解。为了正确实现自底向上的方法，必须确定哪些表项要被用来计算mi, j。公式(15. 12)说明计算一个有j-i+l个矩阵的矩阵链乘积时，其代价mi, j仅依赖于计算一个有少于j-i+l个矩阵的矩阵链乘积的代价。也就是说，对k=i, i+l, , j-l，矩阵Ai.k是k-i+lj-i+l个矩阵的乘积，矩阵Ak+1j是j-kj-i+l个矩阵的乘积。因此，该算法填表m的方式对应于求解按长度递增的矩阵链上的加全部括号问题。 MATRIX-CHAIN-ORDER(p) 1 n lengthp - 1 2 for i 1 to n 3 do mi, i 0 4 for l 2 to n l is the chain length. 5 do for i 1 to n - l + 1 6 do j i + l - 1 7 mi, j 8 for k i to j - 1 9 do q mi, k + mk + 1, j + pi-1 pkpj10 if q mi, j11 then mi, j q12 si, j k13 return m and s该算法首先在第23行中对i=l，2，n置mi, i 0（长度为1的链的最小代价）。在第412行循环的第一次执行中，利用递归式(15. 12)来计算mi, i+1，i=1,2,n-l（长度l等于2的链的最小代价）。在循环的第二次执行中，计算mi, i+2，i=1,2，n-2（长度l等于3的链的最小代价），这样一直继续下去。在每一步中，第912行中计算出的mi, i仅依赖于已经计算出的表项mi, k和mk+1, i。图15-3演示了对包含n=6个矩阵的链该算法的执行过程。因为我们仅对ij定义了mi, j。故表m中仅主对角线以上的部分被用到。该图已将表进行了旋转，使主对角线水平放置。矩阵链沿表的底部排列。用这样一种安排，在经过Ai的东北方向的直线与经过Aj的西北方向的直线的交点上，可以找到子矩阵链AiAi+1Aj相乘的最小代价mi, j。表中的每一水平行包含相同长度的矩阵链的表项。过程MATRIX-CHAIN-ORDER自底向上地计算每一行，在每一行中又从左到右进行计算。表项mi, j是根据乘积pi-lpkpi（k=i，i+l,，j-l）与所有在mi, j西南向和东南向的表项计算出来的。图15-3 对n=6及下面各矩阵维数由MATRIX-CHAIN-ORDER计算出的表m和s矩阵维数A1 30 35A2 35 15A3 15 5A4 5 10A5 10 20A6 20 25MATRIX-CHAIN-ORDER具有嵌套循环结构，运行时间为。循环的嵌套层数为三层，每一层循环的下标（l，i和k）可至多取n-1个值。练习15. 2-4要求读者证明这个算法的运行时间实际上是。另外，该算法还需要的空间来保存m和s。这样，与穷尽各种可能的加全部括号形式的指数时间方法相比，MATRIX-CHAIN-ORDER就要有效得多了。对图中的两张表进行旋转，使其主对角线处于水平方向。在表m中仅用到了主对角线与上三角，而表s中仅用到了上三。六个矩阵相乘所需的标量乘法的最少次数为ml, 6=15 125。在加了阴影的表项中，在第9行中计算下式时，具有相同阴影程度的对被放在一起。 步骤4：构造一个最优解虽然MATRIX-CHAIN-ORDER确定了计算矩阵链乘积所需的最优标量乘法次数，但它没有直接说明如何对这些矩阵进行相乘。利用保存在表格sln, 1n内的、经过计算的信息来构造一个最优解并不难。在每一个表项si, j中，记录了对乘积AiAi+1.Aj在Ak与Ak+l之间，进行分裂以取得最优加全部括号时的k值。由此可知，按最优方式计算A1n时，最终矩阵相乘次序是A1s1,nAs1,n+1.n。之前的矩阵乘法可以递归地进行，因为sl,sl,n决定计算A1s1,n中最后的矩阵乘法，而ssl，n+l，n则决定计算As1,n+1.n中最后的矩阵乘法。下面的递归过程在给定由MATRIX-CHAIN-ORDER计算出的表s以及下标i和j后，输出的一个最优加全部括号形式。初始调用PRINT-OPTIMAL-PARENS(s，l，n)输出的一个最优加全部括号形式。PRINT-OPTIMAL-PARENS(s, i, j)1 if i = j2 then print Ai3 else print (4 PRINT-OPTIMAL-PARENS(s, i, si, j)5 PRINT-OPTIMAL-PARENS(s, si, j + 1, j)6 print )在图15-3的例子中，调用PRINT-OPTINtAL- PARENS(s,1,6)输出加全部括号(Al(A2A3)(A4A5)A6)。练习15. 2-1对维数为序列的各矩阵，找出其矩阵链乘积的一个最优加全部括号。15- 2-2 请给出一个递归算法MATRIX-CHAIN-MULTIPLY(A，s，i，j)，使之在给出矩阵序列，和由MATRIX-CHAIN-ORDER计算出的表s，以及下标i和j后，能得出一个最优的矩阵链乘法。(初始调用为MATRIX-CHAIN-MULTIPLY(A，s，1，n)。15. 2-3 使用替换法证明递归公式(15. 11)的解为C(2n)。152-4 设R(i, j)表示在调用MATRIX-CHAIN-()RDER中计算其他表项时，表项mi,j被引用的次数。证明：对整个表总的引用次数为(提示：可以利用等式(A.3)。)15. 2-5 证明：一个含n个元素的表达式的加全部括号中恰有n-l对括号。15.3 动态规划基础虽然我们刚刚讨论过动态规划方法的两个例子，但读者对什么时候可以应用这种方法可能仍然不一定很清楚。从工程的角度来看，什么时候才需要寻找一个问题的动态规划解？在本节中，我们要介绍适合采用动态规划方法的最优化问题中的两个要素：最优子结构和重叠子问题。另外，还要分析一种不同的方法，称为做备忘录( memoizaiion) 这并不是拼写错误这个单词确实是memoization，而不是memorization。memoization来源于memo，因为这个方法主要是记录一个值，以便以后可以搜索它。以充分利用重叠子问题性质。最优子结构用动态规划求解优化问题的第一步是描述最优解的结构。回顾一下，如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。当一个问题具有最优子结构时，提示我们动态规划可能会适用。（注意，在这种情况下，贪心策略可能也能适用的，参见第16章）。在动态规划中，我们利用子问题的最优解来构造问题的一个最优解。因此，必须小心以确保在我们所考虑的子问题范围中，包含了用于一个最优解中的那些子问题。到目前为止在本章讨论的两个子问题中，都发现了最优子结构。在15.1节中，可以看到在任何一条装配线上，通过装配站j的最快路线包含了在其中一条装配线上通过装配站j-l的最快路线。在15.2节，我们看到AiAi+1Aj的一个最优加全部括号把乘积在Ak和Ak+1之间分裂，它包含了加全部括号AiAi+1Ak和Ak+l Ak+2Aj问题的最优解。在找寻最优子结构时，可以遵循一种共同的模式：l)问题的一个解可以是做一个选择。例如，选择一个前一个装配线装配站；或者选择一个下标以在该位置分裂矩阵链。做这种选样会得到一个或多个有待解决的子问题。2)假设对一个给定的问题，已知的是一个可以导致最优解的选择。不必关心如何确定这个选择，尽管假定它是已知的。3)在已知这个选择后，要确定哪些子问题会随之发生，以及如何最好地描述所得到的子问题空间。4)利用一种“剪贴”( cut-and-paste)技术，来证明在问题的一个最优解中，使用的子问题的解本身也必须是最优的，通过假设每一个子问题的解都不是最优解，然后导出矛盾，即可做到这一点。特别地，通过“剪除非最优的子问题解再“贴上”最优解，就证明了可以得到原问题的一个更好的解，因此，这与假设已经得到一个最优解相矛盾。如果有多于一个的子问题的话，由于它们通常非常类似，所以只要对其中一个子问题的“剪贴”处理略加修改，即可很容易地用于其他子问题。为了描述子问题空间，可以遵循这样一条有效的经验规则，就是尽量保持这个空间简单，然后在需要时再扩充它。例如，在装配线阔度问题中，我们所考虑的子问题空间就是从工厂入口通过装配站S1, j和S2, j的最快路线。这个子问题空间很合适，因而没有必要再去尝试一个更具一般性的子问题空间了。相反地，在矩阵链乘积问题中，假设我们已经试图将子问题空间约束为形如A1A2Aj的矩阵乘积。如前所述，一个最优的加全部括号必定把乘积在Ak和Ak+l之间分开，对某个lkj。除非我们能保证k总是等于j-1不然会发现有形如A1A2Ak和Ak+1 Ak+2Aj的子问题，而且后者不是Al A2Aj的形式。对这个问题有必要允许子问题在“两端”变化，亦即允许i和j在子问题AiAi+1Aj中可以变化。最优子结构在问题域中以两种方式变化：l)有多少个子问题被使用在原问题的一个最优解中以及2)在决定一个最优解中使用哪些子问题时有多少个选择。在装配线调度问题中，一个最优解只使用了一子问题，但是，为确定一个最优解，我们必须考虑两种选择。为找出通过装配站Si, j的最快路线，我们使用通过S1, j-1或S2, j-1的最快路线；不管采用了哪一种，它都代表了必须最优解决的子问题。子链AiAi+1Aj的矩阵链乘法可作为有两个子问题和j-i个选择的一个例子。对一个在该处分离乘积的给定的矩阵Ak，可以分解出两个子问题，即加全部括号AiAi+1Ak和加全部括号Ak+1 Ak+2Aj，我们必须最优求解这两个子问题。一旦确定了子问题的最优解后，就从ji个候选者中选出那个下标k。非正式地，一个动态规划算法的运行时问依赖于两个因素的乘积：子问题的总个数和每一个子问题中有多少种选择。在装配线调度中，总共有个子问题，并且只有两个选择来检查每个子问题，所以执行时间为。对于矩阵链乘法，总共有个子问题，在每个子问题中又至多有n-1个选择，饵此执行时间为。动态规划以自底向上的方式来利用最优子结构。也就是说，首先找到子问题的最优解，解决子问题然后找到问题的一个最优解。寻找问题的一个最优解需要在子问题中做出选择，即选择将用哪一个来求解问题。问题解的代价通常是子问题的代价加上选择本身带来的开销。例如，在装配线调度问题中，首先要解决寻找通过装配站S1, j-1或S2, j-1的最快路线这一子问题，然后，选择其中一个装配站作为装配站Si, j的前一站。选择本身所带来的开销依赖于是否在装配站j-l与j之间转换装配线；如果停留在原装配线，则代价为ai, j；如果转换了装配线，则为ti, j-1+ai, j，其中。在矩阵链乘法问题中，首先要确定子链AiAi+1Aj的最优加全部括号，然后选择矩阵Ak正在该位置分裂乘积。选择本身所带来的开销为pi-1 pkpj项。第16章中将研究“贪心算法”，它与动念规划有着很多相似之处。特别地，贪心算法适用的问题也具有最优子结构。贪心算法与动态规划有一个显著的区别，就是在贪心算法中，是以自顶向下的方式使用最优结构的。贪心算法会先做选择，在当时看起来是最优的选择，然后再求解一个结果子问题，而小是先寻找子问题的最优解，然后再做选择。一些细微之处要注意在不能应用最优子结构的时候，就一定不能假设它能够应用。考虑下面两个问题，已知一个有向图G=(V, E)和结点u, vV。无权最短路径我们使用名词“无杈”( unweighted)与寻找带权边的最短路径问题相区别；第24、25章中将讨论这个问题，不带权值的问题可以利用第22章中的广度优先搜索技术求解。：找出一条从u到v的包含最少边数的路径。这样的一条路径必须是简单路径，因为从路径中去掉一个回路后，会产生边数更少的路径。无权量长简单路径：找出一条从u到v的包含最多边数的简单路径。我们需要加入简单性的要求，因为否则的话，就可以随意地遍历一个回路任意多次，来得到有任意多的边数的路径。无权最短路径问题具有如下的最优子结构。假设uv，因此这个问题是非平凡的。这样任何从u到v的路径p必定包含一个中间顶点，譬如w。（注意w可以是u或是v）。于是，可以将路径分解为子路径。显然，p上边的数目等于p1上边的数目加上p2上边的数目。我们断言，如果p是从u到v的最优（亦即最短）路径，那么p1必定是从u到w的一条最短路径。为什么呢？我们可以使用“剪贴”方法来进行论证，如果有另一条路径，例如从u到w有比pl更少的边，那么就可以剪下pl然后贴上，以构造比p有更少边的一条路径，而这与p是最优的相矛盾。对称地，p2必定是从w到v的一条最短路径。所以，通过考虑所有的中间顶点w，找出从u到w的一条最短路径和从w到v的一条最短路径，然后选择一个会产生整体最短路径的中间顶点w，来找出从u到v的一条最短路径。在25. 2节中，我们将使用这个最优子结构的一个变形，来找出在带权有向图中每一对顶点之间的最短路径。对无权最长简单路径的问题，假设它具有最优子结构。毕竟，如果将一条最长简单路径，分解成子路径，则pl一定不是从u到w的最长简单路径，p2一定不是从w到v的最长简单路径吗？答案是否定的！图15-4给出了一个例子。考虑路径qrt，这是从q到t的一条最长简单路径。q r是从q到r的一条最长简单路径吗？不是，因为qstr是一条更长的简单路径。rt是一条从r到t的最长简单路径吗？也不是，因为rqst是一条更长的简单路径。这个例子说明对于最长简单路径，不仅缺乏最优子结构，而且无法根据子问题的解来构造问题的一个“合法”解。如果把最长简单路径qstr和rqst合并，得到路径qstrqst，这不是简单路径。确实，在寻找一条无权最长简单路径的问题中，没有显示其具有任何类型的最优子结构。这个问题还没有找到高效率的动态规划算法。事实上，这个问题是NP完全的（这一点将在第34章中看到），即意味着它不可能在多项式时间内解决。为什么最长简单路径的子结构与最短路径的子结构有如此不同呢？虽然在最长和最短路径问题的解中都使用两个子问题，但是在寻找最长简单路径中子问题不是独立的，而在最短路径问题中它们是独立的。子问题独立是什么意思？意思是一个子问题的解不会影响同一问题中另外一个子问题的解。对于图15-4中的例子，找出从q到r的最长简单路径的问题有两个问题：找出从q到r以及从r到t的最长简单路径。对第一个子问题，我们选择路径qstr，因此使用了顶点s和t。在第二个子问题中就不能再使用这些顶点了，因为合并两个子问题的解会得到一个非简单的路径。如果在第二个子问题中不能使用顶点t，那我们就根本无法求解这个子问题，因为t必须在我们要寻找的路径上，而且它不是“接合”两个子问题的解的顶点(此顶点为r)。在一个子问题解中使用顶点s和t，会避免它们在另一个子问题中被使用。但是，我们必须使用这两个顶点中的至少一个，才能求解另外一个子问题，并且，只有同时使用它们，才能求得最优解。因此，我们说这些子问题不是相互独立的。用另外一种方式看，在求解一个子问题时，我们对资源的使用(资源即顶点)使得它们无法被另一个子问题所使用。图15-4 一个有向图，它说明了在一个无权有向图中寻找一条最长简单路径的问题没有最优子结构。路径qrt是从q到t的一条最长简单路径，但是子路径qr不是从q到r的一条最长简单路径，子路径rt也不是从r到t的一条最长简单路径那么为什么在寻找最短路径中子问题是独立的呢？回答是子问题本来就没有共享资源。我们断言，如果顶点w在从u到v的一条最短路径p上，那么我们可以接合的任意最短路径和的任意最短路径来产生一条从u到v的最短路径。我们确信，除了w之外，没有顶点可以同时出现在路径p1和p2上。为什么呢？假设有某个顶点xw同时出现在路径p1和p2上，则可以把p1分解为，以及将p2分解为。根据这个问题的最优子结构，路径p