最大流量和最大流量有什么区别。我在研究福特富尔克森算法时正在阅读这些术语，它们非常令人困惑。我在互联网上尝试过，但无法得到合理的答案。我相信最大流量很清楚，因为它意味着可以在网络中从源传输到接收器的最大流量，但最大流量到底是什么。
如果可能，请用外行的方式回答。
谢谢。
1 回答
3
简短的回答：
想想山顶，每一个都是极大解，附近没有比他们高的地方，只有珠穆朗玛峰的高度最大，因此是极大解。
更长的答案：
让我用几何术语来解释它：想象一个平面（例如一张大的纸）。平面上的每个点都是该问题的可能解决方案。每个点的高度就是该点对应的解的质量。在优化中我们要找到最优解，即平面上的最高点。找到最优解的一个想法是从平面上的一个可能解开始并一点一点地改进它：每次我们从一个点移动到它附近的一个更高的点。这称为局部搜索算法。当我们到达一个高于它附近所有点的点时，这个过程就会停止。这样的点称为局部最优值。相应的解决方案称为最大解决方案，因为我们无法通过移动到它附近的任何解决方案来提高解决方案的质量。然而，一个最大的解决方案没有
有一些共同条件，如果满足，我们将不会在平面上出现局部最优，而这些局部最优不是全局最优。在这种情况下，我们可以使用局部搜索算法来找到最优解。一个这样的条件是，如果解的平面是凸的，直观地说，对于每两个点，我们在线上的所有点也在解空间中连接它们，并且每个点的质量都可以从点到解的相对距离来确定两个端点和两个端点的质量。在凸优化中研究了凸空间上的优化。
现在，让我们回到最大流量问题。修复一个图表作为输入。将满足容量和保持流量要求的每个流量视为一个点。我们称这些有效流。我们想找到一个最大流量。如果我们可以通过增加或减少从源到汇的路径的流量来获得一个点，则两个点彼此靠近。
我们可以从所有边上的流量为零的流程开始（这是一个有效的流程）。在每一步中，我们以某种方式（例如使用 BFS）在更新的剩余容量图中找到从源到接收器的路径（每条边的权重是其未使用的容量量），并通过添加这个来增加流量. 这给了我们一个局部搜索算法。问题是解决方案的空间不是凸的，我们最终可能会得到一个无法再增加的流量，但它不是最大流量。
我们能做什么？一种想法是将解空间更改为凸解空间。凭直觉想想飞机上的一颗星星。恒星内部的点不会形成凸空间，但我们可以通过在解决方案空间中包含更多点并将其变成五边形来将其变成凸空间。
这基本上就是我们通过将图的原始边上的现有流视为新边（称为残差边）所做的事情，其中流过它们对应于减少原始边上的现有流。这使得空间凸出，我们的局部搜索算法不会卡在局部最优但不是全局最优的解决方案上。
于 2014-04-26T20:57:11.327 回答