基于栈的网络最大流算法

基于栈的网络最大流算法 ComputerEngineeringandApplications计算机工程与应用 基于栈的网络最大流算法 厍向阳 SHEXiang——yang 西安科技大学计算机科学与技术学院,西安710054 ComputerScienceandTechnologyCollege,Xi'anUniversityofScienceandTechnology,Xi'an710054,China E—mail:xiangyangshe@sohu.con SHEXiang-yang.Newmax-flowalgorithminnetworkbasedonstack.ComputerEngineeringandApplications,2009,45 (33):13一I5. Abstract:Facingthequestionofmax—flowinnetwork,basedoncutsetdefineandmax— flowmin—cuttheorem,withadjacency matrixtodepositnetworkdata,usingthedatastructureofstacktoorganisenetworkdata,traversingallcutsets,theminimumca— pacityinal1cutsetsiSmax— flowinnetwork.eotherbranches,besidesthebranchesoftheminimumcutset,ayecalculatedby solvingthenodeflowbalanceequationinnetwork.Thealgorithmpioneersanewwaytosolvethequestionofmax-flowinnet— work,andbreaksthelocalizationofcutsetdefineandmax—flowmin— cuttheoremthathaveonlytheoryvalue,donotsolve practicmax—flowinnetwork.Thekeybranchesinnetworkthatdecidemax— flowinnetworkaremadeeasilybythewayoftl1e minimumcutset.Thedirecttechnologysupportforenlargingmax-flowinnetworkisprovidedbythealgorithm.Algorithmtesting shows:Thenewmax—flowalgorithminnetworkbasedonstackiscompletelyfeasibleandavailable. KeyWOrds:max—flowinnetwork;cutset;stack;max—flowmin—cuttheorem 摘要:针对网络最大流问题,在割集定义和最大流一最小割定理基础上,以邻接矩阵为网络数据存储结构,利用栈作为数据组织 形式,遍历网络中所有割集,最小容量的割集即为网络最大流.流量网络其余分支流量由网络结点流量平衡条件来求解.该算法具 有:开辟了一种求解流量网络最大流的新的,克服了割集和最大流一最小割定理仅仅具有理论价值,没有实用价值的局限性; 根据最小容量的割集可以方便确定决定网络最大流的关键分支,为扩展网络流量提供直接技术支持.算法测试表明:基于栈的网 络最大流算法是完全可行和有效的. 关键词:网络最大流;割集;栈;最小容量割集 DOI:10.3778~.issn.1002—8331.2009.33.005文章编号:1002—8331(2009)33—0013—03文献标识码:A中图分类号:TP393.3 1引言 网络最大流问题和它的对偶——最小割问题是一对经典 组合优化问题,在许多工程领域和科学领域有重要的应用,是 计算机科学和运筹学重要的内容.最大流问题已经有40多 年的研究历史,目前网络最大流问题主要有两类算法:(1)组合 算法.按在剩余网络中推进流方式的不同,组合算法分为:增载 轨算法和预流推进算法.增载轨算法有Ford和Fulkerson的标 号算法[31,Dinic的阻塞流算法和Ahuja和Orlin的最短增载轨 算法[51等.预流推进算法有Karzanov的阻塞流算法,Goldberg 和Taqan的推进重标号算法,Goldgerg和Rao的二分长度阻 塞流算法[81等.(2)线性规划算法.最大流问题是一个特殊的线 性规划问题,利用其特殊性,可以得到比一般线性规划算法更 有效的算法,如:网络单纯形法,网络内点法.在网络最大流 问题中,割集概念和最大流一最小割定理是各种网络最大流算 法理论基础,具有重要的理论意义,然而仅此而已,对具体网络 最大流算法没有实用价值.针对网络最大流问题,根据割集定 义和最大流一最小割定理,以邻接矩阵为网络数据存储结构,利 用栈作为数据组织形式,遍历网络中所有割集,找到的最小容 量的割集即为网络最大流.流量网络其余分支流量由网络结点 流量平衡条件来求解.最后,通过实例进行了算法测试和比较. 2问题描述和预备知识 2.1网络与流 (1)流网络 在以为结点集,A为弧集,且ll,IAI为图G中结点和分 支数,且IVl=m,IAI=n.有向图?=(V,A,c)上定义女I1下的权函数: c:A—为弧上的权函数,弧()?A对应的权C(i)记 为c,称为弧(J)的容量上界,或直接称为容量(Capacity); 依此构成的网络称为流网络,记为?:(V,A,c). (2)可行流 对于流网络?_(V,A,C),其上的一个流是指从?的弧 基金项日:陕西省教育厅专项科研计划项目(No.08JK354). 作者简介:厍向阳(1968一),男,博士后,副教授,从事数据挖掘与智能信息处理,人工 智能与模式识别,复杂系统建模与优化等方面研究. 收稿日期:2009—08—07修回日期:2009—09—27 ComputerEngineeringandApplications计算机工程与应用 集A—的函数,即每一条弧(,)?A赋予一个流量在流 网络中指定一个源结点s?V和一个汇结点tV,其余点为中 转点.如果流网络中?:(,A,c)存在从s到t的流=},且 满足: ?(1) l厂()i=s ??:{o?,,(2) "l一)i:, 则称为流网络?=(V,A,C)中从S到t的可行流,流量记为 .厂【).式(1)为弧的容量约束条件,式(2)为结点流量平衡条件. (3)最大可行流 在流网络?=(,A,c)的所有从s到t的可行流=}中, 流量)最大的可行流称为最大可行流=},菏足式(3): )-~max)(3) 以式(3)作为目标函数,以式(1),(2)为约束条件,便可构 成网络最大流模型. 2.2基本理论 (1)割集 容量网络?_(V,A,C),.,分别为源点,汇点,若有边集 AC_ A,将?分为两个子图?.和,其顶点集合分别为S,S, SuS=V,Sn.s=,?S,",?S,满足:??=(V,A-A)不连通; ?ACAA,而?=(,-A)连通.则称A为?的割集,记 A,=(5,j). (2)割集容量 割集A=(Js,S)中所有始点在S,终点在S的边的容量之和, 称为割集A=(s,S)的容量,记为c(s,S). (3)最大流一最d,g-~定理 由割集定义不难看出,在容量网络中割集是由源点到汇 点的必由之路,无论去掉哪个割集,到,便不相通. 可行流有界性定理:设.厂为络?=(,A,C)的任一可行 流,流量为,A=(S,S)是分离,的任意割集,则有W? c(s,S). 最大流一最小割定理:任一网络?=(V,A,C),从到,的 最大流的流量等于分离.,的最小割集容量. 3基于栈的网络最大流搜索算法 (1)基本思想 根据割集定义和最大流一最小割定理,以邻接矩阵为网络 数据存储结构,利用栈作为数据组织形式,采用深度搜索的方 法来遍历网络中所有可能的割集fIl】'按照网络割集的定义进行 筛选,最后找到的容量最小的割集即为网络最大流量. (2)基于栈的网络最大流搜索算法 算法:基于栈的网络最大流搜索算法. 输入:网络的流量的邻接矩阵. 输出:最小割集,网络最大流流量. 方法: 步骤1设置Js=s=,最小割集的初始割集A=(s,s),初 始容量=*. 步骤2源点进栈,栈顶位置Top=O,S=}. 步骤3判断(s,V—S)是否满足割集的条件.若满足,NS= V—S,并计算c(s,S),转向步骤4,否则,转向步骤5. 步骤4若c(s,S)<,则W=C(S,S),A=(s,So 步骤5在邻接矩阵中搜索栈顶元素的下一个未被访问过 的邻接点.当?,则进栈,栈顶位置roy=Top+l,顶点集 合S=StO},返回步骤3.当栈顶元素为时或栈顶元素.的 所有邻接点全被访问过,则退栈,栈顶位置roy=Top一1,顶点集 合S=S—v}. 步骤6当Top>0时,返回步骤3.当Top=0时,算法结束, 输出最小割集A:(s,S),网络最大流流量w=c(s,S). 4算法实例 (1)网络最大流测试实例1 某一通风网络如图1所示ll21,通风网络有13个结点,20个 分支,图1中圈起来的数字为通风网络分支最大允许风量,未 圈起来的数字为通风网络结点标号,箭头表示对应分支风流方 向.使用该算法,得到从源点s到汇点t方向的最小割集容量 163ms,,也就是从源点s到汇点t方向的通风网络的最大流 为163nl?s,,害0集为{1一一>5,4一一>13,6一一>5,6一一 >7,6-->9}. 图1中的虚线为割集对应的分支,割集{1一>5,4一>13,6--> 5,6-->7,6-->9}为进一步扩大通风网络最大流量关键分支. 图1通风网络图 (2)网络最大流测试实例2 两家工厂1和2生产一种产品,商品通过如图2所示道路 网络运送到城市7,8和91I,道路网络有12个结点,24个分 支,图2中圈起来的数字为道路网络分支最大允许运输量,未 图2运输网络图 厍向阳:基于栈的网络最大流算法2009,45(33)15 圈起来的标号为道路网络结点标号,箭头表示对应道路允许行 驶方向.增加1O和11为虚拟源点s和汇点t.使用该算法,得 到从源点10到汇点11方向的最小割集容量23,也就是从源 点10到汇点11方向的道路网络的最大运输能力为23,正割 集(与源点10到汇点11方向相同):f2一>6,3一>7,4一>9,5-> 8,5->9},负割集(与源点lO到汇点11方向相反):{6一>3,6-> 5,6->12},割集容量等于正割集中各分支最大允许运输量的 和,图2中的长虚线为正割集对应的分支,短虚线为负割集对 应的分支.正割集为进一步扩大道路网络的最大运输能力的关 键分支. 5结束语 根据割集定义和最大流一最小割定理,利用栈作为数据组 织形式,通过遍历方法得到网络最大流.网络其余分支流量由 网络结点流量平衡条件来求解.该算法具有:(1)开辟了一种求 解流量网络最大流的新的方法,克服了割集和最大流一最小割 定理仅仅具有理论价值,没有实用价值的局限性.(2)根据最小 容量的割集可以方便确定决定网络最大流大小的关键分支,为 扩展网络流量提供直接技术支持. 参考文献: [1】AhujiaRK,MagnantiTL,OrlinJB.Networkflows:Theory,algo— rithmsandapplications[M].NewJersey:RenticeHall,1993. [2】张宪超,陈国良,万颖瑜.网络最大流问题研究进展IJ】.计算机研究 与发展,2003,40(9):1281—1292. [3]FordLR,FulkersonDR.Maximumflowthroughanetwork叨.Cana— dianJournalofMath,1956,8(5):399—404. [4】DinicEA.Algorithmforsolutionofaproblemofmaximumflowin networkswithpowerestimation[J].SovietMathDokl,1970,11(8): 1277-1280. [5】AhujaRK,OrlinJB.Distance-directedaugmentingpathalgorithms forthemaximumflowproblem[J].NavalResearchLogisticsQuarterly, 1991,38(2):413—430. [6】KarzanovAV.Determiningthemaximumflowinanetworkbythe methodofpre—flows[J].SovietMathDokl,1974,15(3):434-437. [7]GoldbergAV,TarjanRE.Anewapproachtothemaximumflow problem[J].JAssocComputMach,1988,35(4):921—940. 【8]GoldbergAV,RaoS.Beyondtheflowdecompositionbarrier[J].JAs- SOCComputMach,1998.45(5):783—797. [9]DantzigGB.Applicationofthesimplexmethodtoatransportation problem[M]//ActivityAnalysisandProductionandAllocation.New York:Wiley,1951:359-373. [10]GoldforbD,HaoJ.Aprimalsimplexalgorithmthatsolvesthemaxi- mumflowprobleminatmostnmpivotsand0(n2m)time[J]. MathematicalProgramming,1990,47(3):353—365. [11]严蔚敏,吴伟民.数据结构【M】.北京:清华大学出版社,2008. [12]王惠宾.矿井通风网络理论与算法[M].徐州:中国矿业大学出版社, 1996. 【13】钱颂迪.运筹学【M】.3版.北京:清华大学出版社,2005. (上接3页) 得越严重,以往可知这是由于MTRC导致的,这点是容易 理解的,也在预料之中.从表3,表4和图3(e),图3(d),可以 看出,Keystone变换校正算法对上述情况的处理效果和R—D 算法的处理效果相当,说明了Keystone变换校正算法只是对散 射点的位置进行了校正,而对于散射点幅度问的大小相对关系 并未做出有效的处理,也就是说该算法和R—D算法一样也破 坏了散射点幅度间大小的原来相对比例,这是其不足之处. 表3五球(横向排列)仿真数据幅度对比图(rl=O.5m,r2=lm) 4 af=-3G;AS=-5.二维傅里叶算法(keystone)处理结果 表4五球(横向排列)仿真数据幅度对比图(rl=lm,r2=2m) af=3G;AS=-5.二维傅里叶算法(keystone)处理结果 R-D算法4.54.24.54.44.4 Keystone变换校正算法21.221.621.721.521.5 新算法22.622.822.722.722.7 小结 介绍了Keystone变换的原理,并从回波模型的角度分析了 Keystone变换在MTRC中的应用,利用尺度变换消除了由于径 向速度引起的MTRC,计算结果表明,基于Keystone变换的成 像算法能有效地处理MTRC现象.但还有待完善,提出的新校 正算法,考虑了两次测量间产生的回波包络移动,利用加权方 法加以处理,取得了更好的处理效果. 参考文献: BerizziF,DianiM.TargetangularmotioneffectsonISARimagindJy/ [1】 IEEProceedings:Radar,SonarandNavigation,1997,144(2):87—95. 【2]ChenCC,AndrewsHC.Target—motion—inducedradarimaging[J1. IEEETransonAES,1980,AES一16(1):2-14. 【3]LuGuang-yue,BaoDoppleralgorithmin ISARbasedoninstantfrequencyestimation[C]//ProcofInternational SymposiumonMultispectralImageProcessing(IS—MIP'98),Wuhan, China,1998:198—201. 【4]姜正林,邢孟道,保铮.ISAR成像的越距离单元走动校正叨.电子与 信息,2002,24(5):577—583. [5】WangGen-yuan,BaoZheng.Inversesyntheticapertureradarimaging ofmaneuveringtargetsbasedonchirpletdecomposition[J1.OptEng, 1999,38(9):1534—1541. [6】PerryRP,DipietroRC,FanteRL.SARimagingofmovingt一 gets叫.IEEETransonAES,1999,35(1):188—199. [7]DiPietroRC,FanteRL,PerryRP.Muhi—resolutionFOPENSAR imageformation[C]//PartoftheSPIEConferenceonAlgorithmsfor SyntheticApertureRadarImageryVI,SPIE,1999,3721:58—67. 【8]SoumekhM.Fourierarrayima~ng[M].EnglewoodCliffs,NJ:Prentice- Ha11.1994.