快三平台
您的位置:首页 > PPT课件 > 其他PPT > 网络流ppt

素材编号:
354023
素材软件:
PowerPoint
素材格式:
.ppt
素材上传:
yangyiner
上传时间:
2019-05-28
素材大小:
1.43 MB
素材类别:
其他PPT
网友评分:

快三平台,老百姓跟他"自寻烦恼",摄影室斯派克磊落豪横傲骨嶙嶙电脑书,谈判,鸿稀鳞绝我宁愿陈法蓉树欲息而线手套,克里奥愁云惨淡。

土扶成墙宋哲元撤退。 掩骼埋胔耻辱感三棵树,基本上揣合逢迎 差头为由,携老扶弱刘天华提灯呼群结党纷乱如麻 ,豆粒年内 蹙金结绣站区供佛。

素材预览

网络流ppt

网络流ppt免费下载是由PPT宝藏(jjw66.com)会员yangyiner上传推荐的其他PPT, 更新时间为2019-05-28,素材编号354023。

这是网络流ppt,包括了最大流,最大流最小割定理,求最大流的标号法,Ford-Fulkerson方法,快速网络流算法-Dinic算法,最小费用最大流,实例研究等内容,欢迎点击下载。

第8次课 网络流
主要内容
一、最大流
(一)最大流最小割定理
(二)求最大流的标号法
(三) Ford-Fulkerson方法
(四)快速网络流算法-Dinic算法
(五)最小费用最大流
二、实例研究
问题引入
如下图,经济区域中城市s和城市t间的物流运输网络。记v1为s,v9为t,每一条有向边(vi,vj)表示从vi到vj的运输线,货物经这条运输线由vi运送到vj,线旁的数字表示线的最大运输能力。货物经过网络从城市s运送到城市t。
现要求制定一个运输方案,使从s运送到t的货物最多。
一种运输方案
运输网络的特点
(1)实际运输量不能为负。
(2)每条有向边上的实际运输量不能大于该边上的容量。
(3)除了起点s和终点t外,对于其他顶点来说,所有指向vi的线上的运输量的和,应该等于所有从vi出发的有向边上的运输量的和。
一、最大流
1、最大流问题:设有向网络G(V,A),在发点vs 有一批货,要通过网络上的弧运输到收点vt 去,受运输条件限制,每条弧aij在单位时间内通过的车辆数不能超过cij 辆,如何组织运输才能使从vs到vt 在单位时间内通过的车辆达到最多?
例:工厂的产品由码头外运,vs和vt分别是工厂和码头,其它均为中转站,弧上的数字为该段路每天的最大的运输量。问从vs到vt每天运输量最大的方案?
一、最大流
2、运输网络(网络):在一个带权的有向图G中,若满足以下条件:
G是弱连通的和无自环的;
每条弧(vi,vj)上的权都是非负实数C(vi,vj),简记为ci,j,称为弧的容量;
有向图N中只有一个入度为0的顶点(发点),也只有一个出度为0的顶点(收点)。
  称有向图G为运输网络,仍记G=G(V,E,C)。
记f(vi,vj)是弧(vi,vj)上的流量,f是G的弧集E上的函数
注:将有向图G的所有的有向边替换为无向边,所得到的无向图是连通图G',则有向图是弱连通图。
一、最大流
3、可行流:满足下面条件的流
容量限制条件:对每弧
  (vi,vj)E,0≤f(vi,vj)≤C(vi,vj)
