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

doi:10.11772/j.issn.1001-9081.2015.12.3398

计算机应用 ›› 2015, Vol. 35 ›› Issue (12): 3398-3402.DOI: 10.11772/j.issn.1001-9081.2015.12.3398

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

赵礼峰, 严子恒

南京邮电大学理学院, 南京 210000

收稿日期:2015-06-08 修回日期:2015-07-13 出版日期:2015-12-10 发布日期:2015-12-10
通讯作者: 严子恒(1991-),男,江苏南京人,硕士研究生,主要研究方向:网络最大流、最小费用流
作者简介:赵礼峰(1959-),男,安徽淮北人,教授,主要研究方向:图论及其应用、矩阵论。

Lowest label algorithm for minimum cut/maximum flow based on preflow push

ZHAO Lifeng, YAN Ziheng

School of Science, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210000, China

Received:2015-06-08 Revised:2015-07-13 Online:2015-12-10 Published:2015-12-10

摘要/Abstract

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

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

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 large-scale network traffic distribution and the image processing of computer vision.

Key words: preflow push, highest label, lowest label, backtracking, random network

中图分类号:

TP301.6

赵礼峰, 严子恒. 基于预流推进的最小标号最大流算法[J]. 计算机应用, 2015, 35(12): 3398-3402.

ZHAO Lifeng, YAN Ziheng. Lowest label algorithm for minimum cut/maximum flow based on preflow push[J]. Journal of Computer Applications, 2015, 35(12): 3398-3402.

参考文献

[1] ARBELAEZ P, MAIRE M, FOWLKES C, et al. Contour detection and hierarchical image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(5):898-916.
[2] LI C, HUANG R, DING Z, et al. A level set method for image segmentation in the presence of intensity in homogeneities with application to MRI[J]. IEEE Transactions on Image Processing, 2011, 20(7):2007-2016.
[3] FULKERSON D R, DANTZIG G B. Computation of maximal flows in networks[J]. Naval Research Logistics Quarterly, 1955, 2(4):277-283.
[4] FORD L R, FULKERSON D R. A suggested computation for maximal multi-commodity network flows[J]. Management Science, 1958, 5(1):97-101.
[5] GOLDBERG A V. Recent developments in maximum flow algorithms[C]//Proceedings of the Algorithm Theory-SWAT'98, LNCS 1432. Berlin:Springer, 1998:1-10.
[6] EDMONDS J, KARP R M. Theoretical improvements in algorithmic efficiency for network flow problems[J]. Journal of the Association for Computing Machinery, 1972, 19(2):248-264.
[7] KARZANOV A V. Determining the maximal flow in a network by the method of preflows[J]. Soviet Mathematics Doklady, 1974, 15:434-437.
[8] CHERKASSKY B V, GOLDBERG A V. On implementing the push-relabel method for the maximum flow problem[J]. Algorithmica, 1997, 19(4):390-410.
[9] EISENSTAT D, KLEIN P N. Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs[C]//Proceedings of the 45th Annual ACM Symposium on Theory of Computing. New York:ACM, 2013:735-744.
[10] ITALIANO G F, NUSSBAUM Y, SANKOWSKI P, et al. Improved algorithms for min cut and max flow in undirected planar graphs[C]//Proceedings of the 43rd Annual ACM Symposium on Theory of Computing. New York:ACM, 2011:313-322.
[11] ORLIN J B. Max flows in O (nm) time, or better[C]//Proceedings of the 45th Annual ACM Symposium on Theory of Computing. New York:ACM, 2013:765-774.
[12] BOYKOV Y, KOLMOGOROV V. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(9):1124-1137.
[13] LIU H, CHEN Y. Communication network graph theory and application[M]. Beijing:Posts and Telecom Press, 2010:104-107. (刘焕淋,陈勇.通信网图论及应用[M].北京:人民邮电出版社,2010:104-107.)
[14] XIE Z. Network algorithm and complexity theory[M]. Changsha:National University of Defence Technology Press, 2003:124-128. (谢政.网络算法与复杂性理论[M].长沙:国防科技大学出版社,2003:124-128.)
[15] ERDOS P, RENYI A. On the evolution of random graphs[J]. Publication of the Mathematical Institute of the Hungarian Academy Ofences, 1960, 5:17-61.
[16] BRESSON X, TAI X-C, CHAN T F, et al. Multi-class transductive learning based on l1 relaxations of cheeger cut and Mumford-Shah-Potts model[J]. Journal of Mathematical Imaging and Vision, 2014, 49(1):191-201.
[17] BEAMER S, ASANOVIC K, PATTERSON D. Direction-optimizing breadth-first search[J]. Scientific Programming, 2013, 21(3/4):137-148.
[18] ZHAO L, YAN Z. New algorithm for problem of minimum cut/maximum flow based on augmenting path restoration[J]. Journal of Computer Applications, 2015, 35(5):1246-1249. (赵礼峰,严子恒.基于增广链修复的最大流求解算法[J].计算机应用,2015,35(5):1246-1249.)

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

Lowest label algorithm for minimum cut/maximum flow based on preflow push

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张伟伟, 陶聪, 范岩, 于坤杰, 文笑雨, 张卫正. 改进回溯搜索算法解决光伏模型参数识别问题[J]. 计算机应用, 2021, 41(4): 1199-1206.
[2]	丁静文, 陈树越, 陆贵荣. 基于Q学习算法的X光主动视觉安检方法[J]. 计算机应用, 2018, 38(12): 3414-3418.
[3]	张雁峰, 范西岸, 尹志益, 蒋铁钢. 基于回溯的共轭梯度迭代硬阈值重构算法[J]. 计算机应用, 2018, 38(12): 3580-3583.
[4]	李丽娜, 李文浩, 尤洪祥, 王越. 回溯搜索优化改进矩阵填充的高效位置指纹库构建[J]. 计算机应用, 2017, 37(7): 1893-1899.
[5]	李燕, 王耀力. 回溯正则化分段正交匹配追踪算法[J]. 计算机应用, 2016, 36(12): 3398-3401.
[6]	庄燕滨桂源肖贤建. 基于运动估计与回溯自适应正交匹配追踪的视频压缩传感[J]. 计算机应用, 2013, 33(09): 2577-2579.
[7]	鲁萍王玉英. 多约束分级寻优结合预测计算的智能组卷策略[J]. 计算机应用, 2013, 33(02): 342-345.
[8]	张英杰毛赐平. 面向多模态函数优化的回溯克隆选择算法[J]. 计算机应用, 2012, 32(07): 1947-1950.
[9]	李伟葛洪伟纪鹏. 不均匀网络中的局域搜索免疫[J]. 计算机应用, 2011, 31(01): 135-138.
[10]	纪鹏葛洪伟. 删除边的免疫策略[J]. 计算机应用, 2010, 30(07): 1775-1777.
[11]	杨春德任静静. 时延受限费用最小多播树算法[J]. 计算机应用, 2009, 29(1): 25-27.
[12]	李瑞宁周竹荣. 基于完备回溯树的语义Web服务自动组合[J]. 计算机应用, 2008, 28(6): 1427-1430.
[13]	顾晓清，刘渊. 基于自适应包标记的IP回溯[J]. 计算机应用, 2005, 25(09): 2092-2093.
[14]	唐常杰，彭京，张欢，钟义啸. 基于基因表达式编程的知识发现的三项新技术——转基因,重叠基因表达和回溯进化[J]. 计算机应用, 2005, 25(09): 1978-1981.
[15]	唐皓，卢显良. 基于改进双链树的多模式匹配算法[J]. 计算机应用, 2005, 25(02): 365-366.