根据球员排名创建公平/平均匹配球队的算法

Question

我有球员的技术排名，年龄和性别的数据集，并希望创建均匀匹配的球队。

• 球队将有相同数量的球员（目前8队12名球员）。
• 团队应该有相同或相似的男女比例。
• 球队应该有类似的年龄曲线/分布。

我想在Haskell中尝试这个，但编码语言的选择是这个问题的最不重要的方面。

Answer 1

这是一个bin packing problem或multi-dimensional knapsack problem。 BjörnB.勃兰登堡取得了a bin packing heuristics library in Haskell，您可能会觉得有用。

你需要这样的东西......

data Player = P { skill :: Int, gender :: Bool, age :: Int } 

决定有多支球队的N（我猜这是玩家总数的函数）。

查找每队所需的总技能：

teamSkill n ps = sum (map skill ps)/n 

找到理想的性别比例：

genderRatio ps = sum (map (\x -> if gender x then 1 else 0))/length ps 

找到理想的年龄差异（你会希望Math.Statistics包）：

ageDist ps = pvar (map age ps) 

而且您必须将三个约束分配给某个给定团队的评分：

score skillW genderW ageW team = skillW * sk + genderW * g + ageW * a 
    where (sk, (g, a)) = (teamSkill 1 &&& genderRatio &&& ageDist) team 

问题归结为团队之间分数差异的最小化。蛮力方法将花费与Θ成比例的时间（n ^k-1）。考虑到问题的严重程度（每组12名球员），这意味着在典型的现代PC上可以使用大约6到24小时。

编辑

可以很好地帮助你（因为你并不需要在实践中准确的解决方案）的一种方法是模拟退火，或通过随机排列持续改进：

1. 随机挑选球队。
2. 获得此配置的分数（参见上文）。
3. 在两个或更多球队之间随机交换球员。
4. 获取新配置的分数。如果它比前一个更好，则保留它并递归到第3步。否则，丢弃新配置并再次尝试第3步。
5. 当某些固定次数的迭代得分没有提高时（实验找到这条曲线的拐点），停止。很可能您在此时的配置将接近理想状态。运行这个算法几次，以获得信心，你没有击中一些局部最优比理想更差的局面。

Answer 2

两支球队几乎微不足道的方法：

1. 排序的所有玩家通过你的技能/等级评定。
2. 派队A最好的球员。
3. 分配B队接下来最好的球员
4. 分配A队接下来最好的球员
5. 转到3
6. 结束，当你出门在外的球员。

不是很灵活，并且仅适用于一个列排名，所以它不会试图得到类似的性别或年龄组别。但是，如果输入分配合理平稳，它确实使公平的匹配团队。另外，如果有奇数，A队并不总是有备用球员。

Answer 3

理念：

1. 排序玩家通过技能
2. 分配，以最好的球员（即：A队：1号球员，球队B：第二的球员，...）
3. 分配最差球员order
4. Loop on 2
5. 评估可能的更正并执行它们（即：如果A队的总技能为19与技能5的玩家并且B队的总技能为21与技能4的玩家，交换他们）
6. 评价将性别分布情况可能出现修正，并执行他们
7. 评估在年龄分布可能的修正和执行这些

Answer 4

鉴于每队和性别口粮（你可以很容易地计算），玩家数量。其余的问题被称为n-partition problem，这是不幸的NP完成，因此很难准确解决。如果您的问题规模对于暴力解决方案来说太大，您将不得不使用近似或启发式算法（演进算法）。一个非常简单的近似将按年龄进行排序并以交替方式进行分配。

Answer 5

1. 分配点值的技能水平，性别和年龄
2. 通过他们的计算点值分配点，为每个标准和每个玩家
3. 排列玩家
4. 分配下一个玩家到第一队
5. 将队员分配给第二队，直到队员总分> =第一队或队伍达到最高队员为止。
6. 为每个团队执行5，循环回到一线队，直到所有球员都分配

你可以调整的技术水平，性别和年龄点值来改变每个分布。

Answer 6

好，

我的回答是不是得分策略的球队/球员因为所有的发布都不错，但我会尝试蛮力或随机搜索方法。 我不认为值得创建一个遗传算法。

问候。

Answer 7

假设你有六个玩家（例如简单的例子）。我们可以使用相同的算法，在单次淘汰赛中将对手配对，并根据您选择的任何标准对其进行调整以生成“偶数”球队。

将您的球员排在第一位。不要太直接了当。你想要一个按照你希望独立他们的标准排序的球员列表。

为什么？

让我们来看看第一场淘汰赛。使用算法来产生最佳单次淘汰赛的想法是为了避免在比赛中太早召开“顶级选手”的问题。如果顶级球员很快就会见面，其中一名顶尖球员将很快被淘汰，这让比赛变得不那么有趣。我们可以使用这种“最佳”配对来生成队伍，其中“顶级”球员均匀分布在球队中。然后展开第二名顶级球员等等。

因此，按照标准列出您的球员，您希望他们分开：男性第一，然后女性...按年龄秒排序。我们得到（例如）：

Player 1: Male - 18 
Player 2: Male - 26 
Player 3: Male - 45 
Player 4: Female - 18 
Player 5: Female - 26 
Player 6: Female - 45 

然后，我们将运用它使用自己的“等级”（这只是他们的球员号码）创建“好比赛跌宕”的单淘汰算法。

单淘汰锦标赛发电机基本上是这样工作的：取他们的等级（玩家号码）并反转比特（二进制）。你提出的这个新号码成为他们在比赛中的“角子机”。

Player 1 in binary (001), reversed becomes 100 (4 decimal) = slot 4 
Player 2 in binary (010), reversed becomes 010 (2 decimal) = slot 2 
Player 3 in binary (011), reversed becomes 110 (6 decimal) = slot 6 
Player 4 in binary (100), reversed becomes 001 (1 decimal) = slot 1 
Player 5 in binary (101), reversed becomes 101 (5 decimal) = slot 5 
Player 6 in binary (110), reversed becomes 011 (3 decimal) = slot 3 

在一次单淘汰赛中，第1个时隙播放第2个时间段，3-vs-4，5-vs-6。我们将使用这些“配对ups”来生成最佳团队。

综观上述，通过他们的“插槽号”责令玩家数，这里是我们想出了名单：

Slot 1: Female - 18 
Slot 2: Male - 26 
Slot 3: Female - 45 

Slot 4: Male - 18 
Slot 5: Female - 26 
Slot 6: Male - 45 

当您拆分的插槽分成小组（两个或更多）你插槽1-3中的球员与插槽4-6中的球员。这是您可以获得的最佳/最佳组合。

这项技术可以很好地扩展到更多的玩家，多个标准（只需将它们组合在一起）和多个团队。