算法根据玩家的排名创造公平/势均力敌的球队 [英] Algorithm to create fair / evenly matched teams based on player rankings

问题描述

我对球员的技能等级，年龄和性别的数据集，并希望创建势均力敌的球队。

I have a data set of players' skill ranking, age and sex and would like to create evenly matched teams.

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

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

I would like to try this in Haskell but the choice of coding language is the least important aspect of this problem.

推荐答案

这是一个装箱问题或<一href="http://books.google.com/books?id=u5DB7gck08YC&lpg=PP1&ots=wt7vslxOHo&dq=Knapsack%20Problems&pg=PP1#v=onepage&q=&f=false"相对=nofollow>多维背包问题。比约恩B.勃兰登堡取得了在Haskell一个装箱启发式库中，你会发现有用的。

This is a bin packing problem, or a multi-dimensional knapsack problem. Björn B. Brandenburg has made a bin packing heuristics library in Haskell that you may find useful.

您需要这样的东西...

You need something like...

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

确定一个数支球队的N（我猜这是玩家总数的函数）。

Decide on a number of teams n (I'm guessing this is a function of the total number of players).

查找每队所需要的总技能：

Find the desired total skill per team:

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

找到理想的男女比例：

Find the ideal gender ratio:

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

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

Find the ideal age variance (you'll want the Math.Statistics package):

ageDist ps = pvar (map age ps)

和您必须将三个约束一些权重来了一个进球对于一个给定的团队：

And you must assign the three constraints some weights to come up with a scoring for a given team:

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名球员），这相当于约6〜24小时典型的现代个人电脑上。

The problem reduces to the minimization of the difference in scores between teams. A brute force approach will take time proportional to Θ(n^k−1). Given the size of your problem (8 teams of 12 players each), this translates to about 6 to 24 hours on a typical modern PC.

修改

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

An approach that may work well for you (since you don't need an exact solution in practise) is simulated annealing, or continual improvement by random permutation:

1. 在挑选团队是随机的。
2. 获取的分数为这个配置（见上文）。
3. 在随机两个或两个以上的球队之间的交换球员。
4. 获取的分数为新配置。如果它比previous一个人好，保持和递归步骤3。否则放弃新的配置，然后再次尝试第3步。
5. 当比分一直没有好转的迭代的一些固定数量（实验中发现这条曲线的拐点），停止。这可能是因为在这一点上，你拥有的配置将足以接近理想。运行该算法几次获得信心，你有没有击中一些局部最优比理想的要差。

这篇关于算法根据玩家的排名创造公平/势均力敌的球队的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！