><b>一、引言</b></P>; Q" V3 m1 `- U% }1 c3 p
align=left>如同我们可以把一个实际的道路地图抽象成一个有向图来计算两点之间的最短路径,我们也可以将一个有向图看作一个流网络来解决另一类型的问题。流网络比较适合用来模拟液体流经管道、电流在电路网络中的运动、信息网络中信息的传递等等类似的过程。</P>3 b2 a0 B3 C3 e! W4 \) g* T
align=left><b>二、网络流和最大流问题8 M1 E. \- w' S" r2 x* V
><IMG src="http://www.frontfree.net/articles/pages/0000000554/pic01.gif"></P>
align=left>在流网络中,每条有向边可以被看导管。每根导管有一个固定的容量,代表物质流经这个导管的最大速率,例如一个管道每小时最多能流过200加仑液体或者一根电线最多能承载20安培的电流。流网络中的顶点可以看作是导管的连接处。除了源点和汇点之外,物质流进每个点的速率必须等于流出这个点的速率。如果我们把研究的物质特化为电流,这种“流的保持”属性就好像电路中的基尔霍夫电流定律一样。</P>
align=left>下面我们用数学语言来进行相关概念的定义:
>流的保持:对于所有的 u ∈ V - {s, t},要求:∑ f(u, v) = 0(v∈V)( j P# Y8 a' ]; Y8 d0 s
align=left>最大流问题就是找出给定流网络的最大流。网络流问题可以归结为一类特殊的线性规划问题。</P>
align=left><b>三、解决最大流问题常用算法一览</b></P>8 ]0 e( G6 l1 H
align=left>解决最大流问题的常用到Ford-Fulkerson方法,之所以称其方法而不是算法,是因为在这种思想下包含着若干种时间复杂度不同的实现,其中较多地是使用Edmonds-Karp算法。与此相对,Push-relabel算法采用了与Ford-Fulkerson方法完全不同的思考角度,降低了渐进意义下的时间复杂度。而relabel-to-front算法则是对Push-relabel算法的改良和精炼,效率更佳。</P>) }( K5 O9 ~7 A
align=left>关于这三种常用算法的时间复杂度可见下表:(其中V表示图的顶点数,E表示边数)</P>. U! d2 e, x4 J* Q5 x
align=left>可以看出,当给定的有向图比较稀疏时,三种算法的效率不会相差太多,但当网络稠密时,relabel-to-front算法在效率上有着明显的优势。 }$ d: L' C) ^: C) [
align=left>一般的Ford-Fulkerson方法具有迭代性质,我们把顶点u和v之间的流记作f(u,v)。那么在最开始,我们对所有的u,v∈V置f(u,v)=0。在每次的迭代过程中,通过找到一条增加路径来使|f|增加。在这里,我们可以简单地认为所谓的“增加路径”就是一条可以传送比当前更多流的从源点s到汇点t的路径,一旦找到了这样的路径,我们就可以得到一个比原流数值更大的新流。重复这个过程,直到不存在增加路径为止,这就是Ford-Fulkerson方法的主要过程,可以用伪码表示如下:</P>2 J* {& h+ d9 ~6 p; D2 o" t0 ?
align=left>FORD-FULKERSON-METHOD(G,s,t)
align=left>实现Ford-Fulkerson的时间复杂度主要取决于如何寻找增加路径p。Edmonds-Karp实现正是通过采用了广度优先的搜索策略得以使其复杂度达到O(V*E^2)。</P>/ I* h, l" f4 a
align=left>由于这种算法的效率不很理想,我们在此不多着墨,而主要介绍下述push-relabel算法的思想。</P>
align=left><b>五、一般性的push-relabel算法</b></P>
align=left>很多渐进意义下最优的算法都是采用了push-relabel算法的思想,而且很多其他的相关问题,比如最小费用流问题,也可以用这种方法很好的解决。首先介绍的是一般性的push-relabel算法。</P>8 g4 }+ E5 N% C
align=left>不同于Ford-Fulkerson方法在残留网络中寻找增加路径的方式,push-relabel算法在运行的过程中只关注某一个顶点以及它的相邻顶点,在这个过程中,它并不像Ford-Fulkerson方法保持着“流的保持”性质,而是以一个“先流”进行运作。这个先流同样是一个 V×V →R的函数,满足容量限制和斜对称性,同时,它对所有的u∈V-{s}满足f(V,u)>=0。我们记e(u)=f(V,u)。如果e(u)>0我们就说顶点u溢出。</P>% \' f0 e/ e& `/ y0 M' m
align=left>为了步入正题,我们还需要介绍push-relabel算法引入的一个额外的高度函数。设G=(V,E)是一个流网络,源点是s,汇点是t,f是G中的一个先流。如果函数h:V→N满足h(s)=|V|,h(t)=0,而且对残留网络中所有的边(u,v)有h(u)<=h(v)+1,那么称h是一个高度函数。</P>
align=left>正如其名称一样,push-relabel算法有两个基本操作:push和relabel。一般性的push-relabel算法就是通过往复执行这两种操作完成的:</P>
align=left>GENERIC-PUSH-RELABEL(G)
align=left>下面具体介绍一下这两个基本操作。</P>( u0 X' I2 y! X$ C9 @- p1 A6 d
USH(u,v)</b></TD>+ N: ?$ d/ T: F) z. f# N- Q5 N6 n
align=left>具体步骤:2 Q! j6 |8 u7 z; t- J' T
align=left><b>RELABEL(u)</b></P></TD>
align=left>动作描述:增加u的高度</P></TD></TR>& s+ `2 J; i$ Y+ ~- L
align=left>具体步骤:
u,v)是残留网络中的边}</P></TD></TR></TABLE>" X( c2 W9 k* d1 U' U
align=left>通过证明,在一般性的push-relabel算法执行过程中,relabel操作的执行次数小于2|V|^2,push操作的执行次数小于2|V||E|+4|V|^3+4|E||V|^2,而每个relabel操作的耗时在O(V)级,每个push的耗时在O(1)级,选择一个可以执行的操作也可以在O(1)内完成,因此,存在具体的实现使得一般性的push-relabel算法时间复杂度达到O(V^2*E)。</P>
align=left><b>六、relabel-to-front算法</b></P>
>谢谢</P>
>very hard</P>
的??????| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) | Powered by Discuz! X2.5 |