匹配算法

Question

我正在编写一个应用程序,它将一组用户分成两组,以便一起执行任务.每个用户可以指定关于其伙伴的各种偏好,例如

• 性别
• 语言
• 年龄
• 位置(通常在用户居住的X英里/公里范围内)

理想情况下,我希望用户能够指定这些首选项中的每一个是"很高兴"还是"必须拥有",例如"我更愿意与英语母语人士匹配,但我不能是与女性相匹配".

我的目标是最大化比赛的整体平均质量.例如,假设系统中有4个用户,A,B,C,D.这些用户可以通过3种方式进行匹配:

Option 1     Match Score
A-B           5
C-D           4
---
Average       4.5

Option 2     Match Score
A-C           2
B-D           3
---
Average       2.5

Option 3     Match Score
A-D           1
B-C           9
---
Average       5

所以在这个人为的例子中,选择第3个选项是因为它具有最高的整体匹配质量,即使A和D根本不匹配.

有没有一种算法可以帮助我:

• 计算上面显示的"匹配分数"
• 选择最大化平均匹配分数的配对(同时尊重每个用户的绝对约束)

并不是绝对必须匹配每个用户,因此在显着降低匹配的整体质量和留下几个没有匹配的用户之间做出选择,我会选择后者.

显然,我希望计算匹配的算法尽快完成,因为系统中的用户数量可能非常大.

最后,这个计算匹配分数和最大化整体平均值的系统只是我自己提出的一个heurisitic.如果有更好的方法来计算配对,请告诉我.

更新

我所描述的问题似乎与稳定的婚姻问题类似,有一个众所周知的解决方案.但是,在这个问题中,我不要求所选择的对是稳定的.我的目标是选择对,以便最大化平均"匹配分数"

Answer 1

您一直在研究哪些最大匹配算法？我一开始读你的问题太匆忙了：看来你不一定将自己限制在二分图上。这似乎更棘手。