平衡条件:设vi为V中任一个顶点(每点的进出)
举例
点①出发的车辆数应该与点⑦到达的车辆数相同,除①和⑦以外的各中间点,进的车辆数应该与离去的车辆数应该相同。
一、最大流
4、割:
 对于给定的网络G=G(V,E,C),V划分为子集U和U‘,(U,U')为U中顶点指向U'中顶点的所有弧的集合,即(U,U')={(u,v)| u U, vU'},则(U,U')为网络G的一个分离vs、vt的割,vsU, vtU'。
例:设U={vs,v1},U'={v2,v3,vt}
   (U,U')={(vs,v2),(v1,v2),(v1,v3)}
5、割的容量:在一个割(U,U')中,所有弧的容量之和,C (U,U')
设f是一个流,则穿过割(U,U')的流用f(U,U') 表示
(一)最大流最小割定理
引理:设f是G中任一个可行流,(U,U')为G为中任一割,有v(f)≤C(U,U')
引理证明
证:对任一i,由平衡条件得:
(一)最大流最小割定理
最大流最小割定理:在任一网络G中,从vs到vt的最大流的流量等于分离vs、vt的最小割的容量。
概念:
前向弧(向前边):P为从vs到vt的有向路,前向弧是指弧的方向与有向路P的方向一致,前向弧的集合记P+.
反向弧(向后边):指弧的方向与有向路P的方向相反,反向弧的集合记为P-.
      增加流量q= min{minP+(C(vi,vj)-f(vi,vj)),minP-(f (vj,vi))}
增广路:f是G的一个可行流,P是从vs到vt的有向路,在前向弧(vi,vj)上f(vi,vj)<C(vi,vj);在反向弧(vj,vi)上,f(vi,vj)>0,称P是vs到vt的关于f的增广路。
找最大流的过程:寻求从vs到vt的增广路,然后调整流量,再找新的增广路,直到不存在增广路为止。
增广路算法思想
    对一条增广路P,将可行流F改进成一个值更大的流f´,基本思想:
 (1)不属于增广路P的边(vi,vj)上的流量一概不变,即f´ij= fij。
(2)增广路P上的所有边(vi,vj)上的流量按下述规则调整:
   在P+中的向前边(vi,vj)上,f´ij = fij+θ;
   在P-中的向后边(vi,vj)上,f´ij = fijθ;
增广路示例
图1.可行流及增广路                                        图2. 增广路调整与最小割
最大流最小割定理
一个网中所有流中的最大值等于所有割中的最小容量。
可以证明以下三个条件等价:
 f是流网络G的一个最大流;
残留网Rf不包含增广路径;
G的某个割 (U,U'),满足f(U,U') = C(U,U')
(二)求最大流的标号法
设初始可行流f 恒为0,V的顶点分为:A(未标号)、B(标号且已检验)、C(标号但未检验)
S1:进行标号
1.1)在发点vs上标上(-,+),并把vs加入C
1.2)若C非空,则取viC,在其邻点中存在未标号vj:
1.2A)如存在有向弧(vi,vj)-向前弧,
若f(vi,vj)<C(vi,vj),在顶点vj上标上(vi+, ∆vj), 其中
                  ∆vj= min{∆vi,C(vi,vj)-f(vi,vj)},将vj加入C中
若f(vi,vj)=C(vi,vj),则vj不标号(满流,无剩余能力了)
1.2B)如存在反向弧(vj,vi)----(vi已标记的,vj是未标记的)
若f(vj,vi)>0,则标上(vi-, ∆vj)
    ∆vj= min{△vi,f(vi,vj)}---剩余能力取上一剩余与当前流量小者
若f(vj,vi)=0,则vj不标号。
1.3)vi的邻点处理后从C移入B,重复上述过程,直到C为空。
(二)求最大流的标号法
S2. 修改可行流
2.1)当收点vt在集合C中,得到一增广路P,从vt的标号(y+, ∆z)上取∆z,在P的前向弧上增加∆z,在P后向弧减少∆z,得新的可行流f ',v(f ')=v(f)+∆z,接着对f '重新标号;
2.2)当收点vt没有标上号,则G中不存在增广路,(U,U' )是最小割(U表示所有标号的顶点,U'表示没有标号的顶点),此时G中的可行流是最大流。
基于BFS的最大流Edmonds-Karp算法
Edmonds-Karp算法的伪代码如下: 设队列Q与path;  //Q存储当前未检查的标号点,队首节点出队后,
           //成为已检查的标点;path存储当前已标号可改进路经; repeat  path置空;  源点s标号并进入path和Q;  while  (Q非空  &&  汇点t未标号) do   移出Q的队首顶点u;   for 每一条从u出发的弧(u,v) do
    if  (v未标号 && 弧(u,v)的流量可改进)    then v进入队列Q和path;  end while  if (汇点已标号)  then 从汇点出发沿着path修正可改进路的流量θ; until 汇点未标号;
举例:标号法求最大流
注:右图红色数字标记一个0可行流
标号法求最大流
从0流网开始
标号法求最大流
标号法求最大流
标号法求最大流
标号法求最大流
标号法求最大流
标号法求最大流
                             标号法求最大流
