动态规划

HUASHI3483

动态规划

动态规划的基本概念
动态规划的发展及研究内容
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

多阶段决策问题
多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。

例1是一个多阶段决策问题的例子，下面是另一个多阶段决策问题的例子：

[例2] 生产计划问题

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


决策过程的分类
根据过程的时间变量是离散的还是连续的，分为离散时间决策过程(discrete-time decision process)，即多阶段决策过程和连续时间决策过程(continuous-time decision process)；根据过程的演变是确定的还是随机的，分为确定性决策过程(deterministic decision process)和随机性决策过程(stochastic decision process)，其中应用最广的是确定性多阶段决策过程。

动态规划模型的基本要素
一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素：

1.阶段

阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k=1,2,..,n表示。在例1中由A出发为k=1，由Bi(i=1,2)出发为k=2，依此下去从Di(i=1,2,3)出发为k=4，共n=4个阶段。在例2中按照第一、二、三、四季度分为k=1,2,3,4，共4个阶段。

2.状态

状态(state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后向性，即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。

描述状态的变量称状态变量(state variable)。变量允许取值的范围称允许状态集合(set of admissible states)。用xk表示第k阶段的状态变量，它可以是一个数或一个向量。用Xk表示第k阶段的允许状态集合。在例1中x2可取B1，B2，X2={B1,B2}。

n个阶段的决策过程有n+1个状态变量，xn+1表示xn演变的结果，在例1中x5取E。

根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。

状态变量简称为状态。

3.决策

当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策(decision)，在最优控制问题中也称为控制(control)。

描述决策的变量称决策变量(decision variable)。变量允许取值的范围称允许决策集合(set of admissible decisions)。用uk(xk)表示第k阶段处于状态xk时的决策变量，它是xk的函数，用Uk(xk)表示了xk的允许决策集合。在例1中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)有一定的范围，称为允许策略集合(set of admissible policies)，用P1n(x1),Pkn(xk),Pkj(xk)表示。

5.状态转移方程

在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程(equation of state)表示这种演变规律，写作

在例1中状态转移方程为：xk+1=uk(xk)

6.指标函数和最优值函数

指标函数(objective function)是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段k到阶段n的指标函数用Vkn(xk,pkn(xk))表示，k=1,2,...,n。

能够用动态规划解决的问题的指标函数应具有可分离性，即Vkn可表为xk,uk,Vk+1 n 的函数，记为：

其中函数是一个关于变量Vk+1 n单调递增的函数。这一性质保证了最优化原理(principle of optimality)的成立，是动态规划的适用前提。

过程在第j 阶段的阶段指标取决于状态xj和决策uj，用vj(xj,uj)表示。阶段k到阶段n的指标由vj(j=k,k+1,..n)组成，常见的形式有：

阶段指标之和，即

阶段指标之积，即

阶段指标之极大(或极小)，即

这些形式下第k到第j阶段子过程的指标函数为Vkj(xk,uk,xk+1,...,xj+1)。可以发现，上述(3)-(5)三个指标函数的形式都满足最优性原理。在例1中指标函数为(3)的形式，其中vj(xj,uj)是边<xj,uj(xj)>的权（边的长度）,uj(xj)表示从xj出发根据决策uj(xj)下一步所到达的节点。

根据状态转移方程，指标函数Vkn还可以表示为状态xk和策略pkn的函数，即Vkn(xk,pkn)。在xk给定时指标函数Vkn对pkn的最优值称为最优值函数(optimal value function)，记作fk(xk)，即

其中opt可根据具体情况取max或min。上式的意义是，对于某个阶段k的某个状态xk，从该阶段k到最终目标阶段n的最优指标函数值等于从xk出发取遍所有能策略pkn所得到的最优指标值中最优的一个。

7.最优策略和最优轨线

使指标函数Vkn达到最优值的策略是从k开始的后部子过程的最优策略，记作pkn*={uk*,..un*},p1n*又是全过程的最优策略，简称最优策略(optimal policy)。从初始状态x1(=x1*)出发，过程按照p1n*和状态转移方程演变所经历的状态序列{x1*,x2*,..,xn+1*}称最优轨线(optimal trajectory)。

HUASHI3483

动态规划的基本定理和基本方程
动态规划发展的早期阶段，从简单逻辑出发给出了所谓最优性原理，然后在最优策略存在的前提下导出基本方程，再由这个方程求解最优策略。后来在动态规划的应用过程中发现，最优性原理不是对任何决策过程普遍成立，它与基本方程不是无条件等价，二者之间也不存在任何确定的蕴含关系。基本方程在动态规划中起着更为本质的作用。

[基本定理]

对于初始状态x1∈X1，策略p1n*={u1*,..un*}是最优策略的充要条件是对于任意的k,1<k<=n,有

[推论]

若p1n*∈P1n(x1)是最优策略，则对于任意的k,1<k<n，它的子策略pkn*对于由x1和p1,k-1*确定的以xk*为起点的第k到n后部子过程而言，也是最优策略。

上述推论称为最优化原理，它给出了最优策略的必要条件，通常略述为：不论过去的状态和决策如何，对于前面的决策形成的当前的状态而言，余下的各个决策必定构成最优策略。

根据基本定理的推论可以得到动态规划的基本方程：

其中是决策过程的终端条件，为一个已知函数。当xn+1只取固定的状态时称固定终端；当xn+1可在终端集合Xn+1中变动时称自由终端。最终要求的最优指标函数满足(10)式：
(9)式是一个递归公式，如果目标状态确定，当然可以直接利用该公式递归求出最优值（这种递归方法将在后文介绍，称作备忘录法），但是一般在实际应用中我们通常将该递归公式改为递推公式求解，这样一般效率会更高一些。

HUASHI3483

动态规划的适用条件
任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

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

图2

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

最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。动态规划的最优化理在其指标函数的可分离性和单调性中得到体现。根据最优化原理导出的动态规划基本方程是解决一切动态规划问题的基本方法。

可以看出，例1是满足最优化原理的。

2.无后向性
将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

如果用前面的记号来描述无后向性，就是：对于确定的xk，无论p1,k-1如何，最优子策略pkn*是唯一确定的，这种性质称为无后向性。

[例3] Bitonic旅行路线问题

欧几里德货郎担问题是对平面给定的n个点确定一条连结各点的、闭合的最短游历路线问题。图3(a)给出了七个点问题的解。Bitonic旅行路线问题是欧几里德货郎担问题的简化，这种旅行路线先从最左边开始，严格地由左至右到最右边的点，然后再严格地由右至左到出发点，求路程最短的路径长度。图3（b）给出了七个点问题的解。


图3

这两个问题看起来很相似。但实质上是不同的。为了方便讨论，我将每个顶点标记了号码。由于必然经过最右边的顶点7，所以一条路(P1-P2)可以看成两条路（P1-7）与(P2-7)的结合。所以，这个问题的状态可以用两条道路结合的形式表示。我们可以把这些状态中，两条路中起始顶点相同的状态归于一个阶段，设为阶段[P1,P2]。

那么，对于Bitonic旅行路线问题来说，阶段[P1,P2]如果可以由阶段[Q1,Q2]推出，则必须满足的条件就是1<Q1或P2<Q2。例如，阶段[3,4]中的道路可以由阶段[3,5]中的道路加一条边4-5得出，而阶段[3,5]的状态却无法由阶段[3,4]中的状态得出，因为Bitonic旅行路线要求必须严格地由左到右来旅行。所以如果我们已经知道了阶段[3,4]中的状态，则阶段[3,5]中的状态必然已知。因此我们可以说，Bitonic问题满足无后向性，可以用动态规划来解决。

有些问题乍一看好像有后向性，但如果按照某种合理的方式重新划分阶段，就可以发现其本质上是无后向性的，所以关键是阶段的合理划分，这一点将在动态规划的技巧中详细阐述。

3.子问题的重叠性
在例1中我们看到，动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。以Bitonic旅行路线问题为例，这个问题也可以用搜索算法来解决。动态规划的时间复杂度为O(n2)，搜索算法的时间复杂度为O(n!) ，但从空间复杂度来看，动态规划算法为O(n2)，而搜索算法为O(n)，搜索算法反而优于动态规划算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。

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

HUASHI3483

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

HUASHI3483

动态规划算法的基本步骤
设计一个标准的动态规划算法，通常可按以下几个步骤进行：

划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。
写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。
动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下：

标准动态规划的基本框架

1.  对fn+1(xn+1)初始化;    {边界条件}
2.  for k:=n downto 1 do
3.      for 每一个xk∈Xk do
4.        for 每一个uk∈Uk(xk) do
            begin
5.            fk(xk):=一个极值;                 {∞或－∞}
6.            xk+1:=Tk(xk,uk);                  {状态转移方程}
7.            t:=φ(fk+1(xk+1),vk(xk,uk));       {基本方程(9)式}
8.            if  t比fk(xk)更优 then fk(xk):=t; {计算fk(xk)的最优值}
           end;  
9.  t:=一个极值;                               {∞或－∞}
10. for 每一个x1∈X1 do
11.     if f1(x1)比t更优 then t:=f1(x1);       {按照10式求出最优指标}
12. 输出t;
但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：

分析最优解的性质，并刻划其结构特征。
递归地定义最优值。
以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
根据计算最优值时得到的信息，构造一个最优解。
步骤(1)--(3)是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤(4)可以省略，若需要求出问题的一个最优解，则必须执行步骤(4)。此时，在步骤(3)中计算最优值时，通常需记录更多的信息，以便在步骤(4)中，根据所记录的信息，快速地构造出一个最优解。

HUASHI3483

实例分析 最长公共子序列问题LCS
问题描述
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列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的公共子序列。

最长公共子序列(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个不同子序列，从而穷举搜索法需要指数时间。

事实上，最长公共子序列问题也有最优子结构性质，因为我们有如下定理：

定理: LCS的最优子结构性质

设序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一个最长公共子序列Z=<z1, z2, …, zk>，则：

若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；
若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；
若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的一个最长公共子序列。
由于zk≠xm，Z是Xm-1和Y的一个公共子序列。若Xm-1和Y有一个长度大于k的公共子序列W，则W也是X和Y的一个长度大于k的公共子序列。这与Z是X和Y的一个最长公共子序列矛盾。由此即知Z是Xm-1和Y的一个最长公共子序列。
与 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的一个最长公共子序列。

由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算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。其他情况下，由定理可建立递归关系如下：



3.计算最优值
直接利用(2.2)式容易写出一个计算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]中。

Procedure LCS_LENGTH(X,Y);begin  m:=length[X];  n:=length[Y];  for i:=1 to m do c[i,j]:=0;  for j:=1 to n do c[0,j]:=0;  for i:=1 to m do    for j:=1 to n do      if x=y[j] then        begin          c[i,j]:=c[i-1,j-1]+1;          b[i,j]:="↖";        end      else if c[i-1,j]≥c[i,j-1] then        begin          c[i,j]:=c[i-1,j];          b[i,j]:="↑";        end      else        begin          c[i,j]:=c[i,j-1];          b[i,j]:="←"        end;  return(c,b);end;
由于每个数组单元的计算耗费Ο(1)时间，算法LCS_LENGTH耗时Ο(mn)。

4.构造最长公共子序列
由算法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(b,X,length[X],length[Y])，便可打印出序列X和Y的最长公共子序列。

Procedure LCS(b,X,i,j);begin  if i=0 or j=0 then return;  if b[i,j]="↖" then    begin      LCS(b,X,i-1,j-1);      print(x); {打印x}    end  else if b[i,j]="↑" then LCS(b,X,i-1,j)
                      else LCS(b,X,i,j-1);end;
