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

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

球队将拥有相同数量的球员(目前有8队，每队12名球员)。

球队的男女比例应相同或相似。

球队应具有相似的年龄曲线/分布。

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

最佳答案

这是bin packing problem或multi-dimensional knapsack problem。 BjörnB. Brandenburg制作了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

问题减少到了团队之间分数差异的最小化。蛮力方法将花费与Θ(nk-1)成比例的时间。考虑到问题的严重性(每个团队有8个团队，每个团队12个玩家)，这在典型的现代PC上大约需要6到24小时。

编辑

模拟退火或通过随机排列的持续改进可能是一种适合您的方法(因为您实际上不需要确切的解决方案):

随机选择团队。

获取此配置的分数(请参见上文)。

在两个或多个团队之间随机交换球员。

获取新配置的分数。如果它比上一个更好，请保留并递归至步骤3。否则，请放弃新配置，然后再次尝试步骤3。

如果分数的固定迭代次数没有提高(找到此曲线的拐点的实验)，请停止。此时的配置可能已经足够接近理想状态。多次运行此算法，以确保您没有遇到比理想情况差很多的局部最优值。