动态规划算法原理及应用

《动态规划算法原理及应用》由会员分享，可在线阅读，更多相关《动态规划算法原理及应用（14页珍藏版）》请在装配图网上搜索。

1、动态规划算法刘兴田(浙江工业大学计算机学院软件工程 1205班 201226630512) 摘要：动态规划是解决最优化问题的基本方法，本文介绍了动态规划的基本思想 和基本步骤，并通过几个实例的分析，研究了利用动态规划设计算法的具体途径。关键词：动态规划算法Dynamic ProgrammingLiu xingtian(Zhe Jiang University Of Technology, Computer Science and Technology Campus, Software Engineering 1205 26630512)Abstract: Dynamic Programming

2、 is the most effective way to solve the problem ofoptimization This dissertationintroduce the thinking of Dynamic Programming and the step to using Dynamic Programming ,it also gives some examples to help analysis Dynamic Programming and the specific method to use Dynamic Programming Key words : Dyn

3、amic Programming , Alsgorithm1. 引言规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或 极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的； 然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多 阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在 每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进 行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一 个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同 的策略。当过程采取某个具体策略

4、时，相应可以得到一个确定的效果，采取不同 的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策 略中选取一个最优的策略，以便得到最佳的效果。动态规划是一种求解多阶段决 策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。在 多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动 态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。 20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工 作的贝尔曼首先提出了动态规划的概念。 1957 年贝尔曼发表了数篇研究论文， 并出版了他的第一部

5、著作动态规划。该著作成为了当时唯一的进一步研究和 应用动态规划的理论源泉。在贝尔曼及其助手们致力于发展和推广这一技术的同 时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是 爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部 关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild） 一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多 对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数 学性质做出了巨大的贡献。动态规划问世以来，在工程技术、经济管理等社会各个领域都有着

6、广泛的应 用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径 问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题 以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问 题用动态规划的方法来处理，常比线性规划或非线性规划更有效。特别是对于离 散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。 动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态 规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规 划。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一 些与时间无关的

7、静态规划（如线性规划、非线性规划），只要人为地引进时间因素， 把它视为多阶段决策过程，也可以用动态规划方法方便地求解。2. 动态规划的基本思想一般来说，只要问题可以划分成规模更小的子问题，并且原问题的最优解中 包含了子问题的最优解，则可以考虑用动态规划解决。动态规划的实质是分治思 想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题， 并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。由 此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、 相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择 可能要依赖已经作出的所有选

8、择，但不依赖于有待于做出的选择和子问题。因此 贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的 （即不包含公共的子子问题），因此一旦递归地求出各子问题的解后，便可自下而 上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问 题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立 的，则分治法要做许多不必要的工作，重复地解公共的子问题。解决上述问题的 办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的 解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在 若干个取最优值的解的话，它只取其中的一个。在求

9、解过程中，该方法也是通过 求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划 允许这些子问题不独立，也允许其通过自身子问题的解作出选择，该方法对每一 个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树 中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题， 只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不 必重新求解。3. 动态规划的基本概念动态规划的数学描述离不开它的一些基本概念与符号，因此有必要在介绍多 阶段决策过程的数学描述的基础上，系统地介绍动态规

10、划的一些基本概念。3.1 多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出 决策，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确 定了一个过程的活动路线，则称它为多阶段决策问题。各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个 决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的 效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题， 就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到 最好的效果.3.2 动态规划问题中的术语 阶段：把所给求解问题的过程恰当地分成若干个相互

11、联系的阶段，以便于求 解，过程不同，阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况 下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过 程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策 时，阶段变量就是连续的。状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主 观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置， 它既是该阶段某路的起点，同时又是前一阶段某支路的终点。过程的状态通常可以用一个或一组数来描述，称为状态变量。一般，状态是 离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量 形式

12、的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的 处理将会有很大的好处。此外，状态可以有多个分量（多维情形），因而用向量来 代表；而且在每个阶段的状态维数可以不同。无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在 这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定 时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表 示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个 线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以 前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通

13、过当前 的状态去影响它的未来的发展，这个性质称为无后效性。决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种 选择(行动)称为决策。在最优控制中，也称为控制。在许多间题中，决策可以 自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的 变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前 的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合。策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决 策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许 策略集合中达到最优效果的策略称为最优策略。给定k阶段状态变

