Как уравнять суммы в корзинках ленивой перестановкой?

Рейтинг: 1Ответов: 2Опубликовано: 13.11.2014

Есть массив массивов с целыми числами.

Перемещая числа между массивами, надо стремиться уравнять суммы чисел в каждом.

«Ленивые» эти перестановки потому, что надо также минимизировать кол-во переехавших, и дистанцию, на которую они переезжают. Т.е. лучше переместить 1 двойку, чем 2 числа по единице каждое. Лучше переехать на 1 массив вправо, чем на 2 влево. Первый и последний массив считаем соседними.

Подскажите, пожалуйста, каков может быть алгоритм?

В рабочей задаче порядка 100 массивов, около 100k целых чисел в диапазоне от 1 до 1e7.

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

Родственный вопрос, но там свободная сортировка, а здесь приходится иметь дело с имеющимся набором и минимизировать изменения.

статистика математика алгоритм балансировка
Источник: Stack Overflow на русском

Ответы

▲ 2

Я с такими задачами не сталкивался, на ум приходит только то, что тут надо строить граф, у которого весовыми значениями будет выступать сумма: расстояние + количество перемещаемых элементов.

То есть высчитать сумму в каждом массиве, запомнить среднее значение и спроецировать их номера по возрастанию. Далее смотреть и строить этот граф.

  1. Взять самый крупный и из него максимальные числа, которые могут заполнить самый минимальный и уравнять максимальный.
  2. Взять, который ближе по шагам к минимальному, и из него максимальные числа, которые могут заполнить самый минимальный и уравнять этот массив.
  3. И т.д.

То есть в итоге получится граф:

  1. 1 элемент 10 шагов = 11 (самый крупный к минимальному).
  2. 1 элемента 9 шагов = 10 ((самый крупный - 1) к минимальному).
  3. 4 элементов 8 шагов = 12 ((самый крупный - 2) к минимальному).
  4. И т.д.

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

▲ 1

Общая цель "ленивой перестановки" - выравнивание сумм по корзинам, поэтому первое и очевидное действие - вычислить требуемую среднюю сумму чисел и её избыток (недостаток) по каждой из n корзин. Это совсем просто:

av = sum (Si), di = av - Si где Si - суммы в корзинах.

Второй понятный момент - расписать задачу в терминах потоков между соседними корзинами. Пусть qi - сумма всех чисел, перешедших из (i+1)-й корзины в i-ю, тогда для установления требуемой суммы в каждой корзине должны быть соблюдены следующие условия:

q1 - qn = d1, q2 - q1 = d2, ... , qn-1 - qn-2 = dn-1, qn - qn-1 = dn.

Полагая qn = C, нетрудно получить следующие соотношения для потоков:

q1 = d1+С, q2 = d1 + d2 + C, ... , qn-1 = d1 + d2 + ... + dn-1 + C, qn = C.

Параметр С можно задать (как минимум - инициализировать), исходя из критерия минимизации суммы квадратов потоков (который не противоречит идеям "ленивой перестановки"). Приравнивая к нулю производную этой суммы, приходим к выражению

С = ((n-1)d1+(n-2)d2+...+dn-1)/n

Таким образом, задача "ленивой перестановки" сведена к системе локальных задач о наборе чисел с заданной суммой из текущей корзины для перекладывания их в предыдущую корзину. А это - разновидность "задачи о рюкзаке".