第四章 动态规划-old

计算机算法设计与分析NorthChinaElectricPowerUniversityComputerAlgorithmsDesign&Analysis华北电力大学计算机科学与工程系Dept.ofComputerScience&EngineeringofNorthChinaElectricPowerUniversity第四章动态规划法NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity§1引言最短路径问题：

现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图所示，试找出从结点A到结点E的最短距离。可以用搜索法来解决此问题，该问题的递归式为其中

是与v相邻的节点的集合，w(v,u)表示从v到u的边的长度。NorthChinaElectricPowerUniversityintMinDistance(intv){if(v==E)return0else{min=maxint;for所有没有访问过的节点i{ifv和i相邻{标记i访问过了;t=v到i的距离+MinDistance(i);标记i未访问过;if(t<min)min=t;}}}}

开始时标记所有的顶点未访问过，MinDistance(A)就是从A到E的最短距离。可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间复杂度为O(n!)，这是一个“指数级”的算法。NorthChinaElectricPowerUniversity观察一下这个算法。在求从B1到E的最短距离的时候，先求出从C2到E的最短距离；而在求从B2到E的最短距离的时候，又求了一遍从C2到E的最短距离。也就是说，从C2到E的最短距离我们求了两遍。同样可以发现，在求从C1、C2到E的最短距离的过程中，从D1到E的最短距离也被求了两遍。而在整个程序中，从D1到E的最短距离被求了四遍。如果在求解的过程中，同时将求得的最短距离"记录在案"，随时调用，就可以避免这种情况。于是，可以改进该算法，将每次求出的从v到E的最短距离记录下来，在算法中递归地求MinDistance(v)时先检查以前是否已经求过了MinDistance(v)，如果求过了则不用重新求一遍，只要查找以前的记录就可以了。这样，由于所有的点有n个，因此不同的状态数目有n个，该算法的数量级为O(n)。更进一步，可以将这种递归改为递推，这样可以减少递归调用的开销。NorthChinaElectricPowerUniversity可以发现，A只和Bi相邻，Bi只和Ci相邻,...，依此类推。这样，可以将原问题的解决过程划分为4个阶段，设S1={A},S2={B1,B2},S3={C1,C2,C3,C4},S4={D1,D2,D3}，Fk(u)表示从Sk中的点u到E的最短距离，则并且有边界条件：

显然可以递推地求出F1(A)，也就是从A到E的最短距离。这种算法的复杂度为O(n)，因为所有的状态总数（结点总数）为n，对每个状态都只要遍历一次，而且程序很简洁。NorthChinaElectricPowerUniversity动态规划算法描述如下：voidDynamicProgramming(){F5[E]:=0;for(i=4;i>0;i--){foreachu∈Sk{Fk[u]:=maxint;foreachv∈Sk+1∩δ(u)ifFk[u]>w(u,v)+Fk+1[v]Fk[u]:=w(u,v)+Fk+1[v];}}输出F1[A];}其中，δ(u)表示和u邻接的顶点的集合。这种高效算法，就是动态规划算法。NorthChinaElectricPowerUniversity§2动态规划的基本概念

