0 概述

网络最大流问题紧密结合图论与运筹学, 为图论的应用开辟了新途径。解决最大流问题即讨论如何充分利用装置有限的容量来实现运输流量最大。针对这一问题, 很多学者提出了相应的求解算法, 主要可分为增广链算法和预流推进算法两类。经典增广链算法有Ford-Fulkerson算法^[1]、Edmonds-karp算法^[2]和最短增广链算法^[3], 经典预流推进算法有阻塞流算法^[4]和推进重标号算法^[5]。许多学者对网络最大流问题也做了进一步深入的研究^[6], 针对经典算法提出了多种改进算法^[7-11], 如利用容差进行修正的最大流2F算法^[7]、有条件限制的最大流求解算法^[9]、动态网络的最大流增量算法^[10]及大规模网络的最大流求解算法^[11]。文献[12-13]则提出了最短增广链改进算法。

最短增广链算法构建的分层剩余网络AD(f), 使网络中的(v_s, v_t)路始终是剩余网络D(f)中的最短(v_s, v_t)路。相比D(f), 在AD(f)中更易寻找(v_s, v_t)路, 但有时AD(f)中含有交叉顶点, 如果仍然任意选择增广链而不考虑增广先后顺序, 则可能会导致之后构建的AD(f)中某些增广链缺失。

为提高最短增广链算法的准确性, 本文提出一种基于交叉顶点的最大流改进算法。在分层剩余网络AD(f)中依次选择顶点容差较小的顶点, 以下一步推进的原则找到第一条增广链, 在此基础上寻找与该条增广链有交叉顶点的相关增广链, 从而避免在AD(f)中选择增广链的任意性, 提高算法效率。

1 基本概念

定义1  容量网络

给定一个有向图G(V, A), c是定义在A上的正值函数, ∀a∈A, a=(v_i, v_j), c(a)=c_ij, 其中, V、A、c分别表示该有向图的顶点集、弧集和弧上的容量值, 称网络D=(V, A, c)为容量网络^[14]。

定义2  剩余网络

剩余网络为D(f)=(V, A(f), c_f), 其中, f为容量网络D=(V, A, c)上的可行流。定义:

$ \begin{array}{*{20}{l}} {{A^ + }(f) = \left\{ {\left( {{v_i}, {v_j}} \right)\mid \left( {{v_i}, {v_j}} \right) \in A, {f_{ij}} < {c_{ij}}} \right\}}\\ {{A^ - }(f) = \left\{ {\left( {{v_i}, {v_j}} \right)\mid \left( {{v_j}, {v_i}} \right) \in A, {f_{ji}} > 0} \right\}} \end{array} $

记A(f)=A⁺(f)∪A^-(f), 对∀(v_i, v_j)∈A(f), 令:

$ {c_{ij}}(f) = \left\{ {\begin{array}{*{20}{l}} {{c_{ij}} - {f_{ij}}, \left( {{v_i}, {v_j}} \right) \in {A^ + }(f)}\\ {{f_{ii}}, \left( {{v_i}, {v_j}} \right) \in {A^ - }(f)} \end{array}} \right. $

称c_ij(f)为剩余网络D(f)的剩余容量^[14-15]。

广探法即广度优先搜索^[16-18], 是构造分层剩余网络的基础方法, 具体步骤如下:

步骤1  在含有源点v_s和汇点v_t的容量网络D=(V, A, c)中, 源点V_s记为标号未检查, 令h(v_s)=0, l_s=-1。

步骤2  若存在已标号未检查的顶点, 找到最先标号的顶点v_i, 转步骤3;若所有已标号顶点都检查完, 转步骤4。

步骤3  考察v_i的所有出弧(v_i, v_j), 若v_j未标号, 则将v_j记为已标号未检查, 令h(v_j)=h(v_i)+1, l_j=i; 若v_j已标号则不作处理; 若v_i的所有出弧全部考察完, 则顶点v_i记为已检查, 转步骤2。

步骤4  算法终止, h(v_i)为容量网络D=(V, A, c)中最短(v_s, v_t)路的长度。

定义3  分层剩余网络

根据剩余网络和广探法, 可以给出剩余网络的一个子网络, 即分层剩余网络AD(f)^[14-15], 其定义如下:

$ \begin{array}{*{20}{l}} {{\rm{AD}}(f) = \left( {{V^\prime }(f), {A^\prime }(f), {c_f}} \right)}\\ {{V^\prime }(f) = \left\{ {{v_t}} \right\} \cup \left\{ {{v_i} \in V\mid h\left( {{v_i}} \right) < h\left( {{v_t}} \right)} \right\}}\\ {{A^\prime }(f) = \left\{ {\left( {{v_i}, {v_j}} \right) \in A(f)\mid h\left( {{v_j}} \right) = h\left( {{v_i}} \right) + 1 < h\left( {{v_t}} \right)} \right\} \cup }\\ {\;\;\;{\kern 1pt} \left\{ {\left( {{v_i}, {v_t}} \right) \in A(f)\mid h\left( {{v_i}} \right) = h\left( {{v_t}} \right) - 1} \right\}} \end{array} $

定义4  顶点容差

顶点v(v∈V)的所有出弧容量减去该顶点的所有入弧容量的值为顶点v(v∈V)的容差。

定义5  交叉顶点

在分层剩余网络AD(f)中, 除源点与汇点之外, 如果存在一个顶点包含在两条及两条以上的增广链中, 则称该点为交叉顶点。

定义6  交叉顶点原则

在含有交叉顶点的网络图中, 选择增广链时优先搜索与源点关联且容差最小的顶点作为增广链的下一步推进点。确定一条增广链后, 对与上一条有重复顶点所在的增广链进行增广。

定义7  顶点的度

设M=(V, A)为一个非空有向图, 顶点v∈V, 与顶点v所关联的弧的数目即为顶点的度^[18]。

BA无标度网络是被用来模拟不断增长的网络顶点的无标度网络模型^[19-20], 其创建过程如下:

1) 开始于一个包括m₀个顶点的网络, 每新增一个顶点, 都要相应地连接到m(m < m₀)个已有顶点上。

2) 已有顶点i与新顶点连接的概率为${p_{{v_i}}} = {k_{{v_i}}}/\sum\limits_j {{k_{{v_j}}}} $, 其中, k_vi、k_vj分别表示顶点v_i与顶点v_j的度。

2 基于交叉顶点的最大流算法 2.1 算法设计思想

虽然最短增广链算法构建了分层剩余网络, 使得AD(f)的(v_s, v_t)路都是D(f)中的最短(v_s, v_t)路, 简化了网络, 但在AD(f)中仍存在多条增广链的可能, 而且有时几条增广链中会有一些重合顶点存在, 如果在这种情况下依然任意选择AD(f)中的增广链, 可能会造成某些增广链的缺失, 使得最终的最大流值偏小。针对这一情况, 本文对最短增广链算法寻找增广链的过程进行改进, 不再对AD(f)中多条增广链采取视同一律的处理方式, 而是根据交叉顶点原则来寻找增广链。

2.2 算法步骤

初始化  在容量网络D中取初始可行流f_k(一般取零流作为初始可行流), 令k=1。

步骤1  构造D关于可行流f_k的剩余网络D(f_k), 并对该网络应用广探法构建分层剩余网络AD(f_k)。如果在构建AD(f_k)时汇点v_t得不到标号, 则算法结束, f_k即为网络最大流; 否则转步骤2。

步骤2  在AD(f_k)中根据交叉顶点原则寻找增广链, 即(v_s, v_t)路p, 转步骤3;若不存在(v_s, v_t)路, 则令f_k+1=f_k, k=k+1, 转步骤1。

步骤3  沿着增广链p对f_k进行增广, 增广流值$\delta = \mathop {\min }\limits_{\left( {{v_i}, {v_j}} \right) \in A\left( p \right)} \left\{ {{c_{ij}}\left( {{f_k}} \right)} \right\}且对\forall \left( {{v_i}, {v_j}} \right) \in A\left( p \right), 令{c_{ij}}\left( {{f_k}} \right) = {c_{ij}}\left( {{f_k}} \right) - \delta $并删去剩余容量为0的弧, 得到新的网络, 仍记为AD(f_k), 转步骤2。

3 算法可行性与复杂度分析 3.1 算法可行性分析

本文算法是在最短增广链算法基础上的改进, 改进之处在于寻找增广链时按照交叉顶点原则寻找, 每次找到增广链进行增广后, 至少会使容量网络中的一条弧成为饱和弧。设容量网络D=(V, A, c)中共有m条弧, 若至多经过m次增广后D中不存在源点到汇点的增广链, 即在构建分层剩余网络时汇点得不到标号, 则满足算法的终止条件, 算法在有限步内即可停止, 不会陷入无限循环。

3.2 算法复杂度分析

设容量网络D=(V, A, c), 其顶点数为n, 弧数为m。本文算法整体分为两部分, 即构建分层剩余网络和寻找增广链。由于步骤1中构建造层剩余网络AD(f_k)的层数随k单调递增, AD(f_k)的最高层数至多是(n-1)层, 因此算法中最多建立n个分层剩余网络。

由广探法可知, 每构建一个分层剩余网络的复杂度为O(m), 因此, 本文算法构建分层剩余网络的总复杂度为O(nm)。

在一个分层剩余网络中, 最多有m条弧, 由于每增广1次至少删去1条弧, 因此至多增广m次, 而每次增广的计算量为O(n), 所以，在一个分层剩余网络中寻找增广链的复杂度为O(mn), 从而寻找增广链的总复杂度为O(n²m)。

