之间有什么差别最大的流量和最大流？

Question

之间有什么差别最大的流量和最大的流动。我阅读这些条款的工作时，在福特Fulkerson算法和它们是相当令人困惑。我试图在互联网上，但是不能得到一个合理的答案。我认为最大的流量是相当清楚的，因为它意味着最大数量的流动，可以被转移，从来源到水槽的一个网络，但究竟什么是最大的流动。

请回答在外行条款，如果可能的。

谢谢。

Answer 1

简短的回答：

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

再回答：

让我解释一下它在几何条款：想想一个面(例如一个大型和平的纸张)。每个点在飞机上是一个可能的解决方案的问题。高度的每一点是质量的方案对应于这一点。在优化我们要找到最佳解决方案，即最高点上飞机。一个想法，以找到最佳解决方案是开始从一个可能的解决方案在飞机 改善这一点一点:每次我们从一点向附近的一个，它是更高。这就是所谓的本地搜索算法。这个过程停止的时候，我们达到这一点是高于所有的点附近。这一点被称为当地最佳的。相应的解决方案是被称为最大，因为我们无法提高质量的方案，通过移动到任何解决办法靠近它。然而，一个最大的解决方案不需要是最佳的解决方案， 它是最佳的，相较于邻国。

有共同的条件，如果不满意 我们将不具有本地optimals在飞机上而不是全球optimals.在这种情况下，我们可以使用当地的检索算法，以找到最佳解决方案。这样的一个条件是，如果飞机的解决方案是凸的， 直观，用于每两点我们有点线路上接他们 也在解决空间和 质量的每一个他们可以确定 相对距离的点两端点和 质量的两个终点。优化过凸空间研究中 凸优化.

现在，让我们回到最大的流动问题。修复的图表为的输入。认为每一个流动，满足能力和保存流程 要求作为一个点。我们呼吁这些有效的流动。我们希望找到一个最大的流动。有两点是互相靠近如果我们可以获得一个通过增加或减少 通过流动的路径从来源到水槽。

我们可以开始由流的流量在所有的边缘都是零 (这是一个有效的流程)。在每一个步骤，我们找到一个路径从来源到水槽在更新后的剩余能力图表(每个边缘是该数额的其能力，不被使用) 以某种方式(例如使用BFS)和增加流动通过加入这一点。这给了我们一个当地搜索算法。问题是，空间解决方案是不凸和 我们可以结束了一个流动 我们不能增加的任何更多的但是它不是一个最大的流动。

我们可以做些什么呢？一个想法是改变的空间解决方案，以凸之一。直觉思考一个星上飞机。点内的星不使凸空间 但我们可以把它变成一个凸空间，包括更点在我们的空间解决方案 并且把它变成一个五角大楼。

这基本上是我们做的通过考虑现有的流上 原边缘的曲线图 作为新的边缘(称为 剩余的边缘) 这里流过它们相当于减少现有的流动对原的边缘。这使得空间凸和我们当地搜索算法不遇到的解决方案 这是当地最佳的，但不是全球最佳的。