Лучший алгоритм поиска совпадений для 5х5 с пулами миллионов игроков

Question

Предположим, что я пытаюсь создать какой-то алгоритм подбора матчей для своей игры. Игра похожа на League или DOTA, в которой 5 игроков сражаются против 5 игроков. Предположим далее, что пул игроков гигантский (миллионы игроков ищут игру одновременно), и задача создателя матча состоит в том, чтобы собрать как можно больше игроков во многих случаях игр 5 на 5. На данный момент мы совсем не беспокоимся о том, что в игру вступит MMR, ELO или какой-либо рейтинг игрока / партии. Мы просто хотим разместить игроков в 5х5.

Мой текущий алгоритм перебора абсолютно ужасен в масштабировании. Сначала он пытается найти все возможные комбинации из 5 партий игроков в миллионах игроков, затем пытается найти пары партий, одновременно удаляя игроков из возможных партийных матчей, если игроки уже были использованы:

Итак, предположим, что у меня есть 10 игроков, и я хочу найти все возможные 5 на 5, я сначала преобразовываю их в биты и выполняю сдвиг битов, чтобы найти все возможные комбинации.

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

и так далее...

Затем из всех возможных групп я использую 2 для циклов, чтобы начать пытаться найти пары групп:

ABCDE vs FGHIJ
ABCDF vs EGHIJ
ABCDG VS EFHIJ

и так далее...

Этот алгоритм имеет время выполнения O((nCr)^2). Поскольку он пытается найти все возможные комбинации партий, для того, чтобы собрать 50 игроков, потребуется 4.4891439e+12 операций, что безумие.

Каков лучший алгоритм, который не проходит через все возможные стороны и не решает эту проблему?

Answer 1

Из вашего примера я понимаю, что вам не важно собирать игроков по рейтинговым классам, но вам нужно заботиться о сбалансированности итоговых команд. Вот алгоритм, который должен дать вам работоспособное решение. Начните с захвата первых 9 игроков в очереди; назовите это pool,

1. Подсчитать средний рейтинг игроков, avg = mean(pool)
2. Вычислите целевой счет для команды из 5 человек: team_target = 5*avg
3. Найдите комбинацию из 5 игроков, чьи рейтинги имеют сумму, ближайшую к team_target (решено в нескольких других сообщениях). Сделай эту команду1.
4. Подсчитать общий рейтинг команды: team1_rating = sum(team1)
5. Удалить эти пять игроков из pool, Поместите оставшихся игроков в пул в команду2.
6. Вычислите рейтинг этой оставшейся команды из 4: team2_rating = sum(team2)
7. Вычтите оценки, чтобы получить рейтинг необходимого 10-го игрока: player_target = team1_rating - team2_rating
8. Возьмите следующих 10 игроков в очереди; это новый pool,
9. Найти игрока в пуле с рейтингом, ближайшим к player_target,
10. Поместите этого игрока на team2 и опубликовать матч **team1 против 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 низких.