一个自我选择的团队
一个自我选择的团队
提问于 2013-02-12 05:49:56
将从1000名申请者中组建一个由100名成员组成的团队。每个申请者都可以选择他/她希望成为队友的99个其他申请者。
每个可能的团队都会得到一个分数，用来衡量它满足其成员的队友偏好的程度。如果Lisa在一个团队中，Lisas wishlist上的11个人也在这个团队中，那么这个团队会为Lisa得到11分。所有成员的积分都加起来了。理论上，任何可能的团队可以获得的最大值是99*100。最小值为0。
现在我们要找到得分最高的队伍。试图通过计算每个可能的组合(≈10^140)的分数来强行解决这个问题是不可行的。
有没有一种聪明的算法可以找到通向最佳答案的捷径，还是只能满足于找到好答案的算法？
回答 2
Stack Overflow用户
发布于 2013-02-12 13:27:49
我认为如果你能有效地解决这个问题，你就可以高效地解决http://en.wikipedia.org/wiki/Clique_problem --在两个节点之间有一个链接的地方，将每个节点放在另一个节点想要使用的节点列表中。看了这篇文章，我想你会发现很难找到一个保证良好的近似值，除非你的问题有一些特殊的结构。
Stack Overflow用户
发布于 2013-02-12 06:36:11
您可以尝试hill climbing算法。从“受欢迎”的成员开始(最常由其他成员挑选)，逐步添加提高团队分数最多的新成员。不幸的是，这并不能保证找到最好的解决方案，但它可能会找到好的解决方案。要改进您的解决方案，您可以尝试simulated annealing。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14821495
复制相关文章
相似问题
腾讯云开发者
