`
BlogDown
  • 浏览: 212039 次
  • 性别: Icon_minigender_1
  • 来自: 上海
文章分类
社区版块
存档分类
最新评论

动态规划

 
阅读更多


Dynamic Programming

Starfish (starfish.h@china.com)

摘要

本文介绍了动态规划的基本思想和基本步骤,通过实例研究了利用动态规划设计算法的具体途径,讨论了动态规划的一些实现技巧,并将动态规划和其他一些算法作了比较,最后还简单介绍了动态规划的数学理论基础和当前最新的研究成果。

目录

参考文献

引言——由一个问题引出的算法

考虑以下问题

[例1] 最短路径问题

现有一张地图,各结点代表城市,两结点间连线代表道路,线上数字表示城市间的距离。如图1所示,试找出从结点A到结点E的最短距离。

图 1

我们可以用深度优先搜索法来解决此问题,该问题的递归式为

其中是与v相邻的节点的集合,w(v,u)表示从v到u的边的长度。

具体算法如下:

function MinDistance(v):integer;
begin
 if v=E then return 0
  else
   begin
    min:=maxint;
    for 所有没有访问过的节点i do
     if v和i相邻 then 
      begin
        标记i访问过了;
        t:=v到i的距离+MinDistance(i);
        标记i未访问过;        
        if t<min then min=t;
      end;  
   end;
end;

开始时标记所有的顶点未访问过,MinDistance(A)就是从A到E的最短距离。

这个程序的效率如何呢?我们可以看到,每次除了已经访问过的城市外,其他城市都要访问,所以时间复杂度为O(n!),这是一个“指数级”的算法,那么,还有没有更好的算法呢?

首先,我们来观察一下这个算法。在求从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)。

更进一步,可以将这种递归改为递推,这样可以减少递归调用的开销。

请看图1,可以发现,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,对每个状态都只要遍历一次,而且程序很简洁。

具体算法如下:

procedure DynamicProgramming;
 begin
  F5[E]:=0;
  for i:=4 downto 1 do
     for each u ∈Sk do
      begin
       Fk[u]:=无穷大;
       for each v∈Sk+1∩δ(u) do
         if Fk[u]>w(u,v)+Fk+1[v] then Fk[u]:=w(u,v)+Fk+1[v];
   end;
  输出F1[A]; 
 end;

这种高效算法,就是动态规划算法

动态规划的基本概念

动态规划的发展及研究内容

动态规划(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)

动态规划的基本定理和基本方程

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

[基本定理]

对于初始状态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)式是一个递归公式,如果目标状态确定,当然可以直接利用该公式递归求出最优值(这种递归方法将在后文介绍,称作备忘录法),但是一般在实际应用中我们通常将该递归公式改为递推公式求解,这样一般效率会更高一些。

动态规划的适用条件

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

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]推出,则必须满足的条件就是:P1<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的多项式函数时,动态规划法显得特别有意义,此时动态规划法具有线性时间复杂性。所以,能够用动态规划解决的问题还有一个显著特征:子问题的重叠性。这个性质并不是动态规划适用的必要条件,但是如果该性质无法满足,动态规划算法同其他算法相比就不具备优势。

动态规划的基本思想

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

动态规划的实质是分治思想解决冗余,因此,动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。

由此可知,动态规划法与分治法贪心法类似,它们都是将问题实例归纳为更小的、相似的子问题,并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择,但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下,一步一步地作出贪心选择;而分治法中的各个子问题是独立的 (即不包含公共的子子问题),因此一旦递归地求出各子问题的解后,便可自下而上地将子问题的解合并成问题的解。但不足的是,如果当前选择可能要依赖子问题的解时,则难以通过局部的贪心策略达到全局最优解;如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题。

解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话,它只取其中的一个。在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算。

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

动态规划算法的基本步骤

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

  1. 划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的(即无后向性),否则问题就无法用动态规划求解。
  2. 选择状态:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。
  3. 确定决策并写出状态转移方程:之所以把这两步放在一起,是因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以,如果我们确定了决策,状态转移方程也就写出来了。但事实上,我们常常是反过来做,根据相邻两段的各状态之间的关系来确定决策。
  4. 写出规划方程(包括边界条件):动态规划的基本方程是规划方程的通用形式化表达式。一般说来,只要阶段、状态、决策和状态转移确定了,这一步还是比较简单的。

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

标准动态规划的基本框架

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. 分析最优解的性质,并刻划其结构特征。
  2. 递归地定义最优值。
  3. 以自底向上的方式或自顶向下的记忆化方法(备忘录法)计算出最优值。
  4. 根据计算最优值时得到的信息,构造一个最优解。

步骤(1)--(3)是动态规划算法的基本步骤。在只需要求出最优值的情形,步骤(4)可以省略,若需要求出问题的一个最优解,则必须执行步骤(4)。此时,在步骤(3)中计算最优值时,通常需记录更多的信息,以便在步骤(4)中,根据所记录的信息,快速地构造出一个最优解。

动态规划的实例分析

下面我们将通过实例来分析动态规划的设计步骤和具体应用。例1已经在前文介绍过了。例1和例2是标准的动态规划,有明显的阶段和状态转移方程;例3、例4、例5、例6是没有明显阶段划分的动态规划,也是一般常见的形式,其中对例4、例5、例6作了比较详细的分析;例7是比较特殊的动态规划,例8是两重动态规划(即为了解决问题要进行两次动态规划)的例子。

更多实例请参阅动态规划问题集

动态规划的技巧——阶段的划分和状态的表示

在动态规划的设计过程中,阶段的划分和状态的表示是非常重要的两步,这两步会直接影响该问题的计算复杂性,有时候阶段划分或状态表示的不合理还会使得动态规划法不适用。

[例9] 街道问题

在下图中找出从左下角到右上角的最短路径,每步只能向右方或上方走。

这是一道简单而又典型的动态规划题,许多介绍动态规划的书与文章中都拿它来做例子。通常,书上的解答是这样的:

按照图中的虚线来划分阶段,即阶段变量k表示走过的步数,而状态变量xk表示当前处于这一阶段上的哪一点。这时的模型实际上已经转化成了一个特殊的多段图。用决策变量uk=0表示向右走,uk=1表示向上走,则状态转移方程如下:

(这里的row是地图竖直方向的行数)

我们看到,这个状态转移方程需要根据k的取值分两种情况讨论,显得非常麻烦。相应的,把它代入规划方程而付诸实现时,算法也很繁。因而我们在实现时,一般是不会这么做的,而代之以下面方法:

(这里Distance表示相邻两点间的边长)

这样做确实要比上面的方法简单多了,但是它已经破坏了动态规划的本来面目,而不存在明确的阶段特征了。如果说这种方法是以地图中的行(A、B、C、D)来划分阶段的话,那么它的"状态转移"就不全是在两个阶段之间进行的了。

也许这没什么大不了的,因为实践比理论更有说服力。但是,如果我们把题目扩展一下:在地图中找出从左下角到右上角的两条路径,两条路径中的任何一条边都不能重叠,并且要求两条路径的总长度最短。这时,再用这种"简单"的方法就不太好办了。

如果非得套用这种方法的话,则最优指标函数就需要有四维的下标,并且难以处理两条路径"不能重叠"的问题。

而我们回到原先"标准"的动态规划法,就会发现这个问题很好解决,只需要加一维状态变量就成了。即用xk=(ak,bk)分别表示两条路径走到阶段k时所处的位置,相应的,决策变量也增加一维,用uk=(xk,yk)分别表示两条路径的行走方向。状态转移时将两条路径分别考虑

在写规划方程时,只要对两条路径走到同一个点的情况稍微处理一下,减少可选的决策个数:

从这个例子可以看出,合理地划分阶段和选择状态可以给解题带来方便。

[例10] LITTLE SHOP OF FLOWERS (IOI’99)

PROBLEM

You want to arrange the window of your flower shop in a most pleasant way. You have F bunches of flowers, each being of a different kind, and at least as many vases ordered in a row. The vases are glued onto the shelf and are numbered consecutively 1 through V, where V is the number of vases, from left to right so that the vase 1 is the leftmost, and the vase V is the rightmost vase. The bunches are moveable and are uniquely identified by integers between 1 and F. These id-numbers have a significance: They determine the required order of appearance of the flower bunches in the row of vases so that the bunch i must be in a vase to the left of the vase containing bunch j whenever i < j. Suppose, for example, you have a bunch of azaleas (id-number=1), a bunch of begonias (id-number=2) and a bunch of carnations (id-number=3). Now, all the bunches must be put into the vases keeping their id-numbers in order. The bunch of azaleas must be in a vase to the left of begonias, and the bunch of begonias must be in a vase to the left of carnations. If there are more vases than bunches of flowers then the excess will be left empty. A vase can hold only one bunch of flowers.

Each vase has a distinct characteristic (just like flowers do). Hence, putting a bunch of flowers in a vase results in a certain aesthetic value, expressed by an integer. The aesthetic values are presented in a table as shown below. Leaving a vase empty has an aesthetic value of 0.

  V A S E S
1 2 3 4 5
Bunches 1 (azaleas) 7 23 -5 -24 16
2 (begonias) 5 21 -4 10 23
3 (carnations) -21 5 -4 -20 20

According to the table, azaleas, for example, would look great in vase 2, but they would look awful in vase 4.

To achieve the most pleasant effect you have to maximize the sum of aesthetic values for the arrangement while keeping the required ordering of the flowers. If more than one arrangement has the maximal sum value, any one of them will be acceptable. You have to produce exactly one arrangement.

ASSUMPTIONS

  • 1 <= F <= 100 where F is the number of the bunches of flowers. The bunches are numbered 1 through F.
  • F <= V <= 100 where V is the number of vases.
  • -50 <= Aij<= 50 where Aij is the aesthetic value obtained by putting the flower bunch i into the vase j.

INPUT

The input is a text file named flower.inp.

  • The first line contains two numbers: F, V.
  • The following F lines: Each of these lines contains V integers, so that Aij is given as the jth number on the (i+1)st line of the input file.

OUTPUT

The output must be a text file named flower.out consisting of two lines:

  • The first line will contain the sum of aesthetic values for your arrangement.
  • The second line must present the arrangement as a list of F numbers, so that the k’th number on this line identifies the vase in which the bunch k is put.

EXAMPLE

flower.inp:

3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

flower.out:

53
2 4 5

EVALUATION

  • Your program will be allowed to run 2 seconds.
  • No partial credit can be obtained for a test case.

本题虽然是IOI’99中较为简单的一题,但其中大有文章可作。说它简单,是因为它有序,因此我们一眼便可看出这题应该用动态规划来解决。但是,如何动态规划呢?如何划分阶段,又如何选择状态呢?

<方法1>

以花束的编号来划分阶段。在这里,第k阶段布置第k束花,共有F束花,有F+1个阶段,增加第F+1阶段是为了计算的方便;状态变量xk表示第k束花所在的花瓶。而对于每一个状态xk,决策uk就是第k+1束花放置的花瓶号;最优指标函数fk(xk)表示从第k束花到第n束花所得到的最大美学值;A(i,j)是花束i插在花瓶j中的美学值,V是花瓶总数,F是花的总数。

状态转移方程为

规划方程为

边界条件为:

,

事实上这是一个虚拟的边界。

最后要求的最大美学价值是

<方法2>

方法1的规划方程中的允许决策空间:xk+1≤uk≤V-(F-k)+1 比较麻烦,因此有待改进。还是以花束的编号来划分阶段,第k阶段布置第k束花;状态变量xk表示第k束花所在的花瓶;注意,这里我们考虑倒过来布置花瓶,即从第F束花开始布置到第1束花。于是状态变量uk表示第k-1束花所在的花瓶;最优指标fk(xk)表示从第一束花到第k束花所获得的美学价值;A(i,j)是花束i插在花瓶j中的美学值,V是花瓶总数,F是花的总数。则状态转移方程为:

规划方程为:

增加的虚拟边界条件为:

最后要求的最大美学价值是:

可以看出,这种方法实质上和方法1没有区别,但是允许决策空间的表示变得简单了。

<方法3>

以花瓶的数目来划分阶段,第k个阶段决定花瓶k中是否放花;状态变量xk表示前k个花瓶中放了多少花;而对于任意一个状态xk,决策就是第xk束花是否放在第k个花瓶中,用变量uk=1或0来表示。最优指标函数fk(xk)表示前k个花瓶中插了xk束花,所能取得的最大美学值。注意,这里仍然是倒过来考虑。

状态转移方程为

规划方程为

边界条件为

三种不同的方法都成功地解决了问题,只不过因为阶段的划分不同,状态的表示不同,决策的选择有多有少,所以算法的时间复杂度也就不同。

这个例子具有很大的普遍性。有很多的多阶段决策问题都有着不止一种的阶段划分方法,因而往往就有不止一种的规划方法。有时各种方法所产生的效果是差不多的,但更多的时候,就像我们的例子一样,两种方法会在某个方面有些区别。所以,在用动态规划解题的时候,可以多想一想是否有其它的解法。对于不同的解法,要注意比较,好的算法好在哪里,差一点的算法差在哪里。从各种不同算法的比较中,我们可以更深刻地领会动态规划的构思技巧。

动态规划实现中的问题

应用动态规划解决问题,在有了基本的思路之后,一般来说,算法实现是比较好考虑的。但有时也会遇到一些问题,而使算法难以实现。动态规划思想设计的算法从整体上来看基本都是按照得出的递推关系式进行递推,这种递推相对于计算机来说,只要设计得当,效率往往是比较高的,这样在时间上溢出的可能性不大,而相反地,动态规划需要很大的空间以存储中间产生的结果,这样可以使包含同一个子问题的所有问题共用一个子问题解,从而体现动态规划的优越性,但这是以牺牲空间为代价的,为了有效地访问已有结果,数据也不易压缩存储,因而空间矛盾是比较突出的。另一方面,动态规划的高时效性往往要通过大的测试数据体现出来(以与搜索作比较),因而,对于大规模的问题如何在基本不影响运行速度的条件下,解决空间溢出的问题,是动态规划解决问题时一个普遍会遇到的问题。

对于这个问题,可以考虑从以下一些方面去尝试:

一个思考方向是尽可能少占用空间。如从结点的数据结构上考虑,仅仅存储必不可少的内容,以及数据存储范围上精打细算(按位存储、压缩存储等)。当然这要因问题而异,进行分析。另外,在实现动态规划时,一个我们经常采用的方法是用一个与结点数一样多的数组来存储每一步的决策,这对于倒推求得一种实现最优解的方法是十分方便的,而且处理速度也有一些提高。但是在内存空间紧张的情况下,我们就应该抓住问题的主要矛盾。省去这个存储决策的数组,而改成在从最优解逐级倒推时,再计算一次,选择某个可能达到这个值的上一阶段的状态,直到推出结果为止。这样做,在程序编写上比上一种做法稍微多花一点时间,运行的时效也可能会有一些(但往往很小)的下降,但却换来了很多的空间。因而这种思想在处理某些问题时,是很有意义的。

但有时,即使采用这样的方法也会发现空间溢出的问题。这时就要分析,这些保留下来的数据是否有必要同时存在于内存之中。因为有很多问题,动态规划递推在处理后面的内容时,前面比较远处的内容实际上是用不着的。对于这类问题,在已经确信不会再被使用的数据上覆盖数据,从而使空间得以重复利用,如果能有效地使用这一手段,对于相当大规模的问题,空间也不至于溢出(为了求出最优方案,保留每一步的决策仍是必要的,这同样需要空间)。

一般地说,这种方法可以通过两种思路来实现:一种是递推结果仅使用Data1和Data2这样两个数组,每次将Data1作为上一阶段,推得Data2数组,然后,将Data2通过复制覆盖到Data1之上,如此反复,即可推得最终结果。这种做法有一个局限性,就是对于递推与前面若干阶段相关的问题,这种做法就比较麻烦;而且,每递推一级,就需要复制很多的内容,与前面多个阶段相关的问题影响更大。另外一种实现方法是,对于一个可能与前N个阶段相关的问题,建立数组Data[0..N],其中各项为最近N各阶段的保存数据。这样不采用这种内存节约方式时对于阶段k的访问只要对应成对数组Data中下标为k mod (N+1)的单元的访问就可以了。这种处理方法对于程序修改的代码很少,速度几乎不受影响,而且需要保留不同的阶段数也都能很容易实现。

当采用以上方法仍无法解决内存问题时,也可以采用对内存的动态申请来使绝大多数情况能有效出解。而且,使用动态内存还有一点好处,就是在重复使用内存而进行交换时,可以只对指针进行交换,而不复制数据,这在实践中也是十分有效的。

动态规划与其他算法的比较

动态规划与其说是一种算法,不如说是一种算法设计的策略,他的基本思想体现于许多其它算法之中。下面我们通过比较动态规划和其他的一些算法之间的相互联系,来深入理解动态规划的基本思想。

<!-- #EndEditable -->

<script src="../../../lib/footer.js"></script>

<!-- #EndEditable --><!-- #EndEditable -->

<script src="../../../lib/footer.js"></script>

<!-- #EndEditable --><!-- #EndEditable -->

<script src="../../../lib/footer.js"></script>

<!-- #EndEditable -->

<script src="../../../lib/footer.js"></script>

<!-- #EndEditable --><!-- #EndEditable -->

<script src="../../../lib/footer.js"></script>

<!-- #EndEditable -->

<script src="../../../lib/footer.js"></script>

分享到:
评论

相关推荐

    动态规划算法动态规划算法动态规划算法动态规划算法

    动态规划 动态规划 动态规划 动态规划 动态规划 动态规划

    代码 随机动态规划的实例的matlab代码

    代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的...

    动态规划的特点及其应用

    动态规划是信息学竞赛中的常见算法,本文的主要内容就是分析 它的特点。 文章的第一部分首先探究了动态规划的本质,因为动态规划的特 点是由它的本质所决定的。第二部分从动态规划的设计和实现这两个 角度分析了动态...

    算法设计与分析-4动态规划金罐游戏.pptx

    (1) 动态规划算法设计思想。 (2) 金罐游戏问题的动态规划解法。 算法设计与分析-4动态规划金罐游戏.pptx 蛮力法(简单重复递归)和动态规划解决金罐问题 状态数组 子问题 状态方程 蛮力法(时间复杂度O(2n))和...

    动态规划的一些资料--挺详细的

    动态规划是解决多阶段决策最优化问题的一种思想方法。所谓“动态”,指的是在问题的多阶段决策中,按某一顺序,根据每一步所选决策的不同,将随即引起状态的转移,最终在变化的状态中产生一个决策序列。动态规划就是...

    矩阵相乘问题的动态规划

    矩阵相乘问题的动态规划,动态规划是解决多阶段决策过程最优化问题的一种方法,其思想是将求解的问题一层一层地分解成一级一级的子问题,子问题的求解由繁到简逐步缩小,直到可以直接解出子问题为止。下面用动态规划...

    会议安排(贪心算法和动态规划) 贪心算法和动态规划.pdf

    会议安排(贪心算法和动态规划) 贪心算法和动态规划.pdf

    算法与分析实验三:动态规划法

    应用动态规划算法思想求解矩阵连乘的顺序问题。 【实验性质】 验证性实验(学时数:2H) 【实验要求】 应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想,应用动态规划策略...

    动态规划~动态规划32讲~

    学习动态规划必备~ 动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~动态规划~

    动态规划.动态规划算法的应用 含代码

    [运筹学]动态规划 动态规划应用,各种题目和代码

    浅谈动态规划的几种优化方法

    动态规划是求解最优化问题的一种方法;动态规划虽然空间复杂度一般较大,但时间效率可观。但是,动态规划在求解中也会存在一些不必要、或者重复求解的子问题,这时就需要进行进一步优化。 在NOI及省选赛场上,一般...

    动态规划策略求解最大子段和问题

    最大子段和问题,可参考《算法设计与分析》讲义中关于用动态规划策略求解最大子段和问题的思想设计动态规划算法。本算法用户需要输入元素个数n,及n个整数。程序应该给出良好的用户界面,输出最大子段相关信息,包括...

    动态规划算法经典题目

    几道动态规划的经典算法 非常经典 值得分享

    java 最短路径 问题 动态规划

    java 最短路径 问题 动态规划java 最短路径 问题 动态规划

    动态规划实验报告

    这是一份简单的动态规划实验报告,独立完成的,参考了一些资料

    动态规划——经典教程

    详细阐述动态规划的应用范围及方法 动态规划经典教程 引言:本人在做过一些题目后对DP有些感想,就写了这个总结: 第一节 动态规划基本概念 一,动态规划三要素:阶段,状态,决策。 他们的概念到处都是,我就不多说...

    动态规划.ppt

    动态规划是解决多阶段决策问题最优化的一种数学方法,大约产生于50年代,1951年美国数学家数学家贝尔曼(R.Bellman)等人根据多阶段决策问题的特点,把多阶段决策问题变换为一系列相互联系的单阶段问题,然后逐个加以...

    用遗传算法和动态规划来求解经典算法问题-TSP商旅问题_Pytho源代码

    经典算法问题-TSP商旅问题(Traveling Salesman Problem),它是数学领域中著名问题之一。...代码包含遗传算法和动态规划来求解这个问题,里面有完整源代码,并且有详细注释,还有两者的比较分析。

    ACM动态规划经典题

    12个ACM动态规划经典题 习题+分析+程序 (转载)

    混合动力动态规划_;matlabcode_动态规划汽车_能量管理matlab_vehicle_动态规划混合

    动态规划混合动力汽车模式切换程序,附带工况。

Global site tag (gtag.js) - Google Analytics