Алгоритм для создания ярмарки / равномерно подобранные команды на основе рейтингов плеера
@Kronikarz: От взглядов его GLEW, кажется, способ будущего. NVIDIA уже поставляет его наряду с OpenGL SDK. И его последний выпуск был в 2007 по сравнению с ЛИКОВАНИЕМ, которое было в 2006.
, Но, использование обеих библиотек смотрит почти то же мне. (GLEW имеет init () , который нужно назвать перед чем-либо еще все же.) Так, Вы не должны переключаться, если Вы не находите некоторое расширение, не поддерживаемое под ЛИКОВАНИЕМ.
7 ответов
Это задача упаковки бункера или многомерная задача о рюкзаке . Бьорн Б. Бранденбург создал библиотеку эвристики упаковки контейнеров в 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.
- Если результат не улучшился для некоторого фиксированного количества итераций (поэкспериментируйте, чтобы найти излом этого кривая), стоп. Вероятно, что конфигурация, которая у вас есть на данный момент, будет достаточно близка к идеальной. Запустите этот алгоритм несколько раз, чтобы убедиться, что вы не достигли некоторого локального оптимума, который значительно хуже идеального.
Учитывая количество игроков в команде и соотношение полов (которое вы можете легко вычислить). Оставшаяся проблема называется проблемой n-разбиений , которая, к сожалению, является NP-полной и поэтому ее очень трудно решить точно. Вам придется использовать приближенные или эвристические алгоритмы (эволюционные алгоритмы), если размер вашей задачи слишком велик для решения методом грубой силы. Очень простое приближение - сортировка по возрасту и присвоение поочередно.
- Присвойте значения очков уровню навыков, полу и возрасту
- Назначьте сумму очков по каждому критерию каждому игроку
- Сортировка игроков по их вычисленному значению очков
- Назначьте следующего игрока в первую команду
- Назначьте игроков во вторую команду, пока она не наберет> = общее количество очков, чем первая команда, или пока команда не достигнет максимального количества игроков.
- Выполните по 5 для каждой команды, возвращаясь к первой команды, пока не будут назначены все игроки
Вы можете настроить уровень навыков, пол и возрастные очки, чтобы изменить распределение каждого из них.
Допустим, у вас шесть игроков (для простого примера). Мы можем использовать тот же алгоритм, который объединяет соперников в пары в турнирах с одним выбыванием и адаптировать его для создания «равных» команд на основе любых критериев, которые вы выберете.
Сначала ранжируйте ваших игроков от лучшего к худшему. Не воспринимайте это слишком буквально. Вам нужен список игроков, отсортированный по критериям, которые вы хотите разделить .
Почему?
Давайте на секунду посмотрим на турниры на выбывание. Идея использования алгоритма для генерации оптимальных матчей с выбыванием одного игрока состоит в том, чтобы избежать проблемы слишком ранней встречи «лучших игроков» в турнире. Если лучшие игроки встречаются слишком рано, один из лучших игроков вылетает раньше, что делает турнир менее интересным. Мы можем использовать это " для создания оптимальных команд.
Глядя на номер игрока выше, отсортированный по «номеру слота», вот список, который мы придумали:
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. Это лучшая / оптимальная группировка, которую вы можете получить.
Этот метод очень хорошо масштабируется с большим количеством игроков, несколькими критериями (просто правильно сгруппируйте их вместе) и несколькими командами.
Идея:
- Сортировка игроков по навыкам
- Назначить лучших игроков по порядку (например: команда A: 1-й игрок, команда B: 2-й игрок, ...)
- Назначить худшие игроки в порядке
- Зациклить на 2
- Оценить возможные исправления и выполнить их (например: если у команды A общий навык 19 с игроком с навыком 5, а у команды B общий навык 21 с игроком с навык 4, поменяйте их местами)
- Оцените возможные исправления гендерного распределения и выполните их
- Оцените возможные исправления возрастного распределения и выполните их
Ну,
Мой ответ не о стратегиях подсчета очков команд / игроков, потому что все опубликованные хороши, но я бы попробовал брутфорс или случайный поиск подход. Не думаю, что стоит создавать генетический алгоритм.
С уважением.
Почти тривиальный подход для двух команд:
- Отсортируйте всех игроков по оценке навыков / ранга.
- Назначьте команду A лучшим игроком.
- Назначьте команду B следующим ] два лучших игрока
- Назначьте команду A следующих двух лучших игроков
- goto 3
- Закончите, когда у вас закончились игроки.
Не очень гибкий, и только работает с ранжированием по одному столбцу, поэтому не будет пытаться получить аналогичные половые или возрастные профили. Но при достаточно плавном распределении входных данных из него действительно получаются хорошо подобранные команды. К тому же это не всегда заканчивается тем, что у команды А есть запасной игрок, когда есть нечетное число.