在算法LCS中，每一次的递归调用使i或j减1，因此算法的计算时间为O(m+n)。

例如，设所给的两个序列为X=<A，B，C，B，D，A，B>和Y=<B，D，C，A，B，A>。由算法LCS_LENGTH和LCS计算出的结果如图2所示。

　

   j  0  1  2  3  4  5  6  
i   yj  B  D  C  A  B  A  
  ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐
0 xi │   0  0  0  0  0  0 │
  │   ↑  ↑  ↑ ↖    ↖  │
1 A │ 0  0  0  0  1 ← 1  1 │
  │  ↖       ↑ ↖    │
2 B │ 0  1 ← 1 ← 1  1  2 ← 2 │
  │   ↑  ↑ ↖     ↑  ↑ │
3 C │ 0  1  1  2 ← 2  2  2 │
  │  ↖   ↑  ↑  ↑ ↖    │
4 B │ 0  1  1  2  2  3 ← 3 │
  │   ↑ ↖   ↑  ↑  ↑  ↑ │
5 D │ 0  1  2  2  2  3  3 │
  │   ↑  ↑  ↑ ↖   ↑ ↖  │
6 A │ 0  1  2  2  3  3  4 │
  │  ↖   ↑  ↑  ↑ ↖   ↑ │
7 B │ 0  1  2  2  3  4  5 │
  └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘

　
　

图2   算法LCS的计算结果

5.算法的改进
对于一个具体问题，按照一般的算法设计策略设计出的算法，往往在算法的时间和空间需求上还可以改进。这种改进，通常是利用具体问题的一些特殊性。

例如，在算法LCS_LENGTH和LCS中，可进一步将数组b省去。事实上，数组元素c[i,j]的值仅由c[i-1,j-1]，c[i-1,j]和c[i,j-1]三个值之一确定，而数组元素b[i,j]也只是用来指示c[i,j]究竟由哪个值确定。因此，在算法LCS中，我们可以不借助于数组b而借助于数组c本身临时判断c[i,j]的值是由c[i-1,j-1]，c[i-1,j]和c[i,j-1]中哪一个数值元素所确定，代价是Ο(1)时间。既然b对于算法LCS不是必要的，那么算法LCS_LENGTH便不必保存它。这一来，可节省θ(mn)的空间，而LCS_LENGTH和LCS所需要的时间分别仍然是Ο(mn)和Ο(m+n)。不过，由于数组c仍需要Ο(mn)的空间，因此这里所作的改进，只是在空间复杂性的常数因子上的改进。

另外，如果只需要计算最长公共子序列的长度，则算法的空间需求还可大大减少。事实上，在计算c[i,j]时，只用到数组c的第i行和第i-1行。因此，只要用2行的数组空间就可以计算出最长公共子序列的长度。更进一步的分析还可将空间需求减至min(m, n)。

HUASHI3483

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

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



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



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

其中允许决策集合Uk由每阶段的最大生产能力决定，设过程终结时允许存储量为x0n+1，则终端条件为：

将以上各式代入到标准动态规划的框架中，就可以求得最优解

itmwk

在目前设计算法最常用的几种方法
动态规划与与贪心法是用得非常多的
动态规划前提是要有最优子结构
也就是最优解的子问题同样也是最优解
他的思路一般是从若干个子问题的最优解中构造出最优解
由于存在子问题的重复调用问题
所以，从上至下的方法可能达到指数级的时间复杂度

贪心法的思路是从当前的数据结构中找一个局部的最优解
把他加到最后的解中
一步步的构造出最优解来

动态规划与贪心法都只是方法
所以，对于利用他们设计出来的算法
时间复杂度是不定的，有可能超多项式
还有，就是设计出来的解不一定是最优解
可能只是近似解
在近似算法中，很多都采用了贪心法，或者动态规划
也都达到了很好的近似度，与时间复杂度

itmwk

