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であるため、既知の多項式解はありません。

Subset Sub Problemからの簡単な還元を示すことができます:

一般化された部分集合の合計 問題: 集合Sと整数が与えられたとき、合計kが になる部分集合が存在する場合にのみ true を返します。Sk

縮小: サブセット sum のインスタンスが与えられた場合、(S,k)サイズのコンテナーを作成し、(1,k)要素は(1,s)それぞれsにS.

コンテナーを完全に満たすことができる場合にのみ、元の部分集合和問題の解が真であり、したがって上記は多項式簡約であり、問​​題は NP 困難であることは簡単にわかります。(注: 「できるだけコンパクトにする」という元の問題は、実際にはこの問題の最適化問題であり、依然として NP 困難です)。

悪い知らせで申し訳ありません。
いくつかの代替手段は、指数解法 (バックトラッキングなど)、ヒューリスティック、または近似アルゴリズムを使用しています。
1 次元空間では、問題には動的計画法を使用した疑似多項式の解があることに注意してください。

于 2012-07-17T05:55:11.533 に答える
2

amit が指摘したように、あなたの問題は NP 困難です。ただし、これは、レンガのすべての順列を単純に反復し、それらのどれが最適であるかを確認することを妨げるものではありません。つまり、「多すぎる」レンガがない場合です。

「多すぎる」の値は、主に計算速度と利用可能な時間に依存しますが、私の推測では、たとえば 14 までの値で問題ありません。

ブルートフォース ソリューションが遅すぎることが判明した場合でも、ヒューリスティックまたは近似アルゴリズムを試すことができます。

編集:あなたの例のレンガはかなり人工的に見えます. レンガのサイズは特定の基準に従っていますか、それとも完全に恣意的ですか? レンガのサイズに制約がある場合は、それを利用できるかもしれません。

于 2012-07-17T08:41:22.197 に答える