图论问题在计算机科学领域具有重要地位, 作为运筹学领域的一个重要分支, 当今最大流算法已经被广泛运用于实际工程与技术中. 例如, 计算机网络中基于最大流的路由选择算法^{[1, 2]}, 分布式存储系统的查询^[3], 除此之外, 最大流算法还大量运用于计算机视觉领域中对图形的分割、立体和重塑^{[4, 5]}, 以及机器学习领域^{[6, 7]}. 因此, 为了提升对大数据量最大流模型的求解速度, 对最大流算法的优化是十分必要的, 最大流问题的研究具有较高的实用价值.

最大流问题是指在一张给定流网络上进行搜索、计算由源点s出发到汇点t的最大可行流量. 最大流算法大体上分为两大类: 第1类是由Ford等人在1956年提出的增广算法^[8], 增广算法将网络中所能找到的任意一份流量称为可行流量, 当且仅当其符合容量限制与流守恒定律. 该类算法的思想是在流网络中不断地寻找增广路径与该路径的阻塞流, 直到网络中由源点s到汇点t的所有可行路径都被阻塞, 即网络中不存在任何一条增广路径时, 算法终止. 第2类最大流算法是由Karzanov在1974年提出的基于“预流”概念的预流推送算法^[9].

对于基于增广路径的经典算法Ford-Fulkerson算法而言, Edmonds等人^[10]和Dinitz^[11]分别在1972年和1970年提出了运用层次网络来对搜索策略进行改进. 随着大数据时代的来临, 信息数据量爆炸式激增, 传统的增广路径最大流算法的搜索策略无法高效的应用于现今复杂多样的流网络结构. 因此, 许多学者已经对最大流算法提出了优化和改进, 其中包括对动态网络最大流算法的优化, 对包含交叉顶点的最大流算法优化以及通过构建反向有效网络来优化Dinic算法等^[12-17].

在实际工程应用中, 传统基于深度优先策略的Ford-Fulkerson算法和基于宽度优先策略的Edmonds-Karp算法时常因为无法高效的应用于稠密网络而不受工程实践者的青睐, 而基于层次网络的Dinic算法有着简洁、易懂且高效的特点, 常受到实践者们的喜爱. 但Dinic算法在实际运用的过程中会反复搜索网络的“无效部分”, 且随着流网络规模及稠密程度的增大, Dinic算法的效率将变得十分低下. 针对这一问题, 本文对基于层次网络的原始Dinic算法在增广路径搜索策略上实现优化, 通过记录单次搜索的搜索状态来实现记忆化搜索, 能够有效地避免算法进行无效的搜索和增广, 最终提高算法效率. 除此之外, 在本文实验部分提出了搜索步数、增广步数以及有效搜索率等概念来衡量、量化和对比算法额外代价与搜索效率.

1 基本概念与定义 1.1 最大流的数学模型

若带权有向网络G=(V,E, W)满足以下两个条件: 1) s、t均属于结点集合V且源点s入度为0, 汇点t出度为0; 2)设c(u,v)为边容量, 对任意的边满足:

$ \forall \left( {{{u}}, {{v}}} \right) \in {{E}}, \;{{c}}\left( {{{u}}, {{v}}} \right) = W(u, v) $

(1)

则称G为流网络, 记作G=(V, E, C). 在流网络G=(V, E, C)中, 设实值函数f为G的流, 对任意的边满足容量限制:

$ \forall \left( {{{u}}, {{v}}} \right) \in {{E}},\; 0 \leqslant {{f}}\left( {{{u}}, {{v}}} \right) \leqslant {{c}}\left( {{{u}}, {{v}}} \right) $

(2)

且同时满足流守衡定律:

$ {\displaystyle \sum }_{v\in \text{ }V\backslash u}f\left(v, u\right)={\displaystyle \sum }_{v\in V\backslash u}f\left(u, v\right) $

(3)

则称流f为流网络G上的一个可行流量. 则由流f所诱导的残流网络为 $R = \left( {V, {E_f}, {C_f}} \right)$ , 其中 ${C_f}$ 为R中边残余流量的集合, 边残余流量为:

$ {c_f}\left( {u, v} \right) = \left\{ \begin{gathered} c(u, v) - f(u, v),\; (u, v)\in E \\ f(v, u),\;(v, u)\in E \\ \end{gathered} \right. $

(4)

其中, 对R中任意的边满足:

$ {E_f} = \left\{ {\left( {{{u}}, {{v}}} \right) \in E{{|}}\forall {c_f}\left( {{{u}}, {{v}}} \right) \geqslant 0} \right\} $

(5)

最大流问题是求解当前流网络G中的最大可行流f的容量总和:

$ {f}_{\mathrm{max}}=Max\left({\displaystyle \sum }_{v\in \text{ }V\backslash \left\{t\right\}}f\left(u, t\right)\right) $

(6)

1.2 层次网络

层次网络 $D = \left( {s, t} \right) \in R$ , 记录残流网络R中各结点层次, 其中源点s在首层, 汇点t在末层, 当前残流网络 $R'$ 划分得层次网络 $D'$ 中不包含t, 即 $D' = \left( {s, k} \right)$ , $k \ne t$ 时认为当前残流网络 $R'$ 已经不可再被分层, 即此时无法在残留网络中由s搜索到t.

1.3 动态堆栈与已访问结点集

STACK表示在搜索过程中动态变化的堆栈, 按搜索次序依次存入流网络G中各待处理的结点. SEEN是一个无序的结点集合, 保存当前搜索已访问结点.

1.4 深度优先搜索树

$TREE = (V', E')$ 表示由源点s起始的深度优先搜索树, 以多个有序对(v, u)的形式表示DFS搜索过边(u, v), 其中u是v的前驱结点. 当搜索到汇点t时, 可以由汇点t不断回溯直至源点s, 即:

$ TREE(s, t)=\{(t{\textit{-}}v)\text{, }(v{\textit{-}}\cdots {\textit{-}}u), (u{\textit{-}}s)\} $

(7)

1.5 s-t路径上/下连通性

将一条s-t路径P以结点n分为上、下两个部分, 即 $P = (s {\textit{-}} \cdots {\textit{-}} n {\textit{-}} \cdots {\textit{-}} t) = (s {\textit{-}} \cdots {\textit{-}} n, n {\textit{-}} \cdots {\textit{-}} t)$ , 其中 $ n \in V/\{ s, t\} $ . 定义当 ${c_f}(s {\textit{-}} \cdots {\textit{-}} n) > 0$ 时, 则称路径P为上连通, 当 ${c_f}(n {\textit{-}} \cdots {\textit{-}} t) > 0$ 时, 则称路径P为下连通. 当且仅当 ${c_f}(s {\textit{-}} \cdots {\textit{-}} n) \cdot {c_f}(n {\textit{-}} \cdots {\textit{-}} t) > 0$ 路径P为s-t有效路径, 即增广路径.

2 Dinic算法问题分析

原始Dinic算法的思想是先用宽度优先策略在残流网络R上生成层次网络D, 再对层次网络D采用深度优先策略搜索增广路径, 直至当前层次网络中无法找到任意一条s-t增广路径时, 对当前残流网络重新划分层次, 直至残流网络无法再生成层次网络时, 算法结束. Dinic算法描述如算法1.

算法1. Dinic算法

输入: G=(V, E, C), 源点s和汇点t

输出: 残流网络R和最大流f_max

1) 初始化: $\scriptstyle{R\left( {V, {E_f}, {C_f}} \right) = G\left( {V, E, C} \right)}$ , $\scriptstyle D = \varnothing$ , f_max=0;

2) 步骤1. 使用宽度优先搜索对残流网络R分层, 生成层次网络 $\scriptstyle D = \left( {s, k} \right),\; k \in V$ , 转步骤2;

3) 步骤2. 若汇点t属于层次网络 $\scriptstyle D$ , 则转步骤3; 反之, 返回当前最大流f_max, 算法结束;

4) 步骤3. 在所得层次网络 $\scriptstyle D$ 采用深度优先策略搜索s-t增广路径P. 若路径P存在, 则转步骤4; 反之, 转步骤1;

5) 步骤4. 计算路径P的阻塞流:

$\scriptstyle {c_f}\left( P \right) = \min \left( {R\left( {u, v} \right){\text{|}}\forall \left( {u, v} \right) \in P} \right) $

转步骤5;

6) 步骤5. 执行推流, 更新残流网络:

$\scriptstyle {{R}}\left( {{{u}}, {{v}}} \right) = {{R}}\left( {{{u}}, {{v}}} \right) - {c_f}\left( P \right), \; \forall \left( {{{u}}, {{v}}} \right) \in {{P}} $

$\scriptstyle {{R}}\left( {{{v}}, {{u}}} \right) = {{R}}\left( {{{v}}, {{u}}} \right) + {c_f}\left( P \right),\; \forall \left( {{{u}}, {{v}}} \right) \in {{P}} $

转步骤6;

7) 步骤6. 更新最大流 $\scriptstyle{f_{\max}} = {f_{\max}} + {c_f}\left( P \right)$ , 转步骤3;

2.1 原始Dinic算法与深度优先策略问题分析

原始Dinic算法在层次网络中搜索增广路径时, 会随着搜索次数的增加逐渐减慢算法在单张层次网络上的收敛速度, 其原因是深度优先搜索策略总是从源点s起始, 每当成功找到s-t路径时, 其阻塞流几乎无可避免地会对后续若干次路径搜索产生影响. 在后续搜索中, 深度优先的搜索策略会继续反复的搜索残流网络中的“无效部分”, 这些“无效部分”是若干次搜索所阻塞的路径或流网络中本来就存在的仅具有上连通性而不具有下连通性的路径的集合. 最坏情况下, Dinic算法在单张层次网络上每次搜索一条s-t增广路径的代价随搜索次数依次递增.

如图1(a)所示层次网络为例, 当前层次为3. 图1–图3展示了深度优先策略的搜索步骤, 其中右侧所示STACK是搜索过程中动态堆栈. 表1汇总了搜索过程及搜索代价.

由上述例子可以得出, 深度优先的搜索策略能够成功地在层次网络中找到所有可能的增广路径P₁、P₂、P₃、P₄、P₅, 但Dinic算法每次都从源点s起始, 额外增加了许多不必要的无效搜索步数, 增加额外开销. 例如, 在搜索增广路径P₂时, (3, 7)是无效搜索步, 见图2(a); 在搜索增广路径P₅时, (s, 3)、(3, 7)、(s, 2)、(2, 6)、(1, 5)是无效搜索步, 见图3(b). 由此可见, Dinic算法在层次网络中搜索增广路径的额外代价随搜索次数增加而递增.

3 记忆化搜索算法 3.1 算法思想

由上述举例中不难发现, 相邻的两次路径搜索过程中至少存在前k步重合( $0 \leqslant k \leqslant n$ , n为网络结点数), 仅后l_P–k步相异(l_P为P的路径长度). 例如, 图2所示增广路径P₂、P₃的搜索过程, 搜索前5步(s, 1)、(s, 2)、(s, 3)、(3, 6)、(3, 7)重合, 仅最后一步(7, t)与(6, t)相异. 则考虑是否能记忆化搜索状态, 保证每次仅搜索网络中未被搜索过的部分. 因此, 本文提出了记忆化搜索策略, 且须保证所找到的路径P满足以下两点.

(1) 满足连通性限制.

(2) 满足最短路径限制.

深度优先搜索策略每次搜索从源点s起始, 仅当 $ {c}_{f}\left(u, v\right) > 0, \left(u, v\right)\in {E}^{\prime } $ 时会继续向下层搜索, 则可保证所得路径 $P'$ 的残余流量 ${c_f}(P') > 0$ , 故Dinic算法满足连通性限制. 对于记忆化搜索策略而言, 假设在残流网络R中找到一条增广路径 $P'$ , 其残余流量 $ {c_f}(P') = $ ${c_f}(s {\textit{-}} \cdots {\textit{-}} u, u {\textit{-}} \cdots {\textit{-}} t) = {c_f}(s {\textit{-}} \cdots {\textit{-}} u) = 0$ , 若下轮搜索从结点u起始得新路径P, 则会导致P的残余流量 ${c_f}(P) = \min \left( {{c_f}(s {\textit{-}} \cdots {\textit{-}} u)} \right., \left. {{c_f}(u {\textit{-}} \cdots {\textit{-}} t)} \right) = {c_f}(s {\textit{-}} \cdots {\textit{-}} u)$ = $0$ . 记忆化搜索策略保证了 ${c_f}(u {\textit{-}} \cdots {\textit{-}} t) > 0$ , 即路径下连通. 但上轮搜索可能会破坏路径的上连通性, 记忆化策略避免从源点s开始搜索, 则无法保证算法满足连通性限制. 因此在每轮记忆化搜索开始前, 须对其进行上连通性校验, 仅当 ${c_f}(s {\textit{-}} \cdots {\textit{-}} u) > 0$ 时, 才由结点u开始恢复路径搜索, 来保证所得s-t路径满足连通性限制, 从而保证路径搜索的有效性.

记忆化搜索策略还需保证所得s-t路径满足最短路径限制. 假设层次网络 $D$ 当前层次为l, 则在残流网络R中不存在路径长度小于l的增广路径, 即 $\forall P \in R|$ $L\left( P \right) \geqslant l$ . 若首次记忆化搜索成功找到增广路径 ${P_1}(s {\textit{-}} \cdots {\textit{-}} u, u {\textit{-}} \cdots {\textit{-}} t)$ 则后续搜索将从结点 $u$ 起始, 其中 $u \in V/\left\{ {s, t} \right\}$ , 设结点u属于 $D$ 中第h层 $(1\leqslant h＜l)$ , 则由首次搜索可以保证 ${P'_1} = \left( {s {\textit{-}} \cdots {\textit{-}} u} \right)$ 是最短路径, 其路径长度 $L\left( {{{P_1'}}} \right) = h$ , 而后续搜索由层次网络性质可以保证 ${P_2} = \left( {u {\textit{-}} \cdots {\textit{-}} t} \right)$ 的路径长度满足 $L({P_2}) \leqslant l - h$ , 故当前s-t路径长度满足 $L\left( {{{P_1'}}} \right) + L\left( {{P_2}} \right) \leqslant l$ . 综上, 若当前残流网络R存在s-t增广路径, 则其路径长度必为l, 即满足最短路径限制.

3.2 算法描述

本文提出的记忆化搜索策略与常规深度优先搜索策略不同之处在于, 算法将上轮搜索结果和状态保存在STACK, SEEN, TREE中, 在此基础上进行下一次搜索并持续更新当前搜索状态, 来保证每次调用搜索时总能针对网络中未搜索过的部分, 避免了原始Dinic算法反复的搜索残流网络中的“无效部分”. 从宏观上看, 每轮执行的若干次记忆化搜索等效于在单张层次网络上进行一次完整的深度优先遍历, 得到若干条增广路径. 记忆化搜索算法描述如算法2.

算法2. 记忆化搜索算法

输入: $\scriptstyle R = \left( {V, E, C'} \right)$ , D, STACK, SEEN, TREE, 源点s和汇点t

输出: STACK, SEEN, TREE

1) 步骤1. 若STACK非空则取栈顶元素u, 转步骤2; 反之, 算法结束;

2) 步骤2. 若所取得顶点u是源点s, 则转步骤4; 反之, 转步骤3;

3) 步骤3. 若结点u在搜索树TREE中上连通性校验通过, 则转步骤4; 反之, 将结点u设置成未访问态, 即 $\scriptstyle {\textit{SEEN}} = {\textit{SEEN}}\backslash \left\{ u \right\}$ , 转步骤1;

4) 步骤4. 获取结点u的邻接结点v, 转步骤5;

5) 步骤5. 若结点v是未访问态, 即 $\scriptstyle v \notin {\textit{SEEN}}$ , 转步骤6; 反之, 转步骤4;

6) 步骤6. 若邻接结点v在结点u的下一层, 即 $\scriptstyle D[v] = D[u] + 1$ , 转步骤7; 反之, 转步骤4;

7) 步骤7. 将结点v加入动态堆栈STACK; 将结点v设置成已访问态; 将边 $\left( {v, u} \right)$ 加入TREE; 结点v迭代结点u, 即 $\scriptstyle u \leftarrow v$ , 转步骤4.

基于记忆化搜索策略的最大流算法首先会根据残流网络R来构建层次网络 $D$ , 在层次网络上不断执行记忆化搜索算法来寻找增广路径, 直到当前层次网络无法再被找到任意一条s-t增广路径时, 对当前残流网络重新划分层次, 直到所划分的层次网络中不包含t时, 算法结束. 此时所找到的增广路径的流量总合为最大流. 算法流程图见图4. 算法描述如算法3.

算法3. 基于记忆化搜索策略的最大流算法

输入: G=(V, E, C), 源点s和汇点t

输出: 残流网络R和最大流f_max

1) 初始化: $\scriptstyle R\left( {V, {E_f}, {C_f}} \right) = G\left( {V, E, C} \right)$ , $\scriptstyle{f_{\max}} = 0$ , $\scriptstyle D = \varnothing ,\; STACK = \varnothing ,\; {\textit{SEEN}} = \varnothing , \; \scriptstyle TREE = \varnothing$ ;

2) 步骤1. 使用宽度优先搜索对残流网络R分层, 生成层次网络 $\scriptstyle D = \left( {s, k} \right), k \in V$ , 转步骤2;

3) 步骤2. 若汇点t属于层次网络D, 转步骤3; 反之, 返回当前最大流f_max, 算法结束;

4) 步骤3. 将源点s加入动态堆栈STACK中, 即 $\scriptstyle {\textit{STACK}} = \left\{ s \right\}$ ; 将源点s设置成已访问态, 即 $\scriptstyle {\textit{SEEN}} = \left\{ s \right\}$ , 转步骤4;

5) 步骤4. 在所得层次网络D上采用记忆化搜索策略搜索s-t增广路径P. 若路径P存在, 则转步骤5; 反之, 转步骤1;

6) 步骤5. 计算路径P的阻塞流:

$\scriptstyle {c_f}\left( P \right) = \min \left( {R\left( {u, v} \right){\text{|}}\forall \left( {u, v} \right) \in P} \right) $

转步骤6;

7) 步骤6. 执行推流, 更新残流网络:

$\scriptstyle {{R}}\left( {{{u}}, {{v}}} \right) = {{R}}\left( {{{u}}, {{v}}} \right) - {c_f}\left( P \right), \forall \left( {{{u}}, {{v}}} \right) \in {{P}} $

$ \scriptstyle {{R}}\left( {{{v}}, {{u}}} \right) = {{R}}\left( {{{v}}, {{u}}} \right) + {c_f}\left( P \right), \forall \left( {{{u}}, {{v}}} \right) \in {{P}} $

转步骤7;

8) 步骤7. 更新最大流 $\scriptstyle {f_{\max}} = {f_{\max}} + {c_f}\left( P \right)$ ; 将汇点t设置成未访问态, 即 $\scriptstyle {\textit{SEEN}} = {\textit{SEEN}}\backslash \left\{ t \right\}$ , 转步骤4.

本文所提出的基于记忆化搜索策略的最大流算法, 须在层次网络上执行搜索. 采用何种搜索策略不直接影响算法何时停止搜索增广路径, 算法的终止条件是当前层次网络中不包含汇点t. 因此, 若所采取的搜索策略能在当前层次网络中找到至少一条s-t增广路径, 则一定能在后续若干张层次网络中找到最大流.

当采用记忆化搜索策略时, 设所找到的s-t增广路径为P, 则每轮搜索会将至少l_P–1 (l_P为P的路径长度)个结点的访问状态标记成已访问态, 并且每轮搜索结束后仅把汇点 $t$ 从 ${\textit{SEEN}}$ 中移除, 从而保证搜索路径不重叠. 但可能会导致某些路径被遗漏, 例如, Dinic算法在如图1(a)所示在层次网络中能找到全部的5条s-t增广路径, 而本文提出的算法无法找到由图2(b)所示增广路径 $P_3 = (s {\textit{-}} 2 {\textit{-}} 6 {\textit{-}} t)$ , 因为记忆化的策略在搜索路径P₂时已经将结点6标记为已访问态, 故只能在下一张层次网络中找到P₃. 对于如图5所示层次网络中的k条增广路径, 则需要通过k张层次网络才能被全部找到.

3.3 实例分析

初始层次网络如图1(a)所示, 当前层次为3. 图6、图7展示了记忆化搜索策略的搜索步骤, 右侧所示 $STACK$ 是搜索过程中动态堆栈, 显示了搜索次序和过程. 图6、图7用虚线标识网络中已搜索过的部分. 表2汇总了记忆化策略的搜索过程及搜索代价.

记忆化策略首次搜索与深度优先策略保持一致, 算法依次遍历结点(s, 1, 2, 3, 6, 7, t)后找到增广路径 $P_1' = (s {\textit{-}} 3 {\textit{-}} 7 {\textit{-}} t)$ , 搜索代价为7, 本次搜索状态将被保留. 搜索过程见图6(a).

