算法分析与设计(最大流问题)(12页).doc
-算法分析与设计(最大流问题)-第 - 12 - 页算 法 分 析 与 设 计题 目： 最 大 流 算 法 院系： 软 件 工 程 班级： 软件11-2班 姓名： 慕 永 利 学号： 23 号 目录1算法提出背景- 3 -2 问题实例及解决- 3 -3算法论述- 4 -、可行流- 4 -3.2 最大流- 5 -最大流算法- 6 -增广路径- 6 -沿增广路径增广- 7 -样例：- 8 -定理：- 13 -算法的实现：- 13 -3.3.6 优化- 16 -4算法应用- 18 -1算法提出背景 一个通信网络，在理想条件下，将网络平面化，并假设网络中各节点及其之间的任意通信链路均无流量限制，在这种情况下，就无需使用最大流最小割算法，只需要寻找一条最短路由即可。 但是在现实生活中，我们不可能拥有这样理想的网络条件，作为正常的通信网络，不管是用户，还是基站，或者是他们之间的不管是无线或者有线信道，其容量都不可能是无限的。我们的任务是：在一定的限制条件下，对一个具有广泛意义的网络求解其最大流，并进行流量分配。以及如何对网络弧进行修改以达到网络最优化最大化。随着计算机网络业务的日益繁忙，通信流量激增而致使网络发生拥塞出现瓶颈部位，甚至造成网络停滞或瘫痪，所以对大型网络拓扑结构的优化设计是网络规划的首要任务。网络的优化通常采用扩充网络最大容量和网络增强性连接来优化网络设计。要解决网络拥塞的问题，首要找出网络流通中的阻塞部分即是网络流通图的最小割集，通过扩充最小割集中饱和弧的容量来改善整个网络的流通能力。2 问题实例及解决 有一自来水管道输送系统，起点是S，目标是T，途中经过的管道都有一个最大的容量。3算法论述 3.1、可行流 每条弧 ( u, v )上 给定一个实数f(u,v),满足：有 0 <= f ( u, v ) <= c( u, v ),则f(u,v)称为弧( u, v )上的流量。如果有一组流量满足条件： 源点s ： 流出量 = 整个网络的流量 汇点t ： 流入量 =整个网络的流量 中间点：总流入量 = 总流出量 那么整个网络中的流量成为一个可行流。 区分：容量和流量3.2 最大流 在所有的可行流中， 流量最大的一个流的流量 如： 图2中可行流7也是最大流。最大流可能不只一个。最大流算法 Ford-Fulkerson （福特-福克森）算法： 步骤：（1）如果存在增广路径,就找出一条增广路径 （2）然后沿该条增广路径进行更新流量 （增加流量）3.3.1 增广路径 从 s 到 t 的一条简单路径，若边 ( u, v ) 的方向与该路径的方向一致，称 ( u, v ) 为正向边，方向不一致时称为逆向边。简单路：1à3 à 2à4à5中。（1，3）（2，4）（4，5）是正向边。（3，2）是逆向边。增广路径： 若路径上所有的边满足：所有正向边有：f ( u, v ) < c ( u, v) 所有逆向边有：f ( u, v ) > 0则称该路径为一条增广路径(可增加流量) 两条增广路径：1à3à51à3 à 2à4à5增加流量=？沿增广路径增广 1） 先设d为为正无穷(可增加流，余流量) 若( u, v ) 是正向边 d = min ( d, c ( u, v ) f (u, v ) ) 若( u, v ) 是逆向边 d = min ( d, f ( u, v ) ) 2 ） 对与该增广路径上的边 若( u, v ) 是正向边，f ( u, v ) = f ( u, v ) + d; 若( u, v ) 是逆向边，f ( u, v ) = f ( u, v ) d;增广后，总流量增加了d 样例： 开始流量为:sum=0一条增广路径: 1à2à3à5 ，d=min4,2,4 =2 ，增加流量: 2Sum=2一条增广路径: 1à2à4à5，d=min4-2,3,5 =2 ，增加流量: 2Sum=2+2=4一条增广路径: 1à à 2 à 4 à5，d=min6,2,3-2,5-2 =1 增加流量: 1，Sum=4+1=5一条增广路径: 1à à5，d=min6-1,4-2 =2 增加流量: 2Sum=5+2=7定理：可行流 f 为最大流，当且仅当不存在关于f 的增广路径证：若 f 是最大流，但图中存在关于 f 的增广路径，则可以沿该增广路径增广，得到的是一个更大的流，与f 是最大流矛盾。所以，最大流不存在增广路径。Ford-Fulkerson方法(增广流)求最大流（福特-福克森）： 步骤：（1）如果存在增广路径,就找出一条增广路径 DFS,BFS（2）然后沿该条增广路径进行更新流量增加流量）While 有增广路径 do 更新该路径的流量迭代算法算法的实现： c u, v ：容量f u, v ：流量Bi：保存找到的增广路径，记录路径上结点i的前驱结点。Sum：最大流量。假定：1是源点S；n是汇点T。1）：DFS找增广路径function findflow(k:integer):boolean; 找结点k的后继结点i var i:integer; begin if k=n then exit(true); 找到了一条增广路径 for i:=1 to n do if(bi=-1) and(ck,i-fk,i>0)or(fi,k>0) then begin bi:=k; if findflow(i) then exit(true); end; exit(false); end;2） procedure addflow;/沿增广路径增广（增加流量） d:=maxint; 增量 i:=n; 沿增广路径的终点向起点反向求d while bi<>0 do begin if cbi,i>0 then d:=min(d,cbi,i-fbi,i); 正向边 if ci,bi>0 then d:=min(d,fi,bi); 逆向边 i:=bi; end; i:=n; while bi<>0 do 逆向更新每条边的流量 begin if cbi,i>0 then inc(fbi,i,d); 正向边 if ci,bi>0 then dec(fi,bi,d); 逆向边 i:=bi; end; inc(sum,d); 总流量增加d主程序： for i:=1 to n do bi:= -1; 初始化增广路径 b1:=0; while findflow(1) do 增广流 begin addflow; for i:=1 to n do bi:=-1; b1:=0; end; writeln(sum); 输出最大流 for i:=1 to n do 输出每条边的流量 for j:=1 to n do if fi,j>0 then writeln(i,'->',j,' ',fi,j); 3.3.6 优化残留网络 d 的设置： 若存在 ( u, v ) 则 d ( u, v ) = c ( u, v ) f ( u, v ) d ( v, u ) = f ( u, v ) d ( u, v ) 是 从 u 到 v 能增加的最大流量理解: (u,v) 的流量为f(u,v),作为正向边还可以增加的量是c ( u, v ) f ( u, v )，作为逆向边，还可以增加的流量为： f ( u, v )。增广路上正向边流量增加，逆向边增加流量减少。 d ( u, v ) = c ( u, v ) d ( v, u ) = 0深搜找增广路径过程function find( k:integer ):boolean; if k=n then exit(true); for i:=1 to n do if (bi= -1) and (dk,i>0) then bi:=k; if find(i) then exit(true); / 此处bi不需要变回-1 exit(false);/ b1=0; b2 n= -1; 主函数中调用find(1)广搜找增广路径过程function bfsbfs:boolean; a 是广搜队列 for i:=1 to n do bi:=-1; b 是前驱 b1:=0; a1:=1; open:=0; closed:=1; while open<closed do inc(open); k:=aopen; for i:=1 to n do d 是残余流量 if (bi= -1) and (dk,i>0) then inc(closed); aclosed:=i; bi:=k; if i=n then exit(true); 找到增广路 exit(false); 没找到增广路 增广过程 min:=maxint; i:=n; while bi<>0 (i<>1) do /逆向求增加流min if min>dbi,i then min:=dbi,i; i:=bi; i:=n; while bi<>0 (i<>1) do/ /逆向修改流量 dec(dbi,i,min); inc(di,bi,min); i:=bi; inc(sum,min); sum是总流量4算法应用在现实生活中，在实际的网络中，网络的结点和边都是有容量限制的. 很多情况下我们需要知道在一个有容量限制的网络中两个指定结点（分别称为源点和汇点）之间最多能传输多少流量，并确定达到这个最大流量的传输策略. 网络最大流问题（简称最大流问题）就是描述这个问题的数学模型.最大流问题是网络流理论的重要组成部分，它是一个经典的组合优化问题，同时也可以看做是特殊的线性规划问题. 除了解决实际网络中的问题以外，最大流问题在电力、交通、通信、计算机网络等工程领域和物理、化学等科学领域有着广泛的应用，许多其它的组合优化问题也可以通过最大流问题求解。限制条件下网络最大流问题在包含流量的系统中有着广泛的应用，例如在公路系统中的车流、控制系统中的信息流等等。如何在现有条件下使网络流量能达到最大流量，并如何进行流量分配是一个具有现实意义的问题。随着生产和科学技术的发展，网络最小费用最大流算法面临新的问题和挑战。例如在VLSI、光网路由等领域，往往涉及到一些节点和边都有容量的有向平面网络。
