algorithm - 加权二分匹配

Question

我知道有很多类似的话题。但他们中的大多数给我留下了一些疑问。我想要做的是找到完美匹配（或者在没有完美匹配的情况下尽可能接近完美），然后从所有可以匹配 n 个顶点中的 k 个的匹配中（其中 k 可能是最高的） )，我想选择尽可能高的总重量。所以简单地说我要说的是以下优先级：

1. 匹配尽可能多的顶点
2. 因为在大多数情况下（非加权）最大匹配是明确的，所以我想选择边缘权重总和最大的匹配。如果其中有几个重量相同，那么选择哪个并不重要。

我听说过 Ford-Fulkerson 算法。它是按照我描述的方式工作还是我需要其他算法？

Answer 1

如果您自己实现它，您可能想要使用Hungarian algorithm。存在更快的算法，但并不容易理解或实现。

Ford-Fulkerson 是一种最大流量算法；您可以轻松使用它来解决未加权匹配问题。将其转换为加权匹配算法需要额外的技巧；有了这个技巧，你就得到了匈牙利算法。

您还可以使用最小成本流算法进行加权二分匹配，但它可能效果不佳。还有网络单纯形法，但它似乎主要具有历史意义。