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

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

1、中国数学建模-编程交流-动态规划算法_3中国数学建模-编程交流-动态规划算法wh-ee重登录隐身用户控制面板搜索风格论坛状态论坛展区社区服务社区休闲网站首页退出>>VC++,C,Perl,Asp...编程学习,算法介绍.我的收件箱(0)中国数学建模→学术区→编程交流→动态规划算法您是本帖的第642个阅读者*贴子主题：动态规划算法b等级：职业侠客文章：470积分：956门派：黑客帝国注册：2003-8-28第21楼动态规划与网络流——动态规划是易设计易实现的算法由于图的关系复杂而无序，一般难以呈现阶段特征（除了特殊的

2、图如多段图--参见例一），因此动态规划在图论中的应用不多。但有一类图，它的点却是有序的，这就是无环有向图。在有向无环图中，我们可以对点进行拓扑排序，使其体现出有序的特征，从而据此划分阶段。在有向无还图中求最短路径的算法，已经体现出了简单的动态规划思想。请看下面的例子。[例16]单源最短路径问题已知从A到J的路线及费用如上图，求从A到J的最小费用路线。问题的分析和解答：本问题没有明显的阶段划分，各点间没有一定的先后次序（请注意与例一不同），不能按照最少步数来决定顺序，如从A到D走捷径需4，但A-C-D只需3，更优。看来图

3、中出现回路，不能实施动态规划。其实不然。细想一下，从A到J的最优策略，它每一部分也是最优的（可以用反证法来证明），换言之，本题也具有最优化性质，只是阶段不明显而已。对于这类问题，我们可以换个角度分析，构造算法。比较一下前面所讲的动态规划法，都是以某个状态为终点，寻找到达次点的路径，然后比较优劣，确定此状态最优值。可是，本题阶段不明显，各状态之间的道路会出现嵌套，故此法不能使用。变一下角度，每次都以某个状态为起点，遍历由它引申出去的路径，等所有已知状态都扩展完了，再来比较所有新状态，把值最小的那个状态确定下来，其它的不动

4、。如上图，先从A出发，找到3个结点B，D，C，费用为F（B）=3，F（D）=4，F（C）=2。因为F（B），F（D）都大于F（C），那么可以确定：不可能再有路线从B或D出发到C，比A-C更优。这样F（C）的最优值便确定了。可是，有没有路线从C出发到B或D，比A-B或A-D更优呢？还不清楚。继续下去，因为A扩展完了，只有从C开始，得到A-C-D=3，A-C-F=3，于是F（D）的值被刷新了，等于3。现在，有F（B）=F（D）=F（F）=3，于是，三点的最优值都确定下来了。然后以分别以三个点为起点，继续找。以次类推，直到J

5、点的最优值确定为止。细心观察，其实本题的隐含阶段就是以各结点的最优值的大小来划分的，上述过程就是按最优值从小到大前向动态规划。人们习惯上把此题归入到图论范畴中，并将上述方法称为标号法。这个算法就是图论中著名的Dijkstra单源最短路径算法。事实上，动态规划在图论中还有更多的应用，请看下例：[例17]N个人的街道问题在街道问题（参见例7）中，若有N个人要从左下角走向右上角，要求他们走过的边的总长度最大。当然，这里每个人也只能向右或向上走。下面是一个样例，左图是从出发地到目的地的三条路径，右图是他们所走过的边，这些边的总

6、长度为5+4+3+6+3+3+5+8+8+7+4+5+9+5+3=78（不一定是最大）。这个题目是对街道问题的又一次扩展。仿照街道问题的解题方法，我们仍然可以用动态规划来解决本题。不过这一次是N个人同时走，状态变量也就需要用N维向量来表示。相应的，决策变量也要变成N维向量：状态转移方程不需要做什么改动：在写规划方程时，需要注意在第k阶段，N条路径所走过的边的总长度的计算，在这里用来表示了：边界条件为可见将原来的动态规划算法移植到这个问题上来，在理论上还是完全可行的。但是，现在的这个动态规划算法的时空复杂度已经是关于N的

7、指数函数，只要N稍微大一点，这个算法就不可能实现了。下面我们换一个思路，将N条路径看成是网络中一个流量为N的流，这样求解的目标就是使这个流的费用最大。但是本题又不同于一般的费用流问题，在每一条边e上的流费用并不是流量和边权的乘积，而是用下式计算：为了使经典的费用流算法适用于本题，需要将模型稍微转化一下：如图，将每条边拆成两条,拆开后一条边上有权w0，但是容量限制为1；另一条边没有容量限制，但是流过这条边就不计费用。这样我们就把问题转化成了一个标准的最大费用固定流问题。这个算法可以套用经典的最小费用最大流算法，在此就不细

8、说了。IOI97的“障碍物探测器”比这一题要复杂一些，但是基本思想是相似的。类似的题目还有99年冬令营的“迷宫改造”。从这些题目中都可以看到动态规划和网络流的联系。推广到一般情况，任何有向无环图中的费用流问题在理论上说，都可以用动态规划来解决。对于流量为N（如果流量不固定，这个N需要事先求出来）的费用流问题，用N维的向量xk=(x