热门标签 | HotTags
当前位置:  开发笔记 > 开放平台 > 正文

网络流解析——最大流EdmondsKarp算法

原理并不复杂,但存在的疑惑主要集中在反向边的引入,以下篇幅作以讲解。首先假设一不存在TS边的单源有向加权图。(所谓“TS边”即是指对于任一割,方向为

原理并不复杂,但存在的疑惑主要集中在反向边的引入,以下篇幅作以讲解。
首先假设一不存在TS边的单源有向加权图。
(所谓“TS边”即是指对于任一割,方向为T->S的边)
类似下图(1为S,6为T,边权(容量)均为10)
这里写图片描述
此时若求解最大流问题(具体命题省略),按照EdmondsKarp算法,作出其残量网络。
为了解释反向边的作用,我们考虑不使用反向边的情况下,所得出的结果。
下图为不包含反向边的残量网络。
这里写图片描述
每条原始图的边流量初始化为0,相应残量则为10。
如此只要我们对于每条增广路(连接S与T的路)进行增广(将增广路的流量灌到最大限度),最后所有增广路灌流量相加即为最大流结果。
以上都十分直观。
引入割的概念
割:通俗理解,一个图或网络的割,表示一个切面或切线,将图或网络分为分别包含源点和漏点的两个子集,该切线或切面与网络相交的楞或边的集合,称为图像的割。(百度百科)
注意,其中不包含T->S边。
由定义,割其实是 Σ cap,而一定有 Σ flow<= Σ cap
这里写图片描述
由图可知,最大流=最小割。
而倘若遇到下图情况,头疼了

这里写图片描述
如图,如果执行bfs一次扫描到增广路1->2->4->6,流量总量累加10,得到的残量网络无法继续进行增广,那么算法返回最大流为10。
然而实际上最大流是20,显然该算法是有问题的。
问题出在哪里呢?
显然每当算法结束(即使最后结果出错)时,所得到的残量网络必然不存在S->T边,而可能存在T->S边。
这里写图片描述
造成残量网络这种结果的是原网络中所有S->T路流量均达到容量大小,而T-S路却不一定存在。
类比最大流最小割原理,此时达到容量的S->T边集等于最小割,也就是我们要的最大流。
因此不论结果是否有错,结果中总能包括最大流,且错误就出在T->S边的保留上 。
显然对于最大流,我们不想要在所有S->T边流量最大的基础上,有回流的T->S边。
因此就需要引入反向边了。
我们为所有边设置反向边,并将其流量与正向边同步。为了保持T->S边流量为0,每当由于增广操作,T->S边流量上升,其反向边也同步上涨,而显然在残量网络中反向边是沿S->T方向的,这就又出现了一条增广路,计算机对此无法容忍,下调它的流量,我们的T->S边流量也随之回到了0,达到了目的。
以上便是对反向边方法的详细解释,对于某些基本概念不清的话需要先熟悉一下EdmondsKarp算法。


推荐阅读
  • “你永远都不知道明天和‘公司的意外’哪个先来。”疫情期间,这是我们最战战兢兢的心情。但是显然,有些人体会不了。这份行业数据,让笔者“柠檬” ... [详细]
  • 解决Cydia数据库错误:could not open file /var/lib/dpkg/status 的方法
    本文介绍了解决iOS系统中Cydia数据库错误的方法。通过使用苹果电脑上的Impactor工具和NewTerm软件,以及ifunbox工具和终端命令,可以解决该问题。具体步骤包括下载所需工具、连接手机到电脑、安装NewTerm、下载ifunbox并注册Dropbox账号、下载并解压lib.zip文件、将lib文件夹拖入Books文件夹中,并将lib文件夹拷贝到/var/目录下。以上方法适用于已经越狱且出现Cydia数据库错误的iPhone手机。 ... [详细]
  • 计算机存储系统的层次结构及其优势
    本文介绍了计算机存储系统的层次结构,包括高速缓存、主存储器和辅助存储器三个层次。通过分层存储数据可以提高程序的执行效率。计算机存储系统的层次结构将各种不同存储容量、存取速度和价格的存储器有机组合成整体,形成可寻址存储空间比主存储器空间大得多的存储整体。由于辅助存储器容量大、价格低,使得整体存储系统的平均价格降低。同时,高速缓存的存取速度可以和CPU的工作速度相匹配,进一步提高程序执行效率。 ... [详细]
  • SLAM中相机运动估计的基本问题及解决方案
    本文讨论了SLAM中相机运动估计的基本问题,指出了解决方案的存在。作者认为阅读相关SLAM书籍是掌握基础原理的有效途径,而不是仅仅依赖现成的解决方案。同时,作者也提到了激光雷达和特征点匹配等技术在SLAM中的应用,并建议读者深入理解相关原理,而不是盲目追求现成的代码。 ... [详细]
  • 本文由编程笔记#小编整理,主要介绍了关于数论相关的知识,包括数论的算法和百度百科的链接。文章还介绍了欧几里得算法、辗转相除法、gcd、lcm和扩展欧几里得算法的使用方法。此外,文章还提到了数论在求解不定方程、模线性方程和乘法逆元方面的应用。摘要长度:184字。 ... [详细]
  • 提升Python编程效率的十点建议
    本文介绍了提升Python编程效率的十点建议,包括不使用分号、选择合适的代码编辑器、遵循Python代码规范等。这些建议可以帮助开发者节省时间,提高编程效率。同时,还提供了相关参考链接供读者深入学习。 ... [详细]
  • 缤果串口网络蓝牙调试助手的特点和下载链接
    本文介绍了缤果串口网络蓝牙调试助手的主要特点,包括支持常用的波特率、校验、数据位和停止位设置,以及以ASCII码或十六进制接收或发送数据或字符的功能。该助手还能任意设定自动发送周期,并能将接收数据保存成文本文件。同时,该软件支持网络UDP/TCP和蓝牙功能。最后,提供了腾讯微云和百度网盘的下载链接。 ... [详细]
  • 众筹商城与传统商城的区别及php众筹网站的程序源码
    本文介绍了众筹商城与传统商城的区别,包括所售产品和玩法不同以及运营方式不同。同时还提到了php众筹网站的程序源码和方维众筹的安装和环境问题。 ... [详细]
  • 本文介绍了C++中的引用运算符及其应用。引用运算符是一种将变量定义为另一个变量的引用变量的方式,在改变其中一个变量时,两者均会同步变化。引用变量来源于数学,在计算机语言中用于储存计算结果或表示值抽象概念。变量可以通过变量名访问,在指令式语言中引用变量通常是可变的,但在纯函数式语言中可能是不可变的。本文还介绍了引用变量的示例及验证,以及引用变量在函数形参中的应用。当定义的函数使用引用型形参时,函数调用时形参的改变会同时带来实参的改变。 ... [详细]
  • 本文讨论了如何查看js的一些方法的官方文档,作者提到了在实现打印功能时遇到了困惑,不知道如何查看方法。虽然百度有时可以得到答案,但作者想要知道官方文档的用法,因为有时候百度并不能满足自己的需求。 ... [详细]
  • 英语思维导图大全 词汇与语法结构详解
    本文详细介绍了英语思维导图大全中的词汇与语法结构,包括新鲜一感的理解和订阅后获取百度网盘链接的方法。通过阅读本文,您将对英语思维导图的相关知识有更深入的了解。 ... [详细]
  • 树莓派语音控制的配置方法和步骤
    本文介绍了在树莓派上实现语音控制的配置方法和步骤。首先感谢博主Eoman的帮助,文章参考了他的内容。树莓派的配置需要通过sudo raspi-config进行,然后使用Eoman的控制方法,即安装wiringPi库并编写控制引脚的脚本。具体的安装步骤和脚本编写方法在文章中详细介绍。 ... [详细]
  • SpringMVC接收请求参数的方式总结
    本文总结了在SpringMVC开发中处理控制器参数的各种方式,包括处理使用@RequestParam注解的参数、MultipartFile类型参数和Simple类型参数的RequestParamMethodArgumentResolver,处理@RequestBody注解的参数的RequestResponseBodyMethodProcessor,以及PathVariableMapMethodArgumentResol等子类。 ... [详细]
  • 如何提高PHP编程技能及推荐高级教程
    本文介绍了如何提高PHP编程技能的方法,推荐了一些高级教程。学习任何一种编程语言都需要长期的坚持和不懈的努力,本文提醒读者要有足够的耐心和时间投入。通过实践操作学习,可以更好地理解和掌握PHP语言的特异性,特别是单引号和双引号的用法。同时,本文也指出了只走马观花看整体而不深入学习的学习方式无法真正掌握这门语言,建议读者要从整体来考虑局部,培养大局观。最后,本文提醒读者完成一个像模像样的网站需要付出更多的努力和实践。 ... [详细]
  • 嵌入式处理器的架构与内核发展历程
    本文主要介绍了嵌入式处理器的架构与内核发展历程,包括不同架构的指令集的变化,以及内核的流水线和结构。通过对ARM架构的分析,可以更好地理解嵌入式处理器的架构与内核的关系。 ... [详细]
author-avatar
诚实的大丈夫_196
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有