имя алгоритма, связанного с балансировкой / перераспределением нагрузки

Учитывая массив [x1, x2, x3, ..., xk], где xi - количество элементов в ящике i, как я могу распределить элементы так, чтобы ни одна коробка не содержала более N элементов. N близко к сумме (xi) / k - то есть N близко к каждому ящику, имеющему одинаковое количество элементов. Промежуточные коробки не следует использовать для перевозки предметов - если x1 имеет излишек, а x2 и x3 имеют дефицит, x1 должен отправить некоторые предметы x2 и x3, но не отправлять все свои предметы в x2, а затем позволить x2 разрешить излишек .

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

Думаю, у такого рода проблем есть название.

7
задан Gus 7 December 2011 в 07:45
поделиться