动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著DynamicProgramming，这是该领域的第一本著作。多阶段决策问题多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。NorthChinaElectricPowerUniversity动态规划模型的基本要素1.阶段阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k=1,2,..,n表示。2.状态状态(state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后向性，即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。描述状态的变量称状态变量(statevariable)。变量允许取值的范围称允许状态集合(setofadmissiblestates)。用xk表示第k阶段的状态变量，它可以是一个数或一个向量。用Xk表示第k阶段的允许状态集合。在引言的例子中x2可取B1，B2，X2={B1,B2}。n个阶段的决策过程有n+1个状态变量，xn+1表示xn演变的结果，在引言的例子中x5取E。NorthChinaElectricPowerUniversity3.决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策(decision)。描述决策的变量称决策变量(decisionvariable)。变量允许取值的范围称允许决策集合(setofadmissibledecisions)。用uk(xk)表示第k阶段处于状态xk时的决策变量，它是xk的函数，用Uk(xk)表示了xk的允许决策集合。在引言的例子中u2(B1)可取C1,C2,C3。决策变量简称决策。4.策略决策组成的序列称为策略(policy)。由初始状态x1开始的全过程的策略记作p1n(x1)，即p1n(x1)={u1(x1),u2(x2),...，un(xn)}。由第k阶段的状态xk开始到终止状态的后部子过程的策略记作pkn(xk)，即pkn(xk)={uk(xk),uk+1(xk+1),...，un(xn)}。类似地，由第k到第j阶段的子过程的策略记作pkj(xk)={uk(xk),uk+1(xk+1),...，uj(xj)}。对于每一个阶段k的某一给定的状态xk，可供选择的策略pkj(xk)有一定的范围，称为允许策略集合(setofadmissiblepolicies)，用P1n(x1),Pkn(xk),Pkj(xk)表示。NorthChinaElectricPowerUniversity5.状态转移方程在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程(equationofstate)表示这种演变规律，写作：引言中例子的状态转移方程为：xk+1=uk(xk)6.指标函数和最优值函数指标函数(objectivefunction)是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段k到阶段n的指标函数用Vkn(xk,pkn(xk))表示，k=1,2,...,n。能够用动态规划解决的问题的指标函数应具有可分离性，即Vkn可表为xk,uk,Vk+1n的函数，记为：例：某工厂拟在今后三年内购买某种设备5台，考虑到设备维护、现金贴现等各种因素后，预计在第一、第二、第三年初购买该设备可获纯利润如下表所示。问如何指定购买计划才能使该厂获得最大利润。纯利与购买设备时间、台数的关系万元设

备

台

数

012345设备

购买

时

间

第一年初

第二年初

第三年初

037912130510111111046111212解：为应用动态规划方法求解，先应明确一下问题：1)以购买设备时间为顺序，将问题划分成3个阶段；2)引进4个状态变量x1,x2,x3,x4，其中，xk(k=1,2,3,4)表示第k年初至第三年末可购买的设备台数，并且规定上一年末与下一年初为同一时刻；NorthChinaElectricPowerUniversity3)决策变量yk表示第k年初购买设备台数；4)状态转移方称为xk+1=xk-yk;5)阶段指标Pk(yk)表示第k年购买yk台设备所获纯利润；最优指标函数fk(xk)表示第k年初至第三年末购买xk台设备所能获得的最大利润;6)由以上所设可得本题的动态规划的基本方程为：由上式可得k=2时，对应x2=0、1、2、3、4、5可分别计算如下：NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity§4动态规划的适用条件1.最优化原理（最优子结构性质）

一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

例如上图中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。这可用反证法证明：假设有另一路径J'是B到C的最优路径，则A到C的路线取I和J'比I和J更优，矛盾。从而证明J'必是B到C的最优路径。NorthChinaElectricPowerUniversity

最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。动态规划的最优化理在其指标函数的可分离性和单调性中得到体现。根据最优化原理导出的动态规划基本方程是解决一切动态规划问题的基本方法。2.无后向性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。如果用前面的记号来描述无后向性，就是：对于确定的xk，无论p1,k-1如何，最优子策略pkn*是唯一确定的，这种性质称为无后向性。NorthChinaElectricPowerUniversity3.子问题的重叠性

在引言的例子中我们看到，动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

设原问题的规模为n，容易看出，当子问题树中的子问题总数是n的超多项式函数，而不同的子问题数只是n的多项式函数时，动态规划法显得特别有意义，此时动态规划法具有线性时间复杂性。所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性。这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。NorthChinaElectricPowerUniversity§5动态规划的基本思想

前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解(即满足最优子化原理)，则可以考虑用动态规划解决。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。NorthChinaElectricPowerUniversity

因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。§6动态规划算法的基本步骤

设计一个标准的动态规划算法，通常可按以下几个步骤进行：划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。2.选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。NorthChinaElectricPowerUniversity

3.确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。

4.写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。

动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算.NorthChinaElectricPowerUniversity

但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：分析最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。根据计算最优值时得到的信息，构造一个最优解。

