algorithm - 最大流量和最大流量有什么区别？

Question

最大流量和最大流量有什么区别。我在研究 Ford Fulkerson 算法时正在阅读这些术语，它们非常令人困惑。我在互联网上尝试过，但无法得到合理的答案。我相信最大流量非常清楚，因为它意味着可以在网络中从源传输到接收器的最大流量，但最大流量到底是什么。

请尽可能通俗地回答。

谢谢。

Answer 1

简答:

想想山顶，他们每个人都是一个最大的解决方案，附近没有比他们高的地方，但只有珠穆朗玛峰的山顶有最大的高度和因此是最大解。

更长的答案:

让我用几何术语解释一下:想想一架飞机(例如一大张纸)。平面上的每个点都是问题的可能解。每个点的高度就是该点对应解的质量。在优化中，我们希望找到最优解，即平面上的最高点。找到最佳解决方案的一个想法是从平面中的可能解决方案开始，并且一点一点地改进它:每次我们从一个点移动到它附近的一个更高的点。这称为局部搜索算法。当我们到达一个高于它附近所有点的点时，这个过程就会停止。这样的点称为局部最优。相应的解决方案称为最大解决方案，因为我们不能通过移动到它附近的任何解决方案来提高解决方案的质量。但是，最大解不一定是最优解，与其邻居相比，它是最优的。

有一些共同的条件，如果满足我们不会在平面上有非全局最优的局部最优。在这种情况下，我们可以使用局部搜索算法来找到最优解。一个这样的条件是如果解决方案的平面是凸的，直观地，对于每两个点，我们将所有点都连接到线上也在解决方案空间和他们每个人的质量可以从确定点到两个端点的相对距离和两个端点的质量。在 convex optimization 中研究了凸空间的优化.

现在，让我们回到最大流问题。将图形固定为输入。想想每一个满足流的容量和保存的流要求作为一个点。我们称这些为有效流。我们想找到最大流量。如果我们可以通过增加或减少获得一个点，则两个点彼此靠近通过从源到汇的路径的流。

我们可以从所有边上的流量都为零的流量开始(这是一个有效的流程)。在每一步，我们都会在更新后的剩余容量图中找到一条从源到汇的路径(每条边的权重是未使用的容量)以某种方式(例如使用 BFS)并通过添加它来增加流量。这给了我们一个本地搜索算法。问题是解决方案的空间不是凸的我们可能会以流程结束我们不能再增加了，但这不是最大流量。

我们能做什么？一种想法是将解决方案的空间更改为凸空间。凭直觉想想飞机上的一颗星星。星内的点不构成凸空间但是我们可以通过在我们的解决方案空间中包含更多点来将它变成一个凸空间并将其变成五边形。

这基本上就是我们通过考虑现有流程所做的事情图的原始边作为新边(称为剩余边)其中流过它们对应于减少原始边缘上的现有流量。这使得空间凸出，我们的局部搜索算法不会卡在解决方案上这是局部最优但不是全局最优的。