Алгоритм, который создает «команды» на основе числового значения умения

Question

Я создаю приложение, которое помогает управлять фристайловыми «турнирами шляп». Идея заключается в том, что люди подписываются на этот «турнир по шляпе». Когда они регистрируются, укажите нам числовое значение между 1 и 6, которое представляет их уровень мастерства.

В настоящее время мы берем этот огромный список людей, которые зарегистрировались, и вручную пытаются создать команды из этого на основе уровней квалификации каждого игрока. Я решил, что могу автоматизировать это, создав алгоритм, который разбивает команды как можно более равномерно.

Единственные данные, подаваемые в это, представляют собой массив «игроков» и желаемое «количество команд». Вообще говоря, мы смотрим 120 игроков и 8 команд.

Мой текущий процесс мышления состоит в том, чтобы в основном иметь «счет» для каждой команды. Этот счетный счет - это сумма всех уровней навыков назначенных игроков. Я прохожу через каждый уровень навыков. Я прохожу через раунды выбора один раз внутри цикла уровня квалификации. Порядок выбора выбирается в каждом раунде на основе оценки команды.

Это на самом деле работает достаточно хорошо, но его не идеально. Например, в моем массиве выборки я имел диапазон 5 баллов. Я мог бы очень легко, вручную поменять игроков вокруг и сделать расхождение не более 1 pt между командами .. проблема в том, что это делается программно.

Вот мой код до сих пор: http://pastebin.com/LAi42Brq

Отрывок из того, что данные выглядит следующим образом:

[2] => Array 
    (
     [user__id] => 181 
     [user__first_name] => Stephen 
     [user__skill_level] => 5 
    ) 

[3] => Array 
    (
     [user__id] => 182 
     [user__first_name] => Phil 
     [user__skill_level] => 6 
    ) 

Может кто-нибудь придумать лучше, легче, более эффективный способ сделать это? Спасибо заранее!!

Answer 1

Эта проблема, к сожалению, NP-Hard. Посмотрите на bin packing, который, вероятно, является хорошим местом для запуска, и включает в себя алгоритм, который вы можете надеяться настроить, это может быть или не быть полезным в зависимости от того, как должны быть «честные» две команды с одинаковым счетом.

Answer 2

Думаю, вы слишком усложняете. Если у вас есть команды T, сортируйте своих игроков в соответствии с их уровнем мастерства. Выберите лучших игроков T, чтобы быть капитанами команд. Затем, начиная с капитана 1, каждый капитан, в свою очередь, выбирает игроков, которых он хочет в команде. Вероятно, это будет человек в верхней части списка неубранных игроков.

Этот алгоритм работал на игровых площадках (и, я полагаю, на фризовых полях Калифорнии) на эоны и будет давать результаты как «справедливые» как более сложные псевдостатистические методы.

Answer 3

Простым решением может быть создание порядка выбора команды, тогда каждая команда «выберет» одного из самых квалифицированных игроков. В следующем раунде порядок отменяется, последняя команда, чтобы выбрать игрока, получает первый выбор, и первая команда получает последний выбор. Для каждого раунда вы меняете порядок комплектования.

Первый раунд комплектации заказов может быть:

A - B - C - D - E

второй раунд затем будет:

Е - Д - С - В - А

, а затем

A - B - C - D - Е и т.д.

Answer 4

похоже, что этот р roblem действительно NP-hard, являясь вариантом Multiprocessor scheduling problem.

Предложения «h00ligan» эквивалентны алгоритму LPT.

Другой эвристический стратегия будет вариация этого алгоритма:

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

С пример «6,5,5,3,3,1» и 2 команды, это даст команды «6,1,5» (= 12) и «5,3,3» (= 11). Стратегия «h00ligan» даст команды «6,3,3» (= 12) и «5,5,1» (= 11).