| 分层法求解网络最大流的研究 |
| |
| 引用本文： | 赵 姝, 苏建忠, 刘倩倩, 张燕平. 分层法求解网络最大流的研究[J]. 计算机研究与发展, 2014, 51(8): 1845-1853. DOI: 10.7544/issn1000-1239.2014.20130184 |
| |
| 作者姓名： | 赵姝 苏建忠 刘倩倩 张燕平 |
| |
| 作者单位： | (安徽大学计算机科学与技术学院 合肥 230601) (计算智能与信号处理教育部重点实验室(安徽大学) 合肥 230601) (zhaoshuzs2002@hotmail.com) |
| |
| 基金项目： | 国家自然科学基金项目,安徽省自然科学基金项目,安徽大学2011级研究生学术创新研究项目 |
| |
| 摘 要： | 网络最大流问题是经典的组合优化问题,随着网络规模的增加,提高算法效率成为解决问题的关键.为了降低求解大规模网络最大流的计算量,针对单源单汇网络提出基于网络分层的最大流问题求解新方法.分层法首先构造原有向网络对应的层次网络,接着在构造出的层次网络中计算各相邻结点层之间的最大流,以此为基础最终获得整个网络最大流的快速估算.分层法有效降低了计算的复杂性,为在大规模网络中快速获取最大流的求解提供了方便,并给出了一个解决最大流问题的新思路.不同网络上测试的实验结果显示,最大流的近似解误差可控制在1%左右,而平均运行时间仅为经典算法(Ford-Fulkerson算法)运行时间的11%,最好情况下的运行时间仅为经典算法运行时间的2%,是two-phase capacity scaling改进算法运行时间的25%,表明分层方法的有效性.
|
| 关 键 词： | 分层法 最大流 流网络 最小割 网络分层 |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《计算机研究与发展》浏览原始摘要信息 |
|
点击此处可从《计算机研究与发展》下载免费的PDF全文 |
|
