两组大小截然不同的顶点的最大加权二分匹配
Ale*_*lex 2 algorithm graph-theory matching bipartite graph-algorithm
抽象问题
我想在完整的加权二分图中找到最佳的最大匹配，其中两组顶点的大小差异很大，即一组顶点非常大，另一组非常小。
匈牙利算法不是解决此问题的好方法，因为它将虚拟顶点添加到较小的集合中，使得两个集合具有相同的大小，因此我失去了其中一个顶点集合非常小的所有潜在效率增益。
更具体地说
我已将对象（边界框）分为两组，并且有一个相似性度量（杰卡德重叠）来衡量任意两个对象的相似程度。我想产生两个集合之间的匹配，使得所有单独匹配的相似度之和最大。
问题在于，其中一组仅包含很少的对象，例如 10 个，而第二组非常大，例如 10,000 个对象。第一组中的 10 个对象中的每一个都需要与第二组中的 10,000 个对象中的一个进行匹配。
两组大小的不对称让我想知道如何有效地做到这一点。我无法使用匈牙利算法生成 10,000 x 10,000 矩阵。
就可用软件而言，可能是最简单的方法：使用最小成本的网络流求解器。这个公式对于矩形成本矩阵没有任何问题！基本思想很简单，这里有一个介绍（下图所示的一张幻灯片）：
有很多可用的软件（例如 Coin-OR Lemon /C++；Google 的ortools /C++ 以及许多包装器）。
Google 的 ortools 也有一个关于此的自己的文档条目。
尽管如此，这本书：
Burkard、Rainer E.、Mauro Dell'Amico 和 Silvano Martello。作业问题，修改后转载。卷。125. 暹罗，2009 年。
有一小章（5.4.4 矩形成本矩阵）概述了其他方法，主要是其他线性分配算法的修改。
该章的部分内容如下：
或者，可以使用第 4.4.1 节中的最小成本流问题的变换，它不要求顶点集 U 和 V 具有相等的基数。