步骤(1)--(3)是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤(4)可以省略，若需要求出问题的一个最优解，则必须执行步骤(4)。此时，在步骤(3)中计算最优值时，通常需记录更多的信息，以便在步骤(4)中，根据所记录的信息，快速地构造出一个最优解。NorthChinaElectricPowerUniversity§7动态规划实例分析1)矩阵连乘问题问题描述给定n个矩阵{A1,A2,….An}，其中Ai与Ai+1是可乘的，我们要计算这n个矩阵的连乘积。连乘积的计算次序不同，计算连乘积的计算量也不同。NorthChinaElectricPowerUniversity§7动态规划实例分析1)矩阵连乘问题两个矩阵标准乘法：ra,ca和rb,cb分别表示矩阵A和B的行数和列数。voidmatrixMultiply(int**a,int**b,int**c,intra,intca,intrb,intcb){if(ca!=rb)error(“矩阵不可乘”)for(inti=0;i<ra;i++)for(intj=0;j<cb;j++){intsum=a[i][0]*b[0][j];for(intk=1;k<ca;k++)sum+=a[i][k]*b[k][j];c[i][j]=sum;}}NorthChinaElectricPowerUniversity§7动态规划实例分析1)矩阵连乘问题矩阵计算次序不同，对计算量有很大影响，如何计算才能确定一种最好的计算次序，使得最后的计算量最小？即矩阵连乘积的最优计算次序问题。方法1穷举搜索法找出所有可能的计算次序。然后计算出相应的乘法次数。这是不现实的！计算量太大，算法复杂性为指数级别。方法2动态规划法求解1、分析最优解的结构（问题是否具有最优子结构）A[i：j]表示矩阵AiAi+1….Aj原问题变为求A[1:n]的一个最优次序。矩阵Ai的维数为pi-1PiNorthChinaElectricPowerUniversity§7动态规划实例分析1)矩阵连乘问题2、建立递归关系设计算A[i][j]所需的最少乘法次数为m[i][j]，原问题最优解为m[1][n]。下面对m[i][j]分析：当i==j时A[i][j]为一个单个矩阵，无需计算当i<j时，假设最优次序是在Ak和Ak+1之间断开则m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj如何确定K的值呢？NorthChinaElectricPowerUniversity§7动态规划实例分析1)矩阵连乘问题3、计算最优值上述公式是一个递归公式，显然我们可以设计一个递归算法来计算m[1][n]，然而我们也会注意到问题的重复计算。我们可以由低向上来计算，在计算过程中，保存已经解决的子问题答案，每个子问题只计算一次，再后面计算时，只需要简单查一下即可。下面给出具体算法：输入参数{p0,p1,p2,….pn}存储在数组p中，S数组存储最优断开位置k的值。NorthChinaElectricPowerUniversity§7动态规划实例分析1)矩阵连乘问题3、计算最优值VoidMatrixChain(int*p,intn,int**m,int**s){for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++)//r为问题规模for(inti=1;i<=n-r+1;r++)//规模为r的子问题个数{intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}

}NorthChinaElectricPowerUniversity§7动态规划实例分析1)矩阵连乘问题4、构造最优解上述算法只是给出了一个最优值,并没有给出最优解.我们知道了所需要的最少乘法次数,但并不知道应该如何做才能达到这个效果.我们在构造最优值的同时,把最优断开位置k保存在数组s[][]中，我们可以利用它来构造最优解。我们可以利用类似于二叉树的后序遍历算法来实现。voidTraceback(inti,intj,int**s){if(i==j)return;Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout<<s[i][j];}NorthChinaElectricPowerUniversity动态规划法基本要素：1、最优子结构当前问题最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。2、子问题重叠用递归算法求解时，每次产生的子问题不是新问题，有些子问题被重复计算多次。动态规划法每个子问题只解一次。动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

NorthChinaElectricPowerUniversity

设原问题的规模为n，容易看出，当子问题树中的子问题总数是n的超多项式函数，而不同的子问题数只是n的多项式函数时，动态规划法显得特别有意义，此时动态规划法具有线性时间复杂性。所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性。这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。看看用普通递归算法解矩阵连乘积最优计算次序问题。NorthChinaElectricPowerUniversityIntRecurMatrixChain(inti,intj){if(i==j)return0;intu=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}returnu;}

