我正在开发一个需要不断将用户匹配在一起的 Rails 应用程序。基本上,我需要一种算法,它将用户列表作为输入并返回最匹配的配对列表。用户被认为是符合标准的良好匹配,例如他们之间有更多的共同兴趣或距离。总的来说,我需要能够调整被认为是“良好匹配”的内容,但我只需要一个方向来进入将接受一组用户并返回一组对的算法。
如果有帮助,我在用户模型中有一个方法,该方法将另一个用户作为参数并返回一个匹配程度的分数。我需要帮助将其用于质量匹配。
我计划让用户输入一个表,然后一个 cron 作业经常在列表中运行,以找到每个人之间的最佳配对。有人有什么想法吗?
非常感谢!
最佳答案
Jack Edmonds' algorithm在一般(非二分)图中找到最大权重匹配。
Vladimir Kolmogorov 有一个 paper and an implementation在 C++ 中。
编辑补充:如果您不介意得不到最佳匹配,并且想要一些易于计算的东西,那么为什么不使用简单的贪心算法呢?在每个阶段,将得分最高的两个用户配对。然后将剩余用户中匹配得分最高的两个用户配对,依此类推。
关于algorithm - 对匹配算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4508171/