热门标签 | HotTags
当前位置:  开发笔记 > 后端 > 正文

mysql最小费用最大流问题_最小费用最大流问题

复杂网络中,单源单点的最小费用最大流算法(MCMF)应用广泛。在实际网络问题中,不仅考虑从Vs到Vt的流量最大,还要考虑可行流在网络传送过

复杂网络中,单源单点的最小费用最大流算法(MCMF)应用广泛。

在实际网络问题中,不仅考虑从 Vs到 Vt的流量最大,还要考虑可行流在网络传送过程中的费用问题,这就是网络的最小费用最大流问题。

最小费用最大流问题的一般提法:已知容量网络 D=(V ,A ,C),每条弧 (Vi,Vj) 除了已给出容量 Cij 外,还给出单位流量的传输费用 bij≥0,记作D=(V, A, C, B),其中bij ∈B。要在费用、容量网络 D 中寻找 Vs→Vt的最大流 f={fij},且使流的总传输费用:

b(f)=Σbijfij 最小

从上一讲可知,最大流的求法就是在容量网络上从某个可行流出发,设法找到一条从 Vs→Vt 的增广链,然后沿着此增广链调整流量,作出新的流量增大了的可行流。在这个新的可行流基础上再寻找它的增广链。如此反复进行,直至再找不出增广链,就得到了该网络的最大流。

例子:给定费用、容量网络图(bij,cij),试求网络的最小费用最大流。

409ccb50a8d959dc5c677e1e40b4ab7f.png

解:

(1)、初始取0流量,此时总费用为 f(0) = 0。

(2)、由原始网络构建费用网络图(费用网络图每条线路上的权重为bij,bij为单位流量的费用)。

(3)、通过当前费用网络图找到一个费用最少的路径,即vs->v3->v2->vt。通过该路径上每条线段的容量得出该线路能通过的最大流量,即调整量θ = min{8,5,7} = 5,即流量为5,当前的最小费用为 f(1) = 5*1+5*2+5*1 = 20。下图为流量网络图。

06630b53d197ed26739112aa5871cab4.png

(4)、在(3)的基础上构造新的费用网络图,构造方法为:当线路没流量通过时,流量方向不变,费用为原始费用。如vs->v2;

当线路流量等于该线路的最大容量时,则流量方向改变,费用为原始费用的负数。如v3->v2变为v2->v3;

当线路流量小于该线路的最大容量时,则增加反向流量,费用为原始费用的负数。如vs->v3新增v3->vs;

f841fa9ba40effaa97bc7de2e6e58728.png

(5)、在(4)中得到的费用网络图上,找到费用最少的路径,即vs->v2->vt,通过该路径上每条线段的容量得出该线路能通过的最大流量,即调整量θ = min{10,7-5} = 2,得到的最小费用流的流量为7,当前的最小费用为 f(2) = 2*4+5*1+5*2+7*1 = 30。

32a2e7c5ed0972e50233a84ef2389860.png

(6)、构造可行流 f2的费用网络图。

c888f6e862344bd1e0d2fe217f7511ff.png

(7)、在(6)中得到的费用网络图上,找到费用最少的路径,即vs->v3->v4->vt,通过该路径上每条线段的容量得出该线路能通过的最大流量,即调整量θ = min{8-5,10,4} = 3,得到的最小费用流的流量为10,当前的最小费用为 f(3) = 2*4+8*1+5*2+7*1+3*3+3*2 = 42

75060eccdafcb8de177b27a55de6a24b.png

(8)、构造可行流 f3 的费用网络图。

acc6e0a89d0b6a049adf31f97edf8721.png

(9)、在(8)的费用网络图上,找到费用最少的路径,即vs->v2->v3->v4->vt,通过该路径上每条线段的容量得出该线路能通过的最大流量,即调整量θ = min{10-2, 10-3, 4-3, 5} = 1,得到的最小费用流的流量为11,当前最小费用为 f(4) = 3*4+8*1+4*2+7*1+4*3+4*2 = 55

ee905d2acc3423eef56588d7bf9fc075.png

(10)、构造可行流 f4 的费用网络图。

3fd189f25db4cde32ff346affcd8f6b5.png

由于无法找到从 vs->vt 的最短路,所以 f(4) 就是该网络的最小费用最大流。



