问题标签 [network-flow]

我正在尝试找到解决以下问题的算法。

假设我有许多对象 A、B、C、...

我有这些对象的有效组合列表。每个组合的长度为 2 或 4。

例如。AF、CE、CEGH、ADFG、……等等。

对于两个对象的组合，例如。AF，组合的长度为2。对于四个对象的组合，例如CEGH，组合的长度。

我只能选择不重叠的组合，即我不能选择 AF 和 ADFG，因为它们都需要对象“A”和“F”。我可以选择 AF 和 CEGH 的组合，因为它们不需要公共对象。如果我的解决方案仅包含 AF 和 CEGH 两个组合，那么我的目标是组合长度的总和，即 2 + 4 = 6。

给定一个对象列表及其有效组合，我如何选择不相互重叠的最有效组合，以便最大化组合长度的总和？我不想将其表述为 IP，因为我正在处理具有 180 个对象和 1000 万个有效组合的问题实例，并且使用 CPLEX 解决 IP 的速度非常慢。寻找其他优雅的方法来解决它。我可以将其转换为网络吗？并使用最大流算法解决它？还是动态程序？不知道如何解决这个问题。

有供应商 P1 到 Pm，他们分别有 A1 到 Am 苹果。和用户 U1 到 Un，他们分别需要 D1 到 Dn 个苹果。

每个提供商都与某些用户（其中​​一些，不是全部）有联系。用户可以从不同的供应商处获得苹果。

问题是，我们可以通过哪种方式满足大多数用户？

很抱歉描述不清楚。只有一种资源，一个用户只能有一个需求。

我得到一个流网络 G 和它们的（边缘）容量和（边缘）流过每个边缘，还有一个流 F。我想检查残差图中是否存在从源到目标的路径以便找到如果 F 是最大流量，则输出。

是否有可能在 O(E) 时间内完成？

有人可以给我一些帮助吗，也许表明我应该这样做？

• 已编辑

所以我正在研究一个网络流问题，并且必须能够删除我的二分图的右半部分才能一次处理多个图。这是我设置节点和边缘类的方式：

在这张图片中可以看到一个潜在的图表：

我的目标是删除第二列右侧的所有边和节点。

我将所有节点组织在节点指针向量中，从左到右/从上到下索引，我试图遍历该向量并删除节点邻接列表中包含的第二和第三列中的任何边或第三和第四列。之后我将向后遍历并删除汇节点以及第三列的节点，然后最后调整节点向量的大小以仅容纳前两列节点。

我是这样做的：

我在编译时遇到的错误是：

我很可能只是没有正确理解我的指针，因为我最近没有处理过这样的释放内存。无论如何，我哪里错了？任何帮助是极大的赞赏。

要点是......我们有两组点A和B。集合A和B具有相同数量的点n。

正式问题：

在A和B中的点之间构造最小成本完全二分匹配。匹配(a, b)的成本是距离 (a, b)。是否存在比O(n^3)更快的算法？

笔记：

• A中的每个点a和B中的每个点b都在匹配(a, b)中。
• A或B中的每个点a都恰好在一个匹配中。
• sum( 每一个(a, b)匹配的距离(a, b ) )被最小化。

例子：

• 点 a (0,0)
• b 点 (2,0)
• 点 c (0,1)
• 点 d (-2,2)
• 设置 Z {a, d}
• 设置 Y {b, c}

解决方案：

匹配1：（a，b）（d，c）

sum (距离(a, b),距离(d, c)) = 2 + sqrt(5) ~ 4.23

匹配2：（a，c）（d，b）

sum (距离(a, c),距离(d, b)) = 1 + sqrt(20) ~ 5.47

匹配 1 (a, b) (d, c) 是最小成本完全二分匹配！

我正在尝试实施“最低成本网络流量”运输问题解决方案R。

我知道这可以使用类似lpSolve. 但是，我看到“最大流量igraph”有一个方便的实现。这种预先存在的解决方案会方便得多，但我找不到最小成本的等效功能。

是否有igraph计算最低成本网络流量解决方案的函数，或者有没有办法将该igraph::max_flow函数应用于最低成本问题？

igraph网络示例：

这是一个有方向边的网络，一个“源节点”（1）和一个“汇节点”（9）。每条边都有一个“容量”（这里通常设置为 99 表示无限）和一个“成本”（一个单元流过该边的成本）。我想找到流的整数向量（x，长度 = 9），它在通过网络传输预定义流（假设 50 个单位，从节点 1 到节点 9）时最小化成本。

免责声明：这篇文章问了一个类似的问题，但没有得到令人满意的答案，而且过时了（2012 年）。

