logo标签列表

我应该使用哪种算法来查找在有流量下限但没有流量上限的有向图中的最小流量？

c++graph-algorithmlinear-programmingnetwork-flow
11

我应该使用什么算法来在有流量下限但没有上限的有向图中找到最小流量？例如这个简单的例子：

Diagram of simple example. Source: <jwezorek.com/wp-content/uploads/2013/09/min_flow.png>

在文献中，这是一个最小费用流问题。然而，在我的情况下，成本与每条边上所需的非零下限流量相同，因此我将问题表述如上。在文献中，问题是：找到单源/单汇有向无环图中最小费用流的最佳算法，其中每条边具有无限容量、非零下限流和等于下限流的成本。
从我的研究来看，人们处理任何类型网络的最小费用的主要方法是将问题设置为LP类型问题并以这种方式解决。然而，我的直觉是，没有流量上限，即具有无限容量的边使问题变得更容易，因此我想知道是否有一种专门针对这种情况使用更多“图形”技术比单纯法等的算法。
我是说，如果所有成本和下限都像上面一样为1...那么我们正在寻找一种涵盖所有边缘的流，遵守流规则，并且没有将太多的流量通过从s到t的任何路径。对我来说，这似乎不需要LP求解器，事实上，维基百科关于最小成本流的文章指出：“如果容量约束被移除，则问题将简化为最短路径问题”，但我认为他们谈论的是所有下限都为零的情况。
此外，是否有开源的C/C++代码用于最小成本流？通过搜索可用内容，我发现我可以将问题设置为自己的LP问题并使用开源LP求解器进行求解，或者我可以使用LEMON，该软件提供了几种用于最小成本流的算法。据我所知，boost图书馆不包括实现。
还有其他需要注意的吗？
3
标题上的漂亮星星，哈哈。 - Natan Streppel
我其实不知道那颗星星是从哪里来的... - jwezorek
3个回答
9
在没有上限的情况下，找到一个图的最小流量的最简单的方法 -- 最容易实现，理解且效率合理 -- 如下所示：
  1. 寻找可行流，即满足流规则和流下限但不一定是最小流的流。这可以通过对图进行深度优先遍历并在遍历时跟踪当前路径，在访问先前发现的节点或t（目标节点）时，将当前路径上所有未满足边缘的最大下限增加到t。
  2. 通过解决最大流问题使可行流变成最小流。您需要找到具有与可行流相等的容量的图的最大流，其中flow（e）表示从可行流中流出的流。从可行流中减去此最大流将是最小流。
如果图也具有流量上限，则可以执行上述版本。在这种情况下，步骤1更复杂，但可以通过在特殊构建的图上执行初始最大流计算来解决。
这种方法似乎可行。有人能解释一下为什么最小流量等于可行流量减去最大流量，就像上面的答案所述吗？我不确定这是为什么。 - devosc
1
如果你从可行流中尽可能地取走了流量，那么你所剩下的必须是最小流，根据最小流的定义。如果你可以取走更多的流量，它就不会是最小值了，但你不能这样做，因为你已经取走了可能的最大值。 - jwezorek
3
建立一个像LEMON这样的图算法库比建立一个求解器要复杂得多，只是Dijkstra/SPFA算法的F倍。如果有其他人在寻找解决方案，可以参考https://github.com/ruippeixotog/algo-lib/blob/master/min-cost-max-flow.cpp，会更容易。（LEMON的NetworkSimplex方法在稀疏/随机图上启发式地快10倍，但对于大多数情况来说这是不必要的，并且在最坏情况下具有较弱的Big-O界限） - undefined
1
在每条边上添加所有流量的“下界”：任何可行解都需要这样做。
对于拓扑顺序中的每个节点n（即按照边的顺序）从汇t开始，如果进入边的总和S-大于外出的总和S +，则在s和t之间的最短路径的所有边上添加流量S + - S-（在执行此操作时构建最短路径列表以提高效率）。
然后，您将获得一个“最小”的分配（在每个可行解中都需要），例如，在每个节点处，S + - S-为非负数，并且在每个边上满足最小容量。
然后，问题就变成了同一图结构上的多流问题：
  • 源相同；
  • 没有容量限制；
  • 每个节点，其中 S+ - S- 严格为正，都成为一个汇点，其所需的流量为 S+ - S-。
  • 如果 F-S- 非负（否则任何解决方案都将满足初始约束条件），则初始汇点（其所需流量为 F）将成为具有流量 F - S- 的汇点。

编辑：对于您的问题，图像如下所示：

     x1 -- x2
   /   \     \
 s      \     t
   \     \   /
     x3 -- x4

每条边的最小容量为1，我假设在汇点 t 处不需要最小流量要求。

首先将每条边的权值赋为1。

每个节点（当然除了 s 和 t）的差异 S+ - S- 是：

x1: 1
x2: 0
x3: 0
x4: -1

唯一的负数是x4的；我们将最短路径上从x4到t的每条边加上1，在这种情况下，是对边缘(x4,t)进行操作。

现在，对于每个节点，S+ - S-都是非负数，仅对x1为正；问题转化为多流问题（在这种情况下为简单的流问题），其中所请求的流量是在x1处的1，源仍然是s。

那么f是流分配，其中每条边上的流量恰好等于下界吗？ - jwezorek
f 不会是合法的流，这意味着对于给定节点，入流量不等于出流量。因此，仅仅沿着从 s 到 t 的最短路径增加 f 并不一定会导致合法的流。那么对于 f 中未满足流量守恒的节点，例如不在最短路径上的节点，该怎么办呢？ - jwezorek
是的，你说得对。我现在尝试适应这个解决方案，如果它有效，我会编辑答案。 - Nicolas Grebille
抱歉，我不太明白...对于我发布的示例问题图表，最小分配看起来是什么样子？它会产生哪些多流问题？您能否发布您提出的算法步骤的图表 - 我可以从中理解。 - jwezorek
我添加了你的问题示例（我假设初始问题中没有必要在水槽中流动）。 - Nicolas Grebille
问题中的任何节点都没有必要流动，只有边缘需要。您将问题简化为一个没有容量或下限的多汇最小化问题，因此它变成了最短路径？这正确吗？ - jwezorek
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接