【算法设计与分析】网络流

目录

  • max-flow 和 min-cut
    • 流网络 Flow network
    • 最小割 Min-cut
    • 最大流 Max-flow
  • Greedy algorithm
  • Ford–Fulkerson algorithm
    • 剩余网络 Residual network
    • Ford–Fulkerson algorithm算法流程
  • 最大流最小割理论 max-flow min-cut theorem
  • 容量扩展算法 capacity-scaling algorithm
    • 时间复杂度分析 Analysis of Ford–Fulkerson algorithm
    • 优化:选择合适的增广路径
    • 选择足够大瓶颈容量的增广路径算法:Capacity-scaling algorithm
    • 寻找最短增广路径算法:BFS
  • 其他算法的时间复杂度

max-flow 和 min-cut

流网络 Flow network

流网络定义为一个元组 G = ( V , E , s , t , c ) G=(V, E, s, t, c) G=(V,E,s,t,c)

  • V:流网络中点的集合
  • s:源点,没有流量输入,只有流量输出 s ∈ V s ∈ V sV
  • t:汇点,没有流量输出,只有流量输入 t ∈ V t ∈ V tV
  • E:流网络中边的集合
  • c ( e i ) c(e_i) c(ei):边的容量, c ( e i ) > = 0 c(e_i) >= 0 c(ei)>=0
    在这里插入图片描述

最小割 Min-cut

割 (s-t cut) 被定义为一个点的划分 ( A , B ) (A, B) (A,B),其中 s ∈ A s ∈ A sA t ∈ B t ∈ B tB。即将流网络的所有点,分成两个部分 A 和 B。
割的容量(capacity):定义为 从 A 到 B 线段的容量之和: c a p ( A , B ) = ∑ e   o u t   o f   A c ( e ) cap(A, B) = \sum_{ e\ out\ of\ A} c(e) cap(A,B)=e out of Ac(e)

如下图所示,A 仅包含 s,因此 c a p ( A , B ) = 10 + 5 + 15 = 30 cap(A, B) = 10 + 5 + 15 = 30 cap(A,B)=10+5+15=30
在这里插入图片描述
下图割的容量: c a p ( A , B ) = 10 + 8 + 16 = 34 cap(A, B) = 10 + 8 + 16 = 34 cap(A,B)=10+8+16=34
在这里插入图片描述

最小割(Min-cut):即整个流网络中,容量最小的那个割(st cut).

最大流 Max-flow

定义 流 st-flow (flow) f f f 是一个满足以下条件的函数:

  • 每一个 e ∈ E e ∈ E eE,均有 0 < = f ( e ) < = c ( e ) 0 <= f(e) <= c(e) 0<=f(e)<=c(e) ,即流量小于等于容量。
  • 对于任意 v ∈ V − s , v v ∈ V - {s , v} vVs,v,即出去源点和汇点的其他点: ∑ e   i n   t o   v f ( e ) = ∑ e   i o u t   o f   v f ( e ) \sum_{e\ in\ to\ v}f(e) = \sum_{e\ iout\ of\ v}f(e) e in to vf(e)=e iout of vf(e),即出去源点和汇点,所有进入点的流量等于流出点的容量。

进入v的流量: 5 + 5 + 0 = 13 5 + 5 + 0 =13 5+5+0=13、流出v的流量: 10 + 0 = 10 10 + 0 = 10 10+0=10
在这里插入图片描述

流 flow 的值定义为: v a l ( f ) = ∑ e   o u t   o f   s f ( e ) − ∑ e   i n   t o   s f ( e ) val(f) = \sum_{e\ out\ of\ s}f(e) - \sum_{e\ in\ to\ s}f(e) val(f)=e out of sf(e)e in to sf(e)

下图中,网络流的值为: 10 + 5 + 10 = 25 10 + 5 + 10 = 25 10+5+10=25
在这里插入图片描述
最大流Max-flow:流网络中,值最大的流即为最大流。

最大流问题最小割问题 问题是等价的。

Greedy algorithm

增广路径 Augmenrt Path:从 源点 s 到 汇点 t 的一条简单路径,路径上任意一条边均满足 f ( e ) < c ( e ) f(e) < c(e) f(e)<c(e)
阻塞流 Blocking Flow:如果一个 流 flow,找不到增广路径,则该流称为阻塞流。最大流一定是阻塞流,但阻塞流不一定是最大流

