在多个集合上均匀分布对象

Question

场景是存在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]]

Answer 1

我认为这是垃圾箱包装问题的一个变种,因此它是NP难的.你的答案本质上是第一个适合减少启发式的变体,这是一个非常好的启发式.也就是说,我相信以下会给出更好的结果.

• 使用平衡二叉树以降序大小顺序对每个桶进行排序.
• 计算平均大小.
• 使用平衡二叉树按大小顺序对大小小于平均值("太小的桶")的桶进行排序.
• 使用平衡二叉树对大小大于平均值的桶("太大的桶")按其最大元素的大小排序(因此,带有{9,1}的桶将首先出现,带有{的桶8,5}将成为第二个).
• Pass1:从最大元素中删除桶中最大的元素; 如果这会将其大小减小到平均值以下,则替换已删除的元素并从"太大的桶"的平衡二叉树中删除该桶; 否则将元素放在最小的桶中,并重新索引两个修改的桶以反映新的最小桶和具有最大元素的新"太大桶".继续迭代,直到你删除了所有"太大的存储桶".
• Pass2:通过从最小到最大的"太小的桶"迭代,从最大的"太大的桶"中选择最合适的元素,而不会使它成为"太小的桶"; 从剩下的"太大的桶"中迭代从最大到最小,从中移除最合适的元素,而不会使它们变成"太小的桶".为剩下的"太小的桶"做同样的事情.这个变体的结果不如它们对于更复杂的变体那样好,因为它不会将桶从"太大"转移到"太小"类别,反之亦然(因此搜索空间将但是这也意味着它有更简单的暂停条件(简单地遍历所有"太小"的桶然后停止),而复杂的变体可能会导致无限循环,如果你不小心的话.

我们的想法是,通过移动Pass1中最大的元素,您可以更轻松地在Pass2中更精确地匹配存储桶的大小.您使用平衡二叉树,以便在删除或添加元素后可以快速重新索引存储桶或存储桶树,但您可以使用链接列表(平衡二叉树将具有更好的最坏情况性能但链接列表可能有更好的平均情况表现).通过在Pass2中执行最佳拟合而不是第一次拟合,您不太可能执行无用的移动(例如,将大小为10的对象从比平均值大5的桶中移动到比平均值低5的桶中 - 首先适合如果盲目地执行电影,那么最佳匹配将查询下一个"太大的存储桶"以获得更大尺寸的对象,否则将从存储桶树中删除"太小的存储桶".

Answer 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]

Answer 3

这不是其他人建议的垃圾箱包装.箱子的大小是固定的,你试图最小化数量.在这里,您尝试最小化固定数量的箱子之间的差异.

事实证明这相当于多处理器调度,并且 - 根据参考 - 下面的算法(称为"最长作业优先"或"最长处理时间优先")肯定会产生不超过4/3的最大总和 -最佳1 /(3m)倍,其中m是桶的数量.在测试案例中,我们有4/3-1/12 = 5/4或不超过25%的最佳值.

我们只是从所有垃圾箱开始,并将每个项目按大小的降序排列到当前最小的垃圾箱中.我们可以使用最小堆有效地跟踪最少的完整bin.对于具有O(log n)insert和deletemin的堆,该算法具有O(n log m)时间(n和m定义为@JonasElfström说).Ruby在这里非常具有表现力:算法本身只有9个sloc.

这是代码.我不是Ruby专家,所以请随意提出更好的方法.我正在使用@JonasElfströ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]