NorthChinaElectricPowerUniversity§7动态规划实例分析3、备忘录方法备忘录方法是动态规划法的一个变形。备忘录方法往往用一个表格或者数组把已经解决的子问题保存起来，下次解时，察看该子问题的解，而不必计算，备忘录方法采用的是由顶向下的方式，动态规划法采用的是由低向上的方式，备忘录方法的控制结构与递归算法相同。区别仅在于在递归解决之前先看看问题是否已经解决。初始时，我们可以为每一个子问题建立一个记录项，存入一个特殊值，表示子问题尚未解决。求解过程中，看该记录项是否为特殊值，如果是，则该子问题第一次求解，解决并保存，反之，则说明已经解决过，可以直接使用。intMemorizedMatrixChain(intn,int**m,int**s){for(inti=1;i<=n;i++)for(intj=i;j<=n;j++)m[i][j]=0returnLookupChain(1,n);}

NorthChinaElectricPowerUniversity§7动态规划实例分析3、备忘录方法

IntLookupChain(inti,intj){if(m[i][j]>0)returnm[i][j]if(i==j)return0;intu=LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}m[i][j]=u;returnu;}

NorthChinaElectricPowerUniversity§7动态规划实例分析1)生产计划问题问题描述工厂生产某种产品，每单位(千件)的成本为1(千元)，每次开工的固定成本为3(千元)，工厂每季度的最大生产能力为6(千件)。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4(千件)。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本(少付固定成本费)，但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5(千元)。还规定年初和年末这种产品均无库存。试制订一个生产计划，即安排每个季度的产量，使一年的总费用(生产成本和存储费)最少。NorthChinaElectricPowerUniversity

这是一个明显的多阶段问题，我们按照计划时间自然划分阶段，状态定义为每阶段开始时的存储量xk，决策为每个阶段的产量uk，记每个阶段的需求量（已知）为dk，则状态转移方程为：

设每个阶段开工固定成本费用为a，生产单位数量产品的成本为b，每阶段单位数量产品的存储费用为ｃ，阶段指标为阶段的生产成本费用和存储费用之和，即：

指标函数Vkn为vk之和，最优值函数fk(xk)为从第k阶段的状态xk出发到过程终结的最小费用，满足NorthChinaElectricPowerUniversity

其中允许决策集合Uk由每阶段的最大生产能力决定，设过程终结时允许存储量为x0n+1，则终端条件为：§8最长公共子序列问题描述：一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=<x1,x2,…,xm>，则另一序列Z=<z1,z2,…,zk>是X的子序列是指存在一个严格递增的下标序列<i1,i2,…,ik>，使得对于所有j=1,2,…,k有

例如，序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列，相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>，则序列<B,C,A>是X和Y的一个公共子序列，序列<B,C,B,A>也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。NorthChinaElectricPowerUniversity最长公共子序列(LCS)问题：给定两个序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>，要求找出X和Y的一个最长公共子序列。1.最长公共子序列的结构

解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列{1,2,…,m}的一个子序列，因此，X共有2m个不同子序列，从而穷举搜索法需要指数时间。事实上，最长公共子序列问题也有最优子结构性质。NorthChinaElectricPowerUniversity定理:LCS的最优子结构性质设序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的一个最长公共子序列Z=<z1,z2,…,zk>，则：若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；2.若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列；3.若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。其中Xm-1=<x1,x2,…,xm-1>，Yn-1=<y1,y2,…,yn-1>，Zk-1=<z1,z2,…,zk-1>。证明:用反证法。若zk≠xm，则<z1,z2,…,zk,xm>是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加在其尾部将产生X和Y的一个长度大于k的公共子序列。此为矛盾。故Zk-1是Xm-1和Yn-1的一个最长公共子序列。NorthChinaElectricPowerUniversity2.由于zk≠xm，Z是Xm-1和Y的一个公共子序列。若Xm-1和Y有一个长度大于k的公共子序列W，则W也是X和Y的一个长度大于k的公共子序列。这与Z是X和Y的一个最长公共子序列矛盾。由此即知Z是Xm-1和Y的一个最长公共子序列。3.与2.类似。这个定理告诉我们，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。2.子问题的递归结构由最长公共子序列问题的最优子结构性质可知，要找出X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。NorthChinaElectricPowerUniversity由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。与矩阵连乘积最优计算次序问题类似，我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=<x1,x2,…,xi>，Yj=<y1,y2,…,yj>。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。其他情况下，由定理可建立递归关系如下：NorthChinaElectricPowerUniversity3.计算最优值

直接利用上式容易写出一个计算c[i,j]的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>作为输入。输出两个数组c[0..m,0..n]和b[1..m,1..n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于c[m,n]中。NorthChinaElectricPowerUniversityvoidLcs_length(charx[],chary[]);

{m=length[x];

n=length[y];

for(inti=1;i<=m;i++)c[i][0]=0;

for(intj=1;j<=n;j++)c[0][j]=0;

for(i=1;i<=m;i++)

{for(j=1;j<=n;j++)

if(x[i]==y[j])

{c[i][j]=c[i-1][j-1]+1;b[i][j]="↖";}

elseif(c[i-1][j]≥c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]="↑";}

else

{c[i][j]:=c[i][j-1];b[i][j]="←“;}

}

}算法描述如下：NorthChinaElectricPowerUniversity4.构造最长公共子序列

由算法Lcs_length计算得到的数组b可用于快速构造序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的最长公共子序列。首先从b[m,n]开始，沿着其中的箭头所指的方向在数组b中搜索。当b[i,j]中遇到"↖"时，表示Xi与Yj的最长公共子序列是由Xi-1与Yj-1的最长公共子序列在尾部加上xi得到的子序列；当b[i,j]中遇到"↑"时，表示Xi与Yj的最长公共子序列和Xi-1与Yj的最长公共子序列相同；当b[i,j]中遇到"←"时，表示Xi与Yj的最长公共子序列和Xi与Yj-1的最长公共子序列相同。

下面的算法LCS(b,X,i,j)实现根据b的内容打印出Xi与Yj的最长公共子序列。通过算法的调用LCS(X,length[X],length[Y])，便可打印出序列X和Y的最长公共子序列。NorthChinaElectricPowerUniversityvoidLCS(X,i,j);

{if((i==0)||(j==0)return;

if(b[i][j]=="↖")

{LCS(X,i-1,j-1);

cout<<x[i];{打印x[i]}

}elseif(b[i][j]=="↑")LCS(b,X,i-1,j)elseLCS(b,X,i,j-1);

}NorthChinaElectricPowerUniversityj0123456iyjBDCABA┌─────────────┐0xi│000000││↑↑↑↖↖│1A│00001←11││↖↑↖│2B│01←1←112←2││↑↑↖↑↑│3C│0112←222││↖↑↑↑↖│4B│011223←3││↑↖↑↑↑↑│5D│0122233││↑↑↑↖↑↖│6A│0122334││↖↑↑↑↖↑│7B│0122345│└─────────────┘

j0123456iyjBDCABA┌─────────────┐0xi│000000││↑↑↑↖↖│1A│00001←11││↖↑↖│2B│01←1←112←2││↑↑↖↑↑│3C│0112←222││↖↑↑↑↖│4B│011223←3││↑↖↑↑↑↑│5D│0122233││↑↑↑↖↑↖│6A│0122334││↖↑↑↑↖↑│7B│0122345│└─────────────┘

j0123456iyjBDCABA┌─────────────┐0xi│000000││↑↑↑↖↖│1A│00001←11││↖↑↖│2B│01←1←112←2││↑↑↖↑↑│3C│0112←222││↖↑↑↑↖│4B│011223←3││↑↖↑↑↑↑│5D│0122233││↑↑↑↖↑↖│6A│0122334││↖↑↑↑↖↑│7B│0122345│└─────────────┘

例如，设所给的两个序列为X=<A，B，C，B，D，A，B>和Y=<B，D，C，A，B，A>。由算法LCS_LENGTH和LCS计算出的结果如图所示。NorthChinaElectricPowerUniversity问题描述：多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点赋予一个整数值，每条边赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。游戏第1步，将一条边删除；随后n-1步按以下方式操作：1)选择一条边E以及由E连接着的两个顶点v1和v2；2)用一个新的顶点取代边E以及由E连接着的两个顶点v1和v2，将顶点v1和v2的整数值通过边E上的运算得到的结果赋予新顶点。最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上整数值。编程任务：

