网络最大流算法的研究

发布时间：2024-07-06 13:42

　　网络最大流问题是特殊的组合优化以及线性规划问题,其在很多领域都存在着广泛的应用,例如物流行业的货物运输、快递企业的站点选址、社交网络的信息分析等,都可以转化为网络最大流问题。在如今大数据时代背景下,虽然网络最大流问题已有几十年的发展历史,但经典的算法很难满足大规模网络的计算要求。于是,对最大流问题的进一步深入钻研具备重大的实际价值。本文对网络最大流问题的经典算法进行了改进,主要成果如下:1、给出基于余网络的最短增广链算法,将余网络与剩余网络进行比较,发现余网络的构造比剩余网络的简单。通过减弱对最短增广链算法的约束,用余网络替换剩余网络,并且将余网络进行划分区域,使得算法的运行效率得以提高。通过分析实验数据可知:新算法与最短增广链算法求解的最大流流值一致,且比经典的最短增广链算法运行效率更高。2、通过分析容量网络图,提出基于分层剩余网络的最短增广链改进算法,首先删除容量网络中不能通向终点的弧,来简化容量网络;其次对分层剩余网络中删除的饱和弧,相应的在原网络中删除该弧,降低构建剩余网络和分层剩余网络的复杂性,于是使算法的运行效率得以进一步的提升。实验结果显示,改进算法能够得到最大流的精确解...

【文章页数】：52 页

【学位级别】：硕士

【部分图文】：

图!9*()多源多汇的仿真结果

结果中可以看到相关的比较结果!从多源多汇的规划公式及相应的结果可以看出"对应每一源&汇的最大流值和相应弧上的流量映射都是相互独立的"完全可以采用在单源&单汇研究中算法’分别找出相应于某一源&汇对的所有路径"并建立相应源&汇之间的路径#()*$"实现各源&汇间的流量传输"从....

图!9*()多源多汇的仿真结果

结果中可以看到相关的比较结果!从多源多汇的规划公式及相应的结果可以看出"对应每一源&汇的最大流值和相应弧上的流量映射都是相互独立的"完全可以采用在单源&单汇研究中算法’分别找出相应于某一源&汇对的所有路径"并建立相应源&汇之间的路径#()*$"实现各源&汇间的流量传输"从....

图1容量网络及可行流

2)去掉所有标号,回到第10步,对f~′={f~′ij}重新标号.5　计算示例图1表明一容量网络及初始可行流,即零流.每条弧上的有序数表示(c~ij,f~ij),求容量网络的最大流.图1　容量网络及可行流10标号过程.先给1标以(Δ,+∞),其它节点的标号见图22、转入调整过....

图46结束语

2、转入调整过程,调整后的可行流见图33、重新开始标号过程,寻找可增广链.其标号亦示于图3中.4、再转入调整过程,调整后的可行流见图45、对图4可行流进行标号过程,寻找可增广链.其标号亦示于图4中.可见只能对1,3点进行标号,由此得到标号集合S={1,3},未标号集合S-={....

本文编号：4002638