两组截然不同大小的顶点的最大加权二部匹配 [英] Maximum weighted bipartite matching for two sets of vertices of drastically different sizes

问题描述

我想在一个完整的加权二部图中找到最佳的最大匹配，其中两组顶点的大小截然不同，即一组顶点很大，而另一组很小.

I want to find the best maximum matching in a complete weighted bipartite graph where the two sets of vertices differ drastically in size, i.e. one set of vertices is very large and the other one very small.

匈牙利算法不是解决此问题的好方法，因为它会向其添加虚拟顶点较小的集合，以使两个集合具有相同的大小，因此我损失了其中一个顶点集很小的潜在效率收益.

The Hungarian algorithm is not a good approach for this problem since it adds dummy vertices to the smaller set such that the two sets have the same size, so I lose all the potential efficiency gains from one of the vertex sets being only very small.

我已将对象(边界框)分为两组，并且对任意两个对象的相似度都有相似性度量(Jaccard重叠).我想产生两个集合之间的匹配，以使所有单个匹配的相似度之和最大.

I have divided objects (bounding boxes) into two sets and I have a similarity measure (Jaccard overlap) for how similar any two objects are. I want to produce the matching between the two sets such that the sum of the similarities of all individual matches is maximal.

问题在于，其中一组仅包含很少的对象(例如10个)，而第二组很大(例如10,000个对象).第一组中的10个对象中的每个对象都必须与第二组中的10,000个对象之一匹配.

The problem is that one of the sets contains only very few objects, say 10, while the second set is very large, say 10,000 objects. Each of the 10 objects in the first set needs to be matched to one of the 10,000 objects in the second set.

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

This asymmetry in the sizes of the two sets is what makes me wonder how to do this efficiently. I can't use the Hungarian algorithm and produce a 10,000 by 10,000 matrix.

推荐答案

在可用软件方面可能是最简单的方法:使用最低成本的网络流求解器.这种公式对于矩形成本矩阵没有问题！基本思想很简单，并且简介是此处(一个下图所示的幻灯片):

Probably the easiest approach in terms of available software: use a min-cost network-flow solver. This formulation has no trouble with rectangular cost-matrices! The basic idea is simple and an intro is here (one slide shown in following image):

有很多可用的软件(例如Coin-OR 柠檬/C ++ ； Google的 ortools /C ++(带有许多包装).

There is a lot of available software (e.g. Coin-OR Lemon/C++; Google's ortools/C++ with many wrappers).

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

Google's ortools also has an own documentation-entry on this.

尽管如此，这本书:

Burkard，Rainer E.，Mauro Dell'Amico和Silvano Martello.作业有问题，修改后重印.卷125.暹罗，2009年.

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

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

has a tiny/small chapter (5.4.4 Rectangular cost matrix) outlining other approaches, mostly modifications of other linear-assignment algorithms.

该章的一部分如下:

或者，可以将变换用于第4.4.1节中的最小成本流问题，该问题不需要顶点集U和V具有相同的基数.

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.

这篇关于两组截然不同大小的顶点的最大加权二部匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！