动态规划算法

《动态规划算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划算法摘要本文介绍了动态规划的基本思想和基本步骤，通过实例研究了利用动态规划设计算法的具体途径，讨论了动态规划的一些实现技巧，并将动态规划和其他一些算法作了比较，最后还简单介绍了动态规划的数学理论基础和当前最新的研究成果。引言——由一个问题引出的算法考虑以下问题[例1]最短路径问题现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图1所示，试找出从结点A到结点E的最短距离。我们可以用深度优先搜索法来解决此问题，该问题的递归式为其中是与v相邻的节点的集合，w(v,u)表示从

2、v到u的边的长度。具体算法如下：functionMinDistance(v):integer;beginifv=Ethenreturn0elsebeginmin:=maxint;for所有没有访问过的节点idoifv和i相邻thenbegin标记i访问过了;t:=v到i的距离+MinDistance(i);标记i未访问过;ift

3、访问过的城市外，其他城市都要访问，所以时间复杂度为O(n!)，这是一个“指数级”的算法，那么，还有没有更好的算法呢？首先，我们来观察一下这个算法。在求从B1到E的最短距离的时候，先求出从C2到E的最短距离；而在求从B2到E的最短距离的时候，又求了一遍从C2到E的最短距离。也就是说，从C2到E的最短距离我们求了两遍。同样可以发现，在求从C1、C2到E的最短距离的过程中，从D1到E的最短距离也被求了两遍。而在整个程序中，从D1到E的最短距离被求了四遍。如果在求解的过程中，同时将求得的最短距离"记录在案"，随时调

4、用，就可以避免这种情况。于是，可以改进该算法，将每次求出的从v到E的最短距离记录下来，在算法中递归地求MinDistance(v)时先检查以前是否已经求过了MinDistance(v)，如果求过了则不用重新求一遍，只要查找以前的记录就可以了。这样，由于所有的点有n个，因此不同的状态数目有n个，该算法的数量级为O(n)。更进一步，可以将这种递归改为递推，这样可以减少递归调用的开销。可以发现，A只和Bi相邻，Bi只和Ci相邻,...，依此类推。这样，我们可以将原问题的解决过程划分为4个阶段，设S1={A},S2

5、={B1,B2},S3={C1,C2,C3,C4},S4={D1,D2,D3}，Fk(u)表示从Sk中的点u到E的最短距离，显然可以递推地求出F1(A)，也就是从A到E的最短距离。这种算法的复杂度为O(n)，因为所有的状态总数（节点总数）为n，对每个状态都只要遍历一次，而且程序很简洁。具体算法如下：procedureDynamicProgramming;beginF5[E]:=0;fori:=4downto1doforeachu∈SkdobeginFk[u]:=无穷大;foreachv∈Sk+1∩δ(u)

6、doifFk[u]>w(u,v)+Fk+1[v]thenFk[u]:=w(u,v)+Fk+1[v];end;输出F1[A];end;这种高效算法，就是动态规划算法。动态规划的基本概念动态规划的发展及研究内容动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(prin

7、cipleofoptimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著DynamicProgramming，这是该领域的第一本著作。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规

8、划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。多阶段决策问题多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。例1是一个多阶段决策问题的例子，下面是另一个多阶段决策问题的例子：[例2]生产计划问题工厂生产某种产品，每单位(