基于顶点的网络最大流求解算法

雩风三日

基于顶点的网络最大流求解算法
; ^+ {& E% ]1 i  A
    网络最大流问题是属于运筹学与图论中一种组合最优化问题，其涉及范围非常大，日常生活和生产中的许多实例都可以抽象成网络最大流问题的数学模型进行求解。例如，交通网络车辆流、管道网络油量流、信息网络数据流等。迄今为止，最大流问题己有六十多年的发展历程，很多专家和学者对此奉献了大量的研究成果。但根据各种网络的蓬勃成长，也就需
' G, F/ z' s+ i3 a  ~6 @0 C6 g/ N要更快更好的有关网络最大流问题的解决方法来面对这些网络的实际需求。因而对网络最大流问题进行更深层次地探索是有一定价值所在的。
4 N# X4 E( U4 o2 F# ^1 j5 t* Q+ Q    本文在网络最大流问题的经典算法的基础上，提出了一些改进算法，内容如下:
" Z3 r8 ?( N! s; K( `    1、提出基于交叉顶点的最大流改进算法，对含有交叉顶点的网络图中，构建其分层剩余网络后寻觅增广链时优先搜索与源点关联且容差最小的顶点作为增广链的下一步推进点。确定好一条增广链后，紧接着考虑与上一条有重复的顶点所在的增广链进行增广。对新算法和最短增广链算法在MATLAB上进行实验模拟，最后得出新算法的性能优于最短增广链算法。
    2、提出基于重置顶点下标的网络最大流算法，沿用了经典算法的顶点分层的思想，将顶点根据层数，源弧容量，汇弧容量和顶点容差这四个因素来确定顶点被选择的先后顺序。然后根据相应规则来选取增广链，此规则可以保证最短增广链优先选取，并可以井然有序地快速找出所有增广链。通过实例验证该算法的性能优于Ford-Fulkerson算法。
    3、提出基于度差的最短增广链算法，该算法是针对最短增广链算法同时沿多条增广路径进行增广，没有考虑增广顺序会影响最大流值的结果加以改进。提出了三个修正原则。通过实例验证新算法的性能优于最短增广链算法。

关键词:网络最大流，交叉顶点，分层剩余网络，容差，度差