基于预流推进的最小标号最大流算法

基于预流推进的最小标号最大流算法

摘要：针对原始最高标号预流推进算法中的回溯现象导致其在部分网络中执行效率低下的问题，提出了基于预流推进的最小标号算法。该算法仍以预流推进为基础，但在选取活跃节点时依据贪心原则寻找最小标号活跃节点作为调整点，同时还需构造回溯检验方法终止回溯现象以提升算法效率。在仿真实验中，该算法能够适应各类复杂网络，并在稀疏网络中具有最高标号预流推进算法5倍以上执行速度；在被应用于图像分割领域时，该算法也具有50%以上性能提升。提出的基于预流推进的最小标号最大流算法能够满足大规模网络流量分配、计算机视觉图像处理等需求。

关键词：预流推进；最高标号；最小标号；回溯；随机网络

中图分类号： TP301.6 文献标志码：A Abstract：

Aiming at the problem of the low execution efficiency in the part of the network caused by the backtracking phenomena of the original highest label preflow push algorithm， the lowest label algorithm based on preflow push was proposed.

Based on the preflow， the proposed algorithm chose the lowest label active node as the adjustment point in the selection of active nodes by following the greedy algorithm. The backtracking verification method was introduced to terminate the backtracking loop for enhancing the efficiency of algorithm. The proposed algorithm could meet the demands of various kinds of network graphs and was five more times faster than the classic highest label preflow push algorithm for the sparse networks in the simulation experiments. When applied into the image segmentation， the proposed method achieved more than 50 percent of speed compared with the classic algorithm. The proposed lowest label algorithm for minimum cut/maximum flow based on preflow push can satisfy the largescale network traffic distribution and the image processing of computer vision.

英文关键词Key words：

preflow push； highest label； lowest label； backtracking； random network 0引言

运筹学中的最大流问题能应用于计算机、工程学、图像处理[1-2]等众多领域。不是文献3第一作者姓，核实是否有误，文献只能直接引用，不能间接引用Fulkerson等[3]首次

运用了图的方法求解了最大流问题，之后，基于图的最大流经典算法相继出现。Ford等[4]发现的增广链法将最大流求解过程领入了多项式时代，随后出现的基于增广链的Dinic阻塞流及层次网络算法[5]，Edmonds等[6]提出的连续最短路增广算法使增广链算法的效率提高到极致，即时间的复杂度为O（mn2），同时也是真正意义上的多项式算法。然而这类方法速度较慢，而后 Karzanov[7]提出的预流推进算法理论， Cherkassky等[8]随之改进的最高标号预流推进算法有效提升了算法效率，是理论时间复杂度最低的网络最大流经典算法，其时间复杂度为O（n2m）。此外，为满足各类网络图的性能需求，研究者们近几年提出了多种新算法，如针对平面图[9-10]及稀疏网络图[11]的算法， Italiano等 [10]指出，目前平面网络最小割求解算法理论复杂度最低为O（n log n）。然而并非所有无向网络都能够满足平面图的特征，现实中绝大部分网络为立体网络，如通过能量函数最小值化进行图像分割时构造的网络。

文献[12]中的仿真实验表明，最大流算法在实际应用中很可能与理论复杂度有相反的表现，如在一些实验中列队预流推进执行速度高于最高标号预流推进，又或者在某些网络中Dinic算法执行速度高于预流推进算法执行速度，这是因为在实际应用中，算法计算量远达不到理论复杂度，即便是增广链算法在实际运行过程中的运算次数也低于最高标号

预流推进的理论运算次数。本文分析了预流推进算法执行过程中存在的回溯现象，并通过直观图与仿真实验验证了这种现象导致了严重的时间损耗，故提出一种基于预流推进的最小标号贪心算法，有效解决这一问题。 1最大流模型、距离标号及两种普通网络

给定一张网络图G（V，E），其中：V表示图中的所有节点，E表示图中的所有关联边。若E是有向的，则称网络图G为有向图。若给图中的关联边E赋予权重w，则称该图为加权图并用G（V，E，w）表示，在容量网络中，加权图G的权重w为容量C。完整的容量网络中还包含关联边上的当前流量F，故一张含流量的容量网络图可以用四个参数表示，记为G（V，E，C，F）。 定义1[13]若网络G（V，E，C，F）中给定的起点s和收点t及任意节点满足流量守恒方程：

∑jf（i， j）-∑jf（j，i）=fst，i=s0，i≠s，t-fst，i=t 其中0≤f（i， j）≤c（i， j），（i， j）∈E，则称fst为网络G（V，E，C，F）中的一个可行流。

定义2网络G（V，E，C，F）中的最大流fmax是指满足守恒方程的最大可行流fst。

定义3[14]给定一个函数d，若能将网络G中的节点集V映射到某个非负整数集合{d（t）|t∈V}中，则称d为网络G的距离函数，{d（t）|t∈V}为构造的距离标号。若距离标号