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

发布时间：2017-12-23 16:47

  本文关键词：分层法求解网络最大流的研究　出处：《计算机研究与发展》2014年08期 　论文类型：期刊论文

  更多相关文章： 分层法 最大流 流网络 最小割 网络分层

【摘要】：网络最大流问题是经典的组合优化问题,随着网络规模的增加,提高算法效率成为解决问题的关键.为了降低求解大规模网络最大流的计算量,针对单源单汇网络提出基于网络分层的最大流问题求解新方法.分层法首先构造原有向网络对应的层次网络,接着在构造出的层次网络中计算各相邻结点层之间的最大流,以此为基础最终获得整个网络最大流的快速估算.分层法有效降低了计算的复杂性,为在大规模网络中快速获取最大流的求解提供了方便,并给出了一个解决最大流问题的新思路.不同网络上测试的实验结果显示,最大流的近似解误差可控制在1%左右,而平均运行时间仅为经典算法(FordFulkerson算法)运行时间的11%,最好情况下的运行时间仅为经典算法运行时间的2%,是two-phase capacity scaling改进算法运行时间的25%,表明分层方法的有效性.
【作者单位】： 安徽大学计算机科学与技术学院;计算智能与信号处理教育部重点实验室(安徽大学);
【基金】：国家自然科学基金项目(61073117,61175046,61203290) 安徽省自然科学基金项目(11040606M) 安徽大学2011级研究生学术创新研究项目(01001770-10117700163)
【分类号】：TP393.01
【正文快照】： 最大流问题[1]是网络流理论的重要组成部分.它是组合优化中的经典问题,同时也可以看作特殊的线性规划问题[2-3].除了解决实际网络中的最大流问题外,最大流算法在许多领域都有广泛的应用[4-6].解决最大流问题的经典算法是Ford和Fulkerson提出的增广路算法[7],随后许多学者提出

【参考文献】

相关期刊论文 前4条

1 张新猛;蒋盛益;;基于核心图增量聚类的复杂网络划分算法[J];自动化学报;2013年07期

2 黄文良;刘勇;钟志强;沈仲明;;基于复杂网络的垃圾短信过滤算法[J];自动化学报;2009年07期

3 张宪超;江贺;刘馨月;于红;;无向平面单位容量网络中的最大流[J];计算机研究与发展;2008年S1期

4 张宪超 ,陈国良 ,万颖瑜;网络最大流问题研究进展[J];计算机研究与发展;2003年09期

【共引文献】

相关期刊论文 前10条

1 赵礼峰;纪亚劲;;基于最短增广链的最大流改进算法[J];计算机技术与发展;2017年08期

2 胡杨;冯旭鹏;戴丹;刘利军;黄青松;;最小费用最大流跨领域情感分类框架[J];小型微型计算机系统;2017年01期

3 周巧扣;倪红军;;一种基于语义的垃圾短信过滤算法[J];实验室研究与探索;2016年11期

4 林洋;李燕;董玮;刘延昕;任丽晔;;复杂网络社区的抽样概率分布估计检测算法[J];西南师范大学学报(自然科学版);2016年10期

5 赵礼峰;纪亚宝;;最大流问题的改进最短增广链算法[J];计算机技术与发展;2016年08期

6 梁晋;梁吉业;赵兴旺;;一种面向大规模社会网络的社区发现算法[J];南京大学学报(自然科学);2016年01期

7 黄孝鹏;罗军;鉴福升;;基于多任务的海上跨平台自主传感网最大流改进模型及求解[J];兵工学报;2015年S2期

8 邓立军;刘剑;;无回路阻力平衡约束的固定风量平衡算法研究[J];安全与环境学报;2015年04期

9 孙大鹏;;云计算技术在垃圾短信过滤中的应用与实现[J];信息网络安全;2015年07期

10 郭鑫龙;;几类求解最大流问题算法在运输问题中的应用[J];电子制作;2015年18期

【二级参考文献】

相关期刊论文 前10条

1 刘旭;易东云;;基于局部相似性的复杂网络社区发现方法[J];自动化学报;2011年12期

2 金弟;刘杰;杨博;何东晓;刘大有;;局部搜索与遗传算法结合的大规模复杂网络社区探测[J];自动化学报;2011年07期

3 李辉;赵海;徐久强;李博;李鹏;王家亮;;基于k-核的大规模软件宏观拓扑结构层次性研究[J];电子学报;2010年11期

4 何东晓;周栩;王佐;周春光;王U，

本文编号：1324690