摘要
网络最大流问题是经典的组合优化问题,随着网络规模的增加,提高算法效率成为解决问题的关键.为了降低求解大规模网络最大流的计算量,针对单源单汇网络提出基于网络分层的最大流问题求解新方法.分层法首先构造原有向网络对应的层次网络,接着在构造出的层次网络中计算各相邻结点层之间的最大流,以此为基础最终获得整个网络最大流的快速估算.分层法有效降低了计算的复杂性,为在大规模网络中快速获取最大流的求解提供了方便,并给出了一个解决最大流问题的新思路.不同网络上测试的实验结果显示,最大流的近似解误差可控制在1%左右,而平均运行时间仅为经典算法(FordFulkerson算法)运行时间的11%,最好情况下的运行时间仅为经典算法运行时间的2%,是two-phase capacity scaling改进算法运行时间的25%,表明分层方法的有效性.
Maximum flow problem is a classical combinational optimization problem. With the growing of the network scale, it is the key to improve the efficiency of the algorithm for the maximum flow problem. For a given single-source single-sink network, a novel layer method for getting its maximum flow is proposed in this paper. Firstly, we transform the original directed network into a layer network. Then we compute the maximum flow for each sub-network which contains two adjacent levels of nodes in the layer network. Finally, the minimum value of each ;ub-network＇s maximum flow is regarded as the estimated maximum flow of the original network. The experimental results on different networks show the efficiency of the proposed method. The maximum flow error is only about 1% averagely. Meanwhile, the running time of our method is only 11% of the classical algorithm （the Ford-Fulkerson algorithm） averagely. And in the best condition, the running time of our method is 2% of the classical algorithm and 25% of the improved two-phase capacity scaling algorithm.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2014年第8期1845-1853,共9页
Journal of Computer Research and Development
基金
国家自然科学基金项目(61073117
61175046
61203290)
安徽省自然科学基金项目(11040606M)
安徽大学2011级研究生学术创新研究项目(01001770-10117700163)
关键词
分层法
最大流
流网络
最小割
网络分层
layering method
maximum flow
flow network
min-cut
the layer network
