V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
microxiaoxiao
V2EX  ›  程序员

才疏学浅,理论知识不够。请教大家一个问题。图里面的最大流问题,求的是两点之间的,那么有没有办法求出来所有节点的能够通过的?直接依次求,更新权重就可以了嘛?

  •  
  •   microxiaoxiao · 9 天前 · 876 次点击
    9 条回复    2022-06-23 15:21:41 +08:00
    GuuJiang
        1
    GuuJiang  
       9 天前
    @microxiaoxiao 重新准确描述下,你的意思是,是否存在一个算法一次性求出指定源点到其他所有汇点的最大流?还是说一次性求出所有点两两之间的最大流?(类似于最短路问题中的 floyd 算法那样)
    microxiaoxiao
        2
    microxiaoxiao  
    OP
       9 天前 via Android
    @GuuJiang 求所有的。就是这个集群最大能接受多少流
    MoYi123
        3
    MoYi123  
       9 天前
    @microxiaoxiao 那到底是第一种情况还是第二种呢?
    第一种情况设置一个虚拟终点, 除了起点外的点到虚拟终点的权重都是无限大, 用起点到虚拟终点跑一次最大流即可
    第二种不会.
    GuuJiang
        4
    GuuJiang  
       9 天前
    @microxiaoxiao 你可能对最大流的定义有点误解,当我们在讨论一个最大流时是不能脱离源点汇点单独存在的,换句话说只有预先指定了源点和汇点,接下来才能讨论最大流
    不过我也大概理解了你的意思,你的意思应该是“在可以任意选择源点和汇点的前提下,所有任意组合的最大流中的最大值”,这个确实没有认真想过,和这个比较接近的是有多个源和多个汇的问题,解决方法是添加一个超级源和超级汇,然后求解,但是我猜这个方法应该是无法直接套用到你说的这个场景的,可能需要一些手段来规避同一个结点既作为源又作为汇的情况,否则的话求出来直接就是无穷大了,细节容我再想想
    GuuJiang
        5
    GuuJiang  
       9 天前
    刚才搜索了下,对于这个问题,目前没有什么比针对每一对结点分别跑一遍最大流算法更优的算法
    vance123
        6
    vance123  
       9 天前 via Android
    最大流问题也是线性规划问题,要不试试万能的求解器?
    nagatoism
        8
    nagatoism  
       9 天前
    全局的最小的 最大流等于全局的最小割。
    microxiaoxiao
        9
    microxiaoxiao  
    OP
       9 天前 via Android
    @GuuJiang 哈哈,要不怎么说才疏学浅呢,就是我不太了解,其实问题更抽象一点,就是现在有多个节点,找到这样的组合,使得能够规划出来的两两节点值加起来最大。那么这个就是整个集群对外提供的输入输出能力
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2533 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 19ms · UTC 08:23 · PVG 16:23 · LAX 01:23 · JFK 04:23
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.