8

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

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

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

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

4

2 回答 2

5

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

于 2013-02-12T05:27:48.980 回答
2

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

于 2013-02-11T22:36:11.033 回答