Задача:
Давайте рассмотрим следующий сценарий:
Пусть T={t_1, t_2, ..., t_h} будет набором различных игр.Каждая игра ведется один на один (это игры для одного игрока).
Пусть n - это число players, каждое с известным показателем производительности для каждой игры.Эта мера может быть непосредственно переведена в вероятность выигрыша в данной игре. Редактировать: функция Q(i|q) дает ожидаемую вероятность того, что игрок i выиграет в игре q против игроков с одинаковым распределением из набора players.
Во время турнира команда игроков берет одну из игр из T (она выбирается случайным образом с равномерным распределением) и может делегировать одного игрока (с лучшим показателем производительности) для игры от имени этих команд.
Из всех возможных k команд-членов (k<n) выберите ту, которая имеет наибольшую вероятность выиграть турнир.
Уточнение: игроки и команды сталкиваются с командами, сформированными из одного и того же набора n игроков.Возможно, лучшим способом описания проблемы было бы сказать, что:
1) все возможные k команды-члены создаются из заданного набора n игроков (игроки могут дублироваться во многих командах, но нет двух командможет иметь одинаковый набор игроков),
2) эти команды объединены в пару, и для каждой пары проводится игра из T,
3) каждая команда выбирает своего лучшего игрока для данной игры (согласноизвестный показатель производительности, приведенный в описании проблемы) - это может привести к тому, что игроки будут играть против одинаковых копий самих себя;обратите внимание, что «лучший игрок» выбирается без каких-либо знаний о членах противостоящей команды, только значения Q(-|q) ее собственных членов,
4) каждая команда набирает количество очков, равное вероятности победы в игре (реальные игры никогда не проводятся, мы переходим к ожидаемым очкам, полученным от игры против данной команды противника, при условии, что проигрыш дает 0 и выигрыш 1 очка),
5) шаги 2-4 повторяются для всех комбинаций паркоманды и игры,
6) выигрывает команда, набравшая наибольшее количество очков (количество команд пропорционально вероятности выиграть одну игру против одной команды, если указанная игра и команда соперника были выбраны случайным образом с равномерным распределением соответственно *)1043 * и набор всевозможных k членов команды)
Что такое "быстрый" способ найти эту команду-победителя?
Решение методом грубой силы:
Мы делаем именно то, что написано в разъяснении .
Этот тип решения не удалсяК сожалению, когда n достигает больших чисел - для n>>k количество возможных команд приблизительно равно n^k, что делает невозможным быстрое указание на лучшую команду.
Чторешения (алгоритма) я ищу?
Очевидно, что все, что может создать эту команду как итеративный процесс, который не включает в себя проверку всех возможных составов команды.Если точного решения не существует, то приемлемо приблизительное решение (т.е. создание команды из 95-го процентиля).
Я некоторое время думал об этой проблеме, но я не могу предоставить каких-либо точных доказательств того, что любой из предложенных мной методов удовлетворит мои условия.Одно из возможных решений, которое я придумал, заключалось бы в выборе игрока с наибольшим количеством игр, в котором его собственный рейтинг выше, чем, например, у.95% игроков - это будет 1-й игрок команды.Затем я бы выбрал всех возможных 2-х игроков и добавил ту, которая увеличивает количество игр, в которых команда лучше, чем, например, 95% игроков.Затем я продолжу процесс, пока k-th игрок не будет найден.
Это решение создает очевидную проблему, заключающуюся в том, что мы ни в коем случае не сравниваем m-th команд игроков друг с другом и даже не пытаемся найти действительно лучшую команду (что, честно говоря, не так уж важно),
Буду признателен за любую помощь - также в виде любых ссылок на внешние источники / опубликованные статьи и т. Д., Связанных с такого рода проблемами.Большинство проблем, которые я рассмотрел, связаны с созданием команд, предполагающих, что производительность команд связана со средней эффективностью ее участников, а не с наивысшей производительностью при выполнении некоторых задач.