【精品】(优)动态规划的发展及研究内容.doc

《【精品】(优)动态规划的发展及研究内容.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、动态规划的发展及研究内容动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)®优花的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决朵过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(principleofoptimality),把多阶衣过程转花为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著DynamicPr

2、ogramming,这是该领域的第一木著作。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因索，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。多阶段决策问题多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分

3、解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效只达到最优的问题，称为多阶段决策问题。引言——曲一•个问题引出的算法［例1］最短路径问题现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字农示城币间的距离。如图1所示，试找出从结点A到结点E的嚴短距离。图1我们可以用深度优先搜索法来解决此问题，该问题的递归式为其中是与v相邻的节点的集合，w(v,u)表示从v到u的边的长度。具体算法如下：functionMinDistiince(v):inte

4、ger;beginifv=Ethenreturn0elsebeginmin:=maxint;for所有没有访问过的节点idoifv和i相邻thenbegin标记i访问过了；t:=v到i的距离+MinDistance(i);标记i未访问过；讦t

5、的算法，那么，还有没有更好的算法呢？首先，我们來观察一下这个算法。在求从B1到E的垠短距离的吋候，先求出从C2到E的最短距离；而在求从B2到E的最短距离的时候，又求了一遍从C2到E的最短距离。也就是说，从C2到E的最短距离我们求了两遍。同样可以发现，在求从Cl、C2到E的最短距离的过程中，从D1到E的最短距离也被求了两遍。而在整个程序屮，从D1到E的最短距离被求了四遍。如果在求解的过程中，同吋将求得的最短距离”记录在案“，随时调用，就可以避免这种情况。于是，可以改进该算法，将每次求出的从v到E的垠短

6、距离记录下來，在算法中递归地求MinDistance(v)时先检杏以前是否已经求过了MinDistance(v),如果求过了则不用重新求一•遍，只要查找以前的记录就可以了。这样，山于所有的点有n个，因此不同的状态数目有n个，该算法的数量级为0(n)。更进一步，可以将这种递归改为递推，这样可以减少递归调用的开销。请看图1,可以发现,A只和Bi相邻,Bi只和Ci相邻，…,依此类推。这样,我们可以将原问题的解决过程划分为4个阶段，设S1={A},S2={B1,B2},S3={C1,C2,C3,C4},S4

7、二{Dl,D2,D3},Fk(u)表示从Sk中的点u到E的垠短距离，贝U并且有边界条件显然可以递推地求出F1(A),也就是从A到E的最短距离。这种算法的复杂度为O(n),因为所有的状态总数(节点总数)为m对每个状态都只要遍历一-次，而口程序很简洁。具体算法如下：procedureDynamicFrogramming;beginF5[E]:=0;fori:=4downto1doforeachuWSkdobeginFk[u]:=无穷大；foreachvWSk+1PI6(u)doifFk[u]>w(u,v

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