11

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

简单示例图。 来源：<jwezorek.com/wp-content/uploads/2013/09/min_flow.png>

在文献中，这是一个最小成本流问题。然而，在我的情况下，成本与每个边缘所需的流量的非零下限相同，因此我将问题表述为上述问题。在文献中，问题是：找到单源/单汇有向无环图的最小成本流的最佳算法是什么，其中每条边具有无限容量，流的非零下限，以及成本等于流量的下限。

从我的研究看来，人们处理任何类型网络的任何类型的最低成本的主要方式是将问题设置为LP 类型的问题并以这种方式解决。然而，我的直觉是，没有流量上限，即具有无限容量的边缘，会使问题变得更容易，所以我想知道是否有一种算法专门针对这种情况，使用比单纯形法等更多的“图形”技术. 人。

我的意思是，如果所有成本和下限都是 1，如上...然后我们正在寻找一个覆盖所有边缘的流，遵守流规则，并且不会通过从 s 到 t 的任何路径推动过多的流. 对我来说，这只是感觉它不应该需要 LP 求解器，事实上，维基百科关于最小成本流的文章指出“如果消除容量限制，问题就会简化为最短路径问题”，但我认为他们正在谈论下界全为零的情况。

还有开源 C/C++ 代码可以在任何地方实现最低成本吗？通过谷歌搜索可用的内容，我发现我可以自己将问题设置为 LP 问题并使用开源 LP 求解器进行求解，或者我可以使用 LEMON，它为最小成本流提供了几种算法。据我所知，boost 图形库不包含实现。

还有别的事吗？

4

3 回答 3

8

在没有上限的情况下，最简单的方法——最容易实现、理解并且相当有效——找到图的最小流如下：

  1. 找到一个可行流，即满足流规则和流下界但不一定是最小流的流。这可以通过对图进行深度优先遍历来实现，在我们遍历时跟踪当前路径，并在访问先前发现的节点或目标节点 t 时，将当前路径上的流量增加为最大下限- 当前路径上不满足的边的边界一直到 t。

  2. 通过解决最大流问题将可行流变成最小流。您需要在图上找到容量等于 flow(e) - lower-bound(e) 的最大流量，其中 flow(e) 表示来自可行流量的流量。从可行流量中减去的最大流量将是最小流量。

在图也具有流量上限的情况下，也可以执行上述的一个版本。在这种情况下，步骤 1. 更复杂，但可以通过在特殊构造的图上执行初始最大流量计算来解决。

于 2013-11-13T20:16:10.357 回答
3

编写求解器并非易事。

请参阅 LEMON 库（COIN-OR 的一部分）。它有许多针对最小成本流问题的高度优化算法。您可以选择最适合您的数据的算法。

有关 LEMON 的信息，请参阅http://lemon.cs.elte.hu/trac/lemon。

有关最低成本网络流量的详细信息，请参见http://lemon.cs.elte.hu/pub/doc/1.3/a00607.html。

于 2013-10-28T20:48:05.517 回答
1

在每条边上添加流的所有“下限”：无论如何，任何可行的解决方案都需要它。

n对于从 sink 开始按拓扑顺序（即沿边）的每个节点t，如果流入S-边的总和大于S+流出的总和，则S+ - S-在s和t(为提高效率而构建最短路径列表）。

然后，您有一个“最小”分配（在每个可行解决方案中都需要它的意义上），例如S+ - S-在每个节点上都是非负的，并且在每个边上都满足最小容量。

然后问题简化为同一图结构上的多流问题：

  • 来源是一样的；
  • 没有容量限制；
  • 每个S+ - S-严格为正的节点都成为具有所需流量的接收器S+ - S-。
  • 如果为非负数，则初始接收器（具有所需的流量F）变为具有流量的接收器（否则任何解决方案都将满足初始约束）。F - S-F-S-

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

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

每个边缘的最小容量为 1，我想 sink 不需要最小流量t。

首先为每条边分配 1。

每个节点的区别S+ - S-（当然，s和除外t）是：

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

唯一的负面因素是x4; 我们添加到从到1的最短路径上的每条边，在这种情况下到边。x4t(x4, t)

NowS+ - S-对于每个节点都是非负数，并且仅对x1; 问题简化为多流问题（在这种情况下，它是一个简单的流问题），其中请求的流1位于x1，而源仍然是s。

于 2013-09-06T09:07:13.510 回答