动态规划与网络流——动态规划是易设计易实现的算法
由于图的关系复杂而无序，一般难以呈现阶段特征（除了特殊的图如多段图--参见例一）
，因此动态规划在图论中的应用不多。但有一类图，它的点却是有序的，这就是无环有向
图。
在有向无环图中，我们可以对点进行拓扑排序，使其体现出有序的特征，从而据此划分阶
段。在有向无还图中求最短路径的算法，已经体现出了简单的动态规划思想。请看下面的
例子。
[例16] 单源最短路径问题
已知从A到J的路线及费用如上图，求从A到J的最小费用路线。
问题的分析和解答：
本问题没有明显的阶段划分，各点间没有一定的先后次序（请注意与例一不同），不能按
照最少步数来决定顺序，如从A到D走捷径需4，但A-C-D只需3，更优。看来图中出现回路，
不能实施动态规划。其实不然。细想一下，从A到J的最优策略，它每一部分也是最优的（
可以用反证法来证明），换言之，本题也具有最优化性质，只是阶段不明显而已。
对于这类问题，我们可以换个角度分析，构造算法。比较一下前面所讲的动态规划法，都
是以某个状态为终点，寻找到达次点的路径，然后比较优劣，确定此状态最优值。可是，
本题阶段不明显，各状态之间的道路会出现嵌套，故此法不能使用。变一下角度，每次都
以某个状态为起点，遍历由它引申出去的路径，等所有已知状态都扩展完了，再来比较所
有新状态，把值最小的那个状态确定下来，其它的不动。如上图，先从A出发，找到3个结
点B，D，C，费用为F（B）=3，F（D）=4，F（C）=2。因为F（B），F（D）都大于F（C），
那么可以确定：不可能再有路线从B或D出发到C，比A-C更优。这样F（C）的最优值便确定
了。可是，有没有路线从C出发到B或D，比A-B或A-D更优呢？还不清楚。继续下去，因为A
扩展完了，只有从C开始，得到A-C-D=3，A-C-F=3，于是F（D）的值被刷新了，等于3。现
在，有F（B）=F（D）=F（F）=3，于是，三点的最优值都确定下来了。然后以分别以三个
点为起点，继续找。以次类推，直到J点的最优值确定为止。
细心观察，其实本题的隐含阶段就是以各结点的最优值的大小来划分的，上述过程就是按
最优值从小到大前向动态规划。人们习惯上把此题归入到图论范畴中，并将上述方法称为
标号法。这个算法就是图论中著名的Dijkstra单源最短路径算法。
事实上，动态规划在图论中还有更多的应用，请看下例：
[例17]  N个人的街道问题
在街道问题（参见例7）中，若有N个人要从左下角走向右上角，要求他们走过的边的总长
度最大。当然，这里每个人也只能向右或向上走。下面是一个样例，左图是从出发地到目
的地的三条路径，右图是他们所走过的边，这些边的总长度为5 + 4 + 3 + 6 + 3 + 3 +
5 + 8 + 8 + 7 + 4 + 5 + 9 + 5 + 3 = 78（不一定是最大）。
这个题目是对街道问题的又一次扩展。仿照街道问题的解题方法，我们仍然可以用动态规
划来解决本题。不过这一次是N个人同时走，状态变量也就需要用N维向量来表示。相应的
，决策变量也要变成N维向量：
状态转移方程不需要做什么改动：
在写规划方程时，需要注意在第k阶段，N条路径所走过的边的总长度的计算，在这里用来
表示了：
边界条件为
可见将原来的动态规划算法移植到这个问题上来，在理论上还是完全可行的。但是，现在
的这个动态规划算法的时空复杂度已经是关于N的指数函数，只要N稍微大一点，这个算法
就不可能实现了。
下面我们换一个思路，将N条路径看成是网络中一个流量为N的流，这样求解的目标就是使
这个流的费用最大。但是本题又不同于一般的费用流问题，在每一条边e上的流费用并不是
流量和边权的乘积，而是用下式计算：
为了使经典的费用流算法适用于本题，需要将模型稍微转化一下：
如图，将每条边拆成两条,拆开后一条边上有权w0，但是容量限制为1；另一条边没有容量
限制，但是流过这条边就不计费用。这样我们就把问题转化成了一个标准的最大费用固定
流问题。
这个算法可以套用经典的最小费用最大流算法，在此就不细说了。
IOI97的“障碍物探测器”比这一题要复杂一些，但是基本思想是相似的。类似的题目还有
99年冬令营的“迷宫改造”。从这些题目中都可以看到动态规划和网络流的联系。
推广到一般情况，任何有向无环图中的费用流问题在理论上说，都可以用动态规划来解决
。对于流量为N（如果流量不固定，这个N需要事先求出来）的费用流问题，用N维的向量x
k=(xk,1,xk,2,…,xk,N)来描述状态，其中xk,i∈V , 1≤i≤N 。相应的，决策也用N维的
向量uk=(uk,1,uk,2,…,uk,N)来表示，其中uk,i∈E(xk,i) , 1≤i≤N ，E(v)表示指向v的
弧集。则状态转移方程可以这样表示：
规划方程为
边界条件为
在大多数情况下，动态规划的实现比网络流要简单的多。但是，由于N维动态规划算法是指
数级算法，因而在实现中的局限性很大，仅可用于一些N非常小的题目适用。

