最大流问题(数学建模资料).ppt

1,网 络 优 化,Network Optimizationhttp:/,清华大学数学科学系 谢金星办公室：理科楼1308#（电话：62787812）Email:http:/,清华大学课号：40420213（本），70420133（研）,第6章 最大流问题(Maximum Flow Problem)第1讲,2,许多实际问题都可以转化为最大流问题,S,T,最大流问题的例子,公路交通网络：车流流量,3,定义6.1 在有向图G=(V，A)上定义如下的权函数：（1）L：AR为弧上的权函数，弧(i,j)对应的权 L(i,j)记为lij，称为弧(i,j)的容量下界（lower bound）;（2）U：A R为弧上的权函数，弧(i,j)对应的权U(i,j)记为uij，称为弧(i,j)的容量上界，或直接称为容量（capacity）;（3）D：V R为顶点上的权函数，节点i对应的权D(i)记为di，称为顶点i的供需量（supply/demand）;此时网络可称为流网络(Flow Network,一般仍简称为网络),记为 N=(V,A,L,U,D).,6.1.1网络中的流,di 0:供应点(supply node)或源(source)、起始点或发货点 di 0:需求点(demand node)或汇(sink)、终止点或吸收点 di 0:转运点(transshipment node)或平衡点、中间点,4,定义6.2 对于流网络N=（V，A，L，U，D），其上的一个流(flow)x是指从N的弧集A到实数集合R的一个函数x：A R,即对每条弧(i,j)赋予一个实数(称为弧(i,j)上的流).如果流x满足,存在可行流的必要条件,则称x为可行流(feasible flow).至少存在一个可行流的流网络称为可行网络(feasible network).如果流x只满足容量约束(6.2),但不一定满足流量守恒条件(6.1),则称x为伪流(pseudoflow)，或容量可行流.,流量守恒/平衡条件,容量约束/可行条件,网络中的流,一般可以把L 0的流网络转化为L=0的流网络进行研究(思考？)除非特别说明,以后我们总是假设L=0,网络简记为N=(V,A,U,D).,5,运输网络的特点是只有源或汇，没有中间转运点.显然，此问题有解的一个必要条件是,网络中的流,例-运输网络和运输计划,有一批货物从货源地运往目的地，假设货源集合为S，目的地集合为T.货源i可提供的货物数量为ai个单位，目的地j对货物的需求量为bj个单位.以（S，T）为节点集作完全二部图，以 ai，-bj 为节点上的供需量。通过每条弧的运输量没有限制（非负即可）。一个运输计划就相当于该网络中的一个流。,6,网络中的流,例6.1 有向网络中，令所有弧上的容量下界为0，容量（上界）为1，并令节点s的供需量为1，节点t的供需量为-1。从s到t的一条有向路正好对应于网络中的一个可行流x（当xij=1时，表示弧(i，j)位于s-t路上，当xij=0时，表示弧(i，j)不在s-t路上）.,思考：网络中的任意一个可行流是否一定对应于一条有向路？,7,网络中的流,定义6.3 在流网络N=(V,A,U,D)中，对于流x,如果某条弧(i,j)上的流量等于其容量（），则称该弧为饱和弧（saturated arc）；如果某条弧（i，j）上的流量为0（），则称该弧为空弧（void arc）.,如果所有弧均为空弧，即则称x为零流，否则为非零流.,8,网络中的流,定义6.4对于给定流网络N=(V,A,U,D)中的流 x：A R，如果N中存在一条有向路P，使得，则称x为路流（Path flow），v称为该路流的流值（流量）.v=0时，称该路流为零路流，否则称为非零路流.,如果N中存在一个有向圈W，使得，则称x为圈流（Cycle flow），v 称为该圈流的流值（流量）.v=0时，称该圈流为零圈流，否则称为非零圈流.,5,9,定理6.1 在网络N=(V,A,U,D)中，任何一个可行流可以表示为若干个路流和若干个圈流之和，且这些路流和圈流满足下列性质：（1）非零路流对应的有向路从一个源点指向一个汇点；（2）至多有m+n个路流和圈流为非零流，且其中至多有m个圈流为非零流.,流的分解定理（Flow Decomposition Theorem）,证明(构造性)记可行流为x，设i0是网络中的一个源点，则存在弧(i0,i1)使得 0.,在一个无源无汇的流网络中，一个可行流称为可行循环流。,推论 一个可行循环流一定可以表示为至多m个非零圈流之和.,如果i1是一个汇点,则找到了从源点指向汇点的一条有向路.否则从i1出发重复上述过程,直到找到一个汇点或再次遇到前面经过的某个顶点时为止,即直到下列两种情况之一出现为止:,10,当找到一个路流时,重新定义使得某个节点的供需量从非零成为零,或者使得某条弧的流量从非零成为零.当找到一个圈流时,重新定义使得某条弧的流量从非零成为零.,对新网络,重复上述过程,直到所有顶点变成为转运点(平衡点).,然后,找到一个至少有一条出弧上的流量为正的顶点,继续重复上述过程,这时只有情形(b)会出现,即一定获得一个非零圈流.重复上述过程,直到重新定义的流x成为零流为止.,(b)找到一个有向圈W.此时,定义,(a)找到一条从一个源点i0指向一个汇点ik的有向路P.定义,上述过程找到路流和圈流的次数之和不会多于m+n次，且其中找到圈流的次数不会多于m次.,11,单源单汇的网络，可行流x的流量（或流值）为v=v（x）=ds=-dt如果我们并不给定ds 和dt,则网络一般记为N=（s,t,V,A,U），容量可行且转运点流量守恒的流称为s-t可行流，有时为了方便也称为可行流.最大流问题(Maximum Flow Problem)就是在N=（s,t,V,A,U）中找到流值最大的s-t可行流(即最大流).,6.1.2 最大流问题的数学描述,定理6.2(整流定理)最大流问题所对应的约束矩阵是全么模矩阵.若所有弧容量均为正整数,则问题存在最优整数解.,12,引理6.1 任意一个s-t可行流流值不超过任意一个s-t割容量.,6.1.3 增广路定理,定义6.5 设S，T是网络N=(s,t,V,A,U)中给定的一个割，且sS，t T，则称割S，T为s-t割.s-t割S，T中的弧(i，j)(iS，jT)称为割的前向弧，弧(i,j)(jS，iT)称为割的反向弧.s-t割S，T的容量定义为前向弧的容量之和，记为一个网络中容量最小的s-t割称为最小割.,13,增广路,引理6.2 如果对于一个可行流存在增广路，则该可行流不是最大流.,定义6.6 设x是流网络N=(s,t,V,A,U)中给定的可行流，P是一条s-t路，则P中满足下列两个条件之一的弧（i，j）称为增广弧(augmenting arc)：（1）弧（i，j）是P的前向弧且为不饱和弧；或（2）弧（i，j）是P的反向弧且为非空弧.如果P中的弧都是增广弧，则称P为关于流x的增广路,简称增广路(augmenting path).,这一过程称为x 关于P的增广(augmentation),14,证明 必要性可以由前面的引理直接得到.下面证明充分性.,定理6.3(增广路定理)一个可行流为最大流的充要条件是不存在增广路.,增广路定理,假设流网络N=(s,t,V,A,U)中不存在关于可行流x的增广路,记网络中从s出发沿增广弧可以到达的节点集合为S,令T=VS,则sS，tT，即S,T为s-t割.并且,对于A中的任意弧(i,j),如果它是该s-t割的前向弧,则;如果它是该s-t割的后向弧,则=0.,引理6.1证明中的中间结果,因此,S,T为最小割,x为最大流.,定理6.4(最大流最小割定理)最大流的流值等于最小割的容量.,15,6.2 增广路算法,6.2.1 Ford-Fulkerson标号算法（）,基本思想：从任何一个可行流开始,沿增广路对流进行增广,直到网络中不存在增广路为止.问题的关键在于如何有效地找到增广路,并保证算法在有限次增广后一定终止.,基本思想：标号过程来寻找网络中的增广路pred（j）：节点j 在可能的增广路中的前一个节点;maxf（j）:沿该可能的增广路到该节点为止可以增广的最大流量.LIST:记录可能的增广路上的节点,16,STEP5.转STEP3.,STEP3.如果LIST 且maxf（t）=0,继续下一步;否则:(3a)如果 t 已经有标号(即maxf(t)0)，则找到了一条增广路，沿该增广路对流 x 进行增广(增广的流量为maxf（t）,增广路可以根据pred回溯方便地得到),转STEP1.(3b)如果 t 没有标号(即LIST=且maxf(t)=0),转STEP1.,STEP4.从LIST中移走一个节点i；寻找从节点i出发的所有可能的增广弧：(4a)对非饱和前向弧（i，j），若节点 j 没有标号(即pred（j）=0)，则对j进行标号，即令maxf(j)=minmaxf(i),uij-xij，pred(j)=i,并将j加入LIST中.(4b)对非空反向弧（j，i），若节点 j 没有标号(即pred(j)=0)，则对j进行标号，令maxf(j)=minmaxf(i),xji，pred(j)=i,并将j加入LIST中.,STEP1.若maxf（t）0,继续下一步;否则结束.,STEP0.置初始可行流 x（如零流）;对节点 t 标号,即令maxf（t）=任意正值（如1）.,STEP2.取消所有节点 jV 的标号，即令maxf（j）=0,pred（j）=0；令LIST=s;对节点 s 标号，即令maxf（s）=充分大的正值.,17,最大流流值为4,Ford-Fulkerson标号算法,例：（uij，xij）,18,最大流流值为2*106,Ford-Fulkerson标号算法,例：（uij，xij）,19,该算法是否一定在有限步内终止呢？如果弧上的容量可以是无理数，可以举出例子说明标号算法不一定在有限步内终止；并且，这一增广路算法的极限过程得到的流的流值即使收敛，也不一定收敛到最大流,Ford-Fulkerson标号算法,标号算法终止时，网络中一定不再含有增广路.,如果所有弧上的容量都是正整数，根据整流定理，最大流v也是整数.实际上，由于割s，Vs中前向弧的条数最多为n条，因此最大流v的上界为nU（U表示网络中弧上的最大容量）.由于每次增广至少使得流值增加1个单位，因此增广的次数不会超过v次，算法一定在有限步内终止.此外，由于每次增广最多需要对所有弧检查一遍，因此算法的复杂度为O（mv），或表示为O（mnU）.伪多项式时间算法，而不是多项式时间算法.,20,定义6.7 对网络N=(s,t,V,A,U)中给定的s-t可行流x，网络N关于流x的残量网络N(x)=(s,t,V,A(x),U(x),其中A(x),U(x)定义如下：（residual network，又常称为增量网络或辅助网络）,6.2.2 残量网络,讨论算法复杂度时，假定:弧（i，j）A时，弧（j，i）A；并假定在残量网络中A（x）=A，也就是说弧的条数和弧集合都不变.这只要允许容量为0的弧仍然保留在网络中就可以了.,命题：若v*是原网络的最大流，则残量网络N(x)中最大流为 v*-v（x）.,其中称,uij(x)为弧(i,j)上的残留容量(residual capacity).,21,残量网络,例：（uij，xij）,N(x)中的s-t有向路P,对应于原网络N中的一条增广路；直接称残量网络中的s-t有向路为增广路.沿P可以增广的最大流量称为P的残留容量.,22,Ford-Fulkerson标号算法每次只是在所有增广路中随便地找一条进行增广,因此增广的次数可能很多.,一个自然的想法是:如果每次都找一条增广容量最大的增广路,则总的增广次数应当减少.这样的算法称为最大容量增广路算法.,6.2.3 最大容量增广路算法,23,最大容量增广路算法 复杂性分析,证明：根据流的分解定理，N(x)中可以找到不超过m条从源点到汇点的有向路（增广路），使得其残留容量之和为v*-v（x）.,现在考虑从可行流x开始的连续2m次最大容量增广：(1)如果每次增广的流量都不小于(v*-v(x)/2m，则2m次增广后一定已经达到了最大流；(2)某次增广的流量小于(v*-v(x)/2m,即每经过连续2m次最大容量增广，残量网络中的最大容量增广路的残留容量至少下降一半.,命题：N(x)中最大容量增广路的残留容量不小于(v*-v(x)/m.,可见，最大容量增广路算法将总的增广次数从Ford-Fulkerson标号算法的O（nU）降为了O（mlogU）次，因此是一种多项式时间算法.由于最大容量增广路算法每次需要在残量网络中寻找最大容量增广路（可以用最短路算法），因此每次增广的时间花费增加了.,由于任何增广路的残留容量不会超过U（U表示网络中弧上的最大容量）且至少为1（这里假设只考虑整数容量网络），因此最多经过O（2mlogU）=O（mlogU）次最大容量增广，一定已经达到了最大流.,24,(Capacity-Scaling Algorithm),6.2.4 容量变尺度算法,STEP3.若N(x,)不存在s-t 路,继续下一步;否则从N(x,)找到一条s-t 路P,沿P对当前流进行增广,并重复STEP3.,STEP1.若 1,结束,已经得到最优解;否则进行下一步.,STEP2.构造-残量网络 N(x，).,STEP0.置初始可行流 x（如零流）;=.,STEP4.=/2；转STEP1.,定义：对N=(s,t,V,A,U)中给定的s-t可行流x，网络N关于流x的-残量网络N(x，)是其残量网络N(x)的子网络，它由残留容量不小于的弧组成.整数容量网络，N(x，1)=N(x).,容量变尺度算法每次都找一条增广容量“充分大”的增广路,但不一定最大.,25,容量变尺度算法 复杂性分析,的值总共有O（logU）种取法.我们下面说明在给定的下，最多执行2m次增广：由于在2-残量网络中已经没有增广路，因此在-残量网络中的最大流不会超过2m.因为-残量网络中的增广路的容量至少为，因此增广次数不会超过2m.,算法总的增广次数是O（m logU）次，而每次增广路的查找可以采用前面介绍的标号算法，即复杂度为O（m）.因此，算法总复杂度为O（m2 logU）.仍不是强多项式时间算法,26,布 置 作 业（第1讲）,目的,掌握流网络的基本概念和基本性质；掌握几种典型的增广路算法及复杂性分析,内容,网络优化第184-189页3;4；5；（第1讲）,思考,1（1）-（7）；20（不交）,27,网 络 优 化,Network Optimizationhttp:/,清华大学数学科学系 谢金星办公室：理科楼1308#（电话：62787812）Email:http:/,清华大学课号：40420213（本），70420133（研）,第6章 最大流问题(Maximum Flow Problem)第2讲,28,-概论,Ford-Fulkerson标号算法每次只是在所有增广路中随便地找一条进行增广,最大容量增广路算法每次都找一条增广容量最大的增广路进行增广,与最大容量增广路算法对称，一个自然的想法是:如果每次都找一条包含弧数最少的增广路（称为最短增广路）,则算法效果如何？这样的算法称为最短增广路算法 本节主要结果之一：最短增广路算法最多经过O（mn）次增广后终止.,对于这时特殊的最短路问题,我们可以很容易构造最短路算法在O（m）的时间内找到一条最短增广路(例如可以采用从节点s或t开始的广度优先搜索方法)，因此这种实现方法的复杂度为O（m2n）.本节主要结果之二：在O（n）的时间内找到一条最短增广路，即算法复杂度为O（mn2）,从目前已有的理论分析和计算经验来看，最短增广路算法是所有增广路算法中效果最好的算法，可以设计出在O（logn）的平均时间内找到一条最短增广路，即算法复杂度为O（mnlogn）,6.3 最短增广路算法,29,定义6.8 对于一个残量网络N（x），如果一个函数d 将节点集合V映射到非负整数集合，则称d是关于残量网络N（x）的距离函数（distance function），d（i）称为节点 i 的距离标号（distance label）.如果距离函数d满足：（1）d（t）=0，（2）对N（x）中的任意一条弧（i，j）有d（i）d（j）+1，则称距离函数 d 关于流 x 是有效的（valid），或称距离标号（函数）d 是有效的.,如果任意一个节点的距离标号正好等于残量网络中从该节点到汇点（节点t）的所有有向路中弧数最少的有向路所包含的弧数(当令所有弧的长度为1时,这就是从该节点到汇点的最短路路长,因此我们后面直接称为最短路路长)，则称距离函数d关于流x是精确的(exact)，或称距离标号是精确的.,如果对N（x）中的某一条弧（i，j）有d（i）=d（j）+1，则称弧（i，j）为允许弧(Admissible Arc).一条s-t有向路如果完全由允许弧组成,则该有向路称为允许路(Admissible Path).,6.3.1 距离标号,精确的距离标号一定是有效的.,30,有效的,距离标号,精确的,对于一个残量网络N（x），如何确定其精确的距离标号呢？从汇点（节点t）开始，对N（x）沿反向弧进行广度优先搜索这一过程的复杂度为O（m）.,可以看出，一个节点的精确的距离标号实际上表示的是从该节点到汇点（节点t）的最短路路长，也就是说对所有节点按照最短路路长进行了层次划分.,31,距离标号 性质,引理6.3 若距离函数d是有效的，则：（1）d（i）是残量网络N（x）中从节点i到节点t的最短有向路路长的下界.（2）如果d（s）n，则残量网络N（x）中从节点s到节点t没有有向路(增广路).（3）允许路是残量网络N（x）中的最短增广路.,32,STEP0.(预处理)置初始可行流x为零流;计算精确的距离函数d；令当前节点i=s.,STEP1.若d（s）n,继续下一步;否则结束,得到最优解x.,STEP2.如果存在节点i的某条出弧（i，j）为允许弧,则转STEP3;否则转STEP4.,STEP3.令pred(j)=i,再令i=j;若i=t,则找到了一条增广路,增广并修改残量网络,再令i=s.转STEP1.,STEP4.修改标号(重新标号):当（i，j）A(x)|uij(x)0 时令d(i)=mind(j)+1|(i，j)A(x)且uij(x)0,否则令d（i）=n;且当i s时再令i=pred(i).转STEP1.,“前进步”,“回退步”,6.3.2 最短增广路算法,33,6.3.2 最短增广路算法 性质,引理6.4 在最短增广路算法中,距离标号始终保持是有效的.,归纳法：在预处理阶段，构造的距离标号是有效的.只需证明一次增广操作和一次重新标号操作不改变距离标号的有效性.,增广操作可能引起残量网络的弧的变化只有两种情况：允许路上的弧(i，j)可能退出残量网络:这不会影响(i，j)弧的端点上的距离标号的有效性；(j，i)弧可能进入残量网络:由于(i，j)弧是允许弧，因此d(i)=d(j)+1，所以d(j)=d(i)-1 d(i),这也不会影响(j，i)弧的端点上的距离标号的有效性.,重新标号将d(i)改为d(i)=mind(j)+1|(i,j)A(x)且uij(x)0:不会破坏任意的(i，j)弧的端点上的距离标号的有效性;重新标号时节点i在残量网络中没有允许弧,即对于任意的(i，j)N(x)满足d(i)d(i),即标号严格增加.对于任意的(j，i)弧,d(j)d(i)+1 d(i)+1，仍有效,34,6.3.2 最短增广路算法 性质,推论：由于距离函数是有效的，算法结束时残量网络N（x）中从节点s到节点t没有允许路,即残量网络中不存在增广路,所以算法确实求到了最大流,例6.5 用最短增广路算法计算如下网络图6.5（a）中的最大流（s=1，t=4，弧上数字表示容量）.,35,36,最短增广路算法,首先思考：如何从一个节点出发找到从该节点出发的一条允许弧？,数据结构：即对每个节点i，算法用链表A（i）记录该节点出发的所有弧，这些弧的顺序可以任意，但一旦确定以后在算法执行过程中就不再改变.,当前弧（Current-Arc）:对每个节点i，用一个指针指向下一条将要被检索的弧，这条弧称为当前弧.算法开始时，当前弧为A（i）中的第一条弧。在查找从该节点出发的允许弧时，总是从当前弧开始判别：如果当前弧是允许弧，则返回这条弧；否则令A（i）中的下一条弧为当前弧。如此下去，直到找到一条允许弧或判别完 A（i）的最后一条弧为止。,6.3.3 复杂度分析,初始当前弧:(1,2),当前弧:(3,4),分析：即确定“前进步”、“回退步”、增广、重标号的次数及每次的复杂度,37,最短增广路算法,采用当前弧（Current-Arc）结构时：如果 A（i）中的一条弧在以前的迭代中不是允许弧，则在节点i的标号改变之前它仍然不是允许弧.Why?非允许弧(i,j)的两种情况：(1)uij(x)=0;(2)d(i)d(j)+1.,这样我们得到如下结论：,复杂度分析,引理6.5 在最短增广路算法的执行过程中,如果每个节点的重新标号操作不超过k次，则算法查找允许弧和重新标号操作的总复杂度为O（|A（i）|）=O（km）.,如果判别完 A（i）的最后一条弧仍然没有找到允许弧，则说明 A（i）中不存在允许弧；这时，算法必须执行对该节点的重新标号操作，并重置该节点的当前弧为A（i）中的第一条弧.由于对节点i的一次检查和一次重新标号操作分别需要对A（i）检索一遍，因此复杂度为O（|A（i）|）.,38,6.3.3 最短增广路算法 复杂度分析,引理6.6 如果算法对任何节点最多进行k次重新标号,则算法最多km/2次使网络中的弧饱和(即弧上的残留容量减少为0).因此,最短增广路算法最多执行km/2次增广.,首先证明在对弧(i,j)进行的两次连续的并使之饱和的增广之间,其两个端点的距离标号都至少增加了2个单位：,在前一次增广时,由于弧(i,j)是允许弧,因此距离标号 d 满足d（i）=d（j）+1.在后一次增广之前,必须有一定的流量沿弧(j,i)增广过.沿弧(j,i)增广时弧(j,i)是允许弧,因此距离标号 d 满足d（j）=d（i）+1.在后一次增广时,由于弧(i,j)是允许弧,因此距离标号 d 满足d(i)=d(j)+1.,由于距离标号是非降的,于是有d（i）=d(j)+1 d（j）+1=d（i）+2 d（i）+2,d（j）d(j)=d（i）+1 d（i）+1=d（j）+2.,如果算法对任何节点最多进行k次重新标号,则算法对任何弧最多执行k/2次使之饱和的增广.对于所有弧而言,算法最多执行km/2次使之饱和的增广.,每次增广至少使一条弧饱和，因此最短增广路算法最多执行km/2次增广.,39,6.3.3 最短增广路算法 复杂度分析,引理6.7 最短增广路算法在执行过程中,最多使每个节点的标号增加n次.因此，最短增广路算法最多执行 nm/2 次增广.,证明:每次对一个节点的重新标号操作使得该节点的标号增加至少一个单位.因此对一个节点的标号增加n次后，其标号将至少为n;此时它不会再出现在任何增广路中，因此算法不再选择它探索允许路.所以，最短增广路算法在执行过程中,最多使每个节点的标号增加n次.因此，最短增广路算法最多执行 nm/2 次增广.,推论 算法对所有节点的重新标号操作不超过n2.由于每次回退操作对一个节点重新标号，因此算法执行回退的次数为O（n2）.,40,6.3.3 最短增广路算法 复杂度分析,由引理6.7，每个节点的重新标号操作不超过n次，所以算法查找允许弧和重新标号操作的总复杂度为O（nm）.由引理6.7，算法最多执行 nm/2 次增广，由于每次增广的复杂度为O(n)，因此增广操作花费的总时间为O（n2m）.由引理6.7，算法对所有节点的重新标号操作不超过n2.由于每次回退操作对一个节点重新标号，因此算法执行回退的次数为O（n2）.,综上所述，最短增广路算法的复杂度为O（n2m）.证毕.,定理6.5 最短增广路算法的复杂度为O（n2m）.,41,容量 全为1,无论采用何种增广路算法,都会找到10条增广路,每条路长为10,容量为1.因此,总共需要10次增广,每次增广1个单位,需要对10条弧进行操作.,容量全为10,6.4.1 一般的预流推进算法,10条增广路中的前9个节点(前8条弧)是完全一样的,能否直接将前8条弧的流量增广10个单位,而只对后面长为2的不同的有向路单独操作呢?这就是预流推进算法(preflow push algorithm)的思想.也就是说,预流推进算法关注于对每一条弧的操作和处理,而不必一次一定处理一条增广路.,增广路算法的固有缺陷：每一次增广复杂度为O（n）,42,定义6.9 流网络N=（s，t,V，A，U）上的一个预流 x 是指从N 的弧集A到实数集合R的一个函数,使得对每个顶点 i 都满足如下条件:,对预流 x，如果存在活跃节点,则说明该预流是不可行的.,预流推进算法的基本思想：选择活跃节点,并把一定的流量推进到它的邻居如果当前活跃点有多个邻居,那么首先推进到哪个邻居呢?由于算法最后的目的是尽可能将流推进到汇(节点t),因此算法总是首先寻求把流量推进到它的邻居中距离节点t最近的节点.距离标号表示节点与t的距离，因此算法总是将流量沿着允许弧推进.如果当前活跃点出发没有允许弧，则增加该节点的距离标号，使得从当前活跃点出发至少含有一条允许弧.,6.4.1 一般的预流推进算法,其中,称为 x 在 i 上的赢余(excess).e(i)0的节点i()称为活跃的(Active).,43,STEP1.如果残量网络中不存在活跃节点,结束,已经得到最优解;否则继续.,6.4.1 一般的预流推进算法,正确性：算法的每次迭代是一次推进操作(STEP2的前面部分)或者一次重新标号操作(STEP2的后面部分).如果推进的流量等于弧上的残留容量,则称为饱和推进(saturating push),否则称为非饱和推进(nonsaturating push).算法预处理阶段已经令距离标号d（s）=n,网络中永远不会有增广路存在.当算法终止时,网络中不含有活跃节点,此时得到的预流实际上已经是一个可行流.因此是最大流。,STEP0.(预处理)置初始可行流x为零流;对节点s的每条出弧（s，j）令;对任意的 iV 计算精确的距离标号d（i）；令d（s）=n.,STEP2.在网络中选取活跃节点i；如果存在节点i的某条出弧(i,j)为允许弧，则将 个单位的流从节点i推进到节点j；否则令d（i）=mind(j)+1|(i,j)A(x)且 0.转STEP1.,44,6.4.1 一般的预流推进算法,例6.8 用预流推进算法计算如下图6.8网络（a）中的最大流（弧上数字表示容量）.s=1,t=4,45,6.4.1 一般的预流推进算法,46,6.4.1 一般的预流推进算法,47,一般的预流推进算法,引理6.8 在预流推进算法中,距离标号始终保持是有效的.,归纳法 在预处理阶段，构造的距离标号是有效的.只需证明：算法的一次推进和一次重新标号不会改变距离标号的有效性.,一次沿允许弧（i，j）的推进操作可能引起残量网络弧的变化只有两种情况：（i，j）弧可能退出残量网络（饱和推进），不影响距离标号的有效性；（j，i）弧可能进入残量网络，由于(i，j)弧是允许弧，因此 d(i)=d(j)+1，所以d（j）=d（i）-1 d（i）,不会影响距离标号的有效性.,设一次重新标号操作将d(i)修改为d(i)=mind(j)+1|(i,j)A(x)且uij(x)0.显然,这不会破坏任意的(i，j)弧的端点上的距离标号的有效性.由于重新标号时节点i在残量网络中没有允许弧,也就是说对于任意的(i，j)弧满足d(i)d(i),即标号严格增加.对于任意的(j,i)弧,d(j)d(i)+1 d(i)+1,因此也不会破坏任何(j,i)弧的端点上的距离标号的有效性.,分析：首先证明一些基本的结论（引理）,6.4.2 复杂度分析,48,一般的预流推进算法,引理6.9 在预流推进算法的执行过程中,在残量网络上,从任何一个活跃节点到源点s都存在一条有向路.,证明 对于任何一个预流 x 有e(i)0,e(s)0(i s).根据流的分解定理,x在原网络N中一定可以分解为一系列路流和圈流之和,并且这些路流总是从s到t或一个活跃节点.,由于任何圈流以及从s到t的路流不会使得任何节点i(i s,t)产生赢余,因此对于活跃节点i,x在原网络N中分解的路流一定有一个是从 s 到活跃节点i.,于是,在残量网络中,一定有一条从i到节点s的有向路.,6.4.2 复杂度分析,引理6.10 在预流推进算法的执行过程中,d(i)2n.因此,修改距离标号的总次数不超过2n2.,证明 当算法最后一次对节点i进行重新标号时,前面的引理表明一定有一条从i到节点s的有向路.由于该有向路最多包含n-1条弧,并且d(s)=n,因此d(i)d(s)+n-12n.,49,一般的预流推进算法,为了分析算法的计算复杂性，必须确定算法的一些具体实现细节,在算法的每次迭代中，我们要找到一个活跃节点，然后找到从该节点出发的一条允许弧（或证明从该节点出发不存在允许弧）.找到一个活跃节点比较容易，我们只要在算法中使用一个链表LIST记录所有活跃节点，每次从中取出一个即可，因此每次迭代找到一个活跃节点的复杂度为O（1）.为了找到从一个活跃节点出发的一条允许弧（或证明从该节点出发不存在允许弧），与上一节一样，可以采用当前弧（Current-Arc）数据结构.这样我们仍然得到如下结论：,6.4.2 复杂度分析,引理6.11 在预流推进算法的执行过程中,如果每个节点的重新标号操作不超过k次，则算法查找允许弧和重新标号操作的总复杂度为O（|A（i）|）=O（km）.,50,一般的预流推进算法,引理6.12 如果算法对任何节点最多进行k次重新标号,则算法最多执行km/2次饱和推进.预流推进算法最多执行nm次饱和推进.,证明 首先证明在对弧(i,j)进行的两次连续的饱和推进之间,其两个端点的距离标号都至少增加了2个单位.前一次推进时,弧(i,j)是允许弧:d（i）=d（j）+1.后一次推进之前,必须有一定的流量沿弧(j,i)推进过.沿弧(j,i)推进时弧(j,i)是允许弧,距离标号d:d（j）=d（i）+1.后一次推进时,弧(i,j)是允许弧,距离标号d:d(i)=d(j)+1.由于距离标号是非降的,于是有d（i）=d（j）+1 d（j）+1=d（i）+2 d（i）+2,d（j）d（j）=d（i）+1 d（i）+1=d（j）+2.,6.4.2 复杂度分析,如果算法对任何节点最多进行k次重新标号,则算法对任何弧最多执行k/2次饱和推进.对所有弧,算法最多执行km/2次饱和推进.,51,一般的预流推进算法,引理6.13 预流推进算法最多执行O(n2m)次非饱和推进.,算法没有找到允许弧,进行一次重新标号.也就是说，节点 i 的标号增加1个单位，由此引起的的增加至多为个单位.因为所有的距离标号均不超过2n，因此整个算法由于重新标号操作引起的的增加至多为2n2个单位.,6.4.2 复杂度分析,算法找到允许弧(i,j),进行一次饱和推进.此时，节点j可以从非活跃节点变成为活跃节点，且节点i可能仍保持为活跃节点.因此，由此引起的的增加至多为d（j）2n个单位.因为所有的饱和推进不超过mn次，因此整个算法由于饱和推进操作引起的的增加至多为2mn2个单位.,算法找到允许弧(i,j),进行一次非饱和推进.此时j可以从非活跃节点变为活跃节点，但节点i一定转为非活跃节点.由此引起至少减少d(i)-d(j)=1个单位.,权函数法 令I是所有活跃节点的集合,=.显然,算法开始时(预处理后),2n2（因为所有的距离标号均不超过2n）；算法结束时,=0.在算法对活跃节点i操作的过程中,有三种可能:,的增加值最大不超过2n2+2n2+2mn2=O(n2m)个单位.由于永远是非负的，且算法结束时=0，因此预流推进算法最多执行O(n2m)次非饱和推进.,52,一般的预流推进算法,定理6.6 一般的预流推进算法的计算复杂度为O(n2m).,证明:根据前面的引理，所有查找允许弧和重新标号操作可以在O（nm)时间内完成.此外,算法最多进行O(n2m)次推进操作.由于每次推进操作可以在O(1)时间内完成，因此一般的预流推进算法的计算复杂度为O(n2m).证毕.,6.4.2 复杂度分析,53,布 置 作 业,目的,掌握最大流问题的最短增广路算法及复杂性分析；掌握最大流问题的一般预流推进算法及复杂性分析；,内容,网络优化第184-189页16；17；18（第2讲）,思考,1（8）-（10）；10；（不交）,54,网 络 优 化,Network Optimizationhttp:/,清华大学数学科学系 谢金星办公室：理科楼1308#（电话：62787812）Email:http:/,清华大学课号：40420213（本），70420133（研）,第6章 最大流问题(Maximum Flow Problem)第3讲,55,-6.5.1 算法,第一个预流推进算法:Karzanov,1974,O(n3)，“分层网络”；预流推进算法最有效的实现方案：最高标号预流推进算法 Goldberg 和Tarjan于1986年提出，Cheryian和Maheshwari于1989年证明复杂度为O(),一般的预流推进算法的瓶颈：非饱和推进.直观想法：使得距离标号较小的活跃节点累积尽可能多的来自距离标号较大的活跃节点的流量，然后对累积的盈余进行推进，可能会减少非饱和推进的次数.最高标号预流推进算法的思想：从具有最大距离标号的活跃节点开始预流推进.,（Highest-Label Preflow-Push Algorithm）,6.5 最高标号预流推进算法,56,-6.5.1 算法,用链表LIST(k)记录距离标号为k的所有活跃节点（k=1，2，,2n-1）,用变量level记录当前的活跃节点中最大可能的距离标号,为找到最高标号活跃节点,扫描LIST(level),LIST(level-1),直到非空LIST（p）止:令level=p,并从LIST(p)中任选一个节点每当某个活跃节点的距离标号增加时,只需将新标号的值赋给level,并将该活跃节点放到LIST（level）中.,距离标号的增加次数不超过2n2,因此level的增加次数不超过2n2,level的减少次数最多也就不超过n+2n2.对链表进行操作以便找到最高标号节点的总复杂度为O(n2).,预流推进算法中可以要求下一次迭代尽可能选择紧上次的活跃节点,直到其赢余减少到0或必须对它进行重新标号为止.我们以后总是讨论采用这样规则的算法,并把针对同一节点的这些连续推进称为对该节点的一次检查.,6.5 最高标号预流推进算法,57,最高标号预流推进算法执行非饱和推进的总次数是关键：标号的修改次数不超过2n2次；每两次相邻的标号修改操作之间对所有节点的检查不超过n次（如算法连续对n个节点的检查而中间没有对任何节点进行距离标号修改,则赢余一定已经达到s或t点,算法求到最大流终止）；每个节点检查执行非饱和推进的次数不超过1次；,-6.5.2 复杂度分析,O(n3),能否进一步改进？-采用什么数据结构？,当前弧数据结构中，对每一个节点至多只有一条弧同时为当前弧和允许弧，我们记所有这些弧的集合为F.F最多含有（n-1）条弧，每个节点最多有一条出弧，并且不可能含有任何圈.F是一个森林，我们称它为当前森林(Current Forest).,6.5 最高标号预流推进算法,58,-6.5.2 复杂度分析,F中，记后代(直接或间接后继,包括该节点本身)的集合为D(i),D（i）中任何节点的标号不会小于节点i的标号d（i）如果节点i是活跃节点，且除节点i以外D（i）中不含有活跃节点，则称节点i是一个最大活跃节点.两个最大活跃点不可能含有同一个后代节点.最高标号预流推进总是从一