基于栈的网络最大流算法.doc

基于栈的网络最大流算法厍向阳1 1(西安科技大学计算机科学与技术学院，西安，710054)1()摘收稿日期：_；修回日期：_。基金项目：陕西省自然科学基金项目(2009JM7007)、陕西省教育厅专项科研计划项目(08JK354)。作者简介：厍向阳(1968-)，男，汉族，陕西周至人，博士后，副教授，从事数据挖掘与智能信息处理、人工智能与模式识别、复杂系统建模与优化等方面研究。要: 针对网络最大流问题，在割集定义和最大流-最小割定理基础上，以邻接矩阵为网络数据存储结构，利用栈作为数据组织形式，遍历网络中所有割集，最小容量的割集既为网络最大流。流量网络其余分支流量由网络结点流量平衡条件来求解。该算法具有：开辟了一种求解流量网络最大流的新的方法，克服了割集和最大流-最小割定理仅仅具有理论价值、没有实用价值的局限性。根据最小容量的割集可以方便确定决定网络最大流的关键分支，为扩展网络流量提供直接技术支持。算法测试表明：基于栈的网络最大流算法是完全可行和有效的。关 键 词:网络最大流；割集；栈；最小容量割集中图分类号:TP393.3 文献标识码1.引言网络最大流问题和它的对偶最小割问题是一对经典组合优化问题，在许多工程领域和科学领域有重要的应用，是计算机科学和运筹学重要的内容12。最大流问题已经有40多年的研究历史，目前网络最大流问题主要有两类算法：组合算法。按在剩余网络中推进流方式的不同，组合算法分为:增载轨算法和预流推进算法。增载轨算法有Ford和Fulkerson的标号算法3、Dinic的阻塞流算法4和Ahuja和Orlin的最短增载轨算法5等。预流推进算法有Karzanov的阻塞流算法5、Goldberg和Tarjan的推进重标号算法7、Goldgerg和Rao的二分长度阻塞流算法8等。线性规划算法。最大流问题是一个特殊的线性规划问题，利用其特殊性，可以得到比一般线性规划算法更有效的算法，如：网络单纯形法、网络内点法910。在网络最大流问题中，割集概念和最大流-最小割定理是各种网络最大流算法理论基础，具有重要的理论意义，然而仅此而已，对具体网络最大流算法没有实用价值。本文针对网络最大流问题，根据割集定义和最大流-最小割定理，以邻接矩阵为网络数据存储结构，利用栈作为数据组织形式，遍历网络中所有割集，找到的最小容量的割集既为网络最大流。流量网络其余分支流量由网络结点流量平衡条件来求解。最后，通过实例进行了算法测试和比较。2.问题描述和预备知识2.1网络与流1.流网络在以为结点集，为弧集，且、为图G中结点和分支数，且=m、=n。有向图上定义如下的权函数： 为弧上的权函数，弧对应的权记为，称为弧的容量上界，或直接称为容量(Capacity)；依此构成的网络称为流网络，记为。2.可行流对于流网络，其上的一个流是指从的弧集的函数，即每一条弧赋予一个流量。在流网络中指定一个源结点和一个汇结点，其余点为中转点。如果流网络中存在从到的流，且满足： （1） （2）则称为流网络中从到的可行流，流量记为。式（1）为弧的容量约束条件，式（2）为结点流量平衡条件。3.最大可行流在流网络的所有从到的可行流中，流量最大的可行流称为最大可行流，亦满足下式： （3）以式（3）作为目标函数，以式（1）、（2）为约束条件，便可构成网络最大流模型。2.2基本理论111.割集容量网络，、分别为源点、汇点，若有边集，将分为两个子图和，其顶点集合分别为，满足：不连通；，而连通。则称为的割集，记。2.割集容量割集中所有始点在，终点在的边的容量之和，称为割集的容量，记为3.最大流-最小割定理由割集定义不难看出，在容量网络中割集是由源点到汇点的必由之路，无论去掉那个割集，到便不相通。可行流有界性定理：设为网络的任一可行流，流量为，是分离、的任意割集，则有。最大流-最小割定理：任一网络，从到的最大流的流量等于分离、的最小割集容量。3.基于栈的网络最大流搜索算法1.基本思想根据割集定义和最大流-最小割定理，以邻接矩阵为网络数据存储结构，利用栈作为数据组织形式，采用深度搜索的方法来遍历网络中所有可能的割集12，按照网络割集的定义进行筛选，最后找到的容量最小的割集既为网络最大流量。2.基于栈的网络最大流搜索算法算法：基于栈的网络最大流搜索算法。输入：网络的流量的邻接矩阵。输出：最小割集、网络最大流流量。方法：Step1.设置，最小割集的初始割集，初始容量；Step2.源点进栈，栈顶位置Top=0，；Step3.判断是否满足割集的条件。若满足，则，并计算，转向Step4，否则，转向Step5。Step4.若，则，；Step5.在邻接矩阵中搜索栈顶元素的下一个未被访问过的邻接点。当，则进栈，栈顶位置Top=Top+1，顶点集合，返回Step3。当栈顶元素为时或栈顶元素的所有邻接点全被访问过，则退栈，栈顶位置Top=Top-1，顶点集合。Step6.当Top0时，返回Step3。当Top=0时，算法结束，输出最小割集、网络最大流流量。4.算法实例1.网络最大流测试实例1某一通风网络如图1所示13，通风网络有13个结点，20个分支，图1中圈起来的数字为通风网络分支最大允许风量，未圈起来的数字为通风网络结点标号，箭头表示对应分支风流方向。使用该算法，得到从源点s到汇点t方向的最小割集容量163 m3s-1，也就是从源点s到汇点t方向的通风网络的最大流为163 m3s-1，割集为1-5,4-13,6-5,6-7,6-9。图1中的虚线为割集对应的分支，割集1-5,4-13,6-5,6-7,6-9为进一步扩大通风网络最大流量关键分支。2.网络最大流测试实例2两家工厂1和2生产一种产品，商品通过如图2所示道路网络运送到城市7、8和911，道路网络网络有12个结点，24个分支，图2中圈起来的数字为道路网络分支最大允许运输量，未圈起来的标号为道路网络结点标号，箭头表示对应道路允许行驶方向。增加10和11为虚拟源点s和汇点t。使用该算法，得到从源点10到汇点11方向的最小割集容量23，也就是从源点10到汇点11方向的道路网络的最大运输能力为23，正割集(与源点10到汇点11方向相同): 2-6,3-7,4-9,5-8,5-9，负割集(与源点10到汇点11方向相反):6-3,6-5,6-12，割集容量等于正割集中各分支最大允图1 通风网络图许运输量的和，图2中的长虚线为正割集对应的分支，短虚线为负割集对应的分支。正割集为进一图2 运输网络图步扩大道路网络的最大运输能力的关键分支。5.结束语根据割集定义和最大流-最小割定理，利用栈作为数据组织形式，通过遍历方法得到网络最大流。网络其余分支流量由网络结点流量平衡条件来求解。该算法具有：开辟了一种求解流量网络最大流的新的方法，克服了割集和最大流-最小割定理仅仅具有理论价值、没有实用价值的局限性。根据最小容量的割集可以方便确定决定网络最大流大小的关键分支，为扩展网络流量提供直接技术支持。参考文献:1 Ahujia R. K., Magnanti T.L., Orlin J.B. Network Flows: Theory, Algorithms and ApplicationsMNew Jersey: Rentice Hall,19932 张宪超，陈国良，万颖瑜网络最大流问题研究进展计算机研究与发展J，2003，40(9):1281-12923 L R Ford，D R Fulkerson. Maximum flow through a networkJ.Canadian Journal of Math，1956，8(5):399-4044 E A Dinic. Algorithm for solution of a problem of maximum flow in networks with power estimation J. Soviet Math Dokl，1970，11(8):1277-12805 R K Ahuja，J B Orlin. Distance-directed augmenting path algorithms for the maximum flow problemJ.Naval Research Logistics Quarterly，1991，38(2):413-4306 A V Karzanov. Determining the maximum flow in a network by the method of pre-flowsJSoviet Math Dokl，1974，15(3):434-4377 A V Goldberg，R E Tarjan. A new approach to the maximum flow problemJJ Assoc Comput Mach，1988，35(4):921-9408 A V Goldberg，S Rao. Beyond the flow decomposition barrier J. J Assoc Comput Mach，1998，45(5):783-7979 G B Dantzig. Application of the simplex method to a transportation problem J. In: Activity Analysis and Production and Allocation. New York: Wiley，1951,359-37310 D Goldforb，J Hao. A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and O (n2m) time. Mathematical Programming，1990，47(3):353-36511 钱颂迪等运筹学（第三版）M北京：清华大学出版社，200512 严蔚敏，吴伟民数据结构M北京：清华大学出版社，200813 王惠宾矿井通风网络理论与算法M徐州：中国矿业大学出版社，1996The new max-flow algorithm in network based on stackShexiangyang1 1(computer science and technology college,Xi an University of Science and Technology; Xian 710054; China)1()Abstract: Facing the question of max-flow in network, based on cut set define and max-flow min-cut theorem,with adjacency matrix to deposit network data, using the data structure of stack to organise network data, traversing all cut sets,the minimum capacity in all cut sets is max-flow in network.The other branchs, besides the branchs of the minimum cut set,are calculated by solving the node flow balance equation in network. The algorithm pioneers a new way to solve the question of max-flow in network,and breaks the localization of cut set define and max-flow min-cut theorem that has only theory value,do not solve practic max-flow in network.The key branchs in network that decide max-flow in network are make certain easily by the way of the minimum cut set,the direcet technology support for enlarging max-flow in network is provided by the algorithm.Algorithm testing show: The new max-flow algorithm in network based on stack is completely feasible and availability.Key words: max-f