ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2014, Vol. 51 ›› Issue (8): 1845-1853.doi: 10.7544/issn1000-1239.2014.20130184

• 人工智能 • 上一篇    下一篇

分层法求解网络最大流的研究

赵 姝,苏建忠,刘倩倩,张燕平   

  1. (安徽大学计算机科学与技术学院 合肥 230601) (计算智能与信号处理教育部重点实验室(安徽大学) 合肥 230601) (zhaoshuzs2002@hotmail.com)
  • 出版日期: 2014-08-15
  • 基金资助: 
    基金项目:国家自然科学基金项目(61073117,61175046,61203290);安徽省自然科学基金项目(11040606M);安徽大学2011级研究生学术创新研究项目(01001770-10117700163)

To Solve Maximum Flow Problem of Network with a Layering Method

Zhao Shu, Su Jianzhong, Liu Qianqian, Zhang Yanping   

  1. (School of Computer Science and Technology, Anhui University, Hefei 230601) (Key Laboratory of Intelligent Computing and Signal Processing (Anhui University), Ministry of Education, Hefei 230601)
  • Online: 2014-08-15

摘要: 网络最大流问题是经典的组合优化问题,随着网络规模的增加,提高算法效率成为解决问题的关键.为了降低求解大规模网络最大流的计算量,针对单源单汇网络提出基于网络分层的最大流问题求解新方法.分层法首先构造原有向网络对应的层次网络,接着在构造出的层次网络中计算各相邻结点层之间的最大流,以此为基础最终获得整个网络最大流的快速估算.分层法有效降低了计算的复杂性,为在大规模网络中快速获取最大流的求解提供了方便,并给出了一个解决最大流问题的新思路.不同网络上测试的实验结果显示,最大流的近似解误差可控制在1%左右,而平均运行时间仅为经典算法(Ford-Fulkerson算法)运行时间的11%,最好情况下的运行时间仅为经典算法运行时间的2%,是two-phase capacity scaling改进算法运行时间的25%,表明分层方法的有效性.

关键词: 分层法, 最大流, 流网络, 最小割, 网络分层

Abstract: 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 sub-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.

Key words: layering method, maximum flow, flow network, min-cut, the layer network

中图分类号: