女士和男士们,
我最好的朋友和我每年都会做一次"秘密圣诞老人"类型的礼物交换,今年我一直试图想办法让它变得有趣.我们有六个人参与,我想设计一个小程序,让我们六个人将他们喜欢的礼物接受者从1到5以及他们喜欢的送礼者排名.
所以,假设我们称之为A,B,C,D,E和F.
A提交两个列表:
清单1 - 我最想给的人是:B,D,C,F,E
清单2 - 我最想收到礼物的人:F,D,E,B,C
我们所有六个人都会提交这两个列表,所以我将共有12个列表.我想我的问题是现在最好的算法是什么,并为每个人分配礼物接收者？
我想到了这样的事情:
如果两个人都在他们的对立名单中相互选择(即A最想给B,B最想从A获得)那么我立即将A分配给B.所以现在A从我们的礼物接收者列表中删除从我们的礼品赠送者中删除了B和B.
一旦我分配了"完美匹配",我有点迷失了,是否有针对这种情况的建立算法？显然它只是为了娱乐价值,但肯定必须有类似的"真实"应用吗？也许是时间表或其他什么？
我的Google-fu失败了,但我觉得这可能只是因为我自己在搜索方面缺乏精确性.
干杯,(我猜是节日快乐),Rob
好的,Ying Xiao通过推荐用于稳定婚姻问题的Gale Shapley算法来解决这个问题,我已经在Python中实现了它并且它可以实现.然而,这只是我想到的一个想法.我想在我们这六个最好的朋友中,有三对"超级好"的朋友,所以我有一种感觉,我们最终会得到三对AB,CD,EF和BA,DC,FE的礼物给予和接受.
是否有我们可以设计的算法确实考虑了人们的排名,但也限制了两个人形成一个"封闭的群体"？也就是说,如果指定A为B购买礼物,则不能指定B 为A购买礼物？也许我需要解决稳定的室友问题？
相关问题:
秘密圣诞老人算法
什么是最好的低技术协议,从帽子模拟绘图名称,并确保保密？
ShreevatsaR.. 7
Gale-Shapley算法(用于稳定婚姻问题)仅适用于每个人都有所有其他参与者的排名列表 - 您可能会或可能不会将您的问题转换为该表格(让每个人都对所有人进行排名).
此外,请注意它正在优化的东西是不同的:它试图找到一组稳定的婚姻,其中没有一对人会"私奔",因为他们彼此更喜欢他们当前的合作伙伴.这不是您在Secret Santa应用程序中关注的内容.
您想要的(取决于您对"最佳"的定义)是最大权重的二分匹配,它解决了上述两个异议:将"给予者"放在一边,将"接收者"放在另一边(因此每个两个副本)在这种情况下,给每个边缘一个权重,该权重对应于给予者接收者的排名,现在是分配问题.你可以使用匈牙利语算法,或更简单(慢)的算法.您还可以改变分配权重的方式以针对不同的事情进行优化(例如,最大化获得首选的人数,或最小化任何人获得的最差选择等)
如果你确实使用Gale-Shapley稳定婚姻算法,请注意它对于"提议者"(男性最佳和女性 - 生育)是最佳的,所以一定要把"给予者"作为"提议者",而不是副词反之亦然.
Gale-Shapley算法(用于稳定婚姻问题)仅适用于每个人都有所有其他参与者的排名列表 - 您可能会或可能不会将您的问题转换为该表格(让每个人都对所有人进行排名).
此外,请注意它正在优化的东西是不同的:它试图找到一组稳定的婚姻,其中没有一对人会"私奔",因为他们彼此更喜欢他们当前的合作伙伴.这不是您在Secret Santa应用程序中关注的内容.
您想要的(取决于您对"最佳"的定义)是最大权重的二分匹配,它解决了上述两个异议:将"给予者"放在一边,将"接收者"放在另一边(因此每个两个副本)在这种情况下,给每个边缘一个权重,该权重对应于给予者接收者的排名,现在是分配问题.你可以使用匈牙利语算法,或更简单(慢)的算法.您还可以改变分配权重的方式以针对不同的事情进行优化(例如,最大化获得首选的人数,或最小化任何人获得的最差选择等)
如果你确实使用Gale-Shapley稳定婚姻算法,请注意它对于"提议者"(男性最佳和女性 - 生育)是最佳的,所以一定要把"给予者"作为"提议者",而不是副词反之亦然.
京公网安备 11010802040832号 | 京ICP备19059560号-6 