最大动态流关键弧的改进算法

doi:10.11772/j.issn.1001-9081.2014.04.0969

计算机应用 ›› 2014, Vol. 34 ›› Issue (4): 969-972.DOI: 10.11772/j.issn.1001-9081.2014.04.0969

最大动态流关键弧的改进算法

刘杨杨,谢政,陈挚

国防科学技术大学理学院,长沙 410073

收稿日期:2013-10-21 修回日期:2013-12-26 出版日期:2014-04-01 发布日期:2014-04-29
通讯作者: 刘杨杨
作者简介:刘杨杨(1990-),男,湖北襄阳人,硕士研究生,主要研究方向:网络最优化;
谢政(1960-),男,湖南衡阳人,教授,主要研究方向:网络最优化;
陈挚(1965-),男,湖南湘乡人,副教授,主要研究方向:网络最优化。

Improved algorithm for vital arc of maximum dynamic flow

LIU Yangyang,XIE Zheng,CHEN Zhi

College of Science, National University of Defense Technology, Changsha Hunan 410073, China

Received:2013-10-21 Revised:2013-12-26 Online:2014-04-01 Published:2014-04-29
Contact: LIU Yangyang

摘要/Abstract

摘要：

针对时间容量网络的最大动态流的关键弧问题，首先分析了经典的Ford-Fulkerson最大动态流算法，在此基础上简化了最大动态流算法，并由此提出一个基于最小费用增广路来寻找最大动态流关键弧的改进算法。算法将计算新网络最大动态流时共有的最小费用路保留，去掉了自然算法中重复的计算。的效率更高。

Abstract:

For the vital arc problem of maximum dynamic flow in time-capacitated network, the classic Ford-Fulkerson maximum dynamic flow algorithm was analyzed and simplified. Thus an improved algorithm based on minimum cost augmenting path to find the vital arc of the maximum dynamic flow was proposed. The shared minimum augmenting paths were retained when computing maximum dynamic flow in new network and the unnecessary computation was removed in the algorithm. Finally, the improved algorithm was compared with the original algorithm and natural algorithm. The numerical analysis shows that the improved algorithm is more efficient than the natural algorithm

中图分类号:

TP301.6

刘杨杨谢政陈挚. 最大动态流关键弧的改进算法[J]. 计算机应用, 2014, 34(4): 969-972.

LIU Yangyang XIE Zheng CHEN Zhi. Improved algorithm for vital arc of maximum dynamic flow[J]. Journal of Computer Applications, 2014, 34(4): 969-972.

参考文献

［1］AHUJIA R K, MAGNANTI T L, ORLIN J B. Network flows: theory algorithms and application ［M］. Upper Saddle River: Prentice Hall, 1993.
［2］FORD L R, FULKERSON D R. Constructing maximal dynamic flows from static flows ［J］. Operations Research, 1958, 6(3): 419-433.
［3］PICARD J-C, QUEYARANNE M. On the structure of all minimum cut in a network and applications ［C］// Combinatorial Optimization II: Mathematical Programming Studies. Berlin: Springer-Verlag, 1980: 8-16.
［4］RAD M A, KAKHKI H T. Maximum dynamic network flow interdiction problem: new formulation and solution procedures ［J］. Computers & Industrial Engineering, 2013, 65(4): 531-536.
［5］LUNDAY B J, SHERALI H D. A dynamic network interdiction problem ［J］. Informatica, 2010, 21(4): 553-574.
［6］ROYSET J O, WOOD R K. Solving the bi-objective maximum flow network-interdiction problem ［J］. INFORMS Journal on Computing, 2007, 19(2): 175-184.
［7］ANEJA Y P, CHANDRASEKARAN R, NAIR K P K. Maximizing residual flow under an arc destruction ［J］. Networks, 2001, 38 (4): 194-198.
［8］DU D, CHANDRASEKARAN R. The maximum residual flow problem: NP-hardness with two arc destruction ［J］. Networks, 2007, 50(3): 181-182.
［9］TAHMASBI R, NASRABADI E, HASHEMI S M. The value of information in stochastic maximum flow problems ［J］. Computers & Operations Research, 2013, 40(7): 1744-1751.
［10］SKUTELLA M. An introduction to network flows over time ［C］// Research Trends in Combinatorial Optimization. Berlin: Springer-Verlag, 2009: 451-482.
［11］XIE Z. Theory of network algorithm and complexity ［M］. 2nd ed. Changsha: National University of Defense Technology Press, 2003. (谢政.网络算法与复杂性理论［M］.2版.长沙:国防科技大学出版社,2003.
［12］ZHANG L. The concept of maximum flow and its properties in dynamic networks ［J］. Pattern Recognition and Artificial Intelligence, 2013, 26(7):609-614. (张铃.动态网络上最大流概念及其性质的研究［J］.模式识别与人工智能,2013,26(7):609-614.)
［13］STRANG G. Maximum flows and minimum cuts in the plane ［J］. Journal of Global Optimization, 2010, 47(3): 527-535.

[1]	平凡, 汤小春, 潘彦宇, 李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3295-3301.
[2]	雷鹰, 郑万波, 魏嵬, 夏云霓, 李晓波, 刘诚武, 谢洪. 基于概率性能感知演化博弈策略的“云+边”混合环境中任务卸载方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3302-3308.
[3]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[4]	邹复民, 罗思杰, 陈志辉, 廖律超. 基于轨迹数据的出租车交接班时空分布识别方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3376-3384.
[5]	肖智豪胡志华朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 计算机应用, 0, (): 0-0.
[6]	沙林秀，聂凡，高倩，孟号. 基于布朗运动与梯度信息的交替优化算法[J]. 计算机应用, 0, (): 0-0.
[7]	董永峰孙跃华高立超韩鹏季海鹏. 基于改进一维卷积和双向长短期记忆神经网络的故障诊断方法[J]. 计算机应用, 0, (): 0-0.
[8]	李大海刘庆腾艾志刚王振东. 基于动态D向分割和混沌扰动的阴阳对算法[J]. 计算机应用, 0, (): 0-0.
[9]	朱诚潘旭华张勇. 基于趋化校正的哈里斯鹰优化算法[J]. 计算机应用, 0, (): 0-0.
[10]	杨杰张名扬芮晓彬王志晓. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 计算机应用, 0, (): 0-0.
[11]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[12]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[13]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[14]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[15]	张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.

最大动态流关键弧的改进算法

Improved algorithm for vital arc of maximum dynamic flow

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics