algorithm - 对匹配算法

Question

我正在开发一个需要不断将用户匹配在一起的 Rails 应用程序。基本上，我需要一种算法，它将用户列表作为输入并返回最匹配的配对列表。用户被认为是符合标准的良好匹配，例如他们之间有更多的共同兴趣或距离。总的来说，我需要能够调整被认为是“良好匹配”的内容，但我只需要一个方向来进入将接受一组用户并返回一组对的算法。

如果有帮助，我在用户模型中有一个方法，该方法将另一个用户作为参数并返回一个匹配程度的分数。我需要帮助将其用于质量匹配。

我计划让用户输入一个表，然后一个 cron 作业经常在列表中运行，以找到每个人之间的最佳配对。有人有什么想法吗？

非常感谢!

Answer 1

Jack Edmonds' algorithm在一般(非二分)图中找到最大权重匹配。

Vladimir Kolmogorov 有一个 paper and an implementation在 C++ 中。

---

编辑补充:如果您不介意得不到最佳匹配，并且想要一些易于计算的东西，那么为什么不使用简单的贪心算法呢？在每个阶段，将得分最高的两个用户配对。然后将剩余用户中匹配得分最高的两个用户配对，依此类推。