一个自我选择团队

Question

由100名成员组成的团队将由1000名申请人组成.每个申请人都可以选择他/她希望作为队友的其他99名申请人.

每个可能的团队都会得到一个分数,用于衡量其满足其成员的队友偏好的程度.如果Lisa在一个团队中,并且Lisas愿望清单中的11个人也在团队中,团队为Lisa获得11分.所有成员的积分都加起来了.任何可能的团队可以得到的理论最大值是99*100.最小值为0.

现在我们想找到得分最高的球队.试图通过计算每种可能组合的分数(≈10^ 140)来强制解决这个问题不是一种选择.

是否有一个聪明的算法,它将采用最佳答案的快捷方式,还是必须找到一个能找到一个好答案的算法？

Answer 1

我认为,如果你能有效地解决这个问题,你可以有效地解决http://en.wikipedia.org/wiki/Clique_problem - 两个节点之间存在链接,将每个节点放在另一个节点的节点列表中与...合作.看看这篇文章,我想你会发现很难找到一个保证良好的近似值,除非你的问题有一些特殊的结构.

Answer 2

您可以尝试爬山算法。从“受欢迎”的成员（最常被其他成员挑选）开始，然后逐步添加增加团队得分最多的新成员。不幸的是，这不能保证找到最好的解决方案，但它可能会找到好的解决方案。为了改进您的解决方案，您可以尝试模拟退火。