为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

基于层次网络的最大流求解方法

2017-12-08 10页 doc 24KB 13阅读

用户头像

is_601191

暂无简介

举报
基于层次网络的最大流求解方法基于层次网络的最大流求解方法 第1O卷第4期 2010年8月 潍坊学院学报 JournalofWeifangUniversity V0l_10NO.4 Aug.2010 基于层次网络的最大流求解方法 徐翠霞 (潍坊学院,山东潍坊261061) 摘要:针对最大流问题的研究现状,提出了分层求解最大流的简单方法,并给出了该方法可行的严 格证明.该方法首先求得层次网络的阻塞流,进而最终求得一个最大流.另外,该方法还针对有向流网络 的特点,将算法中涉及的流网络,剩余网络和层次网络共用一个网络结构,既有效地降低了算...
基于层次网络的最大流求解方法
基于层次网络的最大流求解方法 第1O卷第4期 2010年8月 潍坊学院学报 JournalofWeifangUniversity V0l_10NO.4 Aug.2010 基于层次网络的最大流求解方法 徐翠霞 (潍坊学院,山东潍坊261061) 摘要:针对最大流问题的研究现状,提出了分层求解最大流的简单方法,并给出了该方法可行的严 格证明.该方法首先求得层次网络的阻塞流,进而最终求得一个最大流.另外,该方法还针对有向流网络 的特点,将算法中涉及的流网络,剩余网络和层次网络共用一个网络结构,既有效地降低了算法的空间复 杂度,还大大提高了算法的执行效率. 关键词:剩余网络;层次网络;饱和弧;最大流;阻塞流 中图分类号:TP301文献标识码:A文章编号:1671—4288(2010)04—0042—04 1基本概念 1.1有向流网络 一 个有向流网络N一(G,S,t,C)是一个四元组,其中,G一(V,E)是一个具有n个顶点,m条弧的有向 图;V是n个顶点的非空有限集合;E是m条弧的非空有限集合;S和t是G的两个特殊顶点,分别称为源 点和汇点,S?V,t?V;C是一个E一的函数,R是正实数集合,即每条弧e(e?E)都赋有一个非负的容 量C(e). 1.2顶点的层次和层次网络 顶点v的层次,记为level(v),是从源点S到顶点v路径中边的最小数,给定一个有向图G一(V,E), 层次网络I为(V,E),其中E一{<u,v>}jlevel(v)一level(u)+1}. 1.3弧容量,弧流量和剩余流量 在有向流网络中,每条弧e(e?E)上的非负容量C(e),称为该弧的弧容量,而实际通过该弧 的流量f(e),称为弧流量,弧容量是允许通过该弧的最大流量,然,弧流量不超过弧容量.弧容量和弧流 量之差为该弧的剩余流量,记为r(e). 1.4可行流和最大流 有向流网络中的一个可行流f,它一方面赋予网络中的每一条弧e(e ?E)一个非负流量f(e),另一方 面还满足两个规则. (1)容量规则 f(e)?C(e) 对于有向流网络中的每条弧e(e?E),其弧流量f(e)不超过其弧容量C(e). (2)守恒规则 IN(f,v)一OUT(f,v),其中v?V,{s,t} 除源点和汇点外的其余顶点的输人量IN(f,v)等于输出量()UT(f,v). ()UT(f,s)一IN(f,t) 源点的输出量等于汇点的输入量.(注意,源点的输入量和汇点的输出量均为0) 一 个可行流f的流量为源点的输出量或汇点的输入量,分别示为: *收稿日期:2O10—0312 基金项目:潍坊市2009年科学技术发展计划(20090l129) 作者简介:徐翠霞(】973一),女,山东雄坊人,潍坊学院计算机与通信工程学院副教授,工学硕士.研究方向:算法设 计与分析. —— 42--—— 第4期徐翠霞:基于层次网络的最大流求解方法 value(f)一OUT(f,s)或value(f)一IN(f,t) 设f是可行流,若对任何其他可行流f,均有value(f)~value(f,),则f是最大流. 1.5可行流中弧的种类 (1)饱和弧和非饱和弧 在一个可行流f中,若一条弧e(e?E)满足f(e)一C(e),则称该弧为饱和弧.若一条弧e(eEE) 满足f(e)<C(e),称该弧为非饱和弧. (2)零流量弧和非零流量弧 在一个可行流f中,若一条弧e(e?E)满足f(e)一0,则称该弧为零流量弧.若一条弧e(e?E) 满足f(e)>O,称该弧为非零流量弧. 1.6阻塞流 设G一(V,E)是一个具有n个顶点,m条弧的有向图,L是包含顶点S和t的G的子图,L中的流f称 为关于L的阻塞流,如果在L中每一条从S到t的路径中都至少有一条饱和弧. 1.7剩余网络 已知一个有向流网络和一个可行流,可行流的剩余网络与原始网络有相同的顶点,原始网络中的每条 弧在剩余网络中对应两条弧.定义如下:对于原始网络中的每条弧<u,v>,令f(u,v)为弧流量,c(u,v)为 弧容量.如果f(U,v)>0,则剩余网络中包含一条流量为f的弧<v,u>;如果f(u,v)<c(u,v),则剩余网 络中包含一条流量为c—f的弧<u,v>. 2算法的基本思想 2.1最大流的分层计算方法 首先初始化流为零流量,并设网络的剩余网络R为原始图,然后分阶段进行,每一阶段由两步组成. (1)根据剩余网络R计算层次网络L,如果t不在L中,则算法停止,否则继续; (2)计算L上的阻塞流,即只要在L中存在S到t的路径P,就用P对当前的可行流进行增值,并相应 地修改剩余网络R和层次网络I. 注意,增广路径在同一层次网络中具有相同长度,而且,在第一阶段后的任一阶段的增广路径都严格 地比它前面阶段的路径长.一旦t在新构造的层次网络中不出现,算法就立即终止. 2.2层次网络的计算方法 首先初始化各顶点的层次为一l,然后进行如下操作: Step1:初始化源点S的层次为0,即levelEs]一0; Step2:调用广度优先遍历算法,执行一步遍历操作,设当前遍历的弧为<v,v.>,令r(v,v)为该弧 的剩余流量.若r(v,v.)>O,则执行如下操作: ?若v还没有遍历,则levelEv.]一level[-v1]+1,且将弧<v1,v2>JJH人到L中; ?若v2已遍历且level[v.]一level[-v]+1,则将弧<v,v.>an人到L中; ?否则,不能将弧<v,v>加入到L中. 算法执行后,如果某顶点的层次为一1,表示该顶点不在层次网络L中,否则,该顶点在层次网络L 中. 2.3阻塞流的计算方法 在层次网络中搜索从S到t的增广路径,既可以使用BFS搜索,也可以DFS搜索.可以在找到了一 条增广路径后停止图搜索,进行增广运算,然后重新启动搜索;也可以继续搜索,并找到另一条路径,重复 进行,直到无路径为止. 为了提高算法的执行效率,在此选择第二种途径利用DFS搜索实现层次网络上阻塞流的计算.具体 操作如下: while(t为L中的顶点){ for(u—S;u!一t&&S有出弧未访问;){ if(u有出弧<u,v>未访问){//前进 一 43— 潍坊学院学报2010年8月 ?将<u,v>添入路径P中; ?u—v; ) else{//后退 ?删除I和U的所有邻接边; ?删除路径P中最末一条边; ?将u设为路径P中最后一个顶点. (注意U可能是s); } if(u一一t){//增值 ?计算P的瓶颈容量?; ?更新G中的流f,即将f增加?; ?更新R和I,删除饱和边; ?将U设为路径P中最后一个顶点. (注意U可能是s); ) )//for }//while 3算法选择的数据结构 为了实现最大流算法,在此使用流网络的邻接表表示,这是通过 扩展常用的邻接表得来的. (1)让每条边关联两个权重,cap(弧容量)和flow(弧流量). (2)虽然流网络是有向图,而算法需要从两个方向遍历边,所以使用针对无向图的类似表示:如果从U 到v有一条边,容量为C,流量为f,也可以有一条从v到u的边,容量为一C,流量为一f.如此以来,不需要 显式地构造剩余网络,使用一个简单的宏即可. #defineQ(e一>cap<07一e一>flow:e一>flow) (3)为了避免过多的表遍历,还运用了连接表示每条边的两个表节点的链接,当更改一个地方的流量 时,另一个地方的流量也会被更新. (4)由于L是G的子图,可以隐式地构造层次网络,将G中的每一条弧增加一个标识位,如果该弧加 入I,即置为true,否则置为false. typedefstruetnode*link; structnode{ //弧头顶点 ,,弧容量 //弧流量 //指向反方向的弧 //指向下一条弧 //该弧是否已加入I中 ff顶数 //弧数 }f谖轰 ; m;明 一一,,,一;一,,一;一一s算4 第4期徐翠霞:基于层次网络的最大流求解方法 引理1算法计算的层次网络至多为n个. 为了证明此算法计算的层次网络至多为n个,首先证明算法中增广路径的长度序列是严格递增的. 设P为当前层次网络中的任意增广路径,在用P增值后,至少有一条边将饱和,并在剩余图中消失.同时, 至多有lPJ条新边将在剩余图中出现,但它们是回边,因此不会对从s到t的最短路径做出贡献.因为 每次有一条边在层次网络中消失,因此最多可能有m条长度为IPf的路径.当t在层次网络中再也不能 从S到达时,任何增广路径必须用一条回边或交叉边,并且因此一定具有严格大于IPI的长度.因为任 何增广路径的长度介于1到n,1之间,用做增值的层次网络个数最多为n一1个,因为t不出现的层次网 络也要计算一次,因此计算的层次网络总数最多是n. 5算法运行时间分析 利用广度优先搜索,计算每一个层次网络L,需要的时问均为O(m); 在每一个L上计算阻塞流的时间 为0(ran).分析如下: (1)因为在每一次增值时,至少删除层次网络的一条边,因此增值次数至多是m.每次增值耗费o(n) 时间,用以修改流量,因此每一阶段增值的总耗费是O(mn). (2)因为每一次后退将导致除S或t外的一个顶点被删除,因此后退的次数(即for语句的else部分) 最多是n一2.在后退中,从层次网络中删除的边的总数至多是m,这意味着在每一个阶段中,后退的总耗 费为O(m+n). (3)在每次增值或后退前的向前次数(for语句的if部分)不能超过n—l;否则,在增值或后退前有一个 顶点将不止一次被访问.因此在每一阶段,前进的总数为O(mn). 每一阶段的总耗费为0(mn),因为最多有n个阶段,因此该算法的总运行时间为O(mn). 6结论 该方法不仅合理使用BFS搜索和DFS搜索分别求解层次网络及其上的阻塞流,进而最终求得一个最 大流;针对流网络的特点,将算法中涉及的流网络,剩余网络和层次网络共用一个网络结构,既有效地降低 了算法的空问复杂度,还大大提高了算法的执行效率. 参考文献: [1]KolmanB,BusbyRC,RossSC.DiscreteMathematicalStructuresEM].北 京:高等教育出版社,2001 [2~RobertSedgewick.C算法:第二卷(图算法)EM].周良忠,译.3版.北 京:人民邮电出版社,2004. [3]王晓东.算法与分析EM].北京:清华大学出版社,2003. ASimpleAlgorithmofMaximumFlowBasingonLayerNetwork XUCui—xia (WeifangUniversity,Weifang261061,China) Abstract:Inordertosolvetheproblemofmaximumflows,anewfeasibilityapproachwasproposedac— cordingtothepresentresearchsituation.Thismethodusedtofindblockflowsinlayernetworks,and thenfinallyfindamaximumflow.Itisprovedthatthemethodisefficientandfeasible.Itcanhelpteach— ingimprovementandpracticeapplication.Itisalsoworthpopularization. Keywords:residualnetwork,layernetwork,saturationedge,maximumflow,blockflow (责任编辑:肖恩忠)
/
本文档为【基于层次网络的最大流求解方法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索