小编典典

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

algorithm

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

  • 球队的球员人数相同(目前有8队,每队12名球员)。
  • 参赛队伍的男女比例应相同或相似。
  • 团队应具有相似的年龄曲线/分布。

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


阅读 277

收藏
2020-07-28

共1个答案

小编典典

这是一个装箱问题,或一个多维背包问题。BjörnB.
Brandenburg
在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)成比例的时间。考虑到问题的严重性(每组8个团队,每个团队12个玩家),这在典型的现代PC上大约需要6到24小时。

编辑

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

  1. 随机选择团队。
  2. 获取此配置的分数(请参见上文)。
  3. 在两个或多个团队之间随机交换球员。
  4. 获取新配置的分数。如果比以前更好,请保留并递归至步骤3。否则,请放弃新配置,然后再次尝试步骤3。
  5. 如果分数在一定的固定迭代次数下没有提高(尝试找到该曲线的拐点),请停止。此时的配置可能已足够接近理想值。多次运行此算法,以确保您没有遇到比理想情况差很多的局部最优值。
2020-07-28