Есть N игроков. Нужно распределить их на M команд, по K игроку в каждой команде (для удобства, N делится на M без остатка, т.е. M*K = N)
Для каждого игрока известен его уровень, который определяется числом (скажем, от 0 до 1000). Уровень команды определяется как сумма уровней игроков в ней.
Задача — распределить игроков по командам так, чтобы все команды были как можно более одинаковы. Т.е. нужно минимизировать максимальное отклонение от среднего уровня.
Здравствуйте, RiNSpy, Вы писали:
RNS>Есть N игроков. Нужно распределить их на M команд, по K игроку в каждой команде (для удобства, N делится на M без остатка, т.е. M*K = N)
RNS>Для каждого игрока известен его уровень, который определяется числом (скажем, от 0 до 1000). Уровень команды определяется как сумма уровней игроков в ней.
RNS>Задача — распределить игроков по командам так, чтобы все команды были как можно более одинаковы. Т.е. нужно минимизировать максимальное отклонение от среднего уровня.
Если нужно самое оптимальное решение — то полный перебор вариантов, иначе — разные "жадные" алгоритмы. Вроде так.
Здравствуйте, Qulac, Вы писали:
Q>Если нужно самое оптимальное решение — то полный перебор вариантов,
Перебор не выйдет, там факториальная сложность. Число возможных распределений — N! / (M! * K!). Если у нас 100 человек и 10 команд, перебор уже не получится.
Q>иначе — разные "жадные" алгоритмы. Вроде так.
Какие? Думаю, тут не столько жадные алгоритимы лучше, сколько итеративная оптимизация (взять случайный вариант, и итеративно его улучшать, пока не упрёмся в локальный минимум). Затем можно взять другую случайную стартовую конфигурацию, и повторять процесс, находя новые локальные минимумы. Затем как результат брать наименьший локальный минимум. Если процесс будем повторять бесконечно, то гарантированно найдём глобальный минимум, но можем остановить процесс в любой момент и использовать результат, известный на тот момент.
Вопрос тогда, что мы должны делать во время каждой итерации, чтобы гарантированно направляться к локальному минимуму (т.е. уменьшать максимальную дистанцию от среднекомандного значения).
Здравствуйте, RiNSpy, Вы писали:
RNS>Здравствуйте, Qulac, Вы писали:
Q>>Если нужно самое оптимальное решение — то полный перебор вариантов,
RNS>Перебор не выйдет, там факториальная сложность. Число возможных распределений — N! / (M! * K!). Если у нас 100 человек и 10 команд, перебор уже не получится.
Это мы в курсе.
Q>>иначе — разные "жадные" алгоритмы. Вроде так.
RNS>Какие? Думаю, тут не столько жадные алгоритимы лучше, сколько итеративная оптимизация (взять случайный вариант, и итеративно его улучшать, пока не упрёмся в локальный минимум). Затем можно взять другую случайную стартовую конфигурацию, и повторять процесс, находя новые локальные минимумы. Затем как результат брать наименьший локальный минимум. Если процесс будем повторять бесконечно, то гарантированно найдём глобальный минимум, но можем остановить процесс в любой момент и использовать результат, известный на тот момент.
RNS>Вопрос тогда, что мы должны делать во время каждой итерации, чтобы гарантированно направляться к локальному минимуму (т.е. уменьшать максимальную дистанцию от среднекомандного значения).
Здравствуйте, Qulac, Вы писали:
RNS>>Какие? Думаю, тут не столько жадные алгоритимы лучше, сколько итеративная оптимизация (взять случайный вариант, и итеративно его улучшать, пока не упрёмся в локальный минимум). Затем можно взять другую случайную стартовую конфигурацию, и повторять процесс, находя новые локальные минимумы. Затем как результат брать наименьший локальный минимум. Если процесс будем повторять бесконечно, то гарантированно найдём глобальный минимум, но можем остановить процесс в любой момент и использовать результат, известный на тот момент.
RNS>>Вопрос тогда, что мы должны делать во время каждой итерации, чтобы гарантированно направляться к локальному минимуму (т.е. уменьшать максимальную дистанцию от среднекомандного значения).
Q>Вот решение похожей задачи о камнях разными способами: https://petrsu.ru/files/document/uploads/algol.pdf
Там перебором испытывают все кобминации замен и проверяют, улучшают ли они решение.
В нашем случае можно даже проще — т.к. мы пытаемся уменьшить разницу для команды, которая максимально удалена от среднего значения, нам надо рассмотреть только замены с участием игроков из этой команды. Получается перебор K*(N-K), с проверкой, уменьшается ли максимальное расстояние от среднего значения. Можно ли ускорить эту итерацию? Чтобы было даже не O(K^2), а O(K)?
Здравствуйте, RiNSpy, Вы писали:
RNS>В нашем случае можно даже проще — т.к. мы пытаемся уменьшить разницу для команды, которая максимально удалена от среднего значения, нам надо рассмотреть только замены с участием игроков из этой команды. Получается перебор K*(N-K), с проверкой, уменьшается ли максимальное расстояние от среднего значения. Можно ли ускорить эту итерацию? Чтобы было даже не O(K^2), а O(K)?
Это не даст оптимального решения, только квазиоптимальное.
Здравствуйте, RiNSpy, Вы писали:
RNS>Задача — распределить игроков по командам так, чтобы все команды были как можно более одинаковы. Т.е. нужно минимизировать максимальное отклонение от среднего уровня.
Ну ты же знаешь, чему равен этот "средний уровень". Вот и подгоняй под него.
Здравствуйте, gandjustas, Вы писали:
G>Здравствуйте, RiNSpy, Вы писали:
RNS>>В нашем случае можно даже проще — т.к. мы пытаемся уменьшить разницу для команды, которая максимально удалена от среднего значения, нам надо рассмотреть только замены с участием игроков из этой команды. Получается перебор K*(N-K), с проверкой, уменьшается ли максимальное расстояние от среднего значения. Можно ли ускорить эту итерацию? Чтобы было даже не O(K^2), а O(K)?
G>Это не даст оптимального решения, только квазиоптимальное.
В смысле? Да, мы будем застревать в локальных минимумах, но если начинать из различных случайных конфигураций, то мы должны, при количестве попыток стремящимся к бесконечности, найти оптимальное решение. На практике, должны к нему довольно быстро приблизиться.
Но главный вопрос — как проводить итерации, чтобы они были O(K)?
G>>Это не даст оптимального решения, только квазиоптимальное. RNS>В смысле? Да, мы будем застревать в локальных минимумах, но если начинать из различных случайных конфигураций, то мы должны, при количестве попыток стремящимся к бесконечности, найти оптимальное решение. На практике, должны к нему довольно быстро приблизиться.
Количество попыток, стремящихся к бесконечности не гарантируют оптимальности.
Но множество решений счетное, поэтому при достаточном количестве попыток мы просто все варианты переберем.
Здравствуйте, gandjustas, Вы писали:
G>Количество попыток, стремящихся к бесконечности не гарантируют оптимальности.
G>Но множество решений счетное, поэтому при достаточном количестве попыток мы просто все варианты переберем.
Ну то есть значит всё-таки гарантирует?
На практике, я думаю мы должны придти к оптимальному решению намного раньше, а к достаточно хорошему решению — совсем быстро. Но зависит от исходных данных.
Здравствуйте, RiNSpy, Вы писали:
RNS>Есть N игроков. Нужно распределить их на M команд, по K игроку в каждой команде (для удобства, N делится на M без остатка, т.е. M*K = N) RNS>Для каждого игрока известен его уровень, который определяется числом (скажем, от 0 до 1000). Уровень команды определяется как сумма уровней игроков в ней. RNS>Задача — распределить игроков по командам так, чтобы все команды были как можно более одинаковы. Т.е. нужно минимизировать максимальное отклонение от среднего уровня.
вообще, перебор тут работает. разделение 100 человек на 10 команд делается очень быстро. сложности начинаются на 3-5к.
ну и если брать реальность, а не абстрактные задачи, то там начинают ролять разные игровые нюансы.
Здравствуйте, RiNSpy, Вы писали:
RNS>Есть N игроков. Нужно распределить их на M команд, по K игроку в каждой команде (для удобства, N делится на M без остатка, т.е. M*K = N)
RNS>Для каждого игрока известен его уровень, который определяется числом (скажем, от 0 до 1000). Уровень команды определяется как сумма уровней игроков в ней.
RNS>Задача — распределить игроков по командам так, чтобы все команды были как можно более одинаковы. Т.е. нужно минимизировать максимальное отклонение от среднего уровня.
Сортируем игроков по убыванию уровня. Далее, берем первые M игроков (т.е. с наибольшем уровнем) и назначаем их в команды от 1 до M. На сл. итерации берем следующие M игроков и назначаем их в команды уже от M до 1. На сл. итерации опять от 1 до М. Т.е. команде на пред. итерации достававшейся игрок с наименьшим уровнем, на тек. уровне получает игрока с наибольшим.
Здравствуйте, Sharov, Вы писали:
S>Сортируем игроков по убыванию уровня. Далее, берем первые M игроков (т.е. с наибольшем уровнем) и назначаем их в команды от 1 до M. На сл. итерации берем следующие M игроков и назначаем их в команды уже от M до 1. На сл. итерации опять от 1 до М. Т.е. команде на пред. итерации достававшейся игрок с наименьшим уровнем, на тек. уровне получает игрока с наибольшим.
Здравствуйте, Kernighan, Вы писали:
K>Здравствуйте, Sharov, Вы писали:
S>>Сортируем игроков по убыванию уровня. Далее, берем первые M игроков (т.е. с наибольшем уровнем) и назначаем их в команды от 1 до M. На сл. итерации берем следующие M игроков и назначаем их в команды уже от M до 1. На сл. итерации опять от 1 до М. Т.е. команде на пред. итерации достававшейся игрок с наименьшим уровнем, на тек. уровне получает игрока с наибольшим.
K>А после этого доравнять парными перестановками.
Здравствуйте, Kernighan, Вы писали:
K>Здравствуйте, Sharov, Вы писали:
S>>Сортируем игроков по убыванию уровня. Далее, берем первые M игроков (т.е. с наибольшем уровнем) и назначаем их в команды от 1 до M. На сл. итерации берем следующие M игроков и назначаем их в команды уже от M до 1. На сл. итерации опять от 1 до М. Т.е. команде на пред. итерации достававшейся игрок с наименьшим уровнем, на тек. уровне получает игрока с наибольшим.
K>А после этого доравнять парными перестановками.
Можно ли найти необходимую парную перестановку для улучшения результата, без перебора всех возможных перестановок? Т.е. за время O(K)? Можно считать, что игроки в командах уже отсортированы по убыванию.
Здравствуйте, Sharov, Вы писали:
S>Здравствуйте, Kernighan, Вы писали:
K>>Здравствуйте, Sharov, Вы писали:
S>>>Сортируем игроков по убыванию уровня...
K>>А после этого доравнять парными перестановками.
S>Зачем?
Когда мы сортируем игроков по убыванию, в некоторых местах получаются большие "ступеньки".
Чтобы сгладить эти ступеньки при втором-третьем проходе бывает нужно взять не следующего игрока из списка, а игрока подальше.
Здравствуйте, RiNSpy, Вы писали:
RNS>Здравствуйте, Kernighan, Вы писали:
K>>Здравствуйте, Sharov, Вы писали:
S>>>Сортируем игроков по убыванию уровня. Далее, берем первые M игроков (т.е. с наибольшем уровнем) и назначаем их в команды от 1 до M. На сл. итерации берем следующие M игроков и назначаем их в команды уже от M до 1. На сл. итерации опять от 1 до М. Т.е. команде на пред. итерации достававшейся игрок с наименьшим уровнем, на тек. уровне получает игрока с наибольшим.
K>>А после этого доравнять парными перестановками.
RNS>Можно ли найти необходимую парную перестановку для улучшения результата, без перебора всех возможных перестановок? Т.е. за время O(K)? Можно считать, что игроки в командах уже отсортированы по убыванию.
Для заданной пары команд, очевидно, можно найти лучшую перестановку пары игроков за O(K ln(K)).
Однако, для перебора всех пар команд потребуется O( (M/K)^2 K ln(K) )=O( M^2 ln(K)/K ), что лучше чем O(M^2) (полный перебор пар игроков), но не на много. Для K=10, вероятно, не стоит заворачиваться.
Если начинать с пары команд, для которых вероятность найти перестановку максимальна, (лучшая + худшая команды), и ограничиться первой найденной перестановкой по среднее время будет еще меньше.
Учитывая, что нужен не минимум, а только "достаточно хорошее решение", иногда цикл разравнивания останавливают, если улучшающих перестановок больше нет среди между лучшей и худшей команд.
Здравствуйте, Chorkov, Вы писали:
K>>>А после этого доравнять парными перестановками.
RNS>>Можно ли найти необходимую парную перестановку для улучшения результата, без перебора всех возможных перестановок? Т.е. за время O(K)? Можно считать, что игроки в командах уже отсортированы по убыванию.
C>Для заданной пары команд, очевидно, можно найти лучшую перестановку пары игроков за O(K ln(K)).
А почему O(K ln(K))? Это самая интересная часть.
C>Однако, для перебора всех пар команд потребуется O( (M/K)^2 K ln(K) )=O( M^2 ln(K)/K ), что лучше чем O(M^2) (полный перебор пар игроков), но не на много. Для K=10, вероятно, не стоит заворачиваться.
C>Если начинать с пары команд, для которых вероятность найти перестановку максимальна, (лучшая + худшая команды), и ограничиться первой найденной перестановкой по среднее время будет еще меньше. C>Учитывая, что нужен не минимум, а только "достаточно хорошее решение", иногда цикл разравнивания останавливают, если улучшающих перестановок больше нет среди между лучшей и худшей команд.
А в остальном да, это имхо правильный/наилучший ответ.
Здравствуйте, Kernighan, Вы писали:
K>Здравствуйте, Sharov, Вы писали:
S>>Здравствуйте, Kernighan, Вы писали:
K>>>Здравствуйте, Sharov, Вы писали:
S>>>>Сортируем игроков по убыванию уровня...
K>>>А после этого доравнять парными перестановками.
S>>Зачем?
K>Когда мы сортируем игроков по убыванию, в некоторых местах получаются большие "ступеньки". K>Чтобы сгладить эти ступеньки при втором-третьем проходе бывает нужно взять не следующего игрока из списка, а игрока подальше.
Ну вот в свое решении выше я брал отсортированных по рейтингу игроков и распределял по командам от 1 до M, в сл. итерации наоборот от М до 1, буквально. Я так понял, что для более эффективного распределения, команды перед распределение игроков надо сортировать по уже полученным очкам. Это правильно?
Здравствуйте, RiNSpy, Вы писали:
RNS>А почему O(K ln(K))? Это самая интересная часть.
Пусть S1, S2 — суммы для первой и второй группы.
Пусть S1>S2, (чтобы рассматривать вдвое меньше случаев).
Тогда для уменьшения энтропии нам нужно найти такую пару a_i, a_j, чтобы минимизировать
f(i,j) = | (S1-a_i+a_j) — (S2-a_j+a_i) |
на множестве пар i,j из заданных групп.
Обозначим D(i,j)=a_i-a_j, тогда:
f(i,j) = | (S1-S2) — 2 D(i,j) |
Т.е. оптимальная разница между элементами D=(S1-S2)/2 (она уравновешивает группы), но нас устроит 0 < D < (S1-S2)
Т.е. задавшись a_i, мы будем иметь ограничение на a_j: a_i < a_j < a_i+(S1-S2).
Оптимальное значение a_j_opt = a_i+(S1-S2)/2.
Алгоритм:
1) цикл по всем a_i (из первой группы) O(K)
{
2) Делением отрезка пополам ищем минимальное a_j , такое что a_j >= a_i+(S1-S2)/2
(обозначим его как a_j_u)
сложность O(ln(K))
3) возьмем предыдущий элемент, обозначим как a_j_l, это будет максимальные элемент,
такой что a_j < a_i+(S1-S2)/2
сложность O(1)
4) смотрим какой из элементов лучше (a_j_l или a_j_u), и удовлетворяет ли он условию.
сложность O(1)
}
