当前位置:首页 >> 城乡/园林规划 >>

动态规划与网络流


动态规划与网络流——动态规划是易设计易实现的算法 由于图的关系复杂而无序,一般难以呈现阶段特征(除了特殊的图如多 段图--参见例一),因此动态规划在图论中的应用不多。但有一类图, 它的点却是有序的,这就是无环有向图。 在有向无环图中, 我们可以对点进行拓扑排序, 使其体现出有序的特征, 从而据此划分阶段。在有向无还图中求最短路径的算法,已经体现出了 简单的动态规划思想。请看下面的例子。

[例 16] 单源最短路径问题 已知从 A 到 J 的路线及费用如上图,求从 A 到 J 的最小费用路线。 问题的分析和解答: 本问题没有明显的阶段划分,各点间没有一定的先后次序(请注意与例 一不同),不能按照最少步数来决定顺序,如从 A 到 D 走捷径需 4,但 A-C-D 只需 3,更优。看来图中出现回路,不能实施动态规划。其实不 然。细想一下,从 A 到 J 的最优策略,它每一部分也是最优的(可以用 反证法来证明),换言之,本题也具有最优化性质,只是阶段不明显而 已。

对于这类问题,我们可以换个角度分析,构造算法。比较一下前面所讲 的动态规划法,都是以某个状态为终点,寻找到达次点的路径,然后比 较优劣,确定此状态最优值。可是,本题阶段不明显,各状态之间的道 路会出现嵌套,故此法不能使用。变一下角度,每次都以某个状态为起 点,遍历由它引申出去的路径,等所有已知状态都扩展完了,再来比较 所有新状态,把值最小的那个状态确定下来,其它的不动。如上图,先 从 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 点的最优值确定为止。 细心观察, 其实本题的隐含阶段就是以各结点的最优值的大小来划分的, 上述过程就是按最优值从小到大前向动态规划。 人们习惯上把此题归入 到图论范畴中,并将上述方法称为标号法。这个算法就是图论中著名的 Dijkstra 单源最短路径算法。 事实上,动态规划在图论中还有更多的应用,请看下例: [例 17] N 个人的街道问题

在街道问题(参见例 7)中,若有 N 个人要从左下角走向右上角,要求 他们走过的边的总长度最大。当然,这里每个人也只能向右或向上走。 下面是一个样例,左图是从出发地到目的地的三条路径,右图是他们所 走过的边,这些边的总长度为 5 + 4 + 3 + 6 + 3 + 3 + 5 + 8 + 8 + 7 + 4 + 5 + 9 + 5 + 3 = 78(不一定是最大)。

这个题目是对街道问题的又一次扩展。仿照街道问题的解题方法,我们 仍然可以用动态规划来解决本题。 不过这一次是 N 个人同时走, 状态变 量也就需要用 N 维向量来表示。 相应的, 决策变量也要变成 N 维向量:

状态转移方程不需要做什么改动:

在写规划方程时,需要注意在第 k 阶段,N 条路径所走过的边的总长度 的计算,在这里用 来表示了:

边界条件为

可见将原来的动态规划算法移植到这个问题上来, 在理论上还是完全可 行的。 但是, 现在的这个动态规划算法的时空复杂度已经是关于 N 的指 数函数,只要 N 稍微大一点,这个算法就不可能实现了。 下面我们换一个思路,将 N 条路径看成是网络中一个流量为 N 的流, 这样求解的目标就是使这个流的费用最大。 但是本题又不同于一般的费 用流问题,在每一条边 e 上的流费用并不是流量和边权的乘积 而是用下式计算: ,

为了使经典的费用流算法适用于本题,需要将模型稍微转化一下:

如图, 将每条边拆成两条,拆开后一条边上有权 w0, 但是容量限制为 1; 另一条边没有容量限制,但是流过这条边就不计费用。这样我们就把问 题转化成了一个标准的最大费用固定流问题。 这个算法可以套用经典的最小费用最大流算法,在此就不细说了。

IOI97 的“障碍物探测器”比这一题要复杂一些, 但是基本思想是相似的。 类似的题目还有 99 年冬令营的“迷宫改造”。从这些题目中都可以看到 动态规划和网络流的联系。 推广到一般情况,任何有向无环图中的费用流问题在理论上说,都可以 用动态规划来解决。对于流量为 N(如果流量不固定,这个 N 需要事先 求出来) 的费用流问题, N 维的向量 xk=(xk,1,xk,2,…,xk,N)来描述状态, 用 其中 xk,i∈V , 1≤i≤N 。 相应的, 决策也用 N 维的向量 uk=(uk,1,uk,2,…,uk,N) 来表示,其中 uk,i∈E(xk,i) , 1≤i≤N ,E(v)表示指向 v 的弧集。则状态转 移方程可以这样表示:

规划方程为

边界条件为

在大多数情况下,动态规划的实现比网络流要简单的多。但是,由于 N 维动态规划算法是指数级算法,因而在实现中的局限性很大,仅可用于 一些 N 非常小的题目适用。


赞助商链接
相关文章:
更多相关标签: