基于宽度优先的网络最大流求解算法

发布时间：2021-05-01 03:10

　　网络最大流问题是经典的组合优化问题,为了降低求解大规模网络最大流的计算量,若用Ford-Fulkerson算法寻找增广链,则效率不高且步骤繁杂。为了改善以上不足,在原有算法的基础上作了一些改进,应用图的宽度优先搜索原理,针对单源单汇网络提出了一种新的求解最大流问题的算法。该算法的思想是:用宽度优先搜索原理,寻找一条包含剩余容量最大的弧的最短增广链后,删除饱和弧,且沿合适的路径修复包含剩余容量最大的弧的最短增广链。该算法避免了Ford-Fulkerson算法的标号过程,减少了反复重新寻找增广链的次数,为在大规模网络中快速获取最大流的求解提供了方便并提高了求解网络最大流的执行效率。通过实例分析与BA无标度网络建模仿真,验证了该算法的实用性,且新算法的运行效率高于Ford-Fulkerson算法。 

【文章来源】：计算机技术与发展. 2019,29(06)

【文章页数】：4 页

【文章目录】：
0 引 言
1 基本概念
    1.1 最大流的模型
    1.2 剩余网络 (增量网络)
2 一种改进的最大流算法
    2.1 算法思想
    2.2 算法步骤
    2.3 算法可行性分析
    2.4 算法复杂度分析
3 数值实例与分析
4 算法的仿真与比较
5 结束语


【参考文献】：
期刊论文
[1]基于最短增广链的最大流改进算法[J]. 赵礼峰,纪亚劲.  计算机技术与发展. 2017(08)
[2]动态网络中最大流快速增量求解[J]. 张柏礼,王媛瑗,洪亮,田伟,吕建华.  东南大学学报(自然科学版). 2017(03)
[3]定流值比例的最小双费用流算法研究[J]. 赵礼峰,刘艳清.  计算机技术与发展. 2017(04)
[4]最大流最小截问题的遗传算法研究[J]. 赵礼峰,纪亚宝.  计算机技术与发展. 2017(04)
[5]最大流问题的改进最短增广链算法[J]. 赵礼峰,纪亚宝.  计算机技术与发展. 2016(08)
[6]基于增广链修复的最大流求解算法[J]. 赵礼峰,严子恒.  计算机应用. 2015(05)
[7]容差修正网络最大流2F算法[J]. 陈静,单锐.  长春工业大学学报(自然科学版). 2008(06)
[8]一个新的最大流问题增载轨算法[J]. 张宪超,江贺.  小型微型计算机系统. 2006(09)
[9]求解网络最大流问题的一个算法[J]. 谢凡荣.  运筹与管理. 2004(04)
[10]网络最大流的"冲塞式"求法[J]. 纪伟,戴理昱,王永红.  运筹与管理. 2003(03)



本文编号：3170029