动态规划算法工科.docVIP

?动态规划算法 动态规划Dynamic Programming Starfish (starfish.h@) 摘要 本文介绍了动态规划的基本思想和基本步骤，通过实例研究了利用动态规划设计算法的具体途径，讨论了动态规划的一些实现技巧，并将动态规划和其他一些算法作了比较，最后还简单介绍了动态规划的数学理论基础和当前必威体育精装版的研究成果。 ? 目录 引言 动态规划的基本概念 动态规划的基本定理和基本方程 动态规划的适用条件 动态规划的基本思想 动态规划的基本步骤 动态规划的实例分析 动态规划的技巧 动态规划实现中的问题 动态规划与其他算法的比较 动态规划的理论基础 引言——由一个问题引出的算法 考虑以下问题 [例1] 最短路径问题 现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图1所示，试找出从结点A到结点E的最短距离。 图 1 我们可以用深度优先有哪些信誉好的足球投注网站法来解决此问题，该问题的递归式为 其中是与v相邻的节点的集合，w(v,u)表示从v到u的边的长度。 具体算法如下： function MinDistance(v):integer;beginif 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 tmin 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年出版了