推荐阅读
  • 结语 | 《探索二进制世界:软件安全与逆向分析》读书笔记:深入理解二进制代码的逆向工程方法
    结语 | 《探索二进制世界:软件安全与逆向分析》读书笔记:深入理解二进制代码的逆向工程方法 ... [详细]
  • 从无到有,构建个人专属的操作系统解决方案
    操作系统(OS)被誉为程序员的三大浪漫之一,常被比喻为计算机的灵魂、大脑、内核和基石,其重要性不言而喻。本文将详细介绍如何从零开始构建个人专属的操作系统解决方案,涵盖从需求分析到系统设计、开发与测试的全过程,帮助读者深入理解操作系统的本质与实现方法。 ... [详细]
  • 智能制造数据综合分析与应用解决方案
    在智能制造领域,生产数据通过先进的采集设备收集,并利用时序数据库或关系型数据库进行高效存储。这些数据经过处理后,通过可视化数据大屏呈现,为生产车间、生产控制中心以及管理层提供实时、精准的信息支持,助力不同应用场景下的决策优化和效率提升。 ... [详细]
  • MySQL 错误:检测到死锁,在尝试获取锁时;建议重启事务(Node.js 环境)
    在 Node.js 环境中,MySQL 数据库操作时遇到了“检测到死锁,在尝试获取锁时;建议重启事务”的错误。本文将探讨该错误的原因,并提供有效的解决策略,包括事务管理优化和锁机制的理解。 ... [详细]
  • 超分辨率技术的全球研究进展与应用现状综述
    本文综述了图像超分辨率(Super-Resolution, SR)技术在全球范围内的最新研究进展及其应用现状。超分辨率技术旨在从单幅或多幅低分辨率(Low-Resolution, LR)图像中恢复出高质量的高分辨率(High-Resolution, HR)图像。该技术在遥感、医疗成像、视频处理等多个领域展现出广泛的应用前景。文章详细分析了当前主流的超分辨率算法,包括基于传统方法和深度学习的方法,并探讨了其在实际应用中的优缺点及未来发展方向。 ... [详细]
  • HBase在金融大数据迁移中的应用与挑战
    随着最后一台设备的下线,标志着超过10PB的HBase数据迁移项目顺利完成。目前,新的集群已在新机房稳定运行超过两个月,监控数据显示,新集群的查询响应时间显著降低,系统稳定性大幅提升。此外,数据消费的波动也变得更加平滑,整体性能得到了显著优化。 ... [详细]
  • 在稀疏直接法视觉里程计中,通过优化特征点并采用基于光度误差最小化的灰度图像线性插值技术,提高了定位精度。该方法通过对空间点的非齐次和齐次表示进行处理,利用RGB-D传感器获取的3D坐标信息,在两帧图像之间实现精确匹配,有效减少了光度误差,提升了系统的鲁棒性和稳定性。 ... [详细]
  • 在计算机系统中,核心组件与架构是其稳定运行的基石。本文深入解析了R1路由器如何通过子网掩码与目的IP地址(如145.13.3.10)进行逐位逻辑“与”操作,以确定目标子网的网络地址。如果计算结果与路由表中的某一行的目的网络地址匹配,数据包将直接或间接地被传输至指定目的地。此外,文章还探讨了这一过程在现代网络通信中的重要性及其对数据传输效率的影响。 ... [详细]
  • 总分与最高分:MySQL多表联合查询技巧解析
    总分与最高分:MySQL多表联合查询技巧解析 ... [详细]
  • 尽管存在唯一列,仍显示“当前选择不包含唯一列。网格编辑、复选框、编辑、复制和删除功能不可用”的消息。 ... [详细]
  • 本文深入探讨了在Android应用开发中常见的相机连接故障问题,特别是在RK3288平台和Android 6.0系统上。通过分析具体案例,本文提供了详细的解决方案和应对策略,旨在帮助开发者有效解决相机连接问题,提升应用的稳定性和用户体验。 ... [详细]
  • 对于前端开发新手而言,理解JavaScript模块加载机制常常是一个挑战。本文将深入解析Node.js中的`require`方法及其与RequireJS之间的区别,并探讨它们在不同场景下的应用。通过对比这两种模块加载方式,读者可以更好地掌握如何在项目中选择合适的模块管理工具。此外,文章还提供了实际示例,帮助读者加深对模块化编程的理解。 ... [详细]
  • 在处理高并发场景时,确保业务逻辑的正确性是关键。本文深入探讨了Java原生锁机制的多种细粒度实现方法,旨在通过使用数据的时间戳、ID等关键字段进行锁定,以最小化对系统性能的影响。文章详细分析了不同锁策略的优缺点,并提供了实际应用中的最佳实践,帮助开发者在高并发环境下高效地实现锁机制。 ... [详细]
  • 深入解析Python中的循环双向链表数据结构
    本文详细探讨了Python中循环双向链表的数据结构,包括其定义、特点及应用场景。文章首先介绍了循环双向链表的基本概念,随后深入分析了其核心操作,如节点的插入、删除和遍历等。最后,通过具体的Python代码示例,展示了如何高效地实现这些操作,帮助读者全面理解并掌握这一重要数据结构。 ... [详细]
  • 本文深入探讨了数据库性能优化与管理策略,通过实例分析和理论研究,详细阐述了如何有效提升数据库系统的响应速度和处理能力。文章首先介绍了数据库性能优化的基本原则和常用技术,包括索引优化、查询优化和存储管理等。接着,结合实际应用场景,讨论了如何利用容器化技术(如Docker)来部署和管理数据库,以提高系统的可扩展性和稳定性。最后,文章还提供了具体的配置示例和最佳实践,帮助读者在实际工作中更好地应用这些策略。 ... [详细]
author-avatar
峰的紫色摩天轮
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有