algorithm - 基于玩家偏好的团队创建算法

Question

我正在制作一个配对客户端，将 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 个团队的大型游戏，在这些游戏中，可以通过搜索功能来选择你喜欢的队友。我知道这个系统可能不是最适合它的目的 - 然而，这是一个有趣的问题，我想找到一个有效的解决方案，同时在此过程中学习一些东西。

Answer 1

首先是免责声明。

如果您的用户建议这样做，则有两种可能性。 或者他们可以提供算法的确切细节，所以问他们。 或者他们很可能不知道自己在说什么，只是当场产生了一个部分想法，在这种情况下，遗憾的是，它的平均值(value)并不高。

因此，一种选择是搜索配对在其他项目中的运作方式，完全无视这个想法。 另一个是探索用户的想法。 它可能不会变成一个好的系统，但它有可能会变成一个好的系统。 无论如何，您都必须自己做一些实验。

---

现在，让我们谈谈您将乐于探索这个想法的情况。 首先，为了将十个项目分成两组，每组五个，there are只需选择 (10,5)=252 种可能性，因此，除非系统必须每秒执行数百万次，否则您可以为所有这些计算一些分数，然后选择最好的一个。 最直接的方法可能是考虑所有 2^{10} = 1024 种方法来形成 10 个元素的子集，然后探索子集大小为 5 的方法。 但可能会有更好的，more to-the-point ，工具随时可用，具体取决于语言或框架。 10选5为一组，没取的为另一组。

那么，组合的得分是多少？ 现在我们看看我们的偏好。

1. 对于满足的每个偏好，我们可以将其权重、权重平方或其他方式添加到分数中。 哪种效果最好肯定需要一些实验。

2. 同样，对于每个不满足的偏好，我们可以根据其权重添加惩罚。

3. 接下来，我们可以考虑所有玩家，并可能对每个偏好都不满足的玩家增加更多惩罚。

4. 另一件需要考虑的事情是团队平衡。 由于到目前为止唯一的数据是偏好(结果很可能是不够的)，不平衡意味着一个团队满足了他们的许多偏好，而另一个团队只有很少的偏好，如果有的话。 因此，我们根据(第一队的满意度总和)和(第二队的满意度总和)的绝对差值添加另一个惩罚。

5. 当然还有其他因素需要考虑...

基于所有这些，构建一个至少表面上看起来合理的系统，然后再试验再试验，调整它，使其更符合匹配目标。