I'm considering using cvxopt to solve some nonlinear network flow optimisation problems. In order to understand the basics, I am trying it with a very simple test network with just 4 vertices and 5 edges.

My network looks like this. The blue and red nodes are a source and sink respectively.

The cost on each edge is:

where x is the vector containing the flow on each edge, and alpha is some coefficient. My optimisation problem is then:

where E is the edge-arc incidence matrix and b is the vector containing sources and sinks. The matrix-vector equation Ex = b should therefore just enforce Kirchoff's laws (i.e. conservation of flow at each node).

My python script to do this is:

The error I get is:

I am unsure how to proceed from here. I assumed this optimisation problem would be soluble with cvxopt, since it is simple enough to find the optimal flow by hand. I would appreciate it if somebody could tell me how to rectify this code, or else tell me why this type of problem is not suitable for this software.

Thanks in advance.

我正在学习计算机科学/运筹学，现在我对最大流量问题感兴趣。我写了一个算法来解决这个问题，但在计算复杂度方面遇到了麻烦。Python-esque 伪代码如下：

其中 graph.capacity(a,b) 表示从 a 到 b 的弧的容量。要找到总最大流量，可以将该算法称为 max_flow(graph,graph.source,infinity)。

我向自己证明了该算法是正确的（尽管如果这也是错误的，请随时纠正我），并且我对复杂性的信念是该算法在 O(|V| ² ) 中运行，其中 |V| 是顶点的数量。理由是：

1. 在最坏的情况下，每个节点都连接到其他每个节点，因此它是一个完整的有向图。这意味着每个节点最多有 |V| - 1 条边。但是，由于倾斜对称性，如果从 a 到 b 的容量为正，则从 b 到 a 的容量必须为负。所以，如果源有 |V| - 1 个正容量边，那么次高节点最多可以有 |V| - 2 个正容量边，因为至少一个边必须具有负容量。因此，正容量边的总数最多为 (|V|-1)*(|V|-2) / 2 = O(|V| ² )。

这就是我卡住的地方。直觉上，这听起来像是经历了每一个 |V| 节点最大 |V| 次，结果为 O(|V| ² )。然而，我的一部分认为实际的复杂性是 O(|V| ³ )，但我找不到任何严格的解释。有人可以推动我朝着正确的方向前进吗？

注意：这些都不是家庭作业，也不是任何课程的一部分。

给定一个网络流 G(V,E)。在我们运行 FF 算法并得到一个残差 grpah Gf 和一个 min-cut (S,T)

我想知道边 E′⊂ E 的最小数量，这样每个 e ∈ E 的容量增加一个单位将使最大流量增加到 val(f)+1。该算法应该在 O(E*log(V)) 中运行。

这是我的方法。

对于每个交叉边 (u,v)

(1) 使用 BFS 找到 u 的部分增广路径 s；以及从 v 到 t 的所有部分增广路径。如果两个这样的部分增广路径都存在。然后增加（u，v）可以使最大流量增加一。

如果 (1) 为假，

可能性很小

(a) 在残差中，源 s 没有出边

(b) 在残差中，sink t 没有传入边。

(c) 以上两种情况都发生

在 (a) 的情况下，最小切割有一组仅包含源 s。找到从交叉边缘到 t 的最短路径，这个距离 + 1（交叉边缘）将是我们的最小值。通过在 O(E*log(V)) 时间内使用 Dijlstra 算法

在 (b) 的情况下，类似地，找到从交叉边缘到 t 的最短路径（假设这个交叉边缘是 (u,v) 和 T 中的 v，v 到 t 是所有交叉边缘的最短路径），这距离 + 1 + 从 s 到 u 的最短路径的距离 = 将所有容量增加 1 的最小边数，导致最大流量增加 1

在 (c) 的情况下，我们需要寻找从 s 到 t 的最短路径；我们可以在 O(E*log(V)) 时间内应用 Dijlstra 算法。

但是，我认为上述方法可以达到目标但效率不高（特别是在处理情况（2）时，它可能无法在 E*log(V) 时间内运行）。

有没有更容易接近的方法？

我正在尝试实现“ Beyond the Flow Decomposition Barrier , 1988”中描述的 Goldberg-Rao maxflow 算法。论文说我们正在寻找可接受弧上的流动。

要找到弧的长度，我们需要以下计算：

在算法计算期间，F 只能减小。所以，如果有大容量的弧，它们将永远不会被接受，我们将无法推动流通过它们。
在示例中 F = 5, lambda = 1.7, Δ = 3 - 所以从 2 到 T 的容量为 10 的弧是绝对不允许的。
有谁知道如何解决这个问题？以及弧的上限容量的限制究竟是如何改进最大流搜索的？