algorithm - 自选团队

Question

一个由 100 名成员组成的团队将从 1000 名申请者中组成。每个申请者都可以选择他/她希望成为队友的 99 名其他申请者。

每个可能的团队都会得到一个分数，该分数衡量它满足其成员的队友偏好的程度。如果 Lisa 在一个团队中，并且 Lisa 愿望 list 上的 11 个人也在该团队中，则该团队为 Lisa 获得 11 分。所有成员的积分相加。任何可能的团队可以获得的理论最大值是 99*100。最小值为 0。

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

是否有一种聪明的算法可以走捷径获得最佳答案，或者人们是否必须满足于找到一个好答案的算法？

Answer 1

我认为如果你能有效地解决这个问题，你就能解决 http://en.wikipedia.org/wiki/Clique_problem高效 - 在两个节点之间存在链接的地方，将每个节点放在另一个节点想要使用的节点列表中。看了这篇文章，我想您会发现即使是保证良好的近似也很难找到，除非您的问题有一些特殊的结构。