1第53节 网络流算法22.docx
《1第53节 网络流算法22.docx》由会员分享,可在线阅读,更多相关《1第53节 网络流算法22.docx(48页珍藏版)》请在冰点文库上搜索。
1第53节网络流算法22
第三节网络流算法
一、网络流的基本概念
先来看一个实例。
现在想将一些物资从S运抵T,必须经过一些中转站。
连接中转站的是公路,每条公路都有最大运载量。
如下图:
每条弧代表一条公路,弧上的数表示该公路的最大运载量。
最多能将多少货物从S运抵T?
这是一个典型的网络流模型。
为了解答此题,我们先了解网络流的有关定义和概念。
若有向图G=(V,E)满足下列条件:
1、有且仅有一个顶点S,它的入度为零,即d-(S)=0,这个顶点S便称为源点,或称为发点。
2、有且仅有一个顶点T,它的出度为零,即d+(T)=0,这个顶点T便称为汇点,或称为收点。
3、每一条弧都有非负数,叫做该边的容量。
边(vi,vj)的容量用cij表示。
则称之为网络流图,记为G=(V,E,C)
譬如图5-1就是一个网络流图。
1.可行流
对于网络流图G,每一条弧(i,j)都给定一个非负数fij,这一组数满足下列三条件时称为这网络的可行流,用f表示它。
1、每一条弧(i,j)有fij≤cij。
2、除源点S和汇点T以外的所有的点vi,恒有:
该等式说明中间点vi的流量守恒,输入与输出量相等。
3、对于源点S和汇点T有:
这里V(f)表示该可行流f的流量。
例如对图5-1而言,它的一个可行流如下:
流量V(f)=5。
2.可改进路
给定一个可行流f={fij}。
若fij=cij,称为饱和弧;否则称为非饱和弧。
若fij=0,称为零流弧;否则称为非零流弧。
定义一条道路P,起点是S、终点是T。
把P上所有与P方向一致的弧定义为正向弧,正向弧的全体记为P+;把P上所有与P方向相悖的弧定义为反向弧,反向弧的全体记为P-。
譬如在图5-1中,P=(S,V1,V2,V3,V4,T),那么
P+={,,,}
P-={}
给定一个可行流f,P是从S到T的一条道路,如果满足:
那么就称P是f的一条可改进路。
(有些书上又称:
可增广轨)之所以称作“可改进”,是因为可改进路上弧的流量通过一定的规则修改,可以令整个流量放大。
具体方法下一节会重点介绍,此不赘述。
3.割切
要解决网络最大流问题,必须先学习割切的概念和有关知识。
G=(V,E,C)是已知的网络流图,设U是V的一个子集,W=V\U,满足S
U,T
W。
即U、W把V分成两个不相交的集合,且源点和汇点分属不同的集合。
对于弧尾在U,弧头在W的弧所构成的集合称之为割切,用(U,W)表示。
把割切(U,W)中所有弧的容量之和叫做此割切的容量,记为C(U,W),即:
例如图5-1中,令U={S,V1},则W={V2,V3,V4,T},那么
C(U,W)=+++=8+4+4+1=17
定理:
对于已知的网络流图,设任意一可行流为f,任意一割切为(U,W),必有:
V(f)≤C(U,W)。
通俗简明的讲:
“最大流小于等于最小割”。
这是“流理论”里最基础最重要的定理。
整个“流”的理论系统都是在这个定理上建立起来的,必须特别重视。
下面我们给出证明。
证明对任意一个中间点(即非S、也非T的点)vi,恒有:
(1)
当vi=S时有
(2)
从
(1)、
(2)对i∈U求和得
因为:
V=U∪W,所以
又因:
即
故有:
所以
即V(f)≤C(U,W)
命题得证。
网络流、可改进路、割切都是基础的概念,应该扎实掌握。
它们三者之间乍一看似乎风马牛不相干,其实内在联系是十分紧密的。
二、求最大流
何谓最大流?
首先它必须是一个可行流;其次,它的流量必须达到最大。
这样的流就称为最大流。
譬如对图5-1而言,它的最大流如下:
下面探讨如何求得最大流。
在定义“可改进路”概念时,提到可以通过一定规则修改“可改进路”上弧的流量,可以使得总流量放大。
下面我们就具体看一看是什么“规则”。
对可改进路P上的弧,分为两种情况讨论:
第一种情况:
∈P+,可以令fij增加一个常数delta。
必须满足fij+delta≤cij,即delta≤cij–fij。
第二种情况:
∈P-,可以令fij减少一个常数delta。
必须满足fij-delta≥0,即delta≤fij
根据以上分析可以得出delta的计算公式:
因为P+的每条弧都是非饱和弧,P-的每条弧都是非零流弧,所以delta>0。
容易证明,按照如此规则修正流量,既可以使所有中间点都满足“流量守恒”(即输入量等于输出量),又可以使得总的流量有所增加(因为delta>0)。
因此我们对于任意的可行流f,只要在f中能找到可改进路,那么必然可以将f改造成为流量更大的一个可行流。
我们要求的是最大流,现在的问题是:
倘若在f中找不到可改进路,是不是f就一定是最大流呢?
答案是肯定的。
下面我们给出证明。
定理1可行流f是最大流的充分必要条件是:
f中不存在可改进路。
证明:
首先证明必要性:
已知最大流f,求证f中不存在可改进路。
若最大流f中存在可改进路P,那么可以根据一定规则(详见上文)修改P中弧的流量。
可以将f的流量放大,这与f是最大流矛盾。
故必要性得证。
再证明充分性:
已知流f,并且f中不存在可改进路,求证f是最大流。
我们定义顶点集合U,W如下:
(a)S∈U,
(b)若x∈U,且fxy若x∈U,且fyx>0,则y∈U。
(这实际上就是可改进路的构造规则)
(c)W=V\U。
由于f中不存在可改进路,所以T∈W;又S∈U,所以U、W是一个割切(U,W)。
按照U的定义,若x∈U,y∈W,则fxy=cxy。
若x∈W,y∈U,则fxy=0。
所以,
又因v(f)≤C(U,W)
所以f是最大流。
得证。
根据充分性证明中的有关结论,我们可以得到另外一条重要定理:
最大流最小割定理:
最大流等于最小割,即maxV(f)=minC(U,W)。
至此,我们可以轻松设计出求最大流的算法:
step1.令所有弧的流量为0,从而构造一个流量为0的可行流f(称作零流)。
step2.若f中找不到可改进路则转step5;否则找到任意一条可改进路P。
step3.根据P求delta。
step4.以delta为改进量,更新可行流f。
转step2。
step5.算法结束。
此时的f即为最大流。
下面看一个实例。
求图5-4所示网络流图的最大流。
图中弧上的数字是该弧的容量。
第一步,令所有弧的流量为0。
找到一条可改进路P=(S,V1,V2,T),delta=min{4-0,2-0,4-0}=2。
找到一条可改进路P=(S,V1,T),delta=min{4-2,4-0}=2
这时又找到一条可改进路P=(S,V2,V1,T),P+={,},P-={}。
此时,
delta=min{Cs2–FS2,C1t–F1t,F12}=min{4–0,4–2,2}=2
新的流如下:
(反向弧F12被减少了2)
最后找到一条可改进路
P={S,V2,T},delta=2。
对此流再也找不到可改进路了。
所以它就是图2所示网络流图的最大流。
再回到求网络最大流的算法中来。
算法的关键步骤是step2,即:
判断是否存在可改进路,若存在又如何求。
可以考虑用广度优先搜索。
设置标志数组,记录顶点是不是被访问过;使用队列来存储已经访问过的顶点;另用一个一维数组,记录每个顶点是由哪个顶点扩展而来(即记录父亲节点)。
首先S入队列。
然后每次取队首顶点v,分析所有与v相邻的未访问顶点u:
1、存在弧(正向弧),且u未访问。
若fvu2、存在弧(反向弧),且u未访问。
若fuv>0(非零流弧),那么u入队列,给u打上“已访问”的标志,记u的父亲节点为-v。
(以示和正向弧的区别)。
扩展完成后,若T还没有被访问就必然不存在可改进路;否则就从T出发,根据记录好的每个顶点的父亲节点信息,顺藤摸瓜,找出可改进路(同时还可以计算出delta)。
这只是算法的初步勾勒,具体细节的优化余地极大,留给读者思考。
注:
有些书上是介绍的用“标号法”求可改进路。
“标号法”实质上就是广搜,只是细节的实现上略有偏差。
【程序】
{程序中以1为源点,n为汇点}
programmax_flow;
const
fin='maxflow.in';
fout='maxflow.out';
maxn=100;
type
tline=array[0..maxn]ofinteger;
tmap=array[1..maxn]oftline;{网络流图的邻接矩阵}
var
n:
integer;
limit,flow:
tmap;{上界和流量}
proceduregetinfo;{读入数据}
var
i,j,c:
integer;
begin
assign(input,fin);reset(input);
readln(n);
whilenotseekeofdobegin
readln(i,j,c);
limit[i,j]:
=c;
end;
close(input);
end;
proceduremaxflow;{最大流}
var
i,j,delta,x:
integer;
last:
tline;{可改进路中的前趋}
check:
array[0..maxn]ofboolean;{是否已经检查过}
begin
repeat
fillchar(last,sizeof(last),0);
fillchar(check,sizeof(check),false);
last[1]:
=maxint;
repeat
i:
=0;repeatinc(i)until(i>n)or(last[i]<>0)andnotcheck[i];
{找到一个已检查而未标号的点}
ifi>nthenbreak;
forj:
=1tondoiflast[j]=0then
ifflow[i,j]=ielse{正向弧}
ifflow[j,i]>0thenlast[j]:
=-i;{反向弧}
check[i]:
=true;
untillast[n]<>0;
iflast[n]=0thenbreak;
delta:
=maxint;
i:
=n;
repeat
j:
=i;i:
=abs(last[j]);
iflast[j]>0thenx:
=limit[i,j]-flow[i,j]elsex:
=flow[j,i];
ifx=x;
untili=1;{求改进量}
i:
=n;
repeat
j:
=i;i:
=abs(last[j]);
iflast[j]>0theninc(flow[i,j],delta)elsedec(flow[j,i],delta);
untili=1;{放大网络流}
untilfalse;
end;
procedureprint;{输出}
var
i,j,sum:
integer;
begin
sum:
=0;
assign(output,fout);rewrite(output);
fori:
=1tondo
forj:
=1tondoifflow[i,j]>0thenbegin
ifi=1theninc(sum,flow[i,j]);
writeln(i,'-->',j,'',flow[i,j]);
end;
writeln('maxflow=',sum);
close(output);
end;
begin
getinfo;{输入}
maxflow;{加工}
print;{输出}
end.
三、最小费用最大流
1.问题的模型
流最重要的应用是尽可能多的分流物资,这也就是我们已经研究过的最大流问题。
然而实际生活中,最大配置方案肯定不止一种,一旦有了选择的余地,费用的因素就自然参与到决策中来。
图5-8是一个最简单的例子:
弧上标的两个数字第一个是容量,第二个是费用。
这里的费用是单位流量的花费,譬如fs1=4,所需花费为3*4=12。
容易看出,此图的最大流(流量是8)为:
fs1=f1t=5,fs2=f2t=3。
所以它的费用是:
3*5+4*5+7*3+2*3=62。
一般的,设有带费用的网络流图G=(V,E,C,W),每条弧对应两个非负整数Cij、Wij,表示该弧的容量和费用。
若流f满足:
(a)流量V(f)最大。
(b)满足a的前提下,流的费用Cost(f)=
最小。
就称f是网络流图G的最小费用最大流。
2.算法设计
我们模仿求最大流的算法,找可改进路来求最小费用最大流。
设P是流f的可改进路,定义
为P的费用(为什么如此定义?
)。
如果P是关于f的可改进路中费用最小的,就称P是f的最小费用可改进路。
求最小费用最大流的基本思想是贪心法。
即:
对于流f,每次选择最小费用可改进路进行改进,直到不存在可改进路为止。
这样的得到的最大流必然是费用最小的。
算法可描述为:
step1.令f为零流。
step2.若无可改进路,转step5;否则找到最小费用可改进路,设为P。
step3.根据P求delta(改进量)。
step4.放大f。
转step2。
step5.算法结束。
此时的f即最小费用最大流。
至于算法的正确性,可以从理论上证明。
读者可自己思考或查阅有关运筹学资料。
2.最小费用可改进路的求解
求“最小费用可改进路”是求最小费用最大流算法的关键之所在,下面我们探讨求解的方法。
设带费用的网络流图G=(V,E,C,W),它的一个可行流是f。
我们构造带权有向图B=(V’,E’),其中:
1、V’=V。
2、若∈E,fij∈E’,权为Wij。
若∈E,fij>0,那么∈E’,权为-Wij。
显然,B中从S到T的每一条道路都对应关于f的一条可改进路;反之,关于f的每条可改进路也能对应B中从S到T的一条路径。
即两者存在一一映射的逻辑关系。
故若B中不存在从S到T的路径,则f必然没有可改进路;不然,B中从S到T的最短路径即为f的最小费用可改进路。
现在的问题变成:
给定带权有向图B=(V’,E’),求从S到T的一条最短路径。
考虑到图中存在权值为负数的弧,不能采用Dijkstra算法;Floyd算法的效率又不尽如人意——所以,这里采用一种折衷的算法:
迭代法。
设Short[i]表示从S到i顶点的最短路径长度;从S到顶点i的最短路径中,顶点i的前趋记为Last[i]。
那么迭代算法描述如下:
(为了便于描述,令n=|V’|,S的编号为0,T的编号为n+1)
step1.令Short[i]+∞(1≤i≤n+1),Short[0]0。
step2.遍历每一条弧。
若Short[i]+,同时Last[j]i。
倘不存在任何一条弧满足此条件则转step4。
step3.转step2.
step4.算法结束。
若Short[n+1]=+∞,则不存在从S到T的路径;否则可以根据Last记录的有关信息得到最短路径。
一次迭代算法的时间复杂度为O(kn2),其中k是一个不大于n的变量。
在费用流的求解过程中,k大部分情况下都远小于n。
【程序】
{程序中以1为源点,n为汇点}
programcost_flow;
const
fin='costflow.in';
fout='costflow.out';
maxn=100;
type
tline=array[0..maxn]ofinteger;
tmap=array[1..maxn]oftline;
var
n:
integer;
limit,cost,flow:
tmap;{上界、费用、流量}
proceduregetinfo;{读入数据}
var
i,j,c,w:
integer;
begin
assign(input,fin);reset(input);
readln(n);
whilenotseekeofdobegin
readln(i,j,c,w);
limit[i,j]:
=c;cost[i,j]:
=w;
end;
close(input);
end;
procedureprint;{输出}
var
i,j,sum,acost:
integer;
begin
assign(output,fout);rewrite(output);
sum:
=0;acost:
=0;
fori:
=1tondo
forj:
=1tondoifflow[i,j]>0thenbegin
ifi=1theninc(sum,flow[i,j]);
inc(acost,flow[i,j]*cost[i,j]);
writeln(i,'-->',j,'',flow[i,j]);
end;
writeln('maxflow=',sum);
writeln('mincost=',acost);
close(output);
end;
procedurecostflow;{求最小费用最大流}
var
i,j,x,delta:
integer;
best,last:
tline;{best:
最短路长度;last:
可改进路中的前趋顶点}
more:
boolean;
begin
repeat
fillword(best,sizeof(best)shr1,maxint);
fillchar(last,sizeof(last),0);
last[1]:
=maxint;best[1]:
=0;{赋初值}
repeat
more:
=false;
fori:
=1tondoifbest[i]<>maxintthen
forj:
=1tondobegin
if(flow[i,j]best[j]:
=best[i]+cost[i,j];
last[j]:
=i;
more:
=true;
end;
if(flow[j,i]>0)and(best[i]-cost[j,i]best[j]:
=best[i]-cost[j,i];
last[j]:
=-i;
more:
=true;
end;
end;
untilnotmore;{找最优可改进路}
ifbest[n]=maxintthenbreak;
delta:
=maxint;
i:
=n;
repeat
j:
=i;i:
=abs(last[j]);
iflast[j]>0thenx:
=limit[i,j]-flow[i,j]elsex:
=flow[j,i];
ifx=x;
untili=1;{求改进量}
i:
=n;
repeat
j:
=i;i:
=abs(last[j]);
iflast[j]>0theninc(flow[i,j],delta)elsedec(flow[j,i],delta);
untili=1;
untilfalse;{根据改进量放大流}
end;
begin
getinfo;{输入}
costflow;{计算}
print;{输出}
end.
3.思维发散与探索
1)可改进路费用:
“递增!
递增?
”
设f从零流到最大流共被改进了k次,每i次选择的可改进路的费用为pi,那么会不会有p1≤p2≤p3≤……≤pk呢?
2)迭代法:
“小心死循环!
嘿嘿……”
迭代法会出现死循环吗?
也就是说,构造的带权有向图B中会存在负回路吗?
3)费用:
“你在乎我是负数吗?
”
网络流图中的费用可以小于零吗?
4)容量:
“我管的可不仅是弧。
”
网络流图中的“容量”都是对弧而言的,但若是给每个顶点也加上一个容量限制:
即通过此顶点的流量的上限;任务仍然是求从S到T的最小费用最大流。
你能解决吗?
四、有上下界的最大流
上面讨论的网络流都只对每条弧都限定了上界(其实其下界可以看成0),现在给每条弧加上一个下界限制Aij(即必须满足Aij≤fij)。
例如图5-9:
弧上数字对第一个是上界,第二个是下界。
若是撇开下界不看,此图的最大流如图5-10(a)所示,流量是6;但若是加入了下界的限制,它的最大流量就只有5了,具体方案见图5-10(b)。
那么有上下界的网络最大流怎么求呢?
一种自然的想法是去掉下界,将其转化为只含上界的网络流图。
这种美好的愿望是可以实现的。
具体方法如下:
设原网络流图为G=(V,E,C,A),构造不含下界的网络流图G’=(V’,E’,C’):
1、V’=V∪{S’,T’}
2、对每个顶点x,令
,若h-(x)≠0,就添加一条弧,其上界为h-(x)。
3、对每个顶点x,令
,若h+(x)≠0,就添加一条弧