匹配两组对象

Question

我正在尝试找出如何用程序解决以下问题：

我有一组对象A= Ai和另一组对象B= Bj。

我还有一个矩阵C=cij来计算A和B之间的相似度(这是完全密集的)。

我希望将每个对象分配给一个单独的其他对象(总共min(|A|，|B|)对)，以便所有使用的cij的总和是最大可能的。( Cij也是对称的)

我试图将其描述为一个二部匹配问题，但我无法找到我所问问题的现有定义和实现，尽管它看起来非常熟悉，这就是为什么我寻求您的帮助。

谢谢

Answer 1

问题是分配不平衡：https://en.wikipedia.org/wiki/Assignment_problem

在scipy中似乎有一个实现：https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html

这就解决了问题。你需要将相似性转化为成本(你可以只考虑负面的)。