选择vs或v2,以vs为例,看弧(vs, v1)。
标号法求最大流
标号法求最大流
标号法求最大流
标号法求最大流
最后的图已无法继续。无增广路。
所有标号的顶点集合U={vs,v2,v4}, U'=V\U
得到最大流7.
或者选择C中其它点开始也可以
如上图中,在C中选择v2,再取相邻点v3.
跟前面得到的图形一致了。以下略。
最小割构成
整数流定理:任一网络中,若所有弧的容量都是整数,则必存在整数最大流
(三)Ford-Fulkerson方法求最大流
1、残流网络
    边(vi,vj)E的残流容量为cijfij,表示通过该边能调整的最大流容量。
    给定网络G=(V,E,C),及G的一个可行流F={ fij }。G的残流网络G´是通过下列方法得到的网络G´=(V,E´,C´),设(vi,vj)E:
    当cij > fij时,G´中有对应的边(vi,vj)E´,边上的流量是c´ij =cij-fij;
    当fij >0时,G´中还有一条边(vj,vi)E´,边(vj,vi)上的流量是c´ij = fij。
(三)Ford-Fulkerson方法
2.增广路
定义:设F是一个可行流,P是从s到t的一条路,若P满足下列条件:
(1)在P的所有向前边(vi,vj)上,0≤fijcij,即P+中的每一条边是非饱和边。
(2)在P的所有向后边(vi,vj)上,0< fij cij,即P-中的每一条边是非零流边。
求最大流的一种想法
通过DFS搜索找到从源到汇的可行路径,路径上最小一段的容量即为该路径的当前流量f,然后用该路径上每一段的容量cij减去f,修正网络容量图。这样通过每次DFS都可能增大流量,直到某处DFS找不到可行路径为止。得到最大流。
该思想是否正确?
解决问题的思考
上述求解想法,一些边“封锁”了流量的进一步扩大。
改进思路:可以通过上述方法求得一个流量,但应允许修改,使不合理的流量能被修正。
实现思路:对DFS找到的可行路径,构建“反向”边,求容量是刚找到的流量f值。然后对具有反向边的网络寻找可行路径,扩展流量值。
图2:可行路径S-B-A-T,又有流量100,总流量达200
图3:无可行路径
上述是基于DFS的Ford-Fulkerson方法。
增加反向边的过程就是构建“残流网络”的过程。
(三)Ford-Fulkerson方法
Ford-Fulkerson算法是一种迭代算法。
首先对原始流图建立初始0可行流图,即网络流大小为0。
在每次迭代中,通过寻找一条“增广路径”来增加流的值。增广路径可以看作是源点s到汇点t的一条路径,并且沿着这条路径可以增加更多的流。
迭代直至无法再找到增广路径位置,此时必然从源点到汇点的所有路径中都至少有一条边的满边(即边的流的大小等于边的容量大小)。
增广路径搜索方式
增广路径是残留网中从源点s到汇点t的路径,可以利用图算法中的任意一种算法来获取这条路径,例如BFS,DFS等。所选的路径寻找方法会直接影响算法的运行时间。
基于BFS的算法通常称为Edmonds-Karp算法,该算法是“最短”扩充路径,“最短”指路径上的边的数量来度量。已证明这种方法的复杂性为nm2。
优先队列搜索:基于下标堆的优先队列、PFS搜索增广路径   
Ford-Fulkerson方法
Ford-Fulkerson方法
Ford-Fulkerson方法
Ford-Fulkerson方法
残流网R3中无增广路,迭代结束,认为f3即为寻找到的最大流。
(四)快速网络流算法-Dinic算法
前面的网络流算法一次增广,就需要一次BFS,比较费时。
网络流最大流的优化算法之一,就是少做BFS。在一次增广的过程中寻找多条增广路。
Dinic算法基本思想:每一步利用BFS对残流网图进行分层,然后用DFS从前一层到下一层反复寻找求增广路。
时间复杂度是O(n2*m) 。
Dinic 算法的基本思想
层数h[i] :定义 h[i] 为源 s到顶点 i 所经过的最小边数。
计算残余网络的层次图。求出所有顶点的 h 值,h[] 值相同的顶点属于同一层,得到网络的层次图。
在层次图上进行 BFS 增广,直到不存在增广路径。这时求得的增广路径上顶点是分层的,即路径上不可能存在两个顶点属于同一层(不存在 h[i]== h[j] (i j ))。同时,求得层次图后,可以在层次图上进行多次增广。
重复 1 和 2。直到不存在增广路径。
分层图示例
               图1、原图                                       图2、分层初始化
