点和边有容量约束的网络最小费用最大流算法*

分析了目前网络最小费用最大流算法存在的问题,提出网络最小费用最大流新算法。概括出条件约束下的网络最小费用最大流问题的两目标优化数学模型,针对点和边有容量约束的网络最小费用最大流问题特点,定义了有向路径、有向路径单位流费用和残量网络的概念。依据可行流分解定理,以邻接矩阵为网络数据存储结构,使用数据结构中的遍历方法,实现了网络最小费用最大流新算法。该算法在不破坏平面性条件下,可以求解点和边有容量约束的网络最小费用最大流。最后,通过实例进行了算法测试和比较。算法测试表明：点和边有容量约束的网络最小费用最大流算法是完全可行和有效的。     

小容量网络上的最大流算法

最大流问题是一类经典的组合优化问题。描述了一种小容量网络,这种网络有强的实际应用背景,同时给出了专门解这种网络上最大流问题的算法。该算法比通用的算法快。它已经突破了最大流问题的O（mn)时间障碍,具有较强的理论意义,也为解决许多实际应用问题提供了更有效的算法。同时,由于判断一个网络是否为小容量网络非常简单,因此该算法也具有普遍意义。     

基于栈的网络最大流算法

针对网络最大流问题,在割集定义和最大流-最小割定理基础上,以邻接矩阵为网络数据存储结构,利用栈作为数据组织形式,遍历网络中所有割集,最小容量的割集即为网络最大流。流量网络其余分支流量由网络结点流量平衡条件来求解。该算法具有：开辟了一种求解流量网络最大流的新的方法,克服了割集和最大流-最小割定理仅仅具有理论价值、没有实用价值的局限性;根据最小容量的割集可以方便确定决定网络最大流的关键分支,为扩展网络流量提供直接技术支持。算法测试表明：基于栈的网络最大流算法是完全可行和有效的。     

无向平面单位容量网络中的最大流

无向平面单位容量网络中的最大流问题在VLSI设计等领域中有广泛的应用.针对无向平面单位容量网络的特点, 给出这类网络中一个O(n)时间的最大流算法, 比一般平面网络中O(nlog n)时间的最大流算法快log n倍.     

动态容量网络中的最小最大时间流问题

动态(时间依赖的)容量网络与传统静态网络相比更具现实意义,在交通网络、物流网络和通信网络中都有着广泛的应用。在时间依赖网络最短路算法的基础上,研究具有实际背景的动态容量网络的最小最大时间流问题,给出求动态容量网络的最小最大时间流的多项式算法和算法的应用实例,其时间复杂度为O(mMv)。     

网络最大流的新算法

针对Ford-Fulkerson标号算法在求解网络最大流问题时需要经过多次的标号与调整,从而导致算法效率随着网络规模的增大和网络复杂性的增加而降低的不足,受现实生活中水流流动的启发,通过引入极大一致链的概念提出了一种求解网络最大流问题的消链算法.该算法通过寻找容量网络中的极大一致链,并根据所得到的极大一致链对网络逐步地进行调整,避免了标号算法的标号过程,同时由于极大一致链的极大性加速了链的消去过程.算法分析和算例表明了该算法的有效性和实用性.     

网络最大流求解算法的研究

近年来,随着各种网络的飞速发展,对最大流问题的研究也取得了很大的进展。文章简述了网络最大流问题的现状,提出了一种求解网络最大流与最小截问题的算法。此算法使得计算网络最大流变得简便,且具有很强的实用性。     

最大可行流问题中增值链的一种回溯求解算法

本文就最大可行流问题给出了一种回溯求解的算法，并证明了不可扩展结点的可剪裁性问题，旨在减少后续可能的搜索空间．在一定程度上可以减少求解过程中的时间消耗．     

网络最大流问题的改进算法

网络最大流问题是图论中的经典问题之一,对于最大流问题有很多经典的算法,但这些经典算法皆有不足之处。针对其不足,文中通过引入容量差的概念,对算法进行了一些改进。改进算法的原则是优先选择路径最短且容量差最大的路径进行增广,若当路径长度一样并且容量差也一样时就要对其修正,然后选择修正后的路径,这样每次增广至少使一条弧达到饱和。通过实例说明了改进算法的可行性,整个运算过程可以在一个图上完成,直观性强并且方便计算,较传统算法更为有效。     

