中国数学建模-编程交流-动态规划算法_1

《中国数学建模-编程交流-动态规划算法_1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中国数学建模-编程交流-动态规划算法_1中国数学建模-编程交流-动态规划算法wh-ee重登录隐身用户控制面板搜索风格论坛状态论坛展区社区服务社区休闲网站首页退出>>VC++,C,Perl,Asp...编程学习,算法介绍.我的收件箱(0)中国数学建模→学术区→编程交流→动态规划算法您是本帖的第640个阅读者*贴子主题：动态规划算法b等级：职业侠客文章：470积分：956门派：黑客帝国注册：2003-8-28鲜花(0)鸡蛋(0)楼主动态规划算法动态规划DynamicProgrammingStarfish(starfish.h@china.

2、com)摘要本文介绍了动态规划的基本思想和基本步骤，通过实例研究了利用动态规划设计算法的具体途径，讨论了动态规划的一些实现技巧，并将动态规划和其他一些算法作了比较，最后还简单介绍了动态规划的数学理论基础和当前最新的研究成果。----------------------------------------------plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);2004-5-2819:39:12b等级：职业侠客文章：470积分：9

3、56门派：黑客帝国注册：2003-8-28第2楼目录引言动态规划的基本概念动态规划的基本定理和基本方程动态规划的适用条件动态规划的基本思想动态规划的基本步骤动态规划的实例分析动态规划的技巧动态规划实现中的问题动态规划与其他算法的比较动态规划的理论基础其他资料----------------------------------------------plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);2004-5-2819:41:31b

4、等级：职业侠客文章：470积分：956门派：黑客帝国注册：2003-8-28第3楼引言——由一个问题引出的算法考虑以下问题[例1]最短路径问题现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图1所示，试找出从结点A到结点E的最短距离。图1我们可以用深度优先搜索法来解决此问题，该问题的递归式为其中是与v相邻的节点的集合，w(v,u)表示从v到u的边的长度。具体算法如下：----------------------------------------------plot(100+t+15*cos(3.05*t)

5、,t=0..200,coords=polar,axes=none,scaling=constrained);2004-5-2819:42:19b等级：职业侠客文章：470积分：956门派：黑客帝国注册：2003-8-28第4楼functionMinDistance(v):integer;beginifv=Ethenreturn0elsebeginmin:=maxint;for所有没有访问过的节点idoifv和i相邻thenbegin标记i访问过了;t:=v到i的距离+MinDistance(i);标记i未访问过;ift

6、n=t;end;end;end;----------------------------------------------plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);2004-5-2819:42:36b等级：职业侠客文章：470积分：956门派：黑客帝国注册：2003-8-28第5楼开始时标记所有的顶点未访问过，MinDistance(A)就是从A到E的最短距离。这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外

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

8、将每次求出的从v到E的最短距离记录下来，在算法中递归地求MinDistance(v)时先检查以前是否已经求过了MinDistance(v)，如果求过了则不用重新求一遍，只要查找以前的记录就可以