动态规划

《算法设计与分析》结课作业-1-动态规划和分治算法一样，动态规划(dynamicprogramming)是通过组合子问题的解而解决整个问题的。从第2章已经知道，分治算法是指将整个问题划分成一些独立的子问题，递归地求解各子问题，然后合并子问题的解而得到原问题的解。与此不同，动态规划使用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。在这种情况下，若用分治法则会做许多不必要的工作，及重复的求解公共的子子问题。动态规划算法对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。动态规划通常应用于最优化问题。此类问题可能有很多种可行解。每个解有一个值，而我们希望找出一个具有最优(最大或最小)值的解。称这样的解为该问题的“一个”最优解(而不是“确定”的最优解)，因为可能存在多个取最优值的解。动态规划算法的设计可以分为如下4个步骤：1）描述最优解的结构。2）递归定义最优解的值。3）按自底向上的方式计算最优解的值。4）由计算出的结果构造一个最优解。第1~3步构成问题的动态规划解的基础。第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个装配站表示为jiS,。装配线1的第j个站(jS,1)和装配线2的第j个站(jS,2)执行相同的功能。然而，这些装配站是在不同的时间建造的，并且采用了不同的技术。因此，每个站上所需的时间是不同的，《算法设计与分析》结课作业-2-即使是在两条不同装配线相同位置的装配站上也是这样。我们把在装配站jiS,上所需的装配时间记为jia,。如图15.1所示，一个汽车底盘进入其中一条装配线，然后从每一站进行到下一站。底盘进入装配线i的进入时间为ie，装配完的汽车离开装配线i的离开时间为ix。在正常情况下，一旦一个底盘进入一条装配线后，它只会经过该条装配线。在相同的装配线中，从一个装配站到下一个装配站所花的时间可以忽略。偶尔会来一个特别急的订单，客户要求尽可能快地制造这些汽车。对这些加急的订单，底盘仍然依序经过n个装配站，但是工厂经理可以将部分完成的汽车在任何装配站上从一条装配线移到另一条装配线上。把已经通过装配站jiS,的一个底盘从装配线i移走所花的时间为ji,t，其中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个装配站表示为jiS,，在该站的装配时间是jia,。一个汽车底盘进入工厂，然后进入装配线i(i为l或2)，花费时间ie。在通过一条线的第j个装配站后，这个底盘来到任一条线的第(j+1)个装配站。如果它留在相同的装配线，则没有移动的开销；但是，如果在装配站jiS,后，它移动到了另一条线上．则花费时间jit,。在离开一条线的第n个装配站后，完成的汽车花费时间ix离开工厂。待求解的问题是确定应该在装配线1内选择哪些站、在装配线2内选择些站，才能使汽车通过工厂的总时间量小显然，当有很多个装配站时，用强力法(bruteforce)来极小化通过工厂装配线的时间是不可行的。如果给定一个序列，在装配线1上使用哪些站，在装配线2上使用哪些站，则可以在)(n时间内，很容易计算出一个底盘通过工厂装配线要花的时间。不幸的是，选择装配站的可能方式有2n中：可以把装配线1内使用的装配站集合看作{1,2,…,n}的一个子集，并注意到有2n个这样的子集。因此，要通过穷举所有可能的方式，然后计算每种方式花费的时间来确定最快通过工厂的路线，需要)2(n时间，这在n很大时是不可行的。《算法设计与分析》结课作业-3-图15-2a)一个装配问题的实例，代价标为ie、ji,a、ji,t以及ix。深阴影的路径表示通过工厂的最快方式b)a)中的fi[j]，f*，li[j]以及l*的实例的值步骤1：通过工厂最快路线的结构动态规划方法的第一个步骤是描述最优解的结构的特征。对于装配线调度问题，可以如下执行。考虑底盘从起始点到装配站j,1S的最快可能路线。如果j=1，则底盘能走的只有一条路线，所以很容易就可以确定它的装配站j,1S花费了多少时间。对于j=2,3,…,n，则有两种选择：这个底盘可能是从装配站1-j,1S直接到装配站j,1S，在相同的装配线上，从装配站j-1到j的时间是可以忽略的。或者，这个底盘可能来自装配站1-j,2S，然后再移动到装配站1-j,1S，移动的代价是1-j,2t。我们将分别考虑这两种可能性，后面可以看到，它们之间其实是有很多共性的。首先，假设通过装配站j,1S的最快路线通过了装配站1-j,1S。关键的一点是这个底盘必定是利用了最快的路线从开始点到装配站1-j,1S的。这是为什呢？如果存在一条更快的路线通过1-j,1S，我们就可以采用这条更快的路线，从而得到通过装配站j,1S的更快的路线：这就形成了矛盾。类似地，假设通过装配站j,1S的最快路线就是通过装配站1-j,2S。现在，我们注意到这个底盘必定是利用了最快的路线从开始点到装配站1-j,2S的。理由是相同的：如果有一条更快的通过装配站1-j,2S的路线，就可以采用这条更快的路线，从而得到通过装配站j,1S的更快的路线，这是一个矛盾。更一般地，对于装配线调度问题，一个问题的（找出通过装配站j,iS的最快路线）最优解包含了子问题（找出通过1-j,1S和1-j,2S的最快路线）的一个最优解。我们称这个性质为最优子结构，这是是否可以应用动态规划方法标志之一，具体会在15.3节中看到。下面利用最优子结构来说明，可以利用子问题的最优解来构造原问题的一个最优《算法设计与分析》结课作业-4-解。对于装配线调度问题，推理如下。观察一条通过装配站j,1S的最快路线，会发现它必定是经过装配线1或2上的装配站j-1。因此，通过装配站j,1S的最快路线只能是以下二者之一：通过装配站1-j,1S的最快路线，然后直接通过装配站j,1S；通过装配站1-j,2S的最快路线，从装配线2移动到装配线1，然后通过装配站j,1S。利用对称的推理是想，通过装配站j,2S的最快路线也只能是以下二者之一：通过装配站1-j,2S的最快路线，然后直接通过装配站j,2S；通过装配站1-j,1S的最快路线，从装配线1移动到装配线2，然后通过装配站j,2S。为了解决这个问题，即寻找通过任一条装配线上的装配站j的最快路线，我们解决它的子问题，即寻找通过两条装配线上的装配站j-1的最快路线。所以，对于装配线调度问题，通过建立子问题的最优解，就可以建议原问题某个实例的一个最优解了。步骤2：一个递归的解在动态规划方法中，第二个步骤是利用子问题的最优解来递归定义一个最优解的值。对于装配线的调度问题，我们选择在两条装配线上通过装配站j的最快路线的问题来作为子问题，j=1,2，…，n。令fi[j]表示一个底盘从起点到装配站j,iS的最快可能时间。我们的最终目标是确定底盘通过工厂的所有路线的最快时间，记为f*。底盘必须一路通过装配线1或2通过装配站n，然后到达工厂的出口。由于这些路线的较快者就是通过整个工厂的最快路线，有：)][,][min(*2211xnfxnff(15-1)要对f1[1]和f2[1]进行推理也是很容易的。不管在哪一条装配线上通过装配站1，底盘都是直接到达该装配站的。于是，laef,111]1[(15-2)laef,222]1[(15-3)现在来考虑如何计算fi[j]，其中j=2,3，…，n(i=l,2)。先来看一看f1[j]．前面说过，通过装配站j,1S的最快路线或者是通过装配站1-j,1S，然后直接通过装配站j,1S的最快路线，或者是通过装配站1-j,2S，从装配线2移动到装配线1．然后通过装配站j,1S的最快路线。在第一种情况中，有f2[j]=f1[j-1]+j,1a，而在后一种情况中，f1[j]=f2[j-1]+1-j,2t+j,1a。所以：)]1[,]1[min(][,11,22,111jjjatjfajfjf(15-4)其中j=2,3,…,n。对称地，有：)]1[,]1[min(][,21,11,222jjjatjfajfjf(15-5)《算法设计与分析》结课作业-5-其中j=2,3,…,n。合并公式(15.2)~公式(15.5)，得到递归公式：)]1[,]1[min(][,11,22,11,111jjjjatjfajfaejf(15-6))]1[,]1[min(][,21,11,22,222jjjjatjfajfaejf(15-7)图15-2b示出了图15-2a例子中的由等式(15.6)和等式(15.7)计算出的fi[j]值，以及f*的值。fi[j]的值就是子问题最优解的值。为了有助于跟踪最优解的构造过程，我们定义li[j]为装配线的编号（1或2），其中的装配站j-l被通过装配站j,iS的最快路线所使用。这里，i=l，2且j=2,3,…,n。（我们避免定义li[1]，因为在任一条装配线上都没有一个装配站在站l前面）。此外，还定义l*为这样的装配线，其内的装配站n被通过整个工厂的最快路线所使用。li[j]的值可以帮助找到一个最快的路线。利用图15-2b中所示的l*的值和li[j]，可以如下找到如图15-2a所示通过工厂的一条最快路线。从l*=l开始，使用装配站1,6S。现在看到l1[6]值为2，所以使用装配站2,5S。接着，可以看到l2[5]=2（使用装配站2,4S），l2[4]=1(装配站1,3S)．l1[3]=2（装配站2,2S），以及l2[2]=1（装配站1,1S）。步骤3：计算最快时间此时，写出一个递归算法来计算通过工厂的最快路线是一件简单的事情，它基于公式(15.1)以及递归式(15.6)和式(15.7)。这种递归算法有一个问题：它的执行时间是关于n的指数形式。要知道为什么，令ri(j)为递归算法中引用fi[j]的次数。由公式(15.1)，有1)()(21nrnr(15.8)由递归式(15.6)和式(15.7)得到)1()1()()(2121jrjrjrjr(15.9)其中j=1,2,…,n-l。练习15.1-2会要求读者证明ri[j]=2n-j。这样，单是f1[1]就被引用了2n-1次！如练习15.1-3要求读者证明的那样，引用所有fi[j]值的总次数为)2(n。如果在递归的方式中以不同的顺序来计算fi[j]的值，能做得更好。注意对于2j，fi[j]的每一个值仅依赖于f1[j-1]和f2[j-1]的值。通过以递增装配站编号j的顺序来计算fi[j]的值，即在图15-2b中从左到右，可以在)(n时间内计算出通过工厂的最快路线，以及其所花的时间。FASTES