动态规划与网络流

动态规划与网络流——动态规划是易设计易实现的算法由于图的关系复杂而无序，一般难以呈现阶段特征(除了特殊的图如多段图--参见例一)，因此动态规划在图论中的应用不多。但有一类图，它的点却是有序的，这就是无环有向图。在有向无环图中，我们可以对点进行拓扑排序，使其体现出有序的特征，从而据此划分阶段。在有向无还图中求最短路径的算法，已经体现出了简单的动态规划思想。请看下面的例子。[例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维向量：兔~（耳1，孔2,T）矗=（姝1，叫2,…山加）状态转移方程不需要做什么改动：状态转移方程不需要做什么改动：在写规划方程时，需要注意在第k阶段，N条路径所走过的边的总长度的计算，在这里用来表示了：人区）二“驚｝（兀-1区-1）+劭区亦））边界条件为可见将原来的动态规划算法移植到这个问题上来，在理论上还是完全可行的。但是，现在的这个动态规划算法的时空复杂度已经是关于N的指数函数，只要N稍微大一点，这个算法就不可能实现了。下面我们换一个思路，将N条路径看成是网络中一个流量为N的流，这样求解的目标就是使这个流的费用最大。但是本题又不同于一般的费用流问题，在每一条边e上的流费用并不是流量和边权的乘积 ，而是用下式计算：两>0'.0/（^）=0为了使经典的费用流算法适用于本题，需要将模型稍微转化一下：如图，将每条边拆成两条，拆开后一条边上有权w0,但是容量限制为1；另一条边没有容量限制，但是流过这条边就不计费用。这样我们就把问题转化成了一个标准的最大费用固定流问题。这个算法可以套用经典的最小费用最大流算法，在此就不细说了。IOI97的“障碍物探测器”比这一题要复杂一些，但是基本思想是相似的。类似的题目还有99年冬令营的“迷宫改造”。从这些题目中都可以看到动态规划和网络流的联系。推广到一般情况，任何有向无环图中的费用流问题在理论上说，都可以用动态规划来解决。对于流量为N（如果流量不固定，这个N需要事先求出来）的费用流问题，用N维的向量Xk=（Xk,],Xk2，...,Xk,N）来描述状态，其中XkjUV,lWiWN。相应的，决策也用N维的向量比二⑴第比公…叫小）来表示，其中uk,ieE（xk,i）,1WiWN，E（v）表示指向v的弧集。则状态转移方程可以这样表示：忑_叮=叽的弧尾节点规划方程为人区）二opt（Xi区_i）+附宓）），其中販区）二工叭仏