itmwk

动态规划与搜索——动态规划是高效率、高消费算法
同样是解决最优化问题，有的题目我们采用动态规划，而有的题目我们则需要用搜索。这
其中有没有什么规则呢？
我们知道，撇开时空效率的因素不谈，在解决最优化问题的算法中，搜索可以说是“万能
”的。所以动态规划可以解决的问题，搜索也一定可以解决。
把一个动态规划算法改写成搜索是非常方便的，状态转移方程、规划方程以及边界条件都
可以直接“移植”，所不同的只是求解顺序。动态规划是自底向上的递推求解，而搜索则
是自顶向下的递归求解（这里指深度搜索，宽度搜索类似）。
反过来，我们也可以把搜索算法改写成动态规划。状态空间搜索实际上是对隐式图中的点
进行枚举，这种枚举是自顶向下的。如果把枚举的顺序反过来，变成自底向上，那么就成
了动态规划。(当然这里有个条件，即隐式图中的点是可排序的)
正因为动态规划和搜索有着求解顺序上的不同，这也造成了它们时间效率上的差别。在搜
索中，往往会出现下面的情况：
对于上图(a)这样几个状态构成的一个隐式图，用搜索算法就会出现重复，如上图(b)所示
，状态C2被搜索了两次。在深度搜索中，这样的重复会引起以C2为根整个的整个子搜索树
的重复搜索；在宽度搜索中，虽然这样的重复可以立即被排除，但是其时间代价也是不小
的。而动态规划就没有这个问题，如上图(c)所示。
一般说来，动态规划算法在时间效率上的优势是搜索无法比拟的。（当然对于某些题目，
根本不会出现状态的重复，这样搜索和动态规划的速度就没有差别了。）而从理论上讲，
任何拓扑有序（现实中这个条件常常可以满足）的隐式图中的搜索算法都可以改写成动态
规划。但事实上，在很多情况下我们仍然不得不采用搜索算法。那么，动态规划算法在实
现上还有什么障碍吗？
考虑上图(a)所示的隐式图，其中存在两个从初始状态无法达到的状态。在搜索算法中，这
样的两个状态就不被考虑了，如上图(b)所示。但是动态规划由于是自底向上求解，所以就
无法估计到这一点，因而遍历了全部的状态，如上图(c)所示。
一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜
索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多
。
如何协调好动态规划的高效率与高消费之间的矛盾呢？有一种折衷的办法就是记忆化算法
(备忘录法)。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，
就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合
了搜索和动态规划两方面的优点，因而还是很有实用价值的。