综上可知, 本文算法的复杂度为:

$ O\left( {nm} \right) + O\left( {{n^2}m} \right) = O\left( {{n^2}m} \right) $

4 算法实例与比较

给出以下实例:在容量网络D中, 求从源点v_s到汇点v_t的最大流, 如图 1所示, 其中, 弧边的数值表示该弧的容量大小, 下同。

当容量网络中存在多条源点到汇点的路径, 且这些路径之间包含相同顶点时, 分别应用本文算法和最短增广链算法进行求解。

本文算法求解过程如下:

1) 取零流f₁作为初始可行流, 得到剩余网络D(f₁), 利用广探法构造分层剩余网络AD(f₁), 见图 2。

2) 在AD(f₁)中计算与v_s相关联顶点的容差, 并将容差值标在相应顶点的旁边。选择容差值最小的顶点作为下一步推进点增广, 得到增广链p₁=v_sv₂v₄v_t, 可行流f₂见图 3, 其中, 弧边的数值表示该弧的流量大小, 下同。

3) 在AD(f₂)中继续选择与p₁有交叉顶点的增广链进行增广, 得到增广链p₂=v_sv₁v₄v_t, 可行流f₃见图 4。

4) 在AD(f₃)中继续选择与p₂有交叉顶点的增广链进行增广, 得到增广链p₃=v_sv₁v₆v_t, 可行流f₄见图 5。

5) 此时, 在AD(f₄)中没有与p₁~p₃有交叉顶点的增广链, 只剩下增广链p₄=v_sv₃v₅v_t, 由此得到可行流f₅, 见图 6。

6) 此时, 在AD(f₅)中没有(v_s, v_t)路, 令f₅=f₆, 重新构造分层剩余网络AD(f₆), 见图 7, 并在其中找到增广链p₅=v_sv₃v₅v₆v_t, 可行流f₇见图 8。

7) 此时, AD(f₇)中没有(v_s, v_t)路, 令f₇=f₈, 构建剩余网络D(f₈), 见图 9。由于D(f₈)中不存在(v_s, v_t)路, 因此f₈为容量网络D的最大流, 流值为19。

最短增广链算法求解过程如下:

1) 取零流f₁作为初始可行流, 构建分层剩余网络AD(f₁), 见图 2。

2) 在图 2中找增广链, 找到增广链p₁~p₄:

$ \begin{array}{*{20}{l}} {{p_1} = {v_{\rm{s}}}{v_1}{v_6}{v_{\rm{t}}}, {\delta _1} = 6}\\ {{p_2} = {v_{\rm{s}}}{v_1}{v_4}{v_{\rm{t}}}, {\delta _2} = 3}\\ {{p_3} = {v_{\rm{s}}}{v_2}{v_4}{v_{\rm{t}}}, {\delta _3} = 4}\\ {{p_4} = {v_{\rm{s}}}{v_3}{v_5}{v_{\rm{t}}}, {\delta _4} = 3} \end{array} $

增广之后, 得到可行流f′₂, 见图 10。

3) 继续构建剩余网络D(f′₂), 见图 11。发现D(f′₂)中不存在(v_s, v_t)路, 算法结束。f′₂记为容量网络D的最大流, 流值为16。

可以看出, 最短增广链算法在分层剩余网络中选取增广链的任意性会导致增广链缺失, 从而使最后得到的最大流值偏小。

5 仿真与结果分析 5.1 实验环境与设计

本文使用的实验仿真平台是MATLAB2016a, 处理器为Intel^® Core^TM i3-4030U CPU @1.90 GHz, 内存4 GB, Windows7版本64位操作系统。

仿真实验采用的是BA无标度随机网络, 将网络规模设为顶点数为500、1 000、1 500、2 000、2 500、3 000、3 500。在给定的网络规模下, 对本文算法和最短增广链算法进行10次仿真实验。其中, 参数f₁和t₁分别表示最短增广链算法的最大流值及其运行时间的平均值, 参数f₂和t₂分别表示本文算法的最大流值及其运行时间的平均值。

5.2 实验结果分析

实验结果如表 1所示, 其中列出了2种算法在不同网络规模下得到的最大流值及算法的平均运行时间。可以看出, 本文算法较最短增广链算法结果更精准，并且运行时间相差较小。

6 结束语

最短增广链算法在分层剩余网络中寻找增广链的任意性可能导致增广链缺失。针对该问题, 本文提出一种基于交叉顶点的改进算法。在寻找增广链时不再视同一律, 而是遵循顶点交叉原则, 从而避免增广链缺失的情况, 提高算法的准确性。实验结果表明, 该算法得到的最大流值比最短增广链算法更准确, 并且运行效率相当。后续将在保证准确率的基础上, 进一步提高算法的运行效率。