Распространять объекты равномерно по нескольким коллекциям

Сценарий состоит в том, что существуют n объекты разных размеров, неравномерно распределенные по m ведрам. Размер ведра - это сумма всех размеров объектов, которые он содержит. Теперь случается, что размеры ведер сильно различаются.

Что было бы хорошим алгоритмом, если бы я хотел равномерно распределять эти объекты над этими ведрами, чтобы общий размер каждого ведра был примерно таким же? Было бы неплохо, если бы алгоритм наклонился к меньшему размеру перемещения над совершенно равномерным разбросом.

У меня есть это наивное, неэффективное и багги-решение в Ruby.

buckets = [ [10, 4, 3, 3, 2, 1], [5, 5, 3, 2, 1], [3, 1, 1], [2] ]

avg_size = buckets.flatten.reduce(:+) / buckets.count + 1

large_buckets = buckets.take_while {|arr| arr.reduce(:+) >= avg_size}.to_a

large_buckets.each do |large|
  smallest = buckets.last

  until ((small_sum = smallest.reduce(:+)) >= avg_size)
    break if small_sum + large.last >= avg_size
    smallest << large.pop
  end

  buckets.insert(0, buckets.pop)
end

=> [[3, 1, 1, 1, 2, 3], [2, 1, 2, 3, 3], [10, 4], [5, 5]]

Ответ 1

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

Сортируйте каждое отдельное ведро в порядке убывания размера, используя сбалансированное двоичное дерево.
Рассчитать средний размер.
Сортируйте ведра с размером меньше среднего ( "слишком маленькие ведра" ) в порядке убывания размера, используя сбалансированное двоичное дерево.
Сортируйте ведра с размером больше среднего ( "слишком большие ведра" ) в порядке размера их наибольших элементов, используя сбалансированное двоичное дерево (так что сначала будет ведро с {9, 1}, а ведро с {8, 5} будет вторым).
Pass1: удалить наибольший элемент из ведра с наибольшим элементом; если это уменьшает его размер ниже среднего, то замените удаленный элемент и удалите ведро из сбалансированного двоичного дерева "слишком больших ведер"; иначе поместите элемент в наименьшее ведро и повторно проиндексируйте два измененных ведра, чтобы отразить новый самый маленький ковш и новое "слишком большое ведро" с самым большим элементом. Продолжайте повторять, пока вы не удалите все "слишком большие ведра" .
Pass2: Итерации через "слишком мелкие ведра" от наименьшего до самого большого и выберите наиболее подходящие элементы из самого большого "слишком большого ведра", не заставляя его становиться "слишком маленьким ведром"; итерации через оставшиеся "слишком большие ведра" от самых больших до самых маленьких, удаляя из них наиболее подходящие элементы, не заставляя их становиться "слишком маленькими ведрами". Сделайте то же самое для остальных "слишком маленьких ведер". Результаты этого варианта не будут такими же хорошими, как и для более сложного варианта, поскольку он не будет сдвигать ведра из "слишком большой" в "слишком маленькую" категорию или наоборот (следовательно, пространство поиска будет быть меньше), но это также означает, что он имеет гораздо более простые условия остановки (просто перебирайте все "слишком маленькие" ведра и затем останавливайтесь), тогда как сложный вариант может вызвать бесконечный цикл, если вы не будете осторожны.

Идея состоит в том, что, перемещая самые большие элементы в Pass1, вы упрощаете более точное сопоставление размеров ведер в Pass2. Вы используете сбалансированные двоичные деревья, чтобы вы могли быстро переиндексировать ведра или деревья ведер после удаления или добавления элемента, но вместо этого вы могли бы использовать связанные списки (сбалансированные бинарные деревья имели бы лучшую производительность в худшем случае, но связанные списки может иметь лучшие средние показатели). Выполняя наилучшую посадку вместо первого соответствия в Pass2, вы с меньшей вероятностью выполняете бесполезные ходы (например, перемещая объект размером 10 из ведра, который больше 5, чем средний, в ведро, которое на 5 меньше среднего, будет слепо исполнять фильм, лучше всего подходит либо к следующему "слишком большому ведру" для объекта с более высоким размером, либо удалит "слишком маленькое ведро" из дерева ковша).