网络最大流的自适应求解算法——SAPR算法

为提升对大规模不同拓扑结构网络的求解速度,通过评估基本操作的执行效率、动态调整活跃顶点的选择方式及盈余流的推进方式,提出了一种可高效求解多类拓扑网络的自适应预流推进算法——SAPR(self-adaptive push-relabel)算法.在The First DIMACS implementation Challenge提供的七类不同拓扑结构网络上,对SAPR算法及四种适用于特定拓扑网络的算法进行了对比实验,结果表明:SAPR算法在一半的数据上能持平高效的H_PRF算法,而另一半能超越H_PRF算法.SAPR算法的高效性和强稳定性解决了传统算法在多类拓扑网络中不能都取得高效率的问题.     

无线传感器网络最大生命期与最大流路由算法

提出了一种无线传感器网络最大生命期和最大流路由算法,证明了网络最大生命期相当于获得网络最大流,根据最大流最小割定理,网络一定存在一个可行解满足网络最大流,在算法复杂度较低情况下,建立以最大生命期为最优目标的网络模型,依靠现有的启发式分布式算法解决该模型。通过仿真验证了算法的性能,表明所提出算法可以有效延长网络生命期。     

级连层次图的网络最大流算法研究

给出一种通过构造网络级连层次图的方法,来间接求出最大网络流的算法。对于给定的有n个顶点,e条边的网络N=G,s,t,C,该算法可在On2时间内快速求出流经网络N的最大网络流及达最大流时的网络流。     

基于增广链修复的最大流求解算法

NW小世界网络及BA无标度网络是现实中常见的两种网络,这两种网络中任意两点之间有极大可能存在多条路径,若舍弃饱和增广链并重新寻找增广链,则效率不高,因此针对网络的这一特性提出了一种增广链修复的最大流求解算法.该算法沿最短增广链调整流量后,保留路径上残余的非饱和弧,并用贪心法则选择合适的中继节点修复断开的增广链,提高增广链使用效率.通过对NW小世界网络和BA无标度网络建模仿真,得到并验证了所提算法在这两种网络上的运行速度数倍于Ford-Fulkerson算法且其空间复杂度仅有Dinic算法的一半,因此所提算法能够高效处理更大规模网络流问题,以适应日益膨胀的通信网络和交通运输网络.     

基于网络最大流的交通控制时间研究

本文从网络最大流的角度出发，建立和简化了城市道路网模型，在交通流的控制中引入以时间为控制参数的流量模型的控制方法．使用matlab工具实现了各个路口之间基于网络最大流的时间差别控制的合理化计算。论述了优化城市交通并非是寻求各个单路口的最大通过性，而应按区域内的道路容量对路口进行差别控制，并给出了一个求解通行时间的方法，为智能交通控制提供了参考。     

网络优化的最大利润问题及其增广路算法

仿照最小费用最大流问题的物理意义,将网络上的费用参数转化成为一种利润参数,提出一个最大利润流问题,并建立了该问题的数学规划模型;给出一个求解该问题的最大利润增广路算法,该算法能快速有效地求得该问题的最优解及目标函数值。用示例对算法的求解过程进行了演示,结果表明该算法比一般的线性规划方法更加的方便,且直观得多。     

最大流的弧容忍度问题及其算法

针对通信网络中通道的带宽发生变化是否会影响通道的最大通信能力的问题,提出最大流的弧容忍度问题。结合最大流与最小截的性质,将最小截内外的弧分别进行考虑,提出了求解每条弧的弧容忍度的多项式时间算法,并对算法进行分析比较。实例结果表明,算法复杂度低,易于操作。     

求解最小费用最大流问题的信念传播算法

最小费用最大流问题是一种组合优化问题,在经济、工业等领域具有重要研究意义和应用价值.针对部分最小费用最大流问题求解算法效率较低的情况,依据最小费用最大流问题的线性规划方程,将问题模型映射为对应因子图模型,改进描述函数,给出迭代方程,设计了求解最小费用最大流问题的信念传播算法.利用迭代方程优先对最大可行流特征值进行收敛计算,得到最大流,设置最大流阈值,在此基础上进行最小费用计算,从而求得问题最优解.最后选取若干带权有向图模型进行数值实验,验证了算法的可行性及有效性,且算法在求解效率上优于部分算法.