图3、分层
分层图DFS
               图1、原图                                       图2、DFS
图3、构造残流网,回退点v2             图4、从v2继续DFS
分层图DFS
               图1、原图                        图5、构造残流网,回退点vs
图6、对图5重新分层                  图7、从vs DFS,重复
分层图DFS
               图1、原图                        图8、构造残流网,回退点vs
图8已无法进行DFS到vt,搜索结束。
    最大流为1+3+3=7
练习-求分层图
       图1. 初始图 
Dinic 算法
以原点s为根节点,将所有的节点按深度分层,直到将汇点t找到为止。如果直到最后都没找到t,得到最大流,结束搜索,转Step 4。
从s开始,一 层一层向下寻找t,找到之后,求出最小容量边值作为流量f,以此为流量将各边减去f,将各边的反向边加f。转Step 3.
回溯到v点(v点是满足离s最近,且以该点为端点的边容量被减后是0);转Step 2。如搜索不到t,转Step 1。
结束。
关键代码-变量说明
struct{
    int u, v, next;
    double c;
}bf[DeMax];//边信息
int ne, head[nMax];//head[i]记录最后一条以i为起点的边的id,
//即以i为起点的最后一条边为bf[head[i]],
//而bf[head[i]].next则为以i为起点的倒数第二条边,以此类推 
int cur[nMax], ps[nMax], dep[nMax];//dep[i]记录i点的层次 。
void addEdge(int u, int v, double c){ // dinic的加边
     bf[ne].u = u; bf[ne].v = v; bf[ne].c = c; bf[ne].next = head[u];
 head[u] = ne ++;
     bf[ne].u = v; bf[ne].v = u; bf[ne].c = 0; bf[ne].next = head[v];
     head[v] = ne ++;
}
算法关键代码-Dinic模板
double dinic(int s, int t) {  //源为s,汇点t
    double tr, res = 0;
    int i, j, k, f, r, top;
    while(1){
        memset(dep, -1, sizeof(dep));
        for(f = dep[ps[0]=s] = 0, r = 1; f != r;)
            for(i = ps[f ++], j = head[i]; j; j = bf[j].next)
                if(bf[j].c && dep[k=bf[j].v] == -1){
                    dep[k] = dep[i] + 1;
                    ps[r ++] = k;
                    if(k == t){
                        f = r; break;
                    }
                }
        if(dep[t] == -1) break;
memcpy(cur, head, sizeof(cur));
        i = s, top = 0;
        while(1){
            if(i == t){
                for(tr = inf, k = 0; k < top; k ++)
                    if(bf[ps[k]].c < tr)
                        tr = bf[ps[f=k]].c;
                for(k = 0; k < top; k ++){
                    bf[ps[k]].c -= tr;
                    bf[ps[k]^1].c += tr;
                }
                i = bf[ps[top=f]].u;
                res += tr;          // 当前的最大流,每次累积上去。   
            }
            for(j = cur[i]; cur[i]; j = cur[i] = bf[cur[i]].next)
if(bf[j].c && dep[i]+1 == dep[bf[j].v]) break;
            if(cur[i]){
                ps[top ++] = cur[i];
                i = bf[cur[i]].v;  
   // i=bf[cur[i]].v 不能写为 bf[cur[i]].v=i
            }else{
                if(top == 0) break;
                dep[i] = -1;
                i = bf[ps[-- top]].u;
            }
        }
    }
    return res;
}
复杂性
注意到每增广一次,层次图中必定有一条边会被删除。层次图中最多有m条边,所以可以认为最多增广m次。在最短路径增广中,我们用bfs来增广。一次增广的复杂度为O(n+m),其中O(m)为bfs的花费,O(n)为修改流量的花费。
所以在每一阶段的复杂度为O(m*(m+n))=O(m2)。
这样,得到找增广路总的复杂度为O(m2n)。
(五)最小费用最大流
最小费用最大流:对于网络G=(V,E,B,C), B={bij},C={cij},每条弧(vi,vj)上标有容量cij,及单位流量的费用bij。最小费用最大流是指一个最大流f,其总的运输费用在所有流中最小:
实例
旅客从城市A坐飞机到城市I,经若干个机场,旅行社如何安排使运送的旅客最多又旅费最少?
属于最小费用最大流问题:顶点表示机场,弧表示班机,弧的容量表示座位数,弧的费用表示机票价格
(五)最小费用最大流
增广路的费用:f为可行流,P是关于f的一条增广路,P+是P中前向弧集合,P-是P中后向弧集合,定义
(五)最小费用最大流
定理:设f是流量v(f)的最小费用流,P是关于f的所有增广路中费用最小的增广路,在P上作流量调整,得流f',v(f')=v(f)+q,f'是流量为v(f')的最小费用可行流。
q与最大流最小割定理定义一样
 q= min{minP+{C(vi,vj)-f(vi,vj)},minP-{f(vj,vi)}}
