Ford–Fulkerson算法铁路运输系统中车辆流问题的研究(4)
时间:2016-12-28 17:33 来源:毕业论文 作者:毕业论文 点击:次
：我们利用下面的方法来定义 ： 令 ， 若 ，且 ，则令 ； 若 ，且 ，则令 ； 因为不存在关于 的增广路，故 。 记 ，于是得到一个割集 。显然必有 所以 。于是 必是最大流。 得证。 上面的定理为我们提供了寻求网络 中最大 流的一个方法，这也是Ford–Fulkerson算法的思想。若给了一个可行流 ，只要判断 中有无关于 的 增广路。如果有增广路, 则可以按定理证明 中的办法，改进 ，得到一个流量增大的新的可行流。如果没有增广路，则得到最大流。而利用定理的后半部证明 中定义 的办法, 可以根据 是否属于 来判断 中有无关于 的 增广路[13]。 2.2 Ford–Fulkerson算法的具体步骤 Ford–Fulkerson算法[1][11]，其基本步骤如下： （1）先找一条可行的 流，可以从 开始（因为对于每一条弧 ，有 ，所以 是一个可行流）； （2）在 中寻找一条 增广路 ； （3）如果存在这样的增广路 ，则沿着增广路 给 流 增广 个单位； （4）重复（2）（3）步骤，直到 中没有 增广路； （5）得到 即为网络 的最大 流。 2.3 Ford–Fulkerson算法的实现——标号法 从一个可行流 出发（若网络中未规定 ，则通常可以设 为零流），然后经过标号过程与调整过程两个过程。 1、标号过程 在这个过程，网络中的点或者为标号点（又分为已检查和未检查两种），或者是未标号点。每个标号点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广路；第二个标号是为确定增广路的调整量 用的。 标号的过程开始，总先给 标上 ，这时 是标号而未检查的点，其余的都是未标号点。一般地，取一个已标号但未检查的点 来检查，对一切未标号点 有两种情况： （1）若在弧 上， ，则给 标号 。这里 。这时点 成为已标号但未检查的点。 （2）若在弧 上， ，则给 标号 。这里 。这时点 成为已标号但未检查的点。 于是 成为已标号并检查过的点。重复上述步骤，一旦 被标上号，表明得到一条从到的增广路，转入调整过程。 若所有标号都是已检查的，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。 2、调整过程 首先按 及其他点的第一个标号，利用“反向追踪”的办法，找出增广路 。例如设 的第一个标号为 ，则弧 （或相应地 ）是 上的弧。接下来检查 的第一个标号，若为 （或为 ），则找出 （或相应地 ）。再检查 的第一个标号，依次下去，直到 为止。这时被找出的弧就构成了增广路 。令调整量 ，即 的第二个标号。令 去掉所有的标号，对新的可行流 ，重新进入标号过程。[8][13] 2.4 寻求最大流的标号法举例 例，如下图2.1所示的网络中，弧旁是 ，用标号法求其最大流。[13] 图 2.1 网络的初始流量图 解：（1）标号过程 ① 首先给 标上 。 ② 检查 ，在弧 上， ，给 标号 ，其中 。弧 上， ，不满足标号条件。 ③ 检查 ，在弧 上， ，给 标号 ，其中 。 ④ 检查 ，在弧 上， ，不满足标号条件。 ⑤ 检查 ，在弧 上， ，给 标号 ，其中 。 在弧 上， ，给 标号 ，其中 。 在弧 上， ，给 标号 ，其中 ，因 有了标号，故转入调整过程。 （2）调整过程：按第一个标号找到一条增广路, 如图2.2中双箭头线表示。 图 2.2 网络的增广路易得： 按 在 上调整 。 其余的 不变。 调整后得如下图2.3中的可行流，再对此可行流进行标号，并寻找增广路。 (责任编辑：qin) |