对于给定的多边形，编程计算出最高分，并且列出所有得到这个最高得分首次被删除的边的序号。NorthChinaElectricPowerUniversity§9多边形游戏1.最优子结构性质设所给的多边形的顶点和边的顺时针序列为op[1],v[1],op[2],v[2],…,op[n],v[n]其中，op[i]表示第i条边所相应的运算符，v[i]表示第i个顶点上的数值，i=1,2,..,n。在所给多边形中，从顶点i开始,长度为j(链中有j个顶点)的顺时针链p(i,j)可表示为:v[i],op[i+1],…,v[i+j-1]如果这条链的最后一次合并运算在op[i+s]处发生(1≤s≤j-1),则可在op[i+s]处将链分割为两个子链p(i,s)和p(i+s,j-s)。设m1时对子链p(i,s)的任意一种合并方式得到的值，而a,b分别是在所有可能的合并中得到的最小值和最大值。m2是p(i+s,j-s)的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有：a≤m1≤b,c≤m2≤d

由于子链p(i,s)和p(i+s,j-s)的合并方式决定了p(i,j)在op[i+s]处断开后的合并方式，在op[i+s]处合并后其值为:NorthChinaElectricPowerUniversitym=(m1)op[i+s](m2)1)当op[i+s]=‘+’时，显然有a+c≤b+d。

换句话说，由链p(i,j)合并的最优性可推出子链p(i,s)和p(i+s,j-s)的最优性，且最大值对应于子链的最大值，最小值对应于子链的最小值。2)当op[i+s]=‘*’时，情况有所不同。

由于v[i]可取负整数，子链的最大值相乘未必能得到主链的最大值。但我们注意到最大值一定在边界点达到，即min{ac,ad,bc,bd}≤m≤max{ac,ad,bc,bd}

换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。例如，当m=ac时，最大主链由两个最小子链组成；同理当m=bd时，最大主链由它的两个最大子链组成。无论哪种情形发生，由主链的最优性均可推出子链的最优性。

综上所述，可知多边形游戏问题满足最优子结构性质。NorthChinaElectricPowerUniversity2.递归求解由前面的分析可知，为了求链合并的最大值，必须同时求子链合并的最大值和最小值。因此在整个计算过程中，应同时计算最大值和最小值。

设m[i,j,0]是链p(i,j)合并的最小值，而m[i,j,1]是最大值。若最优合并在op[i+s]处将p(i,j)分为2个长度小于j的子链p(i,s)和p(i+s,j-s)，且从顶点i开始的长度小于j的子链的最大值和最小值均已计算出。为叙述方便，记：

a=m[i,s,0],b=m[i,s,1],c=m[i+s,j-s,0],d=m[i+s,j-s,1]。1)当op[i+s]=‘+’时，m[i,j,0]=a+cm[i,j,1]=b+d2)当op[i+s]=‘*’时，

m[i,j,0]=min{ac,ad,bc,bd}m[i,j,1]=max{ac,ad,bc,bd}综合(1)和(2)，将p(i,j)在op[i+s]处断开的最大值记为maxf(i,j,s)，最小值记为minf(i,j,s),则NorthChinaElectricPowerUniversityminf(i,j,s)=a+cop[i+s]=‘+’min{ac,ad,bc,bd}op[i+s]=‘*’maxf(i,j,s)=b+dop[i+s]=‘+’max{ac,ad,bc,bd}op[i+s]=‘*’由于最优断开位置s有1≤s≤j-1的j-1种情况，由此可知初始值显然为m[i,1,0]=v[i]1≤i≤nm[i,1,1]=v[i]1≤i≤n由于多边形是封闭的，在上面的计算中，当i+s>n时，顶点i+s实际编号为(i+s-1)%n+1。按上述递推关系计算出的m[i,n,1]即为游戏首次删去第i条边后得到的最大值。NorthChinaElectricPowerUniversity算法描述如下(求得minf(i,j,s)和maxf(i,j,s))voidMin_max(intn,inti,ints,intj,int&minf,int&maxf){inte[4];inta=m[i][s][0],b=m[i][s][1],r=(i+s-1)%n+1;intc=m[r][j-s][0];intd=m[r][j-s][1];if(op[r]==‘t’){minf=a+c;maxf=b+d;}else{e[1]=a*c;e[2]=a*d;e[3]=b*c;e[4]=b*d;minf=e[1];maxf=e[1];for(intr=2;r<5;r++){if(minf>e[r])minf=e[r];if(maxf>e[r])maxf=e[r];}}}NorthChinaElectricPowerUniversityintPoly_max(intn){intminf,maxf;for(intj=2;j<=n;j++)//链中有j个顶点的时候for(inti=1;i<=n;i++)//链以顶点i为开始结点时for(ints=1;s<j;s++)//s的取值范围为1<=s<=j-1{Min_max(n,i,s,j,minf,maxf);if(m[i][j][0]>minf)m[i][j][0]=minf;if(m[i][j][1]<maxf)m[i][j][1]=maxf;}inttemp=m[1][n][1];for(inti=2;i<=n;i++)if(temp<m[i][n][1])temp=m[i][n][1];returntemp;}算法的时间复杂性为O(n3)。NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity拦截导弹(问题来源:1999年全国青少年信息学(计算机)奥林匹克分区联赛)

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,并依次输出被拦截的导弹飞来时候的高度.例如:INPUT

38920715530029917015865

OUTPUT

6(最多能拦截的导弹数)

38930029917015865

NorthChinaElectricPowerUniversity因为只有一套导弹拦截系统,并且这套系统除了第一发炮弹能到达任意高度外,以后的每一发炮弹都不能高于前一发炮弹的高度;所以,被拦截的导弹应该按飞来的高度组成一个非递增序列.题目要求我们计算这套系统最多能拦截的导弹数,并依次输出被拦截导弹的高度,实际上就是要求我们在导弹依次飞来的高度序列中寻找一个最长非递增子序列.NorthChinaElectricPowerUniversity问题描述：

给定由n个整数（可能为负整数）组成的序列a1,a2,…an，求该序列形如的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。最优值为max{0,max}其中1<=i<=j<=n

§10最大子段和问题NorthChinaElectricPowerUniversity

1、简单算法对所有的子段和进行比较，取得最大值，并记录取最大值时的i值和j值。§10最大子段和问题算法描述如下：intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++)for(intj=i;j<=n;j++){intthissum=0;for(k=i;k<=j;k++)thissum+=a[k];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}returnsum;}算法的时间复杂性为O(n3)。NorthChinaElectricPowerUniversity

2、算法该进仔细观察算法本身，可以把最内层for循环去掉§10最大子段和问题算法描述如下：intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++){intthissum=0;for(intj=i;j<=n;j++){thissum+=a[j];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}}returnsum;}算法的时间复杂性为O(n2)。NorthChinaElectricPowerUniversity3、分治算法

§10最大子段和问题算法描述如下：intMaxSubSum(intn,int*a,intleft,intright){intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{intcenter=(left+right)/2;intleftsum=MaxSubSum(a,left,center);intrightsum=MaxSubSum(a,center+1,right);ints1=0;intlefts=0;for(inti=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}

NorthChinaElectricPowerUniversity3、分治算法

§10最大子段和问题算法描述如下：ints2=0;intrights=0;for(inti=center+1;i<=right;i++){rights+=a[i];if(rights>s2)s2=rights;}sum=s1+s2;if(sum<leftsum)sum=leftsum;if(sum<rightsum)sum=rightsum;}returnsum;}T(n)=O(1)n<=c2T(n/2)+O(n)n>cT(n)=O(nlogn)NorthChinaElectricPowerUniversity4、动态规划算法

