-6

假设我正在尝试为我的游戏创建某种匹配算法。该游戏类似于联赛或 DOTA，其中 5 名玩家对抗 5 名玩家。进一步假设玩家池是巨大的（数百万玩家同时搜索一个游戏），匹配器的工作是将尽可能多的玩家放入 5v5 游戏的许多实例中。在这一点上，我们完全不用担心 MMR、ELO 或任何玩家/队伍等级的影响。我们只想让玩家进入 5v5。

我目前的蛮力算法在缩放方面绝对是残酷的。它首先尝试在数百万玩家中找到 5 个玩家方的所有可能组合，然后，它尝试找到成对的方，如果玩家已经被使用，则从可能的方匹配中删除玩家：

所以，假设我有 10 个玩家，我想找到所有可能的 5v5，我首先将它们转换为位并进行位移以找到所有可能的组合。

Players: ABCDEFGHIJ
1111100000 => ABCDE
1111010000 => ABCDF 
1111001000 => ABCDG
1111000100 => ABCDH
1111000010 => ABCDI
1111000001 => ABCDJ
1110110000 => ABCEF

等等...

然后在所有可能的参与方中，我使用 2 个 for 循环开始尝试查找参与方对：

ABCDE vs FGHIJ
ABCDF vs EGHIJ
ABCDG VS EFHIJ

等等...

该算法的运行时间为 O((nCr)^2)。因为它试图找到所有可能的派对组合，所以仅仅匹配 50 名玩家将需要 4.4891439e+12 次操作，这太疯狂了。

有什么更好的算法不会经过所有可能的参与方并蛮力解决这个问题？

4

1 回答 1

3

从您的示例中，我了解到您并不关心通过等级等级来收集球员，但您确实关心平衡结果球队。这是一个可以为您提供可行解决方案的算法。首先抓住队列中的前 9 名玩家；称之为pool.

  1. 计算玩家的平均评分，avg = mean(pool)
  2. 计算 5 人团队的目标分数：team_target = 5*avg
  3. 找到 5 个玩家的组合，其评分总和最接近team_target（在其他几个帖子中解决）。让那个团队1。
  4. 计算团队的总评分：team1_rating = sum(team1)
  5. 将这五名球员从pool. 将剩余的台球运动员放入 team2。
  6. 计算剩下的 4 人团队的评分：team2_rating = sum(team2)
  7. 减去评分得到所需第 10 名球员的评分：player_target= team1_rating - team2_rating
  8. 抓住队列中接下来的 10 名玩家；这是新的pool。
  9. 找到评分最接近 的台球运动员player_target。
  10. 将该球员放入team2并发布比赛**team1 vs team2*。
  11. 池中还剩 9 名玩家；返回第 1 步。根据需要进行迭代。

优点

这是一个简单的线性算法，可以处理输入请求流。由于团队规模是固定的，因此队列长度为O(N)。唯一耗时的部分是找到最接近平均评分的球队，检查 9C5 = 126 种可能性，每场比赛的开销非常便宜。

头顶的空间是微不足道的：高水位线同时处理 19 名玩家。

问题

如果分布不平滑，您可能会有不平衡的匹配。例如，有一个明星球员的队列，例如 (100, 5, 5, 5, 5, 6, 6, 6, 6 | 5, 5, 5, 5, 5, 6, 6, 6, 6, 6 ) 将为您提供 120 和 30 的“最佳”配对团队评分。如果这对您来说是一个功能性问题，请随意调整，也许会保留一组异常值来处理，直到您获得 10 个高值和/或 10 个低值。

于 2018-03-22T00:00:26.163 回答