algorithm - 两组大小截然不同的顶点的最大加权二分匹配

Question

抽象问题

我想在一个完整的加权二分图中找到最佳的最大匹配，其中两组顶点的大小差异很大，即一组顶点非常大而另一组顶点非常小。

Hungarian algorithm这不是解决这个问题的好方法，因为它向较小的集合添加了虚拟顶点，使得两个集合具有相同的大小，所以我失去了一个顶点集非常小的所有潜在效率增益。

更具体

我已将对象(边界框)分成两组，并且我有一个相似性度量(Jaccard 重叠)来衡量任何两个对象的相似程度。我想生成两个集合之间的匹配，使得所有单个匹配的相似度之和最大。

问题是其中一个集合只包含很少的对象，比如 10 个，而第二个集合非常大，比如 10,000 个对象。第一组中的 10 个对象中的每一个都需要与第二组中的 10,000 个对象中的一个匹配。

这两个集合大小的不对称让我想知道如何有效地做到这一点。我无法使用匈牙利算法生成 10,000 x 10,000 矩阵。

Answer 1

就可用软件而言，可能是最简单的方法:使用最小成本网络流求解器。这个公式对矩形成本矩阵没有问题!基本思想很简单，介绍是 here (一张幻灯片如下图所示):

有很多可用的软件(例如 Coin-OR Lemon/C++；Google 的 ortools/C++ 有很多包装器)。

Google 的 ortools 在 this 上也有自己的文档条目.

尽管如此，这本书:

Burkard, Rainer E., Mauro Dell'Amico, and Silvano Martello. Assignment problems, revised reprint. Vol. 125. Siam, 2009.

有一小章(5.4.4 矩形成本矩阵)概述了其他方法，主要是对其他线性分配算法的修改。

该章部分内容如下:

Alternatively, one can use the transformation to a minimum cost flow problem of Section 4.4.1, which does not require that vertex sets U and V have equal cardinality.