基于宽度优先的网络最大流求解算法
|
摘要
网络最大流问题是经典的组合优化问题,为了降低求解大规模网络最大流的计算量,若用Ford-Fulkerson算法寻找增广链,则效率不高且步骤繁杂。为了改善以上不足,在原有算法的基础上作了一些改进,应用图的宽度优先搜索原理,针对单源单汇网络提出了一种新的求解最大流问题的算法。该算法的思想是:用宽度优先搜索原理,寻找一条包含剩余容量最大的弧的最短增广链后,删除饱和弧,且沿合适的路径修复包含剩余容量最大的弧的最短增广链。该算法避免了Ford-Fulkerson算法的标号过程,减少了反复重新寻找增广链的次数,为在大规模网络中快速获取最大流的求解提供了方便并提高了求解网络最大流的执行效率。通过实例分析与BA无标度网络建模仿真,验证了该算法的实用性,且新算法的运行效率高于Ford-Fulkerson算法。
The network maximum flow is a classic combinatorial optimization problem. In order to reduce the computational complexity of solving the maximum flow of a large-scale network,if the Ford-Fulkerson algorithm is used to find the augmented chain,the efficiency is not high and the steps are complicated. In order to improve the above deficiencies,we make some improvements on the basis of the original algorithm. Applying the breadth-first search principle,we propose a new algorithm for solving the maximum flow problem for single-source and single-sink networks. The idea of the algorithm is to use the breadth first search principle to find a shortest augmented chain containing the arc with the largest remaining capacity,then remove the saturated arc,repair the shortest augmented chain containing the arc with the largest remaining capacity along the appropriate path. The algorithm avoids the labeling process of the Ford-Fulkerson algorithm,reduces the number of repeated re-finding of the augmented chain,provides convenience for solving the maximum stream in a large-scale network,and improves the execution efficiency of solving the maximum flow of the network. The practicality of the algorithm is verified by an example analysis and experiments in the BA scale-free network,and it is more efficient than the Ford-Fulkerson algorithm.
The network maximum flow is a classic combinatorial optimization problem. In order to reduce the computational complexity of solving the maximum flow of a large-scale network,if the Ford-Fulkerson algorithm is used to find the augmented chain,the efficiency is not high and the steps are complicated. In order to improve the above deficiencies,we make some improvements on the basis of the original algorithm. Applying the breadth-first search principle,we propose a new algorithm for solving the maximum flow problem for single-source and single-sink networks. The idea of the algorithm is to use the breadth first search principle to find a shortest augmented chain containing the arc with the largest remaining capacity,then remove the saturated arc,repair the shortest augmented chain containing the arc with the largest remaining capacity along the appropriate path. The algorithm avoids the labeling process of the Ford-Fulkerson algorithm,reduces the number of repeated re-finding of the augmented chain,provides convenience for solving the maximum stream in a large-scale network,and improves the execution efficiency of solving the maximum flow of the network. The practicality of the algorithm is verified by an example analysis and experiments in the BA scale-free network,and it is more efficient than the Ford-Fulkerson algorithm.
引文
[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] 钱颂迪.运筹学[M].北京:清华大学出版社,2012:312-320.
[4] FULKERSON D R,DANTZIG G B.Computation of maximal flows in network[J].Naval Research Logistics Quarterly,1995,2(4):277-283.
[5] 谢政.网络算法与复杂性理论[M].长沙:国防科技大学出版社,2003.
[6] EDMONDS J,KARP R M.Theoretical improvements in algorithmic efficiency for networks flow problems[J].Journal of ACM,1972,19:248-264.
[7] 赵礼峰,纪亚劲.基于最短增广链的最大流改进算法[J].计算机技术与发展,2017,27(8):88-91.
[8] GOLDBERG A V,RAO S.Beyond the flow decomposition barrier[J].Journal of ACM,1998,45:783-797.
[9] 张柏礼,王媛媛,洪亮,等.动态网络中最大流快速增量求解[J].东南大学学报:自然科学版,2017,47(3):450-455.
[10] 赵礼峰,纪亚宝.最大流最小截问题的遗传算法研究[J].计算机技术与发展,2017,27(4):69-72.
[11] 张宪超,江贺.一个新的最大流问题增载轨算法[J].小型微型计算机系统,2006,27(9):1726-1730.
[12] GOLDBERG A V,HED S,KAPLAN H,et al.Faster and more dynamic maximum flow by incremental breadth-first search[C]//ESA 2015.Berlin:Springer,2015:619-630.
[13] 赵礼峰,刘艳清.定流值比例的最小双费用流算法研究[J].计算机技术与发展,2017,27(4):94-97.
[14] 谢凡荣.求解网络最大流问题的一个算法[J].运筹与管理,2004,13(4):37-40.
[15] 纪伟,戴理昱,王永红.网络最大流的“冲塞式”求法[J].运筹与管理,2003,12(3):38-42.
[16] 陈静,单锐.容差修正网络最大流2F算法[J].长春工业大学学报:自然科学版,2008,29(6):713-716.
[17] 赵礼峰,严子恒.基于增广链修复的最大流求解算法[J].计算机应用,2015,35(5):1246-1249.
[18] 赵礼峰,纪亚宝.最大流问题的改进最短增广链算法[J].计算机技术与发展,2016,26(8):52-54.
[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] 钱颂迪.运筹学[M].北京:清华大学出版社,2012:312-320.
[4] FULKERSON D R,DANTZIG G B.Computation of maximal flows in network[J].Naval Research Logistics Quarterly,1995,2(4):277-283.
[5] 谢政.网络算法与复杂性理论[M].长沙:国防科技大学出版社,2003.
[6] EDMONDS J,KARP R M.Theoretical improvements in algorithmic efficiency for networks flow problems[J].Journal of ACM,1972,19:248-264.
[7] 赵礼峰,纪亚劲.基于最短增广链的最大流改进算法[J].计算机技术与发展,2017,27(8):88-91.
[8] GOLDBERG A V,RAO S.Beyond the flow decomposition barrier[J].Journal of ACM,1998,45:783-797.
[9] 张柏礼,王媛媛,洪亮,等.动态网络中最大流快速增量求解[J].东南大学学报:自然科学版,2017,47(3):450-455.
[10] 赵礼峰,纪亚宝.最大流最小截问题的遗传算法研究[J].计算机技术与发展,2017,27(4):69-72.
[11] 张宪超,江贺.一个新的最大流问题增载轨算法[J].小型微型计算机系统,2006,27(9):1726-1730.
[12] GOLDBERG A V,HED S,KAPLAN H,et al.Faster and more dynamic maximum flow by incremental breadth-first search[C]//ESA 2015.Berlin:Springer,2015:619-630.
[13] 赵礼峰,刘艳清.定流值比例的最小双费用流算法研究[J].计算机技术与发展,2017,27(4):94-97.
[14] 谢凡荣.求解网络最大流问题的一个算法[J].运筹与管理,2004,13(4):37-40.
[15] 纪伟,戴理昱,王永红.网络最大流的“冲塞式”求法[J].运筹与管理,2003,12(3):38-42.
[16] 陈静,单锐.容差修正网络最大流2F算法[J].长春工业大学学报:自然科学版,2008,29(6):713-716.
[17] 赵礼峰,严子恒.基于增广链修复的最大流求解算法[J].计算机应用,2015,35(5):1246-1249.
[18] 赵礼峰,纪亚宝.最大流问题的改进最短增广链算法[J].计算机技术与发展,2016,26(8):52-54.