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

《最大动态流关键弧的改进算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、最大动态流关键弧的改进算法摘要：针对时间容量网络的最大动态流的关键弧问题，首先分析了经典的FordFulkerson最大动态流算法，在此基础上简化了最大动态流算法，并由此提出一个基于最小费用增广路来寻找最大动态流关键弧的改进算法。算法将计算新网络最大动态流时共有的最小费用路保留，去掉了自然算法中重复的计算。与自然算法进行对比分析，结果表明改进算法比自然算法的效率更高。关键词：最大动态流；时间重复流；关键弧；最小费用增广路；最小动态截0引言最大流与最大动态流的关键弧问题是网络流[1]研究的重要内容，研究关键弧可以对关键弧进行额外的保护，或者评估关键弧被破坏

2、带来的损失，在通信网络、交通运输网络中也有很重要的应用价值。例如在交通运输网络中求解拦截问题可以知道重点保护哪些通道就能保证网络被破坏后最大运输量的损失最小，战时要重点保护对物资运输网络最大运输量影响最大的路线以保证战略物资的供给。5最大流与最大动态流的拦截问题一直是网络流研究的热点问题，与最大流的拦截问题紧密相关的一个问题就是最大流与最大动态流的关键弧集问题。最早，Ford和Fulkerson[2]提出去掉网络的最小截可以使最大流的流值减小为零，即最小截就是最大流的关键弧集，并第一次给出了经典的FordFulkerson最大动态流算法；Picard等[

3、3]提出了一个求解所有最小截的算法；Rad等[4]提出了一个新的最大动态流的拦截模型，给出了一个通过循环构造新网络并求解新网络的最小动态截来得到预算固定的最关键弧集的算法，但算法只能求出一条关键弧并且算法在一些情况下有可能失效；Lunday等[5]对于提出的动态流的拦截模型没有给出算法而是通过程序来求解的；Royset等[6]给出一个求解双目标的最大流拦截问题的算法；Aneja等[7]提出了一条弧损坏后的最大剩余流问题，并给出了求解最大流的关键弧的算法，并且说明在无向网络中此算法可以比自然算法降低理论算法复杂度；Du等[8]证明了最大剩余流问题对于损坏两

4、条及两条以上的弧时是NP难的；Tahmasbi等[9]综述了当前随机网络最大流问题的研究结果。5本文在上述研究的基础上主要对最大动态流的关键弧问题进行研究，在分析简化FordFulkerson最大动态流算法的基础上给出求解关键弧的算法MDFVA，并对MDFVA算法进行了分析比较。4结语本文对最大动态流的关键弧问题进行了全面的分析，首先将经典的FordFulkerson算法进行细化，得到最大动态流的直接算法；然后根据算法分析最小费用增广路的性质，得到求解关键弧的MDFVA算法，并将MDFVA算法与自然算法以及文献[4]的算法（R=1）进行对比。结果表明，M

5、DFVA算法比自然算法以及文献[4]的算法都要好。本文只研究了一条关键弧的算法，下一步研究可以考虑多条关键弧即关键弧集的算法；另一方面也可以将网络升级为多商品流的动态网络考虑求解关键弧的算法。参考文献：[1]AHUJIARK，MAGNANTITL，ORLINJB.Networkflows：theoryalgorithmsandapplication[M].UpperSaddleRiver：PrenticeHall，1993.[2]FORDLR，FULKERSONDR.Constructingmaximaldynamicflowsfromstaticflo

6、ws[J].OperationsResearch，1958，6（3）：419-433.[3]PICARDJC，QUEYARANNEM.Onthestructureofallminimumcutinanetworkandapplications[C]//CombinatorialOptimizationII：MathematicalProgrammingStudies.Berlin：SpringerVerlag，1980：58-16.[4]RADMA，KAKHKIHT.Maximumdynamicnetworkflowinterdictionproblem

7、：newformulationandsolutionprocedures[J].Computers&IndustrialEngineering，2013，65（4）：531-536.[5]LUNDAYBJ，SHERALIHD.Adynamicnetworkinterdictionproblem[J].Informatica，2010，21（4）：553-574.[6]ROYSETJO，WOODRK.Solvingthebiobjectivemaximumflownetworkinterdictionproblem[J].INFORMSJournalonC

8、omputing，2007，19（2）：175-184.[7]ANEJAYP，C