根据玩家排名创建公平/均匀匹配的团队的算法

Question

我有一个玩家技能等级,年龄和性别的数据集,并希望创建均匀匹配的团队.

• 球队将拥有相同数量的球员(目前有8支球队的8支球队).
• 团队应该具有相同或相似的男女比例.
• 团队应该有类似的年龄曲线/分布.

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

Answer 1

这是垃圾箱包装问题,或多维背包问题.BjörnB.Brandenburg 在Haskell建立了一个bin包装启发式库,您可能会发现它很有用.

你需要......

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. 当某些固定次数的迭代没有得到改善时(试验找到该曲线的拐点),停止.此时您所拥有的配置可能足够接近理想状态.运行此算法几次,以确保您没有达到比理想情况差得多的局部最优值.

Answer 2

考虑到每个团队的球员数量和性别比例(您可以轻松计算).剩下的问题叫做n分区问题,遗憾的是NP完全,因此很难准确解决.如果您的问题规模对于暴力解决方案来说太大,您将不得不使用近似或启发式算法(进化算法).一个非常简单的近似是按年龄排序并以交替方式分配.