第2次搜索从结点6开始, 假设层次网络中边(7,t)被阻塞, 算法通过(6, t)找到汇点t, 搜索所得增广路径为 $P_2' = (s {\textit{-}} 3 {\textit{-}} 6 {\textit{-}} t)$ , 搜索代价为2. 搜索过程见图6(b).

第3次搜索从结点2开始, 假设层次网络中边(7, t)、(3, 6)被阻塞, 由于结点6已经在上轮搜索中已被标记成已访问态, 故算法无法通(2, 6, t)找到汇点t. 因此, 算法将从结点1继续恢复搜索, 依次遍历结点(4, 5, t)找到汇点t, 所得增广路径为 $P_3' = (s {\textit{-}} 1 {\textit{-}} 5 {\textit{-}} t)$ , 本次搜索代价为4. 搜索过程见图7(a).

根据上一轮搜索所保存的搜索状态, 最后一轮搜索从结点4开始, 假设层次网络中边(7, t)、(3, 6)、(5, t)被阻塞, 算法通过(4, t)找到汇点t, 所得增广路径为 $P_4' = (s {\textit{-}} 1 {\textit{-}} 4 {\textit{-}} t)$ , 本次搜索代价为2. 搜索过程见图7(b).

3.4 复杂度分析

若当流网络中存在类似图8(a)所示的带状分支结构, 两条增广路径长度同为k+2, 则路径有效搜索步数 $Vn$ 为 $2 \cdot (k + 2)$ . 如图8(b)、图8(c)所示, 记忆化策略所得两条路径的搜索步数分别为 ${S_{n1}} = k + 2, {S_{n2}} = 2$ ; 则有效搜索率 $Vr = Vn/({S_{n1}} + {S_{n2}}) = 2\left( {k + 2} \right)/(k + 4) > 1, k > 0$ , 故有效搜索率Vr可能大于1.

在包含n个结点、m条边的流网络G中, 最坏情况下, 每张层次网络中仅能找到一条增广路径, 算法效率等同于基于宽度优先搜索策略的Edmonds-Karp算法, 因此最坏复杂度是 ${\rm{O}}(n{m^2})$ . 最优情况下, 每张层次网络中都包含若干条s-t路径, 而G中n个结点所能构成的最长s-t路径长度为n−1, 故流网络G至多能够划分出n张层次网络, 每次构建层次网络的代价为 ${\rm{O}}(m)$ . 记忆化策略搜索增广路径的代价不超过 ${\rm{O}}(n)$ . 因此, 在一张层次网络上搜索和增广推流的总代价不超过 ${\rm{O}}(nm)$ . 在开始搜索前还需要对结点进行上连通性校验, 代价不超过 ${\rm{O}}(n)$ . 所以单张层次网络上记忆化搜索的总代价为 ${\rm{O}}(n + m + nm)$ , 故算法复杂度为 ${\rm{O}}( n(n + m + nm)) = {\rm{O}}({n^2}m)$ . 因此, 算法整体复杂度介于 ${\rm{O}}(n{m^2})$ 与 ${\rm{O}}({n^2}m)$ 之间.

4 实验与仿真

本文实验部分所有测试代码均是基于Python实现, 由Python 3.9编译, 实验测试平台配置为Intel i7 2.59 GHz CPU和16 GB内存, 64-bit Windows操作系统的计算机, 本文实验所采用的测试数据均为随机生成的流网络, 在对应ENr下分别生成10张随机流网络进行测试, 测试结果取平均值. 实验变量定义如下.

1) FVm表示最大流的流量值.

2) ENr表示随机流网络中边数与结点数的比值.

3) Vn表示有效搜索总步数, 即增广路径长度总和; Sn表示搜索总步数, 即搜索总代价; Vr是有效搜索率, 其定义为: $Vr = Vn/Sn$ .

本文首先在数值上验证了算法的正确性, 在算法执行结束后, 将结合最大流值FVm、残流网络R、流网络G来计算流经每一条边的流量值, 计算其与本文算法所得最大流量值、源点s发出的流量值以及流入汇点t的流量值是否相等, 来验证最大流量FVm数值大小的正确性. 此外, 还将验证每个结点(除s、t以外)的存余流量(excess flow)均为0, 来确定本文算法所得最终残流网络中不存在s-t路径. 通过上述步骤, 可以证明本文算法在数值上的正确性与可行性.