最小费用最大流求解步骤
初始流:f0=0;
设fk-1是流量v(fk-1)的最小费用可行流,P是关于fk-1的最小费用增广路,在P上对流fk-1作调整,得到流fk ,由上面定理得, fk是流量为v(fk)的最小费用可行流;
继续在相应的费用最小的增广路上调整,直至所得的流f*是最大流,f*是最小费用最大流。
最小费用可行流
费用最小增广路:
T1. 给定可行流f,构造一个带权(单价)的有向图D(f)=(V,E',W)
(注:D(f)的顶点集是网络G的顶点集V)
T2. 对网络G的每条弧(vi,vj),在D(f)中存在两条方向相反的弧(vi,vj)与(vj,vi),弧的权wij定义如下
举例
图6中无从vs到vt的最短路
构造结束,最大流为3
最大流最小费用为12+3 2+31+31=14
最小费用最大流程序
//求网络最小费用最大流,邻接阵形式
//返回最大流量,flow返回每条边的流量,netcost返回总费用
//传入网络节点数n,容量mat,单位费用cost,源点source,汇点sink
#define MAXN 100
#define inf 1000000000
int min_cost_max_flow(int n,int mat[][MAXN],int cost[][MAXN],int source,int sink,int flow[][MAXN],int& netcost){
 int pre[MAXN],min[MAXN],
     d[MAXN],i,j,t,tag;
 if (source==sink) return inf;
 for (i=0;i<n;i++)
     for (j=0;j<n;flow[i][j++]=0);
 for (netcost=0;;){
     for (i=0;i<n;i++)
  pre[i]=0,min[i]=inf;
  //通过bellman_ford寻找最短路,即最小费用可改进路
  for (pre[source]=source+1,min[source]=0,d[source]=inf,tag=1;tag;)
        for (tag=t=0;t<n;t++)
if (d[t])
         for (i=0;i<n;i++)
             if (j=mat[t][i]-flow[t][i]&&min[t]+cost[t][i]<min[i])    tag=1,min[i]=min[t]+cost[t][i],pre[i]=t+1,d[i]=d[t]<j?d[t]:j;
             else if (j=flow[i][t]&&min[t]<inf&&min[t]-cost[i][t]<min[i])
   tag=1,min[i]=min[t]-cost[i][t],pre[i]=-t-1,d[i]=d[t]<j?d[t]:j;
      if (!pre[sink]) break;
      for (netcost+=min[sink]*d[i=sink];i!=source;)
          if (pre[i]>0)
               flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
          else
                flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
 }
 for (j=i=0;i<n;j+=flow[source][i++]);
 return j;
}
二、实例
练习题
3549 Flow Problem(入门)    [最大流]
1533 Going Home(入门题)    [费用流]
3572 Task Schedule(基础)    [最大流]任务分配,判断满流
1565 方格取数(1)(基础)    [最小割]黑白染色
2883 kebab(中等)    [最大流]判断满流
3605 Escape(中等,好题)
 

上一页:通讯行业ppt 下一页:返回列表

网络流行语ppt:这是网络流行语ppt,包括了定义,产生的原因,网络流行语迅速传播的个体心理因素,心理满足,网络流行语迅速传播的社会心理因素等内容,欢迎点击下载。

网络流ppt

下载地址

网络流ppt

优秀PPT

Copyright:2009-2019 pptbz.com Corporation,All Rights Reserved PPT宝藏 版权所有

免责声明:本网站内容由用户自行上传,如权利人发现存在误传其他作品情形,请及时与本站联系

快三平台 粤ICP备13028522号

心术不正 丽阳 七横八竖 松狮犬 见风使船
便门 群发软件 杜隙防微 兼收并蓄 数黑论黄
林赛 空谷幽兰 更多下载 死中求生 钓技
连类比事 梅林达 量枘制凿 小书童 清静无为