2

我正在阅读增广路径或库恩算法，以在未加权的二分图中找到最大匹配大小。

该算法试图找到一条交替路径（由交替的不匹配和匹配的边组成）在不匹配的顶点处开始和结束。如果找到交替路径，则增加路径并且匹配计数增加 1。

我可以理解该算法，但是我在理解它的一般实现方式方面存在问题。这是一个参考实现 - https://sites.google.com/site/indy256/algo/kuhn_matching2。

在每个阶段，我们都应该尝试从左侧不匹配的顶点开始找到一条交替路径。然而，在给定的实现中，在每次迭代中，我们不是尝试所有不匹配的顶点作为可能的起始位置，而是只从一个不匹配的顶点开始搜索，如下面的代码所示 -

for (int u = 0; u < n1; u++) {
      if (findPath(graph, u, matching, new boolean[n1]))
        ++matches;
    }

这样，在其迭代期间不匹配的左侧顶点将永远不会再次尝试。我不明白为什么这是最优的？

4

2 回答 2

1

证明算法结束后不存在增广路径就足够了。因为没有增加路径意味着最大流量。假设 A[i] 作为左侧第 i 个顶点，而 B[i] 作为右侧第 i 个顶点。

如果 A[i] 已经匹配，那么它将在任何增广路径中保持匹配。

因此，我们唯一担心的是，当我们考虑 A[i] 并没有找到匹配项时，但在 for 循环中进行了一些迭代后，A[i] 突然有了新的扩充路径。我们将证明它永远不会发生。

让我们考虑 A[i] 之前没有增广路径，并将 S 称为 dfs(i) 可以访问的顶点集。之后只有两种方法可以将新顶点（之前不在 S 中）包含在 S 中。

  1. 对于 S 中的某些 A[x]，边 A[x] - B[y] 由匹配变为不匹配（B[y] 之后将包含在 S 中）

    矛盾。因为我们应该找到增广路径 B[y] - A[x] - ... - Sink，但 Sink 不在 S 中，所以我们不能这样做。

  2. 对于 S 中的一些 B[y]，边 B[y] - A[x] 由不匹配变为匹配（A[x] 之后将包含在 S 中）

    又是矛盾。这一次，我们应该找到增广路径 A[x] - B[y] - ... - Sink，但同样，我们无法从 B[y] 到达 Sink。

由于上述原因，不可能意外离开意味着最大流量的增广路径。

于 2016-12-08T15:49:44.097 回答
0

根据我的理解，该算法试图为每个左顶点 u（从 0 到 n1-1）找到一条增广路径。如果存在这样的路径，则可以将 u 添加到匹配中，同时将所有先前添加的顶点保留在匹配中。如果不存在这样的路径，则无法将 u 添加到匹配中。这源于增广路径的特殊性质。

当我们检查每个 u 时，我们发现可能添加到匹配中的最大顶点数，从而得到最优性保证。

于 2016-08-13T02:59:50.430 回答