文档章节

最大流问题

fengsehng
 fengsehng
发布于 2016/11/09 09:11
字数 1117
阅读 7
收藏 0

举例描述

最大流问题是一个很经典的问题,很多人对此也很熟悉,它能够等同于一个线性规划问题。下面给出最大流问题的一个基本描述:如下图所示,s是源点,t为汇点,每条边上数字的含义是边能够允许流过的最大流量。可以将边看成管道,0/3代表该管道每秒最多能通过3个单位的流量,0代表当前流量。最大流问题即是说,从s点到t点,最大允许流量是多少?

这里写图片描述

公式描述

这里写图片描述
的流量等于流出该点的流量。这个可以理解为流量守恒,就如同电流一样,流入一个电阻的电流必然等于流出的电流。

那么最大流就可以表示为:
这里写图片描述

Ford-Fulkerson解法介绍

该方法依赖于三种重要思想:残留网络,增广路径和割

Ford-Fulkerson思想

Ford-Fulkerson是一种迭代的方法。开始时,对所有的u,v属于V,f(u,v)=0(这里f(u,v)代表u到v的边当前流量),即初始状态时流的值为0。在每次迭代中,可以通过寻找一个“增广路径”来增加流值。增广路径可以看做是从源点s到汇点t之间的一条路径,沿该路径可以压入更多的流,从而增加流的值。反复进行这一过程,直到增广路径都被找出为止。

增广路径

举个例子来说明下,如图所示,每条红线就代表了一条增广路径,当前s到t的流量为3。当然这并不是该网络的最大流,根据寻找增广路径的算法我们其实还可以继续寻找增广路径。

这里写图片描述

残留网络

顾名思义,残留网络是指给定网络和一个流,其对应还可以容纳的流组成的网络。具体说来,就是假定一个网络G=(V,E),其源点s,汇点t。设f为G中的一个流,对应顶点u到顶点v的流。在不超过C(u,v)的条件下(C代表边容量),从u到v之间可以压入的额外网络流量,就是边(u,v)的残余容量(residual capacity),定义如下:

r(u,v)=c(u,v)-f(u,v)

举个例子,假设(u,v)当前流量为3/4,那么就是说c(u,v)=4,f(u,v)=3,那么r(u,v)=1。

我们知道,在网络流中还有这么一条规律。从u到v已经有了3个单位流量,那么从反方向上看,也就是从v到u就有了3个单位的残留网络,这时r(v,u)=3。可以这样理解,从u到v有3个单位流量,那么从v到u就有了将这3个单位流量的压回去的能力。

我们来具体看一个例子,如下图所示一个流网络

这里写图片描述

对应的残留网络:

这里写图片描述

求解步骤举例

1.获得残留网络

2.穷举所有的增广路径

如下图所示:

这里写图片描述

计算最大流的标号法

这里介绍计算网络最大流的简便方法—标号法,此方法是Ford—Fulkerson 于1956年提出来的,它的原理是利用寻找增广链来不断改善可行流。
设μ是网络中 到 的一条链,规定 到 的方向为μ的方向。 μ上与μ的方向一致的弧称为前向弧,前向弧的集合记为μ+, μ上与μ的方向相反的弧称为后向弧,后向弧的集合记为μ-。

这里写图片描述
上图
若给一个可行流{},称网络中 = 的弧为饱和弧,称 <的弧为非饱和弧,称 =0的弧为零流弧,称 >0的弧为非零流弧。
增广链:设{}是可行流, μ是 到 的一条链,若μ满足下列条件,则称μ为关于 f 的增广链。(注意: f ={})
1°对于任何( ,)∈μ+,0≤ < (前向弧为非饱和弧)
2°对于任何( ,)∈μ-,0 <≤ (后向弧为非零流弧)

博客参考:

smartxxyx的两篇博客:
http://blog.csdn.net/smartxxyx/article/details/9275177
http://blog.csdn.net/smartxxyx/article/details/9293665/
以及:
http://dec3.jlu.edu.cn/webcourse/t000048/yun/ch7_04.htm

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
私信 提问
最大流-最小分割问题(Max Flow and Min Cut Problem)

版权声明:本文为博主原创文章,欢迎转载,但请注明出处,谢谢愿意分享知识的你~~ https://blog.csdn.net/qq_32690999/article/details/84964009 最大流-最小分割问题(Max Flow and Min Cut...

蓝色枫魂
昨天
0
0
Ford-Fulkerson 方法——最大流问题

最大流&&最小费用最大流&&最大二分匹配 Python 源码:https://github.com/edisonleolhl/DataStructure-Algorithm/blob/master/Graph/MaxFlow 最大流问题 比喻:有一个自来水管道运输系统,起...

廖少少
2017/09/08
0
0
网络流——最大流问题例题

许多应用都包含了流量问题,例如,公路系统中有车辆流,控制系统中有信息流,供水系统中有水流,金融系统中有现金流等等。下面不讲原理、不讲概念,以一个例题,用通俗的语言,来说明最大流的...

x113773
2017/12/29
0
0
ZOJ ~ 3229 ~ Shoot the Bullet (有源汇上下界最大流)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/ZscDst/article/details/82695507 题意 你要给一些小姐姐拍照。第一行输入N,M表示总共要拍N天,共有M个小姐姐...

张松超
09/14
0
0
用Ford和Fulkerson的增广路径算法,解决网络中的最大流(flow)以及其衍生问题。

管道网络中每条边的最大通过能力(容量)是有限的,实际流量不超过容量。 最大流问题(maximum flow problem),一种组合最优化问题,就是要讨论如何充分利用装置的能力,使得运输的流量最大,...

linuxer
2017/11/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

十万个为什么之为什么大家都说dubbo

Dubbo是什么? 使用背景 dubbo为什么这么流行, 为什么大家都这么喜欢用dubbo; 通过了解分布式开发了解到, 为适应访问量暴增,业务拆分后, 子应用部署在多台服务器上,而多台服务器通过可以通过d...

尾生
44分钟前
2
0
Docker搭建代码质量检测平台-SonarQube(中文版)

Sonar是一个用于代码质量管理的开源平台,用于管理源代码的质量,可以从七个维度检测代码质量。通过插件形式,可以支持包括java,C#,C/C++,PL/SQL,Cobol,JavaScrip,Groovy等等二十几种编程语言...

Jacktanger
51分钟前
2
0
Windows / Linux / MacOS 设置代理上网的方法汇总

本文汇总了 Windows / Linux / MacOS 设置代理上网的各种方法,总结如下: 1、设置系统代理(Windows、Linux、MacOS) 2、设置代理插件(Chrome、Chromium、Firefox、Opera、QQ等浏览器) 3、...

sunboy2050
昨天
4
0
自定义 Maven 的 repositories

有时,应用中需要一些比较新的依赖,而这些依赖并没有正式发布,还是处于milestone或者是snapshot阶段,并不能从中央仓库或者镜像站上下载到。此时,就需要 自定义Maven的<repositories>。 ...

waylau
昨天
3
0
徒手写一个es6代码库

mkdir democd demonpm initnpm install -g babelnpm install -g babel-clinpm install --save-dev babel-preset-es2015-node5 在项目目录创建两个文件夹 functional-playground ......

lilugirl
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部