Dan*_*nny 3 algorithm graph matching
我正在开发一个需要不断匹配用户的rails应用程序.基本上我需要一种算法,它将用户列表作为输入,并返回最匹配的对列表.根据标准,用户被认为是良好的匹配,这些标准具有更多共同利益或它们之间的距 一般来说,我需要能够调整被认为是"良好匹配"的东西,但我只需要一个方向来寻找将需要一组用户并返回一组对的算法.
如果它有帮助,我在用户模型中有一个方法,作为另一个用户的参数,并返回sa得分有多好.我需要帮助把它用于大规模匹配.
我计划让用户进入一个表,然后经常在列表中运行一个cron作业,以找到每个人之间的最佳配对.有人有主意吗？
非常感谢!
Jack Edmonds的算法在一般(非二分)图中找到最大权重匹配.
Vladimir Kolmogorov有一篇论文和 C++ 实现.
编辑添加:如果你不介意没有获得最佳匹配,并且你想要一些易于计算的东西,那么为什么不使用简单的贪心算法？在每个阶段,配对得分最高的两个用户.然后将剩余用户中得分最高的两个用户配对,依此类推.