-3

我在二分图问题中遇到了最大匹配问题。问题是这样的：

给定一个有 m 个圆孔的板和一组 n 个圆盘。孔编号为 h 1 , ..., h m，圆盘编号为 d 1 , ..., d n。

我们有一个 m 行 n 列的矩阵 A。如果 h i可以拟合 d j（即 h i的直径≥ d j的直径），则 A[i][j] = 1 ，否则为 0。

鉴于任何孔最多只能包含一个圆盘的条件，我需要找到最大的孔盘拟合配置。

我读过这个问题可以建模为网络流量问题，但不能完全遵循。有人可以解释如何做到这一点吗？另外，是否有任何我可以查看的 C 代码？

4

1 回答 1

5

从二分匹配到最大流量的减少实际上是相当漂亮的。当你得到一个二分图时，你可以把这个图想象成两列节点，它们通过从第一列到第二列的边连接起来：

  A ----- 1
  B --\   2
  C    \- 3
 ...     ...
  Z       n

为了将问题减少到最大流量，您首先将所有边从第一列指向第二列，这样流量只能从左列向右移动。完成此操作后，您将引入两个新节点 s 和 t，它们充当源节点和终端节点。您定位 s 以便它连接到左侧的所有节点和 t 以便右侧的每个节点都连接到它。例如：

     A ----- 1
 /   B --\   2   \
s-   C    \- 3   - t
 \  ...     ...  /
     Z       n

这里的想法是，您可以从 s 到 t 的任何路径都必须输入左列中的一个节点，然后越过某个边缘到右列，然后从那里到 t。因此，从匹配路径和 st 路径中的一条边有一个简单的一对一映射：只取从 s 到边源的路径，然后沿着边，然后沿着从端点到节点的边吨。此时，我们的目标是找到最大化从 s 到 t 的节点不相交路径数量的方法。我们可以使用如下的最大流量来实现这一点。首先，将离开 s 的每条边的容量设置为 1。这样可以确保最多有一个单位的流量进入第一列中的每个节点。同样，将穿过两列的每条边的容量设置为一，然后我们要么选择边，要么不选择，而不是可能以某种多样性来选择它。最后，将离开第二列的边的容量设置为 t 为 1。这确保了右侧的每个节点只匹配一次，因为我们不能将超过一个单位的流推过它。

构建流量网络后，使用任何标准算法计算最大流量。 Ford-Fulkerson是一个简单的算法，在这里表现很好，因为图中的最大流量等于节点的数量。它的最坏情况性能为 O(mn)。或者，高度优化的Hopcroft-Karp 算法可以在 O(m√n) 时间内完成此操作，这可能要好得多。

至于 C 实现，通过 Google 快速搜索 Ford-Fulkerson 步骤出现了这个链接。您需要先构建流网络，然后再将其传递到此代码中，但构建并不太复杂，我认为您应该不会有太多麻烦。

希望这可以帮助！

于 2011-08-30T00:58:18.950 回答