基于玩家偏好的团队创建算法
我正在制作一个相亲客户端，它将10个人分成两个团队：
每个人选择四个他们想玩的人，从高到低排名。
然后，从该集合中最强的关系中组成两个团队。
你将如何创建一个算法来解决这个问题？
示例：
Given players [a, b, c, d, e, f, g, h, i, j], '->' meaning a preference pick.
a -> b (weight: 4)
a -> c (weight: 3)
a -> d (weight: 2)
a -> e (weight: 1)
b -> d (weight: 4)
b -> h (weight: 3)
b -> a (weight: 2)
...and so on这个问题表面上看起来很简单(毕竟它只是一个相亲客户)，但经过一段时间的思考，似乎需要考虑相当多的关系。
编辑(从评论中粘贴)：理想情况下，我会避免使用暴力方法来扩展到需要100名球员和25个团队的大型游戏，在这些游戏中，通过搜索功能来选择您喜欢的队友。我知道这个系统可能不是最好的--然而，这是一个有趣的问题，我想在学习的过程中找到一个有效的解决方案。
回答 2
Stack Overflow用户
发布于 2018-06-09 21:45:04
首先是免责声明。
如果你的用户建议这样做，有两种可能性。或者他们可以提供算法的确切细节，所以可以问他们。或者他们很可能不知道自己在说什么，只是当场产生了一个部分想法，在这种情况下，可悲的是，它的平均价值并不高。
因此，一种选择是搜索匹配在其他项目中是如何工作的，完全忽略这个想法。另一种是探索用户的想法。也许它不会变成一个好的系统，但它有可能变成一个好的系统。在任何情况下，你都必须自己做一些实验。
现在，让我们来看看你在探索这个想法时会有什么乐趣。首先，为了将十个项目分成两组，there are只需选择(10，5)=252个可能性，因此，除非系统每秒必须执行数百万次，否则您可以为所有项目计算一些分数，并选择最好的一个。最直接的方法可能是考虑所有2^{ 10 } = 1024种方法来形成10个元素的子集，然后探索子集大小为5的方法。但是，根据语言或框架的不同，可能会有更好的more to-the-point工具。10-choose-5组合是一组，未取的项目是另一组。
那么，组合的分数是多少呢？现在我们来看看我们的首选项。
- 对于每个满足的偏好，我们可以将其权重、权重的平方或其他值添加到分数中。接下来，我们可以考虑所有的玩家，也许可以为每个没有偏好的球员添加更多的experimentation.
- Similarly，，satisfied.
- Another
- 考虑的是团队平衡。由于到目前为止唯一的数据是偏好(这很可能被证明是不够的)，不平衡意味着一个团队满足了他们的许多偏好，而另一个团队只有很少的偏好。因此，我们根据(第一队的满意度总和)和(第二队的满意度总和)的绝对差异添加另一个惩罚。
- 确定还可以考虑其他因素...
在此基础上，构建一个至少在表面上看起来合理的系统，然后再进行一次又一次的实验，对其进行调整，使其更适合配对目标。
Stack Overflow用户
发布于 2018-06-10 12:36:58
我会想出一种方法来根据人们的选择对提议的团队进行评分，比如根据权重对提议的团队进行评分。
我会尝试通过爬山来优化这一点(例如，交换一对人，看看这是否会提高分数)，如果只是因为人们可以看到最终的解决方案，并自己尝试-所以你不想错过这种改进。
我会从不同的起点多次爬山，并选择得分最高的答案，因为爬山可能会在局部最优而不是全局最优结束。
至少一些起点应该基于人们最初的选择。如果您让人们的选择达到整个团队的选择价值，这将是最容易的，但是如果您说您将遵循人员A的建议，然后是人员B的选择(如果需要)，然后是人员C的选择(如果需要)，那么您可能可以从多个建议中建立一个团队，依此类推。
如果您包括每个人的选择作为起点，或基于优先级ABCDE的选择。然后优先BCDE..。然后优先级CDEF..。然后你就有了这样的特性，如果有人提交了一个完美的选择，你的算法就会识别它。
如果你的爬山算法试图交换所有的玩家来提高，并继续下去，直到找到一个局部最优，然后停止，那么你也有这样的属性，如果任何人提交了一个离完美只有一次交换的选择，你的算法将识别它。
https://stackoverflow.com/questions/50774618
复制相似问题
腾讯云开发者