贪心算法的流程:

  • 初始流上,任意的 e ∈ E , f ( e ) = 0 e ∈ E, f(e) = 0 eE,f(e)=0
  • 进行流量的增加:
    • 寻找该流上的增广路径 P
    • 增加 增广路径 P 上各个边的流量
  • 重复流量增加的步骤,直至该流变成阻塞流

贪心算法得到的阻塞流并不一定是最大流,因为贪心在寻找增广路径之后,直接沿着找到的增广路径进行流量的增加,之后就继续找下一条增广路径。没有考虑增广路径找错的情况,没有办法减少增广路径上的错误流量。

Ford–Fulkerson algorithm

剩余网络 Residual network

原始边 Original edge e = ( u , v ) ∈ E e = (u, v) ∈ E e=(u,v)E,且边上的流量: f ( e ) f(e) f(e)、边上的容量: c ( e ) c(e) c(e)
在这里插入图片描述

反向边 e r e v e r s e = ( v , u ) e^{reverse} = (v, u) ereverse=(v,u)
剩余容量 c f ( e ) = { c ( e ) − f ( e ) e ∈ E f ( e r e v e r s e ) e r e v e r s e ∈ E c_f(e)=\begin{cases} c(e)-f(e) &e∈E \\ f(e^{reverse})&e^{reverse}∈E \end{cases} cf(e)={c(e)f(e)f(ereverse)eEereverseE
在这里插入图片描述

剩余网络 Residual network G = ( V , E f , s , t , c f ) G = (V, E_f, s, t, c_f) G=(V,Ef,s,t,cf)

  • E f = { e : f ( e ) < c ( e ) } ∪ { e : f ( e r e v e r s e ) > 0 } E_f = \{e: f(e) < c(e)\} ∪ \{e: f(e^{reverse}) > 0\} Ef={e:f(e)<c(e)}{e:f(ereverse)>0}

定义增广路径瓶颈容量 为 增广路径上,最小的剩余容量。

Ford–Fulkerson algorithm算法流程

  • 初始流上,任意的 e ∈ E , f ( e ) = 0 e ∈ E, f(e) = 0 eE,f(e)=0
  • 进行剩余图上流量的增加:
    • 寻找该剩余图上的增广路径 P
    • 增加 增广路径 P 上各个边的流量,同时在剩余图上添加反向变
  • 重复流量增加的步骤,直至该流变成阻塞流

算法的流量增减都是在剩余图上进行操作的。

最大流最小割理论 max-flow min-cut theorem

定义 f f f 为任意的 流 flow ( A , B ) (A, B) (A,B) 为任意的 割 cut,则 f f f的流量大小等于流过 ( A , B ) (A,B) (A,B)的流量。
v a l ( f ) = ∑ e   o u t   o f A f ( e ) − ∑ e   i n   t o   A f ( e ) val(f) = \sum_{e \ out \ of A}f(e) - \sum_{e \ in \ to\ A}f(e) val(f)=e out ofAf(e)e in to Af(e)

在这里插入图片描述
在这里插入图片描述
v a l ( f ) = ∑ e   o u t   o f A f ( e ) − ∑ e   i n   t o   A f ( e ) v a l ( f ) = ∑ e   o u t   o f s f ( e ) − ∑ e   i n   t o   s f ( e ) = ∑ v ∈ A ( ∑ e   o u t   o f A f ( e ) − ∑ e   i n   t o   A f ( e ) ) = ∑ e   o u t   o f A f ( e ) − ∑ e   i n   t o   A f ( e ) val(f) = \sum_{e \ out \ of A}f(e) - \sum_{e \ in \ to\ A}f(e)\\ val(f) = \sum_{e \ out \ of s}f(e) - \sum_{e \ in \ to\ s}f(e)\\ = \sum_{v ∈ A}( \sum_{e \ out \ of A}f(e) - \sum_{e \ in \ to\ A}f(e))\\ = \sum_{e \ out \ of A}f(e) - \sum_{e \ in \ to\ A}f(e) val(f)=e out ofAf(e)e in to Af(e)val(f)=e out ofsf(e)e in to sf(e)=vA(e out ofAf(e)e in to Af(e))=e out ofAf(e)e in to Af(e)

同时定义 f f f 为任意的 流 flow ( A , B ) (A, B) (A,B) 为任意的 割 cut,则 v a l ( f ) < = c a p ( A , B ) val(f) <= cap(A, B) val(f)<=cap(A,B)
v a l ( f ) = ∑ e   o u t   o f A f ( e ) − ∑ e   i n   t o   A f ( e ) < = ∑ e   o u t   o f A f ( e ) < = ∑ e   o u t   o f A c ( e ) = c a p ( A , B ) val(f) = \sum_{e \ out \ of A}f(e) - \sum_{e \ in \ to\ A}f(e)<= \sum_{e \ out \ of A}f(e) <= \sum_{e \ out \ of A}c(e) = cap(A, B) val(f)=e out ofAf(e)e in to Af(e)<=e out ofAf(e)<=e out ofAc(e)=cap(A,B)

定义 f f f 为任意的 流 flow ( A , B ) (A, B) (A,B) 为任意的 割 cut。如果 v a l ( f ) = c a p ( A , B ) val(f) = cap(A, B) val(f)=cap(A,B),那 f f f 一定是最大流, ( A , B ) (A, B) (A,B)一定是最小割。

Max-flow min-cut theorem:Value of a max flow = capacity of a min cut.

容量扩展算法 capacity-scaling algorithm

时间复杂度分析 Analysis of Ford–Fulkerson algorithm

假设 流网络 中所有的边上的容量均为整数,且 范围是 1~C。
则 FFA算法中,每一条边的流量和剩余容量也都是正整数。

假设 f ∗ f* f 是某流网络的最大流,则该流网络中最大流流量 v a l ( f ∗ ) < = n C val(f*) <= nC val(f)<=nC

又每次增广路径最少也会增加 1 的流量,假设使用 BFS、DFS来寻找增广路径,时间复杂度为 O ( m ) O(m) O(m),则Ford–Fulkerson algorithm 的时间复杂度最坏为: T ( n ) = O ( m n C ) T(n) = O(mnC) T(n)=O(mnC)

T ( n ) = O ( m n C ) T(n) = O(mnC) T(n)=O(mnC)的情况出现在,每一次找到的增广路径都只能增加一个容量,例如:
在这里插入图片描述

如果时间复杂度为 O ( m n C ) O(mnC) O(mnC),那么该时间复杂度并非多项式时间的,需要根据边的数量以及容量的大小来判断是否能在一定时间内解决。

优化:选择合适的增广路径

出现上述非多项式时间的时间复杂度的情况的原因:每一次增广路径都只增加1个流量,即瓶颈容量为1的增广路径。
因此我们可以选择更合适的增广路径。

  • 最大瓶颈容量的增广路径
  • 足够大的瓶颈容量的增广路径
  • 最短路径的增广路径

选择足够大瓶颈容量的增广路径算法:Capacity-scaling algorithm

算法大致流程:

  • 首先遍历所有的边,得到最大容量/2,将其设置为当前瓶颈容量下限 k
  • 在剩余图中寻找瓶颈容量大于等于 k 的增广路径
    • 如果找到了就执行FFA算法
    • 如果找不到了,就将 k 减小到原来的一半
  • 一直执行寻找增广路径的循环,直至 k 变为1,此时所有的增广路径都能正常寻找到。

算法伪代码
在这里插入图片描述
m:边的数量
n:点的数量
C:容量的上限
使用该算法寻找增广路径,总的寻找最大流的时间复杂度: T ( n ) = O ( m 2 l o g C ) T(n) = O(m^2logC) T(n)=O(m2logC)

寻找最短增广路径算法:BFS

使用队列,不断扩展下一个节点,当到达 t ,此路径即为最短路。

算法伪代码
在这里插入图片描述

m:边的数量
n:点的数量
C:容量的上限
使用该算法寻找增广路径,总的寻找最大流的时间复杂度: T ( n ) = O ( m 2 n ) T(n) = O(m^2n) T(n)=O(m2n)

其他算法的时间复杂度

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/303716.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Rustdesk本地配置文件存在什么地方?

环境&#xff1a; rustdesk1.1.9 Win10 专业版 问题描述&#xff1a; Rustdesk本地配置文件存在什么地方&#xff1f; 解决方案&#xff1a; RustDesk 是一款功能齐全的远程桌面应用。 支持 Windows、macOS、Linux、iOS、Android、Web 等多个平台。 支持 VP8 / VP9 / AV1 …

UDP 和 TCP 、HTTP、HTTPS、SOCKS5协议的不同之处及应用场景

UDP 和 TCP、HTTP、HTTPS、SOCKS5 协议的不同之处及应用场景&#xff1a; UDP (User Datagram Protocol)&#xff1a; 不同之处&#xff1a;UDP 是无连接的&#xff0c;不保证数据包的顺序到达或完整性&#xff0c;也没有流量控制和拥塞控制机制。它尽可能快地将数据包从源主机…

STL标准库与泛型编程(侯捷)笔记4

STL标准库与泛型编程&#xff08;侯捷&#xff09; 本文是学习笔记&#xff0c;仅供个人学习使用。如有侵权&#xff0c;请联系删除。 参考链接 Youbute: 侯捷-STL标准库与泛型编程 B站: 侯捷 - STL Github:STL源码剖析中源码 https://github.com/SilverMaple/STLSourceCo…

面向应用的离线计算系统:周期任务组合策略

1 场景 业务应用系统想大批量利用数据中心的计算能力跑数,回传结果。比如一个个地区的详情数据。而大数据平台通常是调度平台系统,和业务系统是两个独立的平台系统,如何建立交互方式。 业务有个性化的实验策略,需要组合业务条件达到实验效果。比如捞取不同的数据实验算法…

4.8 SUMMARY 4.9 EXERCISES

总之&#xff0c;在现代处理器中&#xff0c;程序的执行速度可能会受到内存速度的严重限制。为了很好地利用CUDA设备的执行吞吐量&#xff0c;应该在内核代码中获得高计算与全局内存访问率。如果获得的比率很低&#xff0c;则内核受内存约束&#xff1b;即其执行速度受从内存访…

鸿蒙Ability开发-Stage模型下Ability的创建和使用

创建Ability和Page页面 创建两个Ability&#xff1a;EntryAbility&#xff0c;DetailsAbility&#xff0c;其中EntryAbility是由工程默认创建的&#xff0c;这里我们只讲如何创建DetailsAbility。 使用DevEco Studio&#xff0c;选中对应的模块&#xff0c;单击鼠标右键&…

IDEA+Git——项目分支管理

IDEAGit——项目分支管理 1. 前言2. 基础知识点2.1. 分支区分2.2. Git 代码提交规范2.3. 四个工作区域2.4. 文件的四种状态2.5. 常用命令2.6 注重点 3. IDEA分支管理 1. 前言 在Git中&#xff0c;分支是项目的不同版本&#xff0c;当开始开发一个新项目时&#xff0c;主分支通常…

关于外连接、内连接和子查询的使用(2)

目录 一. 前言 二. 使用外连接、内连接和子查询进行解答 三. 思维导图 一. 前言 在前面我们对外连接、内连接和子查询的使用有了一些了解&#xff0c;今天我们将继续更深入的进行学习。&#xff08;这里缺少的八个题目在博主的前面博客有解答&#xff0c;大家可以移步前面一…

Tsmaster使用笔记整理

选择厂商 根据你所选择的CAN分析仪的厂商&#xff0c;确定你的厂商设备设置。 我一般会选择PEAK&#xff0c;和 ZLG多一点&#xff0c;其他的没有用过。除了上图中的&#xff0c;市面上的CAN分析仪还有CANanlyst、广成科技、创芯科技等&#xff0c;但它们都不能在Tsmaster上使…

Android Matrix (二)具体图形变换参数的获取

Android Matrix &#xff08;二&#xff09;具体图形变换参数的获取 Matrix 类在 Android 中用于表示 3x3 的变换矩阵。这个矩阵可以应用于画布&#xff08;Canvas&#xff09;&#xff0c;视图&#xff08;View&#xff09;或者位图&#xff08;Bitmap&#xff09;&#xff0…

嵌入式Linux-Qt环境搭建

本编介绍如何在嵌入式Linux开发板上配置Qt运行环境&#xff0c;并进行Qt程序运行测试。 1 tslib编译 tslib之前在测试触摸屏的时候使用过&#xff0c;这里再来记录一下编译过程。 下载tslib库的源码&#xff1a;https://github.com/libts/tslib/tags 将下载的源码拷贝到ubun…

在当前bash(sh)中执行脚本和注册函数

在研究《管理Python虚拟环境的脚本》时&#xff0c;我们使用了source指令而没有使用sh或者bash来执行脚本&#xff0c;就是因为source指令可以让脚本在当前bash(sh)中执行&#xff1b;而sh或者bash则会新启动一个bash来执行。 我们可以通过下面这个脚本做测试 # test.sh # 用…

一文读懂「多模态大模型」

​ 学习资源 5-多模态大模型一统NLP和CV 1.多模态大模型的基本原理 2.常见的多模态大模型 https://www.bilibili.com/video/BV1NN41177Zp?p5&vd_sourcef27f081fc77389ca006fcebf41bede2d 3.多模态大模型如_哔哩哔哩_bilibili 强强联手&#xff01;科大讯飞和中科院终于把【…

RocketMQ源码 发送 延迟消息 源码分析

前言 rocketMQ 支持的延迟消息&#xff0c;简单理解就是对于生产者发送的消息&#xff0c;支持设置固定时间的延迟级别&#xff0c;在到达指定的延迟时间时&#xff0c;才会投递到消费者队列&#xff0c;消费者才能消费到消息。 延迟队列和普通消息的发送流程&#xff0c;主要…

Dijkstra算法——邻接矩阵实现+路径记录

本文是在下面这篇文章的基础上做了一些补充&#xff0c;增加了路径记录的功能。具体Dijkstra的实现过程可以参考下面的这篇文章。 [jarvan&#xff1a;Dijkstra算法详解 通俗易懂](Dijkstra算法详解 通俗易懂 - jarvan的文章 - 知乎 https://zhuanlan.zhihu.com/p/338414118) …

软考高级选择考哪个好?

&#x1f4d2;软考高级总共5个科目&#xff0c;同样是高级证书&#xff0c;认可度也有区别! 大家一般在「信息系统项目管理师」✔️和「系统架构设计师」✔️二选一 1️⃣信息系统项目管理师 ❤️信息系统项目管理师也叫「高项」&#xff0c;考试内容主要是「项目管理」相关&am…

006-Zynq图像传输中cache刷新对视频的影响(讲究一个恰到好处)

文章目录 前言一、cache是什么玩意儿&#xff1f;二、解决方法1.Xil_DCacheInvalidateRange函数2.未刷新前的问题3.带刷新后的效果 总结 前言 也是移植过程中遇到的一个问题&#xff0c;尝试了一些解决方案&#xff0c;也算是解决了这个问题。 这个问题出现在通过以太网传输分…

为什么要使用云原生数据库?云原生数据库具体有哪些功能?

相比于托管型关系型数据库&#xff0c;云原生数据库极大地提高了MySQL数据库的上限能力&#xff0c;是云数据库划代的产品&#xff1b;云原生数据库最早的产品是AWS的 Aurora。AWS Aurora提出来的 The log is the database的理念&#xff0c;实现存储计算分离&#xff0c;把大量…

基于YOLOv8全系列【n/s/m/l/x】开发构建道路交通场景下CCTSDB2021交通标识检测识别系统

交通标志检测是交通标志识别系统中的一项重要任务。与其他国家的交通标志相比&#xff0c;中国的交通标志有其独特的特点。卷积神经网络&#xff08;CNN&#xff09;在计算机视觉任务中取得了突破性进展&#xff0c;在交通标志分类方面取得了巨大的成功。CCTSDB 数据集是由长沙…

CodeGPT,你的智能编码助手—CSDN出品

CodeGPT是由CSDN打造的一款生成式AI产品&#xff0c;专为开发者量身定制。 无论是在学习新技术还是在实际工作中遇到的各类计算机和开发难题&#xff0c;CodeGPT都能提供强大的支持。其涵盖的功能包括代码优化、续写、解释、提问等&#xff0c;还能生成精准的注释和创作相关内…