Ответ 2

У меня получилось что-то вроде этого.

Сортируйте ведра в порядке убывания размера.
Сортировка каждого отдельного ковша в порядке убывания размера.
Рассчитать средний размер.
Итерации над каждым ведром размером более среднего.
Перемещайте объекты в порядке размера от этих ведер до наименьшего ведра, пока либо большой ковш не будет меньше среднего, либо целевой ковш достигнет среднего размера.

Пример кода Ruby

require 'pp'

def average_size(buckets)
  (buckets.flatten.reduce(:+).to_f / buckets.count + 0.5).to_i
end

def spread_evenly(buckets)
  average = average_size(buckets)
  large_buckets = buckets.take_while {|arr| arr.reduce(:+) >= average}.to_a

  large_buckets.each do |large_bucket|
    smallest_bucket = buckets.last
    smallest_size = smallest_bucket.reduce(:+)
    large_size = large_bucket.reduce(:+)

    until (smallest_size >= average)
      break if large_size <= average
      if smallest_size + large_bucket.last > average and large_size > average
        buckets.unshift buckets.pop
        smallest_bucket = buckets.last
        smallest_size = smallest_bucket.reduce(:+)
      end
      smallest_size += smallest_object = large_bucket.pop
      large_size -= smallest_object
      smallest_bucket << smallest_object
    end

    buckets.unshift buckets.pop if smallest_size >= average
  end
  buckets
end

test_buckets = [ 
  [ [10, 4, 3, 3, 2, 1], [5, 5, 3, 2, 1], [3, 1, 1], [2] ],
  [ [4, 3, 3, 2, 2, 2, 2, 1, 1], [10, 5, 3, 2, 1], [3, 3, 3], [6] ],
  [ [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1], [1, 1] ],
  [ [10, 9, 8, 7], [6, 5, 4], [3, 2], [1] ],
]

test_buckets.each do |buckets|
  puts "Before spread with average of #{average_size(buckets)}:"
  pp buckets
  result = spread_evenly(buckets)
  puts "Result and sum of each bucket:"
  pp result
  sizes = result.map {|bucket| bucket.reduce :+}
  pp sizes
  puts
end

Вывод:

Before spread with average of 12:
[[10, 4, 3, 3, 2, 1], [5, 5, 3, 2, 1], [3, 1, 1], [2]]
Result and sum of each bucket:
[[3, 1, 1, 4, 1, 2], [2, 1, 2, 3, 3], [10], [5, 5, 3]]
[12, 11, 10, 13]

Before spread with average of 14:
[[4, 3, 3, 2, 2, 2, 2, 1, 1], [10, 5, 3, 2, 1], [3, 3, 3], [6]]
Result and sum of each bucket:
[[3, 3, 3, 2, 3], [6, 1, 1, 2, 2, 1], [4, 3, 3, 2, 2], [10, 5]]
[14, 13, 14, 15]

