文档章节

最大流问题

fengsehng
 fengsehng
发布于 2016/11/09 09:11
字数 1117
阅读 7
收藏 0
点赞 0
评论 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
朝阳
程序员
Ford-Fulkerson 方法——最大流问题

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

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

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

x113773
2017/12/29
0
0
用Ford和Fulkerson的增广路径算法,解决网络中的最大流(flow)以及其衍生问题。

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

linuxer
2017/11/11
0
0
一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404
2015/06/24
0
0
网络最大流

网络最大流 例题: 如果网络结构复杂,就得靠算法算出结果。 这里需要注意容量和流量的区别。其中f(u,v)的范围需要额外注意,是 0<= f(u,v) <= c(u,v),不会出现所谓的负流量。 网络流的三个...

evsqiezi
2017/12/02
0
0
12.15~12.16培训总结

图论我在九月份打了很多板,基础较熟练,但对二分图匹配和网络流、费用流以及各种模型不太熟练。 二分图主要有这些模型 (部分参考lrj) 二分图最小覆盖(选择尽量少的点,使得每条边至少有一...

myjs999
2017/12/17
0
0
计算机科学中最重要的32个算法

转载:http://www.infoq.com/cn/news/2012/08/32-most-important-algorithms 奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph Koutschan博士在自......

Nov_Eleven
2013/06/23
0
0
计算机科学中最重要的32个算法

奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph Koutschan博士在自己的页面上发布了一篇文章,提到他做了一个调查,参与者大多数是计算机科学家...

大数据之路
2012/09/05
0
0
Flink watermark

Flink中watermark主要解决保序问题. 而保序问题的根本原因是多个任务同时从流中并行处理数据,顺序无法保证. 上游: 生成watermark 一般在WINDOW 操作之前生成WATERMARK, WATERMARK 有两种: A...

zhanjia
01/09
0
0
ACM程序设计大赛题目分类

第一类:基础算法 (1) 基础算法:枚举,贪心,递归,分治,递推,构造,模拟 (2) 动态规划:背包问题,树形dp,状态压缩dp,单调性优化,插头dp (3) 搜索:dfs,bfs,记忆化搜索,优化...

齐勇cn
2016/04/20
122
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

《Linux Perf Master》Edition 0.4 发布

在线阅读:https://riboseyim.gitbook.io/perf 在线阅读:https://www.gitbook.com/book/riboseyim/linux-perf-master/details 百度网盘【pdf、mobi、ePub】:https://pan.baidu.com/s/1C20T......

RiboseYim
5分钟前
0
0
conda 换源

https://mirrors.tuna.tsinghua.edu.cn/help/anaconda/ conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/free/conda config --add channels https://mir......

阿豪boy
15分钟前
0
0
Confluence 6 安装补丁类文件

Atlassian 支持或者 Atlassian 缺陷修复小组可能针对有一些关键问题会提供补丁来解决这些问题,但是这些问题还没有放到下一个更新版本中。这些问题将会使用 Class 类文件同时在官方 Jira bug...

honeymose
24分钟前
0
0
设计模式:代理模式

代理模式可以分为三种:静态代理,动态代理,cglib代理 1.静态代理:被代理的类需要实现一接口或是继承一父类 委托类(被代理的类): package com.java.pattern.proxy.staticdemo;publ...

人觉非常君
27分钟前
0
0
非常实用的IDEA插件之总结

1、Alibaba Java Coding Guidelines 经过247天的持续研发,阿里巴巴于10月14日在杭州云栖大会上,正式发布众所期待的《阿里巴巴Java开发规约》扫描插件!该插件由阿里巴巴P3C项目组研发。P3C...

Gibbons
33分钟前
0
0
Tomcat介绍,安装jdk,安装tomcat,配置Tomcat监听80端口

Tomcat介绍 Tomcat是Apache软件基金会(Apache Software Foundation)的Jakarta项目中的一个核心项目,由Apache、Sun和其他一些公司及个人共同开发而成。 java程序写的网站用tomcat+jdk来运行...

TaoXu
33分钟前
0
0
TensorFlow,从一个 Android Demo 开始

TensorFlow Android Demo 项目地址 Machine Learning 既然提到了 TensorFlow,那是不是得神经网络、机器学习了解下? 如果你能坚持把 机器学习速成课程 给啃完了,觉得还挺有兴趣的,那可以考...

孟飞阳
35分钟前
0
0
JVM学习笔记二:内存结构规范

1、JVM基本结构图 2、java堆(Heap) 3、方法区(Method Area) 4、程序计数器 5、JAVA栈图解 局部变量表:八大基本类型,还可以存储引用类型 上一篇:JVM学习笔记一:类加载机制介绍...

刘祖鹏
41分钟前
0
0
mui集成微信H5支付(返回白屏问题已经解决)

一.项目需求 因为公司人员缺少,没有专门开发安卓和ios的人员,为了项目尽早上线采用了混合APP开发的方式,我选择了MUI混合开发框架,项目中需要在用户购买VIP会员的时候进行支付,所以需要在项目...

银装素裹
45分钟前
0
0
SpringBoot集成Redis--配置自定义的RedisCacheManager

配置自定义的RedisCacheManager--1自定义键生成规则 默认的键生成器 当不指定缓存的key时,SpringBoot会使用SimpleKeyGenerator生成key。 SimpleKeyGenerator SimpleKey 查看源码可以发现,它...

karma123
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部