Алгоритм создания честных/равномерно согласованных команд на основе ранжирования игроков

Ответ 1

Это проблема с упаковкой bin или multi- мерная проблема ранца. Бьенбург Бранденбург сделал библиотеку эвристики упаковки упаковки в 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 игроков каждый), это переводится примерно на 6-24 часа на типичном современном ПК.

ИЗМЕНИТЬ

Подход, который может хорошо работать для вас (поскольку на практике вам не требуется точное решение), имитируется отжиг или постоянное улучшение путем случайной перестановки:

• Выберите команды в случайном порядке.
• Получить оценку для этой конфигурации (см. выше).
• Случайно меняйте участников между двумя или несколькими командами.
• Получить оценку для новой конфигурации. Если это лучше, чем предыдущий, сохраните его и повторите шаг 3. В противном случае отбросьте новую конфигурацию и повторите шаг 3.
• Когда оценка не улучшилась для некоторого фиксированного количества итераций (эксперимент, чтобы найти колено этой кривой), остановитесь. Вероятно, конфигурация, которая у вас на данный момент, будет достаточно близка к идеалу. Запустите этот алгоритм несколько раз, чтобы получить уверенность в том, что вы не попали на какой-то локальный оптимум, который значительно хуже идеального.

Ответ 2

Учитывая количество игроков в команде и гендерный рацион (который вы можете легко вычислить). Оставшаяся проблема называется проблема n-раздела, которая, к сожалению, является NP-полной и поэтому очень трудно точно решить. Вам придется использовать аппроксимативные или эвристические алгоритмы (эволюционные алгоритмы), если ваш размер проблемы слишком велик для решения грубой силы. Очень простое приближение будет сортировать по возрасту и назначать переменным образом.

Ответ 3

• Назначение значений очков уровням, полу и возрасту
• Назначьте сумму очков для каждого критерия для каждого игрока
• Сортировка игроков по их расчетному значению точки
• Назначить следующего игрока первой команде.
• Назначьте игроков второй команде, пока она не будет >= итоговые очки, чем первая команда, или команда достигнет максимальных игроков.
• Выполните 5 для каждой команды, перейдя к первой команде, пока все игроки не будут назначены.

Вы можете настроить значения уровня навыка, пола и возраста, чтобы изменить распределение каждого из них.

Ответ 4

Допустим, у вас шесть игроков (для простого примера). Мы можем использовать тот же алгоритм, который объединяет противников в турнирах с одиночной элитой и адаптирует их для создания "четных" команд на основе любых критериев, которые вы выбираете.

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

Почему?

Посмотрите на отдельные турниры по ликвидации на секунду. Идея использования алгоритма для генерации оптимальных совпадений с единственными исключениями заключается в том, чтобы избежать слишком короткой встречи с "топ-игроками" в турнире. Если топ-игроки встречаются слишком рано, один из лучших игроков будет ликвидирован на ранней стадии, что сделает турнир менее интересным. Мы можем использовать это "оптимальное" соединение для создания команд, в которых "верхние" игроки распределяются равномерно по командам. Затем разверните второй верхний игрок и т.д. И т.д.

Итак, перечислите игроков по критериям, которые вы хотите их разделить: сначала мужчины, потом женщины... отсортированы по возрасту. Мы получаем (например):

Player 1: Male - 18
Player 2: Male - 26
Player 3: Male - 45
Player 4: Female - 18
Player 5: Female - 26
Player 6: Female - 45

Затем мы применим алгоритм единственного исключения, который использует их "ранг" (который является только их номером игрока) для создания "хороших совпадений".

Генератор турнира с одиночным исключением в основном работает следующим образом: возьмите свой ранг (номер игрока) и измените бит (двоичный). Этот новый номер, который вы придумали, стал их "слотом" в турнире.

Player 1 in binary (001), reversed becomes 100 (4 decimal) = slot 4
Player 2 in binary (010), reversed becomes 010 (2 decimal) = slot 2
Player 3 in binary (011), reversed becomes 110 (6 decimal) = slot 6
Player 4 in binary (100), reversed becomes 001 (1 decimal) = slot 1
Player 5 in binary (101), reversed becomes 101 (5 decimal) = slot 5
Player 6 in binary (110), reversed becomes 011 (3 decimal) = slot 3

В турнире с одним удалением слот 1 воспроизводит слот 2, 3-vs-4, 5-vs-6. Мы собираемся использовать эти "пары ups" для создания оптимальных команд.

Глядя на номер игрока выше, упорядоченный по их номеру "слота", вот список, который мы придумали:

Slot 1: Female - 18
Slot 2: Male - 26
Slot 3: Female - 45

Slot 4: Male - 18
Slot 5: Female - 26
Slot 6: Male - 45

Когда вы разбиваете слоты на команды (два или более), вы получаете игроков в слоте 1-3 против игроков в слоте 4-6. Это лучшая/оптимальная группировка, которую вы можете получить.

Этот метод очень хорошо масштабируется со многими другими игроками, несколькими критериями (просто группируйте их правильно) и несколькими командами.

Ответ 5

Практически тривиальный подход для двух команд:

• Отсортировать всех игроков по оценке навыков/рангов.
• Назначить команду A лучшим игроком.
• Назначить команду B следующим двум лучшим игрокам
• Назначить команду A следующим двум лучшим игрокам
• goto 3
• Конец, когда у вас нет игроков.

Не очень гибкий и работает только в одном рейтинге столбцов, поэтому он не будет пытаться получить аналогичные гендерные или возрастные профили. Но это делает честно подобранные команды, если распределение входных данных достаточно плавное. Плюс это не всегда заканчивается тем, что команда A имеет запасной игрок, когда есть нечетное число.

Ответ 6

Идея:

• Сортировка игроков по умению
• Назначить лучших игроков в порядке (например: команда A: 1-й игрок, команда B: 2-й игрок,...)
• Назначьте худших игроков в порядке
• Loop on 2
• Оцените возможные исправления и выполните их (т.е.: если команда A имеет общий навык 19 с игроком с навыком 5, а команда B имеет общий навык 21 с игроком с навыком 4, замените их).
• Оценить возможные поправки в отношении гендерного распределения и выполнить их.
• Оцените возможные поправки в отношении распределения возраста и выполните их.

Ответ 7

Ну,

Мой ответ не о стратегии забивания команд/игроков, потому что все опубликованные хорошие, но я бы попробовал грубую силу или подход случайного поиска. Я не думаю, что стоит создать генетический алгоритм.

С уважением.