我正在编写一个应用程序,将用户人群分成配对组合以共同完成任务。每个用户可以指定关于其伙伴的各种偏好,例如:
- 性别 - 语言 - 年龄 - 地点(通常在用户所在地的X英里/公里内)
理想情况下,我希望用户能够指定每个偏好是“好有”还是“必须有”,例如:“我更喜欢与母语为英语的人匹配,但我不能与女性匹配”。
我的目标是最大化匹配的整体平均质量。例如,假设系统中有4个用户A,B,C,D。这些用户可以通过以下3种方式进行匹配:
在这个人为构造的例子中,第三个选项会被选择,因为它具有最高的整体匹配质量,即使A和D之间的匹配非常不好。
是否有一种算法可以帮助我: - 计算上述“匹配得分” - 选择将最大化平均匹配得分的配对(同时尊重每个用户的绝对约束条件)
并不是必须匹配每个用户,因此,在显著降低匹配整体质量和留下一些未匹配用户之间进行选择时,我会选择后者。
显然,我希望计算匹配的算法能够尽快完成,因为系统中的用户数量可能相当大。
最后,这种计算匹配得分和最大化整体平均值的系统只是我自己想出来的一种启发式方法。如果有更好的计算配对的方法,请告诉我。
更新
我描述的问题似乎类似于稳定婚姻问题,针对该问题已有一个众所周知的解决方案。但是,在这个问题中,我不需要选择的配对是稳定的。我的目标是选择配对,以使平均“匹配分数”最大化。
- 性别 - 语言 - 年龄 - 地点(通常在用户所在地的X英里/公里内)
理想情况下,我希望用户能够指定每个偏好是“好有”还是“必须有”,例如:“我更喜欢与母语为英语的人匹配,但我不能与女性匹配”。
我的目标是最大化匹配的整体平均质量。例如,假设系统中有4个用户A,B,C,D。这些用户可以通过以下3种方式进行匹配:
在这个人为构造的例子中,第三个选项会被选择,因为它具有最高的整体匹配质量,即使A和D之间的匹配非常不好。
是否有一种算法可以帮助我: - 计算上述“匹配得分” - 选择将最大化平均匹配得分的配对(同时尊重每个用户的绝对约束条件)
并不是必须匹配每个用户,因此,在显著降低匹配整体质量和留下一些未匹配用户之间进行选择时,我会选择后者。
显然,我希望计算匹配的算法能够尽快完成,因为系统中的用户数量可能相当大。
最后,这种计算匹配得分和最大化整体平均值的系统只是我自己想出来的一种启发式方法。如果有更好的计算配对的方法,请告诉我。
更新
我描述的问题似乎类似于稳定婚姻问题,针对该问题已有一个众所周知的解决方案。但是,在这个问题中,我不需要选择的配对是稳定的。我的目标是选择配对,以使平均“匹配分数”最大化。