龙源期刊网 http://www.qikan.com.cn

动态规划算法分析与研究

作者：张爱华 郭喜跃 陈前军 来源：《软件导刊》2014年第12期

摘 要：分析多阶段决策问题，总结动态规划的基本概念、原理以及解题。通过0-1背包问题的具体解题步骤，阐述动态规划算法一般解题思路。并分析常用经典算法在解决最优问题中的差异性，比较各自优缺点，探讨其研究方向。

关键词：多阶段决策;动态规划算法;背包问题;贪心算法 DOI：10.11907/rjdk.143507 中图分类号：PT301.6

文献标识码：A ; ; 文章编号：1672-7800（2014）012-0068-02

作者简介：张爱华（1979-），男，湖北钟祥人，硕士，军事经济学院基础部讲师，研究方向为算法及数学模型。 0 引言

动态规划算法是运筹学的一个分支，是求解决策过程最优化的一种数学方法，也是解决NP问题行之有效的解决方案之一。动态规划算法将一个复杂的多阶段问题转换为一系列单阶段问题，利用各阶段之间的关系，逐个求解，由美国数学家R.E.Bellman等^[1]最早提出。

动态规划算法是以牺牲存储空间换取计算效率的算法。在实际应用中，可将某活动过程分成若干个相关联的阶段，每一阶段都需要作出决策，从而使整个过程达到最优效果。本文就动态规划算法进行综述，并就0-1背包问题展开探讨，具体分析动态规划算法的思想。 1 基本原理

1.1 动态规划算法分类

动态规划一般可分为线性动态规划、区域动态规划、树形动态规划、背包动态规划等4类。如导弹拦截问题是线性动态规划算法的典型应用;统计单词个数等问题是区域动态规划的典型应用;二分查找树问题是树形动态规划的典型应用;0-1背包问题是背包类动态规划算法应用。

1.2 动态规划算法基本原理

龙源期刊网 http://www.qikan.com.cn

动态规划算法的基本思想是将问题分解成若干互相关联的阶段，将子问题在各阶段按照一定的次序排列，对某个给定的阶段状态先求解子问题，然后从子问题的解中得到原问题的解。对于重复出现的子问题，只在第一次遇到时对它进行求解，并将求得的解保存起来，以备后续状态中再次使用。如图1所示，即解决A问题;依赖于解决阶段B的若干个子问题，解决B阶段问题依赖于解决C阶段的若干个问题，以此类推直至所有问题解决。 图1 动态规划算法基本原理

从基本原理可知，每一次新的“特例”问题的求解结果都需要保存在临时表中，因而耗费一定计算空间;另一方面，由于新的计算过程可通过已经存在的结果加以计算，从而降低了计算的时间复杂度，也符合发现问题、求解问题、知识积累学习、知识再利用的基本思想。 1.3 适用范围

动态规划算法适用一定的范围和前提约束，超出了特定条件，便失去了作用。动态规划的问题必须满足最优化原理和无后效性。具体如下：①最优化原理。一个最优化策略不论过去状态和决策，对前面决策所形成的状态而言，余下的各决策必须构成最优策略，是典型的局部最优化;②无后效性。将各阶段按照一定的次序排列后，对于某个给定的阶段状态，此前各阶段的状态无法影响未来的决策。即对于已经解决的子问题，不会被后续问题所改变，又称为无后效性;③子问题的重叠性。动态规划将原来具有指数级时间复杂度的搜索算法改进成具有多项式时间复杂度的算法。其中的关键在于利用空间冗余保存过程知识，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，在实现过程中，不得不存储产生过程中的各种状态，所以其空间复杂度要大于其它算法。 2 动态规划算法应用实例——0-1背包问题

用动态规划算法求解实际问题时，首先要建立动态规划模型，一般需要进行如下几个步骤：①分析问题，界定最优解的特征;②划分问题阶段，定义阶段计算目标;③求解阶段结论，形成决策机制，存储知识集;④根据计算最优值时得到的信息，构造出一个最优解;⑤设计程序，编写相应代码^[2]。

例如0-1背包问题，空间复杂度O（S）=N*C，N=物品个数、C=背包容量，最优解为选取n件物品（0≤n≤N），使得V最大;背包问题是N阶段问题，每个阶段有j个子问题，状态定义为在C=j，N=i的状态如何决策的过程，决策函数为f（i，j），分析可知f（i，j）决策如式（1）所示，其中v（i）是第i个背包的V值，此为决策的核心算法^[3]： f（i，j）=max（f（i-1，j-v（i））+v（i），f（i-1，j）） f（i-1，j） （1）

龙源期刊网 http://www.qikan.com.cn

当v（i） ≤j时，f（i，j）取f（i-1，j-v（i））+v（i）和f（i-1，j）的最大值;当v（i）>j时，第i个背包无法放入，因而求解f（i，j）=f（i-1，j）。

式（1）中，f（i-1，j），f（i-1，j-v（i））都已求解，因而f（i，j）可以计算出来。 3 动态规划算法与贪心算法比较

动态规划算法和贪心算法都是解决最优问题的递推类经典算法，均由局部最优解来推导全局最优解，因而这两个算法具有相似性。但两者之间也有着显著差异。

贪心算法每步决策都无法改变，且成为最终决策方案中的一个确定步骤，其每一步均是在已经抉择的结果集外的最优选择，前面决策结果不保存并为后续决策的过程引用，如式（2）所示。

f（xn）=∪ni=0V（i）（2）

动态规划算法全局最优解中一定包含某些局部最优解，但当前状态的最优解不一定包含前一个状态的局部最优解，因而它和贪心算法不一样，需要计算出每个状态（每一步）最优解，并保存起来备后续状态计算引用。

贪心算法在时间复杂度、空间复杂度方面优于动态规划算法，但“贪心”判定规则（决策依据）却难以确定，即V（x）函数的选取，使不同的决策依据得出的结论可能不一致，影响最优解的生成。

利用动态规划算法解决符合条件的问题时，一般可以在有限时间内解决问题，但该算法需要暂存已经计算的结果，因而动态规划需要很大空间。虽然可以使包含同一个子问题的所有问题共用一个子问题解，从而体现动态规划的优越性，但是以牺牲空间为代价的。为了有效访问已有结果，加上数据不易压缩存储，因而空间矛盾比较突出。动态规划的高时效性往往要通过大的测试数据体现出来。因而，如何在不影响运行速度的条件下，解决空间溢出问题，是动态规划需要解决的，也是今后研究的热点问题^[4]。 4 结语

本文就动态规划算法的基本概念、应用场景、适用范围、基本原理进行阐述，并结合0-1背包动态规划法具体求解过程、思路进行分析，比较动态规划算法和贪心算法的异同点，指出规划法存在的空间复杂度大等问题，对理解动态规划法的意义提供参考和指导。 参考文献：

＼[1＼] 百度百科.动态规划[EB/OL]. http：//baike.http://35331.cn//view/28146.htm， 2013-12-06.