问题标签 [network-flow]

我正在寻找一种算法来检查给定网络流中是否存在信号最小切割。

我知道这是可能的，因为我们可以查找所有切割，并检查我们是否只有 1 个最小切割，但我想找到更有效的多项式运行算法。

我考虑过使用最大流量算法来帮助我，但我没有成功。

问题：给定两个整数数组 A 和 B。现在，在每个步骤中，我们都可以从两个数组中删除任何 2 个非互质整数。我们必须找到可以通过这些步骤删除的最大对数。

界限： A、B 的长度 <=10 ⁵
每个整数 <=10 ⁹
Dinic 算法 - O(V ² E)
Edmonds-karp 算法 - O(VE ² )
Hopcroft–Karp 算法 - O(E sqrt(V))

到目前为止我的方法：这可以建模为具有两个集合 A 和 B 的二分匹配问题，并且可以在相应集合中的每个非互质整数对之间创建边。
但问题是图中可能有 O(V ² ) 条边，大多数二分匹配和最大流算法对于如此大的图来说会非常慢。

我正在寻找一些可以在合理时间内解决问题的特定问题或数学优化。要通过测试用例，我最多需要 O(V log V) 或 O(V sqrt(V)) 算法。

提前致谢。

我正在用 CPLEX（使用 Java）解决一个经典的网络流问题。它包含约束 Ax=b（A 是节点弧关联矩阵，x 是链路流的决策变量，b 是给定的右手边）。我对在一维中减少/减少 b 的阴影奖感兴趣。

在非退化问题中，影子价格由约束 Ax=b 上的对偶变量给出。但是，我的问题是退化的。因此，一个最优解可以由基础和非基础变量的几种组合来表示。这些组合中的每一个都应该有不同的对偶变量。

至少这些对偶中的一个应该给我 a 增加 b 的影子价格，另一个对偶将提供减少 b 的影子价格。（根据 W.Powell (1989)：“线性网络敏感性结果的回顾和减少退化影响的新近似”）

我的问题是：在用 CPLEX 求解 LP 并获得第一组对偶后，如何让 CPLEX 执行基变量和非基变量的交换，以便获得另一组对偶？

我正在研究SDN和NFV。

在 Wikipedia 上的 NFV 概念中，它说：“网络功能虚拟化（NFV）是一种网络架构概念，它提出使用 IT 虚拟化相关技术，将整个网络节点功能类虚拟化为可以连接或链接的构建块，共同创造通信服务。”==> 首先要考虑的是它会降低设施成本。

那么在现实生活中，例如，我们如何像路由器一样虚拟化网络节点？

NFV 是为能够以动态方式（虚拟化路由器）而不是静态方式（购买新路由器）扩展网络而创建的，也就是说，我们必须在服务器或计算机中实现路由器功能，而不是购买和然后让新路由器适应当前的下一个工作，在这种情况下，我看不出这个实现有什么不同，因为购买服务器来实现虚拟化路由器并不比购买新路由器便宜。

谁能为我解释一下，还是我对 NFV 概念的理解有误？

谢谢。

我正在练习我书中的算法问题并遇到了这个问题：

给定一个有 n 个节点和 m 个边的有向网络 G，一个源 s，一个汇 t 和一个从 s 到 t 的最大流 f。假设每条边的容量都是一个正整数，描述一个 O(m + n) 时间的算法，用于在以下两种情况下更新流 f。

(i) 边 e 的容量增加 1。

(ii) 边 e 的容量减少 1。

看起来就像遍历网络流边缘和调整流一样简单，但我认为这并不是那么简单。维基百科只给出 O(n^2 m) 或 O(nm^2) 的算法。任何帮助或想法将不胜感激。

我正在解决一个优化问题，除其他外，我必须最大化流网络。我实现了一个基于 C++ 代码的流最大化算法，该算法基于Sedgewick “Java 中的算法，第三版，第 5 部分：图形算法”一书中出现的以下java 代码，该算法使用基于顶点的 PREFLOW- 最大化网络流-推送算法：

我的实现，基于那段代码，无法最大化下面的网络 执行后，产生的流程如下 有了这个流程，流量值是8，但是最大值是9，如下图的 流程 所示 据我了解，该算法与书中的解释是一致的。但是，我看到了两件奇怪的事情

1. 源中没有明确的预流阶段。当谓词为真时，它被包含在while并首先执行一次。P > 0 && v == s也许这样做是为了缩短代码
2. 根据我的理解和书中的论述，sink 永远不会进入队列。但是，当高度增加时，代码会检查 v != t。这有什么原因吗？

这是我在 C++ 中实现该算法的摘录

¿ 有人发现我的代码和 Sedgewick 的代码之间存在逻辑上的不一致？我的印象是我的代码（也许还有 Sedgewick）没有正确处理高度的增加。但我不明白为什么

我展示了无法最大化的网络的详细执行跟踪（跟踪从 while 的第一个 q.get() 开始。括号中的值是高度的值。IN 是到节点的传入流。OUT即将到来的一个。

例如，该行

指符合条件的弧 4104-->0。节点4104的高度为2，节点0的高度为1。表述“推1”意味着1个单位的流被推向目标节点(0)。该行================分隔每个队列提取。队列是先进先出的，其状态在每次处理结束时打印。

请注意，多次推送或减少零流量单元，但目标节点变为活动状态。

这是执行跟踪

我是 python 新手，我有这个有向图，几乎有 2109 个节点和 6322 条边，在每次迭代中，我在每次迭代中改变一些节点的需求和一些边的权重，使用：
def ChangeTheNodes()：

def ChangeTheEdges():

代码需要几个小时才能给我图表的最低成本发光，有没有办法加快速度？

假设我们有一个网络，节点 A 向节点 B 发送 2 个数据包，出于安全原因，我们希望这两个数据包有不同的路径到达节点 B。如何使用最大网络流量来确定在给定网络中是否可行？

我想我应该考虑所有容量，如果两个数据包必须通过公共边缘，则最大网络流量将为 1，并且给定的网络将无法执行此任务，否则它有能力。但我不确定是考虑所有边缘的容量是真的吗？

假设我们有一个二进制矩阵（只有零个或一个元素）。给定元素的相邻元素是该元素上方、下方、左侧和右侧的所有 4 个元素（如果它们存在）。反转是一对其数量不同且相邻的矩阵。矩阵的成本为 b*q，其中 b 是自然数，q 是反转的数量。我们可以通过 a 的代价翻转任何元素。所以我们想要最小化 x*a + q*b 其中 x 是翻转元素的数量。

我想我可以将所有元素视为节点和连接到所有零元素的源和连接到所有元素的接收器。但是我可以找到一种定义节点之间的边并定义它们的容量的好方法，直到网络流问题的答案成为原始问题的答案

我已经阅读了这两个问题：link1 link2

还有这个维基百科

但我不明白如何解决最大匹配问题来解决最小路径覆盖。我知道解决方案是 nm，其中 n 是 G 中的顶点数，m 是最大匹配，但我找不到原因