基于结点的网络最大流算法

基于结点的网络最大流算法 第31卷第12期 2009年12月 武汉工程大学 J.WuhanInst.Tech. Vo1.31lqo.12 Dec.2009 文章编号:1674—2869(2009)12—0067—03 基于结点的网络最大流算法 胡雄鹰,熊茜,黎伟东 (武汉工程大学管理学院,湖北武汉430074) 摘要:提出了一个基于结点的网络最大流问题的简单算法,本算法容易理解,计算 简便,效率高,还可以很快 地找出网络中的瓶颈,并以此来优化整个网络以提高最大流的流量. 关键词:结点;网络;最大流;算法;优化 中图分类号:TP391文献标识码:A 0引言 最大流问题是一类经典的组合优化问题,它 也可以看做是特殊的线性问题_】].这类问题 在电力,交通,通信,计算机网络等工程领域和物 理,化学等科学领域有着广泛的应用,许多其它的 组合优化问题也可以通过最大流问题求解l_2]. 1网络最大流算法研究进展 1.1组合算法 假设网络中已经有了一定的流.考虑网络的 一 条边,一方面,如果该边的流还没有达到该边的 容量,则可以继续增加该边上的流;另一方面,也 可以减少该流,这相当于在网络中沿该流相反的 方向增加流.称由剩余容量不为零的那些边和与 现有流方向的相反方向的边构成的网络为剩余网 络.组合算法是不断地在剩余网络中增加流量直 到找到最大流]. 组合算法一直是最大流算法研究的主流,随 着各种组合技术的发展和应用,算法的时间复杂 度不断进步.目前具有最好的实际性能的算法也 是组合算法,它们是增广链类算法中的Dinic阻塞 流算法和预流推进类算法中的Goldberg和 Tarjan推进一重标号算法].最近的实验研究 明预流推进算法在实验性能方面更有优势. 1.2线性规划算法 最大流问题是特殊的线性规划问题.一般求 解线性规划问题的如单纯形法,椭球法,内点 法等都可以用来解决最大流问题.利用最大流 问题的特殊性,可以得到比一般算法更有效的算 法.习惯上称利用最大流问题的特殊性得到的单 纯形法,内点法为网络单纯形法,网络内点法_1. 1.3其他算法 随机算法和解随机技术也常用于最大流问 题.其他算法还有遗传算法,神经网络算法 等[1112]. 2基于结点的网络最大流算法 下面提出一个基于结点的网络最大流算法, 它属于组合算法中的预流推进类算法. 2.1基本概念 给定网络D一(,A,C),其中V代表D中结 点的集合,A代表弧的集合.记Il—rt,lA1一m. 每条弧(,,)上有权f(,,)(或简写为c)称作 该弧的容量.其中V和分别是D中的源点和汇 点.流量用(厂)表示[1]. 对于流,有两个明显的要求:一是每条弧上的 流量必须是非负的且不能超过该弧的最大通过能 力(即该弧的容量);二是中间点的流量为零. 定义1称流入结点的各弧容量和为该结 点的流入容量a,从该结点流出的弧容量和为该 结点的流出容量,称各结点流人容量与流出容 量的差值为堵塞量a2一a一. 显然,当32>0时,它是易堵结点,当<0 时,它是不堵结点. 定义2若弧的起始结点的堵塞量z一>0, 结束结点的堵塞量212<O,则该弧称为可优化弧. 若弧的起始结点的堵塞量z一<0,结束结点的堵 塞量z>0,则该弧称为约束弧. 收稿日期:2009—01—01 基金项目:湖北省教育厅科学研究项目(Q20081502);武汉工程大学人文社科项目 (R200801) 作者简介:胡雄鹰(1971一),男,湖北钟祥人,讲师,博士研究生.研究方向:供应链管理 与管理系统模拟 68武汉工程大学第31卷 2.2算法原理 整个网络源点流出的量与流人汇点的量相 等,且各中间结点流入的流量之和必须等于从该 点流出的流量之和. 假设从源点以最大的流量流出(各弧按其容 量流出),在经过有堵塞的结点(>0)时有部分 流量会被堵塞在该点,因要满足其平衡条件需把 堵塞的部分流量外放.源点流出的总量减去各结 点因堵塞而外放的流量为一f?z{,都能流入 汇点,此即最大流()一风一l?1. 2.3算法描述 从以上算法原理的描述中可得到基于结点的 网络最大流算法如下: 输入:源点V,网络中间结点和汇点. 输出:满足约束条件的网络最大流. 方法: (1)首先求出各结点的的流入容量a和流出 容量』9,算出堵塞量z一a一,标于各结点之上; (2)分析各弧起始结点和结束结点的堵塞量, 找出所有的可优化弧,对可优化弧的容量做出相 应减少,该优化不会影响整个网络图的流量; (3)求出所有>O的和?.z(其中可优化弧 的堵塞量为优化后的);求出源点的流出量风; 一 l?I即为该网络的最大流(,). 2.4算法分析 (1)算法正确性.上述标号算法中,源点流出 的总量减去各结点因堵塞而外放的流量,都能流 入汇点,此即最大流量,符合最优化原理,因此算 法是正确的. (2)时间复杂性分析.结点数为,弧数为m, 设每个结点的最大连接弧数为m,则计算各结 点堵塞量的总计算量不大于(一2)…,寻找约束 弧的计算量不大于2(n一2),综上所述,总的算法 时间复杂性为0(). (3)空间复杂性分析.算法的空间复杂度是指 算法需要消耗的空间资源.空间是为了保存中间 结果所需要的存储器的大小.本算法可以对结点 逐个进行分析,所需空间在计算各结点堵塞量时 不大于m…,寻找每个约束弧时不大于2,计算所 需空间极小. (4)并行时间复杂性分析.并行时间是并行计 算所需要的时间,亦即如果多人或多处理机协同 计算,解决一个问题所需要的时间.如果所给网络 庞大,对于不共享弧的独立结点可以并行地计算 它们的结点堵塞量以及寻找约束弧,这样可以加 快求解过程.网络越大,各结点的独立性越强,采 用并行机制加速越明显. 2.5算法示例 有输油管道如图1所示.要求算出该网络的 最大流. 图1输油管道网络 Fig.1Pipelinenetwork 首先求出各点的的流入容量和流出容量,再 算出堵塞量z一一,标于各结点之上如图2所 刀. (十1) 图2堵塞量 Fig.2Blockingvolume 再分析各弧起始结点和结束结点的堵塞量, 找出所有的约束弧.图中弧艇为约束弧,优化步 骤如图3所示. 1) 图3优化步骤 Fig.3Optimizationsteps 然后求出所有>0的和?32(其中约束弧 的堵塞量为优化后的): ?一+z,+一 (+2)+(十1)十(+1):=:4 最后求出源点的流出量,一l?l即为 该网络的最大流: 风一4+6+4—14 (厂)一风一I?1=14—4—10 同时可以得出弧磁,7JCF,VFG均为可优化弧. 相应地提高弧历,VCF,VFG的容量即可提高该网络 的最大流流量. 在现实生活中,各种输油管道的铺设都是需 要很高的费用的,各条管道的费用随着其容量的 第12期胡雄鹰,等:基于结点的网络最大流算法69 增大而增大,在约束弧中有部分的容量自始至终 都不曾被使用过,这样就造成了浪费;提高可优化 弧的容量能立刻提高该网络的最大流流量.通过 该方法可以确定铺设输油管道时各弧的最优容 量,降低成本,提高流量. 3算法比较 通过实例演示了求解网络最大流的一个基于 结点的新算法,它与一般运筹学课本上的基于增广 链的算法不一样.传统上,基于增广链的算法是根据 最大流量最小截量定理,转化为它的对偶问题,即通 过寻找网络的最小截集实现的,它是一种基于全局 的优化算法.而算法是基于局部(结点)的优化算法, 它暗含着可以采用并发机制计算求解. 4结语 上述基于结点的网络最大流算法,容易理解, 计算简便,效率高,能快速找出网络瓶颈,并以此 优化网络以提高最大流的流量. 参考文献: [1] [2] [3] 韩伯棠.管理运筹学[M].北京:高等教育出版社, 2005:242—247. HujiaRK,MagnantiTL,OrlinJB.Algorithms andApplications[M].NetworkFlows:Englewood Cliffs,1993:78—82. 陈国良,梁维发,沈鸿.并行图论算法研究进展 [J].计算机研究与发展,1995,32(9):1—16. [4]GoldbefgAV,TarjanRE.Anewapproachtothe iTl~ximumflowproblem[J].JournaloftheAssociation forComputerMachine,1988,35(4):921—940. E5]AhujaRK,MagnantiTL,OrlinJ.B.Network Flows:Theory,AlgorithmsandApplications[M]. NewJersey:Prentice-Hall,1993:123—13O. [6]GoldbergAV.Recentdevelopmentsinmaximum flowalgorithms(InvitedLecture)[C].ArnborgS, IvanssonL.ed.ProcoftheSixthScandinavian WorkshoponAlgorithmTheory.Heidelberg: Springer-Verlag,1998:1—1O. [7]DantzigGB.Applicationofthesimplexmethodtoa transportationproblem[C].ActivityAnalysisand ProductionandAllocation.NewYork:Wiley,1951: 359—373. [8]FordLR,FulkersonDR.Maximumflowthrougha network[J].CanadianJournalofMath,1956,8(5): 399—404. [9]DinicEA.Algorithmforsolutionofaproblemof maximumflowinnetworkswithpowerestimation [J].SovietMathDok,1970,11(8):1277—1280. [1O]GoldbergAV,RaoS.Beyondtheflowdecomposition barrier[J].AssocComputMach,1998,45(5):783— 797. [11]张彦铎,葛林凤.一种新的基于MMAS的机器人 路径规划方法[J].武汉工程大学,2009, 31(5):76—79. [12]孑L伟,张彦铎.基于遗传算法的自主机器人避障方 法研究[J].武汉工程大学,2008,30(3):l1O— l13. Networkmaximumflowalgorithmbasedonnodes HUXiong-ying,XIONGQian,LJWei—dong (SchoolofManagement,WuhanInstituteofTechnology;Wuhan430074,China) Abstract:WeprovideasimplealgorithmonnetworkSmaxflowproblems,basedonnodes.Th e algorithmiseasytounderstand,anditscalculationissimple,andefficient.Youcanquicklyide ntifythe networkbottlenecksandoptimizetheentirenetworkinordertoincreasethemaximumflow. Keywords:nodes;network;maximumflow;algorithm;optimize 本文编辑:陈晓苹