本文在初始包含500个结点、5 000条边, 每次扩张5 000条边的随机流网络中, 对比了3种传统最大流算法: Ford-Fulkerson算法、Edmonds-Karp算法、Dinic算法以及本文所提的记忆化搜索算法的耗时和搜索效率. 算法耗时的测试结果如图9所示, 当流网络较为稀疏时, Ford-Fulkerson算法耗时上升明显, 是由于深度优先搜索在稀疏流网络中搜索路径的任意性导致算法所得增广路径过长, 进而导致Ford-Fulkerson算法耗时开销明显增大. 而在基于层次网络的最短增广算法中, Edmonds-Karp算法、Dinic算法以及本文算法在稀疏网络上耗时差距不大. 但随着流网络稠密程度上升, Edmonds-Karp算法、Dinic算法的耗时上升明显. 其原因是Edmonds-Karp算法所采用的宽度优先搜索策略每轮搜索大量重复, 导致其搜索代价随着网络稠密程度的增加而递增. Dinic算法通过循环利用层次网络, 减少了宽度优先搜索的调用次数, 因此其算法耗时相较于Edmonds-Karp算法有所下降. 本文算法通过记忆化策略更高效的利用层次网络中的连通路径, 进一步避免了在无效路径上的无效搜索, 因此在稠密网络中的算法耗时大幅下降.

搜索效率的对比主要针对基于层次网络的4种最大流算法, 分别是Edmonds-Karp算法、Dinic算法以及逆向Dinic算法和本文算法, 测试结果如图10和表3所示. 逆向Dinic算法是由文献[14]所提出的基于有效反向网络的最大流算法, 该算法通过不断地剪枝, 剔除 ${c_f}\left( {u, v} \right) = 0$ 的边, 再通过构建反向网络逆向搜索t-s路径, 从而减少搜索代价. 随着随机网络稠密程度增加, 大量无效搜索使得Edmonds-Karp算法和Dinic算法的有效搜索率Vr始终低于5%. 而本文算法的搜索代价变化趋势较为平稳, 在ENr小于100的稀疏流网络中Vr略高于其余两个传统算法. 在稠密的网络结构中, 记忆化搜索策略对层次网络中连通路径的利用率较高, 有效搜索率提升较为显著.

逆向Dinic算法的搜索代价及有效搜索率波动较大, 测试结果表明, 其有效搜索率在本文所定义的随机网络结构中难以体现较为平稳的增长趋势. 在测试过程中发现逆向Dinic算法往往在上连通性较好的网络中对有效搜索率Vr的优化明显, 但在上连通性不佳的网络中Vr接近于原始Dinic算法, 其原因是逆向Dinic算法在搜索过程中路径递归迭代次数不断增加, 若当前路径不连通时逐层路径回退会增加额外搜索代价, 且剪枝操作至多会增加 ${\rm{O}}(m)$ 的额外代价. 因此, 逆向Dinic算法在上连通性不佳的网络中有效搜索率较低, 而在上连通性较好的网络中, 逆向搜索策略几乎不会产生额外代价, 从而保证了较好的效率. 记忆化搜索策略始终保持正向搜索避免路径回退, 虽然存在路径遗漏问题会导致搜索循环若干轮, 但每轮额外搜索代价恒定, 故记忆化搜索策略相较于逆向Dinic算法对有效搜索率Vr的优化更为稳定, 且在随机连通流网络中执行效率更高.

5 结论与展望

本文提出了一个基于记忆化搜索策略的最大流算法, 该算法在基于层次网络的最大流算法上优化了搜索效率, 通过记忆化存储路径搜索状态来避免算法反复搜索网络中的“无效部分”, 进而避免了大量无效增广. 实验结果表明, 算法在稠密网络中的搜索总代价与算法执行效率明显优于传统Edmonds-Karp算法和Dinic算法, 且比同类算法更具稳定性. 与此同时, 本文算法仍旧保留着与传统增广路径算法一致的简易性与可行性. 现如今, 最大流算法被广泛地运用于实际工程技术当中, 本文算法具有较高的实用价值, 为最大流算法相关工程技术的应用与开发提供了一个便捷、可行且高效的选择.