Идеи для алгоритма оптимизации для Fantasy Football

Question

Итак, это немного отличается от стандартного фэнтези-футбола. У меня есть список игроков, их средние «очки за игру» (PPG) и их зарплата. Я хочу максимизировать количество очков за игру при условии, что моя команда не превысит лимит зарплаты. Команда состоит из 1 QB, 1 TE, 3 WR и 2 RB. Итак, если у нас по 15 на каждую позицию, у нас есть 15X15 X (15 c 3) X (15 c 2) = 10749375 возможных команд.

Довольно вычислительно сложен. Я могу использовать немного веток и границ, т. Е. Как только команда превзойдет предел зарплаты, я могу урезать дерево, но даже с этим алгоритм все еще довольно медленный. Я попробовал другой вариант, где я использовал «генетический алгоритм», то есть сделал 10 случайных команд, выбрал лучшую и «мутировал» ее (произвольно меняя некоторых игроков) в еще 10 команд, а затем выбрал их, а затем перебрал группу раз, пока очки за игру «лучшей команды» не перестали улучшаться.

Должен быть лучший способ сделать это. Я не специалист по информатике, и я только прошел начальный курс по алгоритмике. Программисты - что вы думаете? У меня такое ощущение, что какое-то применение динамического программирования может помочь.

Спасибо

Answer 1

Я думаю, что разумно реализованный генетический алгоритм даст приемлемый для вас результат.Возможно, вы захотите использовать метрики, такие как баллы за доллар зарплаты, а не прямой PPG, чтобы выбрать лучшую команду.Таким образом, вы по сути измеряете добавленную стоимость.Кроме того, вам следует рассмотреть возможность запуска полного алгоритма / мутации до удовлетворительного завершения несколько раз, чтобы вы могли определить, какие игроки последовательно показывают в окончательных результатах.Этих игроков тогда стоит ценить выше других.

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

Answer 2

Это помогает?Он устанавливает ограничения и максимизирует количество баллов.

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

http://pena.lt/y/2014/07/24/mathematically-optimising-fantasy-football-teams 14/07/24 / математически-оптимизирующий-фэнтези-футбол-команды

Answer 3

Прежде всего, предоставленный вами вариант не должен быть правильным. Лучший способ построить команду - это ограничить позиции ограниченным, плюс нет абсолютно никакого смысла перемещать 3 одинаковых позиции игроков между собой.

Кристиан Роналду, Суарес и Месси дадут вам равную сумму очков фантазии в любом составе, например: Кристиан Роналду, Суарес и Месси или же Суарес, Кристиан Роналду и Месси или же Месси, Суарес, Роналду

Первый шаг - упростить возможность изменения. Следующий шаг - вычислите среднюю цену и постройте команду один за другим, добавив игрока с более низкой зарплатой, но более высокой ценой. Когда достигнете предела зарплаты, уберите дорогой и добавьте дешевле, но с теми же баллами фантазии - и так далее. Не создавайте вариации, оцените вес каждого игрока комбинацией очков зарплаты и фантазии.

Answer 4

Возьмите i в качестве текущего числа игроков из n игроков, а j в качестве текущей оставшейся зарплаты. Возьмем m [i, j] как динамический набор решений.

Then m[i, 0] = 0, m[0, j] = 0
and

m[i, j] = m[i - 1, j] if salary for player i is greater than j

else

m[i, j] = max ( m[i - 1, j], m[i - 1, j - salary of player i] + PPG of player i)

Извините, что я не знаю R, но я хорошо разбираюсь в алгоритмах, поэтому я надеюсь, что это поможет.

Дальнейшая оптимизация, которую вы можете сделать, заключается в том, что вам действительно нужны только 2 строки m [i, j], потому что решение DP использует только текущую строку и последнюю строку (вы можете сэкономить память таким образом)