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

基于结点的网络最大流算法 () 文章编号 :167422869 20091220067203 基于结点的网络最大流算法 胡雄鹰 ,熊 茜 ,黎伟东 () 武汉大学管理学院 ,湖北 武汉 430074 摘 要 :提出了一个基于结点的网络最大流问的简单算法 ,本算法容易理解 ,计算简便 ,效率高 ,还可以很快地找出网络中的瓶颈 ,并以此来优化整个网络以提高最大流的流量. 关键词 :结点 ;网络 ;最大流 ;算法 ;优化 中图分类号 : T P391文献标识码 : A 法. 习惯上称利用最大流问题的特殊性得到的单 0 引言[ 10 ] 纯形法、内点法为网络单纯形法 、网络内点法. 1 . 3 其他算法 最大流问题是一类经典的组合优化问题 , 它 [ 1 ] 随机算法和解随机技术也常用于最大流问 也可以看做是特殊的线性问题. 这类问题 题. 其 他 算 法 还 有 遗 传 算 法 , 神 经 网 络 算 法 在电力 、交通、通信、计算机网络等工程领域和物 [ 11212 ] 理、化学等科学领域有着广泛的应用 ,许多其它的 等. [ 2 ] 组合优化问题也可以通过最大流问题求解. 2 基于结点的网络最大流算法1 网络最大流算法研究进展 下面提出一个基于结点的网络最大流算法 , 1 . 1 组合算法 它属于组合算法中的预流推进类算法. 假设网络中已经有了一定的流. 考虑网络的 2 . 1 基本概念一条边 ,一方面 ,如果该边的流还没有达到该边的 ( ) 给定网络 D = V , A , C, 其中 V 代表 D 中结 容量 ,则可以继续增加该边上的流 ; 另一方面 , 也 可以减少该流 , 这相当于在网络中沿该流相反的 点的集合 , A 代表弧的集合. 记| V | = n , | A | = m . 方向增加流. 称由剩余容量不为零的那些边和与 ( ) ) ( ) ( 每条弧 v, v 上有权 c v, v 或简写为 c称作i j i j ij 现有流方向的相反方向的边构成的网络为剩余网 该弧的容量. 其中 V s 和 V t 分别是 D 中的源点和汇络. 组合算法是不断地在剩余网络中增加流量直 [ 1 ] [ 3 ] ( ) 点. 流量用 v f 表示.到找到最大流. 对于流 , 有两个明显的要求 :一是每条弧上的 组合算法一直是最大流算法研究的主流 , 随 流量必须是非负的且不能超过该弧的最大通过能 着各种组合技术的发展和应用 , 算法的时间复杂 ( ) 力 即该弧的容量; 二是中间点的流量为零. 度不断进步. 目前具有最好的实际性能的算法也 定义 1 称流入结点 v 的各弧容量和为该结 n 是组合算法 ,它们是增广链类算法中的 Di nic 阻塞 α点的流入容量, 从该结点流出的弧容量和为该n 流算 法 和 预 流 推 进 类 算 法 中 的 Gol dber g 和 β结点的流出容量, 称各结点流入容量与流出容n [ 426 ] Ta rja n 推进 - 重标号算法. 最近的实验研究表 αβ量的差值为堵塞量 x =- .n n n 明预流推进算法在实验性能方面更有优势.显然 , 当 x > 0 时 , 它是易堵结点 , 当 x < 0n n 1 . 2 线性规划算法时 , 它是不堵结点. 最大流问题是特殊的线性规划问题. 一般求 解线性规划问题的方法如单纯形法 、椭球法、内点 若弧的起始结点的堵塞量 x > 0 ,定义 2n - 1 [ 729 ] 法等都可以用来解决最大流问题. 利用最大流 结束结点的堵塞量 x < 0 , 则该弧称为可优化弧.n 若弧的起始结点的堵塞量 x < 0 , 结束结点的堵 问题的特殊性 , 可以得到比一般算法更有效的算n - 1 塞量 x > 0 , 则该弧称为约束弧.n 收稿日期 :2009201201 ( ) ( )基金项目 :湖北省教育厅科学研究项目 Q20081502;武汉工程大学人文社科项目 R200801 () 作者简介 :胡雄鹰 19712,男 ,湖北钟祥人 ,讲师 ,博士研究生. 研究方向 :供应链管理与管理系统模拟. 2 . 2 算法原理.用并行机制加速越明显 整个网络源点流出的量与流入汇点的量相 2 . 5 算法示例等 , 且各中间结点流入的流量之和必须等于从该 有输油管道如图 1 所示. 要求算出该网络 点流出的流量之和. 最大流. ( 假设从源点以最大的流量流出 各弧按其容 ) ( ) 量流出, 在经过有堵塞的结点 x > 0 时有部分 n 流量会被堵塞在该点 , 因要满足其平衡条件需把 堵塞的部分流量外放. 源点流出的总量减去各结 β点因堵塞而外放的流量为- | ?x | , 都能流入 S n β( ) 汇点 , 此即最大流 V f =- | ?x | .S n 图 1 输油管道网络 2 . 3 算法描述Fig. 1 Pipeline net wo r k 从以上算法原理的描述中可得到基于结点的 首先求出各点的的流入容量和流出容量 , 网络最大流算法如下 : αβ算出堵塞量 x =- , 标于各结点之上如图 2 n n n 输入 :源点 V 、网络中间结点和汇点 V .s t 示. 输出 :满足约束条件的网络最大流. 方法 : ( ) α1首先求出各结点的的流入容量和流出 n βαβ容量, 算出堵塞量 x =- , 标于各结点之上 ;n n n n ( ) 2分析各弧起始结点和结束结点的堵塞量 , 找出所有的可优化弧 , 对可优化弧的容量做出相 应减少 , 该优化不会影响整个网络图的流量; 图 2 堵塞量( ) ( 3求出所有 x > 0 的和 ?x 其中可优化弧 n n Fig. 2 Blocking vol ume ) ββ的堵塞量为优化后的; 求出源点的流出量 ; S S 再分析各弧起始结点和结束结点的堵塞 ( ) - | ?x | 即为该网络的最大流 V f .n 找出所有的约束弧. 图中弧 V 为约束弧 , 优化B E 2 . 4 算法分析 骤如图 3 所示.( ) 1算法正确性. 上述标号算法中 , 源点流出 的总量减去各结点因堵塞而外放的流量 , 都能流 入汇点 , 此即最大流量 , 符合最优化原理 , 因此算 法是正确的. ( ) 2时间复杂性分析. 结点数为 n , 弧数为 m , 设每个结点的最大连接弧数为 m, 则计算各结 max ( ) 点堵塞量的总计算量不大于 n - 2m, 寻找约束max 图 3 优化步骤( ) 弧的计算量不大于 2 n - 2, 综上所述 , 总的算法Fig. 3 Op timizatio n step s ( ) 时间复杂性为 O n.( 然后求出所有 x > 0 的和 ?x 其中约束 n n ( ) 3空间复杂性分析. 算法的空间复杂度是指 ) 的堵塞量为优化后的: 算法需要消耗的空间资源. 空间是为了保存中间 x = x + x + x =n E F C ?结果所需要的存储器的大小. 本算法可以对结点 ( ) ( ) ( ) + 2+ + 1+ + 1= 4 逐个进行分析 , 所需空间在计算各结点堵塞量时 ββ最后求出源点的流出量,- | ?x | 即 S S n 不大于 m, 寻找每个约束弧时不大于 2 , 计算所 max 该网络的最大流 : 需空间极小. β= 4 + 6 + 4 = 14S ( ) 4并行时间复杂性分析. 并行时间是并行计 ( ) βV f =- | ?x | = 14 - 4 = 10S n 算所需要的时间 , 亦即如果多人或多处理机协同 同时可以得出弧 v EG 、vCF 、v FG 均为可优化 Goldberg A V , Tarjan R E. A new app roach to t he [ 4 ] 增大而增大 , 在约束弧中有部分的容量自始至终 maximum flow p ro blem [ J ] . Jo urnal of t he Association 都不曾被使用过 , 这样就造成了浪费; 提高可优化 () for Co mp uter Machine , 1988 , 35 4:9212940. 弧的容量能立刻提高该网络的最大流流量. 通过 A huja R K , Magnanti T L , O rlin J . B . Net wo r k [ 5 ] 该方法可以确定铺设输油管道时各弧的最优容 Flo w s : Theo r y , Algo rit hms a nd Applicatio ns [ M ] . 量 , 降低成本 , 提高流量. New J er sey : Prentice2Hall , 1993 :1232130 . [ 6 ] Goldber g A V . Recent develop ment s in ma xi mum 3 算法比较 ( ) f lo w al go rit hms Invit ed L ect ure[ C ] . A r nbo r g S , 通过实例演示了求解网络最大流的一个基于 Iva nsso n L . ed. Proc of t he Sixt h Sca ndinavian 结点的新算法 ,它与一般运筹学课本上的基于增广 Wo r k shop o n Algo rit hm Theo r y. Heidel ber g : 链的算法不一样. 传统上 ,基于增广链的算法是根据 Sp ringer2Verlag , 1998 :1210 . 最大流量最小截量定理 ,转化为它的对偶问题 ,即通 [ 7 ] Dantzig G B . Applicatio n of t he simplex met ho d to a 过寻找网络的最小截集实现的 , 它是一种基于全局 t ranspo rtatio n p ro blem [ C ] . Activit y A nalysi s a nd () 的优化算法. 而算法是基于局部结点的优化算法 , Pro ductio n a nd Allocatio n. New Yo r k : Wiley , 1951 : 它暗含着可以采用并发机制计算求解. 3592373 . Fo r d L R , Ful ker so n D R. Ma ximum f lo w t hro ugh a [ 8 ] () net wo r k [J ] . Ca nadia n J o ur nal of Mat h , 1956 , 8 5: 4 结语 3992404 . 上述基于结点的网络最大流算法 , 容易理解 ,[ 9 ] Di nic E A . Algo rit hm fo r sol utio n of a p ro blem of 计算简便 , 效率高 , 能快速找出网络瓶颈 , 并以此 ma ximum f lo w i n net wo r ks wit h po wer estimatio n 优化网络以提高最大流的流量. () [J ] . So viet Mat h Do k , 1970 , 11 8:127721280 . [ 10 ] Goldberg A V , Rao S. Beyond t he flow decompo sition 参考文献 :( ) barrier [ J ] . Assoc Co mp ut Mach , 1998 , 45 5 : 7832 797. [ 1 ] 韩伯棠. 管理运筹学 [ M ] . 北京 : 高等教育出版社 ,[ 11 ] 张彦铎 , 葛林凤. 一种新的基于 MMA S 的机器人 2005 :2422247 . 路径规 划 方 法 [ J ] . 武 汉 工 程 大 学 学 报 , 2009 , [ 2 ] H ujia R K , Magna nti T L , O rli n J B . Al go rit hms () 31 5:76279 . a nd Applicatio ns [ M ] . Net wo r k Flo w s : Englewoo d [ 12 ] 孔伟 , 张彦铎. 基于遗传算法的自主机器人避障方 Cliff s , 1993 :78282 . ( ) 法研究[J ] . 武汉工程大学学报 , 2008 , 30 3: 1102 [ 3 ] 陈国良 , 梁维发 , 沈 鸿. 并行图论算法研究进展 113 . () [J ] . 计算机研究与发展 , 1995 , 32 9:1216 . Net work maximum f lo w algorithm ba sed on nodes HU Xi o n g2yi n g , X IO N G Qi a n , L I Wei2d o n g ( )School of Ma nagement , Wuha n Instit ute of Technolo gy ; Wuhan 430074 ,China Abstract : We p ro vi de a si mp le al go rit h m o n net wo r k’ s ma x f lo w p ro ble ms , ba se d o n no de s. The al go rit h m i s ea sy to unde r st a nd , a nd it s calculatio n i s si mp le , a nd efficie nt . Yo u ca n quic kl y i de ntif y t he net wo r k bo t t le nec k s a nd op ti mize t he e nti re net wo r k i n o r de r to i ncrea se t he ma xi mu m f lo w . Key words : no de s ; net wo r k ; ma xi mum f lo w ; al go rit h m ; op ti mize 本文编辑 :陈晓苹