algorithm - 具有喜好功能的匹配算法

Question

我有一个算法问题。我想匹配两组人数相等的人。有一个喜欢的功能，它为每一对(由 A 组的一个人和 B 组的一个人组成)分配一个喜欢分数。我现在想要将 A 组的每个人与 B 组的一个人匹配，并且我希望所有比赛的分数总和最大。我设计了一个朴素的算法，它尝试了所有的可能性，然后选择最好的一个，但它的运行时间是 n! (其中 n 是每个组中的人数)。有更快的算法吗？或者至少是一种快速近似算法？

提前致谢!

Answer 1

假设每个人只匹配一次(双向)，这听起来很简单 assignment problem (或:二部图中的最小权重完美匹配)可以在多项式时间内解决(并且在实践中非常有效)。还有很多软件可以使用多种编程语言。

反对经典worker <-> job View ，您的 View 将是:group A <-> group B .

因为大多数图书馆都有些假设:

• 非负成本
• 最小化

你需要翻译你的最大化问题:

x = max(original_likings)
transformed_liking_i_j = x - original_liking_i_j
... solve minimization problem (with transformed likings)

这通常称为机会损失。