14、量x(k)的值后，如果这一阶段的决策变量一经确定，第 k+1阶段的状态变量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k阶段的决 策u(k)的值变化而变化，那么可以把这一关系看成(x(k), u(k)与 x(k+1)确定的对 应关系，用x(k+1)=Tk(x(k),u(k)表示。这是从k阶段到k+1阶段的状态转移规律， 称为状态转移方程。最优性原理：作为整个过程的最优策略，它满足：相对前面决策所形成的状 态而言，余下的子策略必然构成“最优子策略”。4动态规划求解的基本步骤动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过 对中间阶段决策的选择，达到结束状态。这些决

15、策形成了一个决策序列，同时确 定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态 规划的设计都有着一定的模式，一般要经历以下几个步骤。初始状态决策1 |f|决策2决策n结束状态动态规划决策过程示意图(1)划分阶段:，按照问题的时间或空间特征，把问题分为若干个阶段。在划 分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法 求解。确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用 不同的状态表示出来。当然，状态的选择要满足无后效性。(3) 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状 态转移就是根据上一阶段的状态和决策来导

16、出本阶段的状态。所以如果确定了决 策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态 之间的关系来确定决策。(4) 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止 条件或边界条件。(5) 程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成， 实现部分就会非常简单。根据上述动态规划设计的步骤，可得到大体解题框架如图所示。对圮誚初始化(边界条件)fcrkC2 ton这里以顺序求解为例对每一个孔氐&人鼠)个极值(X或一8)对每一个u屆疋1 1 1k-iTk(skut)1输出fjsj动态规划设计的一般模式图上述提供了动态规划方法的一般模式，对于简单的动

17、态规划问题，可以按部 就班地进行动态规划的设计。下面，给出一个利用动态规划方法求解的典型例 子。V数字三角形问题上图示出了一个数字三角形宝塔。数字三角形中的数字 为不超过100的整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右 斜线向下走。任务一：假设三角形行数1Q键盘输入一个确定的整数值M,编程确定是 否存在一条路径，使得沿着该路径所经过的数字的总和恰为M,若存在则给出 所有路径，若不存在，贝峙俞出“NO Answer!”字样。任务二：假设三角形行数100，编程求解从最顶层走到最底层的一条路径, 使得沿着该路径所经过的数字的总和最大，输出最大值。输人数据：由文件输入数据，任务一中文件

18、第一行是三角形的行数 N和整数 值M。以后的N行分别是从最顶层到最底层的每一层中的数字。任务二中文件 数据格式同任务一，只是第一行中没有整数值M。在例子中任务二的文件数据 表示如下：输入：57输出：输出路径和最大值3 87或“No Answer!”字样。8 1 03 82 7 7 48 104 5 2 6 52744图3数字三角形452 65【分析】对于这一问题，很容易想到用枚举的方法去解决，即列举出所有路 径并记录每一条路径所经过的数字总和。然后判断数字总和是否等于给定的整数 值M或寻找出最大的数字总和，这一想法很直观，而且对于任务一，由于数字 三角形的行数不大(=10)，因此其枚举量不是很

19、大，应该能够实现。但对于任 务二，如果用枚举的方法，当三角形的行数等于100时，其枚举量之大是可想而 知的，显然，枚举法对于任务二的求解并不适用。其实，只要对对任务二稍加分 析，就可以得出一个结论：如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一 个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该问题是 一个典型的多阶段决策最优化的问题。算法设计与分析如下：对于任务一，合理地确认枚举的方法，可以优化问题的解法。由于从塔顶 到底层每次都只有两种走法，即左或右。设“0”表示左，T”表示右，对于层数为 N的数字塔，从顶到底的一种走法可用一个N-1位的二进制数表示。如例中

20、二进 制数字串1011，其对应的路径应该是：8146。这样就可以用一个N1位 的二进制数来模拟走法和确定解的范围。穷举出从0到2n-1个十进制数所对应 的N-1位二进制串对应的路径中的数字总和，判定其是否等于M而求得问题的 解。对于任务二，采用动态规划中的顺推解法。按三角形的行划分阶段，若行数 为n则可把问题看做一个n-1个阶段的决策问题。从始点出发，依顺向求出第 一阶段、第二阶段第n1阶段中各决策点至始点的最佳路径，最终求出始 点到终点的最佳路径。设：fk(Uk)为从第k阶段中的点Uk至三角形顶点有一条最佳路径，该路径 所经过的数字的总和最大，fk(Uk)表示为这个数字和；由于每一次决策有两

21、个选 择，或沿左斜线向下，或沿右斜线向下，因此设：Ukl为k-1阶段中某点Uk沿左斜线向下的点；Uk2为k-1阶段中某点Uk沿右斜线向下的点；dk(Ukl)为k阶段中Ukl的数字；dk(Uk2)为k阶段中Uk2的数字。因而可写出顺推关系式(状态转移方程)为：fk(Uk)=maxfk-1(Uk)+dk(Uk1)，fk-1(Uk)+dk(Uk2)(k=1, 2，3，n) fO(UO)=O经过一次顺推，便可分别求出由顶至底N个数的N条路径，在这N条路径所经 过的N个数字和中，最大值即为正确答案。5动态规划的应用实例5.1最短路线问题例1现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示

22、城市间的距离。如图1所示，试找出从结点A到结点E的最短距离。我们可以用深度优先搜索法来解决此问题，该问题的递归式为- min w(v?iz) +)Li 弐(V)其中兀町是与V相邻的节点的集合，w(v,u)表示从v到u的边的长度。这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城 市都要访问，所以时间复杂度为O(n!)，这是一个“指数级”的算法。首先，我们来观察一下这个算法。在求从B1到E的最短距离的时候，先求出从 C2到E的最短距离；而在求从B2到E的最短距离的时候，又求了一遍从C2到E 的最短距离。也就是说，从C2到E的最短距离我们求了两遍。同样可以发现， 在求从Cl、C

