最大流和最大流量有何区别？

Question

最大流和最大化流的区别是什么？我在学习Ford Fulkerson算法时遇到了这些术语，感到很困惑。我在互联网上搜索过，但没有得到合理的答案。我相信最大流是很清楚的，它意味着可以从源到汇点传输的最大流量，但是什么是最大化流呢？

如果可能的话，请用通俗易懂的语言回答。

谢谢。

- Ambidextrous

---

“Maximal”通常用于表示“我不能再增加了”的意思。最大值的意思是“没有比这更大的了”。因此，最大流量是指在不降低某些边缘上的流量的情况下，无法将更多的流量推送到目标的流量。而最大流量则是指具有最高流量值的流量。此外，不鼓励进行交叉发布。 - G. Bach

谢谢回答。好的，我不知道关于跨帖规则的事情，以后会注意的。 - Ambidextrous

如果您不确定在哪个网站发布帖子，Stack Exchange 网络的每个网站都有一个帮助中心，其中包含一个关于“我可以在这里问什么问题？”的章节。 - G. Bach

@Codor 在流程的上下文中，这两个词可能是可以互换使用的；我不确定。 - G. Bach

@user3097157，您能否提供您正在阅读的材料链接？Codor提到（尽管通常情况下，我上面提到的是两个术语的普遍用法），在涉及流程时，“maximal”和“maximum”可能可以互换使用。 - G. Bach

Answer 1

简短回答：

想象一下山顶， 每个山顶都是最大解决方案， 附近没有比它们更高的地方， 但仅珠穆朗玛峰的山顶具有最大高度和最大解决方案。

较长回答：

让我用几何术语来解释： 考虑一个平面（例如一张大纸）。 平面上的每个点都是问题的可能解决方案。 每个点的高度是对应解决方案的质量。 在优化中，我们要找到最佳解决方案，即平面上最高的点。 找到最佳解决方案的一个想法是从平面上的一个可能解决方案开始， 逐渐改进它： 每次我们从一个点移动到附近更高的点。 这被称为局部搜索算法。 当我们到达一个比其附近所有点都更高的点时，该过程停止。 这样的点称为局部最优点。 相应的解决方案称为最大值，因为我们无法通过移动到任何接近它的解决方案来提高解决方案的质量。 然而，最大解决方案不一定是最佳解决方案， 它与其邻居相比是最优的。

存在常见条件，如果满足这些条件，我们将不会在平面上有局部最优解而不是全局最优解。在这种情况下，我们可以使用局部搜索算法来找到最优解。这样的条件之一是如果解空间是凸的，直观地说，对于任意两点，我们都有连接它们的线上的所有点也在解空间中，并且可以通过相对距离和两个端点的质量确定每个点的质量。对凸空间上的优化进行了研究convex optimization。

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

我们可以从所有边的流量为零的流开始（这是有效的流）。 在每个步骤中，我们在更新后的剩余容量图中找到一条从源到汇的路径（每条边的权重是未使用的容量量），并通过添加此路径来增加流量。这给了我们一个局部搜索算法。 问题是解决方案空间不是凸的，我们可能会得到一个流，无法再增加任何流，但它不是最大流。

我们能做什么？ 一个想法是将解决方案空间更改为凸空间。 为了直观理解，考虑平面上的星形。 星形内部的点不构成凸空间，但我们可以通过在解决方案空间中包含更多点并将其转化为五边形来使其成为凸空间。

这本质上是我们通过将原始图的现有流量视为新边（称为残留边）的原始边来考虑的，其中对它们的流量对应于减少原始边上的现有流量。这使得空间变成凸空间，我们的局部搜索算法不会陷入局部最优但不是全局最优的解决方案中。

- Kaveh

---

您可能想在 [cs.se] 上发布您的算法问题。:) - Kaveh