Before spread with average of 4:
[[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1], [1, 1]]
Result and sum of each bucket:
[[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]
[4, 4, 4, 4, 4]

Before spread with average of 14:
[[10, 9, 8, 7], [6, 5, 4], [3, 2], [1]]
Result and sum of each bucket:
[[1, 7, 9], [10], [6, 5, 4], [3, 2, 8]]
[17, 10, 15, 13]

Ответ 3

Это не упаковка бинов, как предложили другие. Там размер бункеров фиксирован, и вы пытаетесь минимизировать количество. Здесь вы пытаетесь минимизировать дисперсию между фиксированным количеством ящиков.

Оказывается, это эквивалентно многопроцессорному планированию, и - согласно ссылке - ниже приведенный ниже алгоритм (известный как "Longest Job First" или "Самое длинное время обработки" ), несомненно, будет давать наибольшую сумму не более 4/3 - 1/(3 м) раз оптимальной, где m - количество ковшей. В тестовых случаях shonw, у нас было бы 4/3-1/12 = 5/4 или не более чем на 25% выше оптимального.

Мы начинаем с пустых пустых ящиков и помещаем каждый элемент в порядке убывания размера в текущую наименее полную корзину. Мы можем отслеживать наименьший полный бит с минимальной кучей. С кучей, имеющим O (log n) insert и deletemin, алгоритм имеет время O (n log m) (n и m, определенное как @Jonas Elfström). Ruby здесь очень выразителен: всего 9 слотов для самого алгоритма.

Вот код. Я не специалист по Ruby, поэтому, пожалуйста, не стесняйтесь предлагать лучшие способы. Я использую тестовые примеры @Jonas Elfström.

require 'algorithms'
require 'pp'

test_buckets = [ 
  [ [10, 4, 3, 3, 2, 1], [5, 5, 3, 2, 1], [3, 1, 1], [2] ],
  [ [4, 3, 3, 2, 2, 2, 2, 1, 1], [10, 5, 3, 2, 1], [3, 3, 3], [6] ],
  [ [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1], [1, 1] ],
  [ [10, 9, 8, 7], [6, 5, 4], [3, 2], [1] ],
]

def relevel(buckets)
  q = Containers::PriorityQueue.new { |x, y| x < y }

  # Initially all buckets to be returned are empty and so have zero sums.
  rtn = Array.new(buckets.length) { [] } 
  buckets.each_index {|i| q.push(i, 0) }
  sums = Array.new(buckets.length, 0)

  # Add to emptiest bucket in descending order. 
  # Bang! ops would generate less garbage.
  buckets.flatten.sort.reverse.each do |val|
    i = q.pop                 # Get index of emptiest bucket
    rtn[i] << val             # Append current value to it
    q.push(i, sums[i] += val) # Update sums and min heap
  end
  rtn
end

test_buckets.each {|b| pp relevel(b).map {|a| a.inject(:+) }}

Результаты:

[12, 11, 11, 12]
[14, 14, 14, 14]
[4, 4, 4, 4, 4]
[13, 13, 15, 14]

Ответ 4

Вы можете использовать мой ответ чтобы подгонять n изображений с переменной высотой в макет столбца 3 (аналогичная длина).

Ментальная карта:

Размер объекта для высоты изображения и
подсчет веток в bincount

Тогда остальная часть этого решения должна применяться...

В следующем случае используется алгоритм first_fit, упомянутый Робин Грин ранее, но затем улучшает это путем жадной замены.

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

Я использовал случайную выборку из 30 изображений с высотами в диапазоне от пяти до 50 'единиц'. Преобразование было быстрым в моем случае и значительно улучшилось по алгоритму first_fit.

Код (Python 3.2:

def first_fit(items, bincount=3):
    items = sorted(items, reverse=1) # New - improves first fit.
    bins     = [[] for c in range(bincount)]
    binsizes = [0] * bincount
    for item in items:
        minbinindex = binsizes.index(min(binsizes))
        bins[minbinindex].append(item)
        binsizes[minbinindex] += item
    average = sum(binsizes) / float(bincount)
    maxdeviation = max(abs(average - bs) for bs in binsizes)

    return bins, binsizes, average, maxdeviation

def swap1(columns, colsize, average, margin=0):
    'See if you can do a swap to smooth the heights'
    colcount = len(columns)
    maxdeviation, i_a = max((abs(average - cs), i)
                              for i,cs in enumerate(colsize))
    col_a = columns[i_a]
    for pic_a in set(col_a): # use set as if same height then only do once
        for i_b, col_b in enumerate(columns):
            if i_a != i_b: # Not same column
                for pic_b in set(col_b):
                    if (abs(pic_a - pic_b) > margin): # Not same heights
                        # new heights if swapped
                        new_a = colsize[i_a] - pic_a + pic_b
                        new_b = colsize[i_b] - pic_b + pic_a
                        if all(abs(average - new) < maxdeviation
                               for new in (new_a, new_b)):
                            # Better to swap (in-place)
                            colsize[i_a] = new_a
                            colsize[i_b] = new_b
                            columns[i_a].remove(pic_a)
                            columns[i_a].append(pic_b)
                            columns[i_b].remove(pic_b)
                            columns[i_b].append(pic_a)
                            maxdeviation = max(abs(average - cs)
                                               for cs in colsize)
                            return True, maxdeviation
    return False, maxdeviation

def printit(columns, colsize, average, maxdeviation):
    print('columns')
    pp(columns)
    print('colsize:', colsize)
    print('average, maxdeviation:', average, maxdeviation)
    print('deviations:', [abs(average - cs) for cs in colsize])
    print()


if __name__ == '__main__':
    ## Some data
    #import random
    #heights = [random.randint(5, 50) for i in range(30)]
    ## Here some from the above, but 'fixed'.
    from pprint import pprint as pp

    heights = [45, 7, 46, 34, 12, 12, 34, 19, 17, 41,
               28, 9, 37, 32, 30, 44, 17, 16, 44, 7,
               23, 30, 36, 5, 40, 20, 28, 42, 8, 38]

    columns, colsize, average, maxdeviation = first_fit(heights)
    printit(columns, colsize, average, maxdeviation)
    while 1:
        swapped, maxdeviation = swap1(columns, colsize, average, maxdeviation)
        printit(columns, colsize, average, maxdeviation)
        if not swapped:
            break
        #input('Paused: ')

Выход:

columns
[[45, 12, 17, 28, 32, 17, 44, 5, 40, 8, 38],
 [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42],
 [46, 34, 9, 37, 44, 30, 20, 28]]
colsize: [286, 267, 248]
average, maxdeviation: 267.0 19.0
deviations: [19.0, 0.0, 19.0]

columns
[[45, 12, 17, 28, 17, 44, 5, 40, 8, 38, 9],
 [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42],
 [46, 34, 37, 44, 30, 20, 28, 32]]
colsize: [263, 267, 271]
average, maxdeviation: 267.0 4.0
deviations: [4.0, 0.0, 4.0]

columns
[[45, 12, 17, 17, 44, 5, 40, 8, 38, 9, 34],
 [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42],
 [46, 37, 44, 30, 20, 28, 32, 28]]
colsize: [269, 267, 265]
average, maxdeviation: 267.0 2.0
deviations: [2.0, 0.0, 2.0]

columns
[[45, 12, 17, 17, 44, 5, 8, 38, 9, 34, 37],
 [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42],
 [46, 44, 30, 20, 28, 32, 28, 40]]
colsize: [266, 267, 268]
average, maxdeviation: 267.0 1.0
deviations: [1.0, 0.0, 1.0]

columns
[[45, 12, 17, 17, 44, 5, 8, 38, 9, 34, 37],
 [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42],
 [46, 44, 30, 20, 28, 32, 28, 40]]
colsize: [266, 267, 268]
average, maxdeviation: 267.0 1.0
deviations: [1.0, 0.0, 1.0]

Хорошая проблема.

Вот информация об обратной сортировке, упомянутая в моем отдельном комментарии ниже.

>>> h = sorted(heights, reverse=1)
>>> h
[46, 45, 44, 44, 42, 41, 40, 38, 37, 36, 34, 34, 32, 30, 30, 28, 28, 23, 20, 19, 17, 17, 16, 12, 12, 9, 8, 7, 7, 5]
>>> columns, colsize, average, maxdeviation = first_fit(h)
>>> printit(columns, colsize, average, maxdeviation)
columns
[[46, 41, 40, 34, 30, 28, 19, 12, 12, 5],
 [45, 42, 38, 36, 30, 28, 17, 16, 8, 7],
 [44, 44, 37, 34, 32, 23, 20, 17, 9, 7]]
colsize: [267, 267, 267]
average, maxdeviation: 267.0 0.0
deviations: [0.0, 0.0, 0.0]

Если у вас есть обратная сортировка, этот дополнительный код добавляется в нижнюю часть приведенного выше кода (в name ==...), будут выполняться дополнительные проверки случайных данных:

for trial in range(2,11):
    print('\n## Trial %i' % trial)
    heights = [random.randint(5, 50) for i in range(random.randint(5, 50))]
    print('Pictures:',len(heights))
    columns, colsize, average, maxdeviation = first_fit(heights)
    print('average %7.3f' % average, '\nmaxdeviation:')
    print('%5.2f%% = %6.3f' % ((maxdeviation * 100. / average), maxdeviation))
    swapcount = 0
    while maxdeviation:
        swapped, maxdeviation = swap1(columns, colsize, average, maxdeviation)
        if not swapped:
            break
        print('%5.2f%% = %6.3f' % ((maxdeviation * 100. / average), maxdeviation))
        swapcount += 1
    print('swaps:', swapcount)

Дополнительный вывод показывает эффект свопов:

## Trial 2
Pictures: 11
average  72.000 
maxdeviation:
 9.72% =  7.000
swaps: 0

## Trial 3
Pictures: 14
average 118.667 
maxdeviation:
 6.46% =  7.667
 4.78% =  5.667
 3.09% =  3.667
 0.56% =  0.667
swaps: 3

## Trial 4
Pictures: 46
average 470.333 
maxdeviation:
 0.57% =  2.667
 0.35% =  1.667
 0.14% =  0.667
swaps: 2

## Trial 5
Pictures: 40
average 388.667 
maxdeviation:
 0.43% =  1.667
 0.17% =  0.667
swaps: 1

## Trial 6
Pictures: 5
average  44.000 
maxdeviation:
 4.55% =  2.000
swaps: 0

## Trial 7
Pictures: 30
average 295.000 
maxdeviation:
 0.34% =  1.000
swaps: 0

## Trial 8
Pictures: 43
average 413.000 
maxdeviation:
 0.97% =  4.000
 0.73% =  3.000
 0.48% =  2.000
swaps: 2

## Trial 9
Pictures: 33
average 342.000 
maxdeviation:
 0.29% =  1.000
swaps: 0

## Trial 10
Pictures: 26
average 233.333 
maxdeviation:
 2.29% =  5.333
 1.86% =  4.333
 1.43% =  3.333
 1.00% =  2.333
 0.57% =  1.333
swaps: 4

Ответ 5

Адаптируйте алгоритмы решения проблем рюкзака, например, укажите "вес" каждого ведра примерно равным среднему значению размеров n объектов (попробуйте гауссовское распределение вокруг среднего значения).

http://en.wikipedia.org/wiki/Knapsack_problem#Solving

Ответ 6

Сортировка ведер в порядке размера.

Переместите объект из самого большого ведра в самое маленькое ведро, пересортируйте массив (который почти сортирован, поэтому мы можем использовать "ограниченную сортировку вставки" в обоих направлениях, вы также можете ускорить процесс, указав, где вы поместите два последних ведра, которые нужно отсортировать. Если у вас есть 6-6-6-6-6-6-5... и получите один предмет из первого ведра, вы переместите его на шестое место. Затем на следующем итерации вы можете начать сравнивать с пятым. То же самое, справа налево, для самых маленьких ковшей).

Если разница в двух ведрах одна, вы можете остановиться.

Это перемещает минимальное количество ведер, но имеет порядок n ^ 2 log n для сравнения (простейшая версия - n ^ 3 log n). Если перемещение объекта дорого, тогда как проверка размера ведра отсутствует, для разумного n он может все еще делать:

Другая возможность - рассчитать ожидаемый средний размер для каждого ведра и "продвинуть" мешок (или еще один ковш) с избытком от больших ведер до меньших.

В противном случае могут произойти странные вещи:

12 7 3 1, the average is a bit less than 6, so we take 5 as the average.

5 7 3 1  bag = 7 from 1st bucket
5 5 3 1  bag = 9
5 5 5 1  bag = 7
5 5 5 8  which is a bit unbalanced.

Принимая 6 (то есть округление), это идет лучше, но иногда иногда это не сработает:

12 5 3 1
 6 5 3 1  bag = 6 from 1st bucket
 6 6 3 1  bag = 5
 6 6 6 1  bag = 2
 6 6 6 3  which again is unbalanced.

Вы можете выполнить два прохода, первый с округленным средним слева направо, а другой с усеченным средним справа налево:

12 5 3 1  we want to get no more than 6 in each bucket
6 11 3 1
6  6 8 1
 6 6 6 3
 6 6 6 3  and now we want to get at least 5 in each bucket
 6 6 4 5  (we have taken 2 from bucket #3 into bucket #5)
 6 5 5 5  (when the difference is 1 we stop).

Для этого потребуются проверки размера "n log n", и перемещается не более 2-го объекта.

Другая интересная возможность - рассуждать так: у вас есть m объектов в n ведрах. Поэтому вам нужно сделать целочисленное отображение m на n, и это алгоритм линеаризации Bresenham. Запустите a (n, m) Bresenham в отсортированном массиве, а на шаге я (т.е. Против ведра i-го) алгоритм скажет вам, следует ли использовать размер раунда (m/n) или пол (m/n). Затем перемещайте объекты из или в "движущийся мешок" в соответствии с размером ящика i-го размера.

Для этого требуется n log n сравнения.

Вы можете дополнительно уменьшить количество перемещений объектов, изначально удалив все ведра, которые либо округлены (m/n), либо пол (m/n) по размеру, в два пула ведра размером R или F. Когда, запустив алгоритм, вам нужно i-е ведро для хранения объектов R, если пул объектов R не пуст, замените i-й ковш на один из R-размеров. Таким образом, балансируют только бедра, безнадежно недоукомплектованные; (большинство) остальные просто игнорируются, за исключением того, что их ссылки перетасовываются.

Если время доступа к объекту огромно пропорционально времени вычисления (например, какой-то автоматический журнал загрузчика), это даст максимально сбалансированный журнал с абсолютным минимумом движения общего объекта.

Ответ 7

Вы можете использовать пакет программирования Integer, если он достаточно быстро.

Это может быть сложно получить ваши ограничения. Что-то вроде следующего может сделать трюк:

пусть переменная Oij обозначает Object i, находящуюся в Bucket j. Пусть Wi представляет вес или размер Oi

Ограничения:

sum(Oij for all j) == 1       #each object is in only one bucket
Oij = 1 or 0.                 #object is either in bucket j or not in bucket j
sum(Oij * Wi for all i) <= X + R   #restrict weight on buckets.

Цель:

minimize X

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

Теперь maximum bucket size есть X + R

Следующим шагом является определение возможного минимального количества при сохранении размера ковша менее X + R

Определите переменную Stay Si, которая управляет, если Oi остается в Bucket j

Если Si - 0, это означает, что Oi остается там, где он был.

Ограничения:

Si = 1 or 0.
Oij = 1 or 0.
Oij <= Si where j != original bucket of Object i
Oij != Si where j == original bucket of Object i
Sum(Oij for all j) == 1
Sum(Oij for all i) <= X + R

Цель:

minimize Sum(Si for all i)

Здесь Sum(Si for all i) представляет количество перемещенных объектов.