§10最大子段和问题算法描述如下：intMaxSum(intn,int*a){intsum=0;intb=0;for(inti=1;i<=n;i++){if(b>0)b+=a[i];elseb=a[i];if(b>sum)sum=b;}returnsum;}NorthChinaElectricPowerUniversity§110-1背包问题算法描述如下：

voidKnapsack(intv[],intw[],intc,intn,intm[6][N])

{

inti,j,jMax,k;

jMax=(w[n]-1<C;<span="">

for(i=0;i<=jMax;i++)

{

m[n][i]=0;

}

for(i=w[n];i<=c;i++)

{

m[n][i]=v[n];

}

NorthChinaElectricPowerUniversity

for(i=n-1;i>1;i--)

{

jMax=(w[i]-1<C;<span="">

for(j=0;j<=jMax;j++)

{

m[i][j]=m[i+1][j];

}

for(j=w[i];j<=c;j++)

{

k=j-w[i];

if(m[i+1][j]<M[I+1][K]+V[I])<span=""/>

m[i][j]=m[i+1][k]+v[i];

else

m[i][j]=m[i+1][j];

}

}

NorthChinaElectricPowerUniversity

m[1][c]=m[2][c];

if(c>=w[1])

{

k=c-w[1];

m[1][c]=(m[2][c]>m[2][k]+v[1])?m[2][c]:m[2][k]+v[1];

}

}

NorthChinaElectricPowerUniversity

voidTraceback(int**m,intw[],intc,intn,intx[])

{

inti;

for(i=1;i<n;i++)

{

if(m[i][c]==m[i+1][c])

x[i]=0;

else{

x[i]=1;

c-=w[i];

}

}

x[n]=(m[n][c])?1:0;

}

NorthChinaElectricPowerUniversity设f(T,2)表示对于一棵树T，在T的树根上布置守卫的情况下，监控T的全部节点所需的最少的费用；假设T的儿子节点为T1,T2,…,Tn；则我们可以得到递归公式：如果T的根不布置守卫，并且要求监控T的所有结点，则必须保证T的子结点中有一个结点Tk的根上布置了一个守卫，这样在Tk的根上的守卫可以同时看守T的根。至于T的其他子结点(i=1,2,..n,i≠k)，可以在树根上布置守卫，也可以不布置，但是必须监控住自己所有的结点(因为T的根上没有守卫)，因此选择最优的方案min{f(Ti,0),f(Ti,2)}。这样就得到了(1)式；如果T的根不布置守卫，并且要求监控除了T的根结点以外的其他全部节点，则必须保证T的所有的子结点Ti都被监控，而不用管Ti的根上是否有守卫。于是每个子节点Ti取最优的方案min{f(Ti,0),f(Ti,2)}。这样就得到了(2)式。

如果规定T的根布置了守卫，则T的所有的子结点上可以布置也可以不布置守卫，而且T的所有的子结点Ti的根原来可以被监控也可以不被监控，这是因为如果原来Ti的根没有被监控，则可以被T的根上布置的那个守卫监控。因此Ti选择最优的方案min{f(Ti,0),f(Ti,1),f(Ti,2)}。这样就得到了(3)式,这里ω(T)表示在根结点T上布置守卫的代价。

如果T是整棵树的树根的话，只要求出f(T,0),f(T,2)取较小者就是结果。对于T没有儿子的情况（结点T为叶子），我们给出上面递归公式的边界条件：NorthChinaElectricPowerUniversity注意，这里我们做了一点特殊规定，因为根据前面对f(T,0)f(T,1)f(T,2)的定义可以知道，在T是叶子的情况下不在T的树根上布置守卫的情况下而要监控T的全部节点是不可能的，f(T,0)实际上是不存在的，但是为了使上面的公式(1)-(3)能够适用于边界条件，我们规定了(4)式对于T是叶子的情况成立。这并不影响公式(1)-(3)的正确性。(5)说明在T是叶子的情况下，不在T的树根上布置守卫的情况下并监控除了T的根结点以外的其他全部节点