2

我有许多不同尺寸（宽度和高度）的“砖块”和一个固定尺寸的容器。我想从顶部向下移动尽可能紧凑地布置容器内的砖块。考虑到前面的步骤，我已经选择了网格在任何步骤中都应该是最佳的标准。到目前为止，我有以下（低效）代码不起作用：

def fits?(x, y, w, h)
  !((x + w > W) || (y + h > H))
end

def overlaps?(existing, modified)
  existing[:x] + existing[:w] > modified[:x] && existing[:y] + existing[:h] > modified[:y] && modified[:x] + modified[:w] > existing[:x] && modified[:y] + modified[:h] > modified[:y]
end

AXIS = :x

W =  800
H = 6400

sizes = [
  { w: 200 , h: 200 },
  { w: 200 , h: 200 },
  { w: 400 , h: 400 },
  { w: 200 , h: 200 },
  { w: 200 , h: 200 },
  { w: 400 , h: 400 },
  { w: 600 , h: 600 },
  { w: 200 , h: 200 },
  { w: 800 , h: 800 },
]

existing = []

sizes.each do |size|
  size[:x] = 0
  size[:y] = 0

  existing.each do |existing|

    if overlaps?(size, existing)  

      if fits?(x = existing[:x] + existing[:w], y = existing[:y], size[:w], size[:h])
        size[:x] = x
        size[:y] = y
        redo 
      end

      if fits?(x = existing[:x], y = existing[:y] + existing[:h], size[:w], size[:h])
        size[:x] = x
        size[:y] = y
        redo
      end

      case AXIS
      when :x then size[:x] = 0; size[:y] = existing[:y] + existing[:h]
      when :y then size[:y] = 0; size[:x] = existing[:x] + existing[:w]
      end      
    end

  end

  puts "#{size[:x]} , #{size[:y]} , #{size[:w]} , #{size[:h]}"

  existing << size
end

有什么想法可以解决这个问题吗？看起来这将是贪心算法的一个主要例子，但我无法弄清楚它应该是什么。

4

2 回答 2

4

您的问题是NP-Hard，因此没有已知的多项式解决方案。

可以显示从子集子问题的简单简化：

广义子集总和 问题：给定一个集合S和一个整数k，当且仅当存在S该总和的子集时才返回真k。

减少：给定一个子集和的实例(S,k)-创建一个大小为的容器(1,k)，并且元素是(1,s)每个sin 的S。

很容易看出，当且仅当你可以完全填满容器时——原始子集和问题的解决方案是正确的，因此上述是多项式归约，问题是 NP-Hard。（注：“get it as compact as possible”的原始问题实际上是这个问题的优化问题，仍然是NP-Hard）。

关于这些坏消息我很遗憾。
一些替代方案正在使用指数解决方案（例如回溯）、启发式或近似算法。
请注意，在一维空间中，问题有一个伪多项式解决方案，使用动态编程，但我认为它不能简单地应用于二维空间（如果有的话）。

于 2012-07-17T05:55:11.533 回答
2

正如 amit 所指出的，您的问题是 NP 难的。但是，这不应该阻止您简单地遍历所有排列的砖块，看看其中哪一个是最合适的。也就是说，假设你没有“太多”的砖块。

“太多”的值主要取决于您的计算速度和可用时间，但我的猜测是，例如 14 的值是可以的。

如果蛮力解决方案太慢，您仍然可以尝试启发式或近似算法。

编辑：你的例子砖看起来很人造。您的砖块尺寸是否符合某些标准，或者它们完全是任意的？如果有的话，也许你可以利用对砖块大小的限制。

于 2012-07-17T08:41:22.197 回答