23、2到E的最短距离的过程中，从D1到E的最短距离也被求了两遍。 而在整个程序中，从D1到E的最短距离被求了四遍。如果在求解的过程中，同 时将求得的最短距离记录在案，随时调用，就可以避免这种情况。于是，可以 改进该算法，将每次求出的从v到E的最短距离记录下来，在算法中递归地求 MinDistance(v)时先检查以前是否已经求过了 MinDistance(v)，如果求过了则 不用重新求一遍，只要查找以前的记录就可以了。这样，由于所有的点有n个， 因此不同的状态数目有n个，该算法的数量级为O(n)。更进一步，可以将这种递归改为递推，这样可以减少递归调用的开销。52资源分配问题所谓资源分配问题，就是将

24、一定数量的一种或若干种资源(如原材料、机器 设备、资金、劳动力等)恰当地分配给若干个使用者，以使资源得到最有效地利 用。设有m种资源，总量分别为bi(i = 1,2,.,m)，用于生产n种产品，若用xij 代表用于生产第j种产品的第i种资源的数量(j = 1,2, .,n)，则生产第j种产品 的收益是其所获得的各种资源数量的函数，即gj = f(x1j,x2j,xmj)。由于总收 益是n种产品收益的和，此问题可用如下静态模型加以描述：maxz = f gj冃丿 x = b (i = 1,2,，m)j ij=1xij -0（i=口 ,m; j=卩,n）若x是连续变量，当g = f( x , x，

25、x )是线性函数时，该模型是线 j j1 j 2 jmj性规划模型；当g = f( x , x，x )是非线性函数时，该模型是非线性规 j1 j 2 jmj划模型。若x是离散变量或(和)g = f( x ,x，x )是离散函数时，此 ijj1 j 2 jmj模型用线性规划或非线性规划来求解都将是非常麻烦的。然而在此情况下，由于 这类问题的特殊结构，可以将它看成为一个多阶段决策问题，并利用动态规划的递推关系来求解。本例只考虑一维资源的分配问题，设状态变量s表示分配于从第k个阶段至 k过程最终(第 N 个阶段)的资源数量，即第 k 个阶段初资源的拥有量；决策变 量xk表示第k个阶段资源的分配量。于

26、是有状态转移律：S = S - xk+1k k允许决策集合：D (S ) = x 10 x S k kkk k最优指标函数(动态规划的逆序递推关系式)f( Sk)= W(叮 + f+i( S+1)(k = N, N 1, N 2,1)fN+1( SN+1) = 0利用这一递推关系式，最后求得的 f (S )即为所求问题的最大总收益，下面来看11一个具体的例子。例2 某公司拟将500 万元的资本投入所属的甲、乙、丙三个工厂进行技术改造， 各工厂获得投资后年利润将有相应的增长，增长额如表7-1所示。试确定500 万 元资本的分配方案，以使公司总的年利润增长额最大。表 7-1投100200300万4

27、00500资额万元万元元万元万元甲307090120130乙50100110110110丙4060110120120解：将问题按工厂分为三个阶段k=l, 2, 3,设状态变量S ( k = 1,2,3 )代表从 k第k个工厂到第3个工厂的投资额，决策变量x代表第k个工厂的投资额。于是 k有状态转移率S = S x、允许决策集合D (S ) = x 10 x S 和递推关系k +1k kk kkk k式：f (S ) = maxg (x ) + fkk0 x Skkkk +1(S x )kk(k = 3,2,1)f4(S4)二 00x 0+0.60.5+0.41.0+01.02/50+1.10.

28、5+0.61.0+0.41.1+01.424L0+1.20.5+1.11.0+0.61.1+0.41.1+01.61，25) 0+1.20.5+1.21.0+1.11.1+0.61.1+0.41.1+02.12当k =1时:小 Si）=呻 %）+ 心xi）于是：g1 (x1)+f2 (s1 -d)x*1 1 111x0S1234550+2.10.3+1.60.7+1.40.9+1.01.2+0.51.3+02.10，2然后按计算表格的顺序反推算，可知最优分配方案有两个：（1）甲工厂投资 200 万元，乙工厂投资 200 万元，丙工厂投资 100 万元；（2）甲工厂没有投资， 乙工厂投资200

29、万元，丙工厂投资 300 万元。按最优分配方案分配投资（资源）， 年利润将增长 210 万元。5.3 用动态规划求解非线性规划问题非线性规划问题的求解是非常困难的；然而，对于有些非线性规划问题，如 果转化为用动态规划来求解将是十分方便的。例 3 用动态规划求解max z = x x x 2 x x123丿 x + x + x = 36123x , x , x 0123解：阶段：将问题的变量数作为阶段，即 k=1，2，3； 决策变量：决策变量 x ；k状态变量:状态变量Sk代表第k阶段的约束右端项，即从x到x占有的份额;kk 3状态转移律：S二S - x ；k+1 k k边界条件：S 二 36，

30、f （S ）二 1 ；1 4 4允许决策集合：0 x Skk当k - 3时：f (S )= maxx x f (S )= maxx = S |3334430x3S30x3S33x；= S3当k = 2时:- x2)f (S ) = max x2 x f (S ) = max x2(S2 20x2 S2 23 30x2 0,dx2鲨 x2 =02dh = 2(S x ) 2x 2x = 2S 6x , x = 2 S 是 f (S )的极大值点 dx2 2 2 2 2 2 2 2 3 2 2 2dx2于是:f (S ) = + S3|2 2 27 2 x2=: S2当k二1时:f (S ) =

31、maxx xf (S ) = maxx x +(S 一x )31 1ov x1 v s1 12 2ov x1 v s1 1 27 11同上可得：f (S 二 36)二壬 S 4 二壬 x 364 二 2624411 164 164x；= 1S1 =9由 S = S x* = 36 9 = 27，有 x ; = - S 2 = 丁 x 27 = 1821123 23由 S = S - X* = 27 -18 = 9，有 x* = S = 932233于是得到最优解X *二(9,18,9)，最优值z *二26244参考文献1 百度文库：运用动态规划模型解决最短路径问题，2 博客园：谈谈动态规划的思想3 谬慧芬，邵小兵动态规划算法的原理及应用J.中国科技信息，2005(21).4 解可新，韩立兴,林友联最优化方法M.天津:天津大学出版社，1997.5 赵旋.变分法、最小值原理、动态规划和最优控制J.自动化博览，1997