包含交叉顶点的最大流改进算法

罗甜甜,赵礼峰

(南京邮电大学 理学院,南京 210023)

0 概述

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

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

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

1 基本概念

定义1容量网络

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

定义2剩余网络

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

记A(f)=A+(f)∪A-(f),对∀(vi,vj)∈A(f),令:

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

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

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

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

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

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

定义3分层剩余网络

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

AD(f)=(V′(f),A′(f),cf)

V′(f)={vt}∪{vi∈V|h(vi)

A′(f)={(vi,vj)∈A(f)|h(vj)=h(vi)+1

{(vi,vt)∈A(f)|h(vi)=h(vt)-1}

定义4顶点容差

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

定义5交叉顶点

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

定义6交叉顶点原则

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

定义7顶点的度

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

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

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

2 基于交叉顶点的最大流算法

2.1 算法设计思想

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

2.2 算法步骤

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

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

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

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

3.1 算法可行性分析

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

3.2 算法复杂度分析

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

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

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

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

O(nm)+O(n2m)=O(n2m)

4 算法实例与比较

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

图1 容量网络D

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

本文算法求解过程如下:

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

图2 分层剩余网络AD(f1)

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

图3 可行流f2

3)在AD(f2)中继续选择与p1有交叉顶点的增广链进行增广,得到增广链p2=vsv1v4vt,可行流f3见图4。

图4 可行流f3

4)在AD(f3)中继续选择与p2有交叉顶点的增广链进行增广,得到增广链p3=vsv1v6vt,可行流f4见图5。

图5 可行流f4

5)此时,在AD(f4)中没有与p1～p3有交叉顶点的增广链,只剩下增广链p4=vsv3v5vt,由此得到可行流f5,见图6。

图6 可行流f5

6)此时,在AD(f5)中没有(vs,vt)路,令f5=f6,重新构造分层剩余网络AD(f6),见图7,并在其中找到增广链p5=vsv3v5v6vt,可行流f7见图8。

图7 分层剩余网络AD(f6)

图8 可行流f7

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

图9 剩余网络D(f8)

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

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

2)在图2中找增广链,找到增广链p1～p4:

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

图10 可行流f′2

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

图11 剩余网络D(f′2)

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

5 仿真与结果分析

5.1 实验环境与设计

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

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

5.2 实验结果分析

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

表1 本文算法与最短增广链算法在不同网络规模下的实验结果

6 结束语

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