12

長方形のセットをパックしたい (例):

ここに画像の説明を入力

四角形が開始したのと同じ列に収まらなければならないという制約の下で、全体の高さができるだけ低くなるようにします。最後に交差します。

現在のアルゴリズムは、長方形を最大の高さから最小の高さまで処理し、利用可能な最も低い y 位置に配置することです。より最適なアルゴリズムはありますか?

編集:必ずしも最適なソリューションが必要なわけではありません。現在のソリューションよりも優れたソリューションを生成するアルゴリズムは興味深いものです。また、長方形の数は約50です。

4

3 に答える 3

7

N長方形があるとします。各長方形について、 を水平スパン、 を高さとしiます。[a_i, b_i]h_i

ソリューション スペースは のようy_i, i = 1, ..., Nに見えます。ここで、長方形の垂直スパンiは です[y_i, y_i + h_i]。

一般性を失うことなく、 を制約できますy_i >= 0。次に、目的関数 を最小化しますmax{y_i + h_i | i}。

重なり合わない四角形に対する制約は次のとおりです。

y_i + h_i <= y_j
   OR
y_j + h_j <= y_i

for all i != j such that `[a_i, b_i]` and `[a_j, b_j]` intersect

[a_i, b_i]互いに交差するものを特定するのは簡単なので、これらの制約を形成する四角形のペアを特定するのは簡単です。

制約内の OR を取り除くには、z_k各制約に対してバイナリ ダミー変数を作成し、十分な大きさkの "Big M"を作成して次のように書き直します。M

y_i + h_i <= y_j + (z_k)M
y_j + h_j <= y_i + (1-z_k)M

for all i != j such that `[a_i, b_i]` and `[a_j, b_j]` intersect

目的関数を最小化として書き直すことができるように、ダミー変数を導入しHて制約を追加できます。y_i + h_i <= HH

結果の最適化問題は次のとおりです。

minimize H
with respect to: y_i, z_k, H
subject to:

 (1) y_i + h_i <= y_j + (z_k)M    for all i != j such that [a_i, b_i]
     y_j + h_j <= y_i + (1-z_k)M  and [a_j, b_j] intersect

 (2) y_i + h_i <= H               for all i

 (3) y_i >= 0                     for all i

 (4) z_k in {0, 1}                for all constraints of type (1) k

これは混合整数線形最適化問題です。このタイプの問題には、直接適用できる一般的なソルバーがあります。

通常、彼らはバイナリ制約をアルゴリズム中に存在する制約に緩和するなどのトリックを実行しますz_k。これにより、これは非常に効率的に解決できる線形計画問題に変わります。z_k[0,1]

これらのソルバーを再発明しようとすることはお勧めしません。

于 2013-06-21T16:52:43.107 に答える
2

長方形が垂直方向にしか移動できないことを考えると、解決策は 2 つしかないように見えます: 衝突が発生するまですべての長方形をできるだけ上に移動するか、衝突が発生するまですべてを下に移動します。私は、これらのソリューションが同等になるのではないかと密かに疑っています*。1 つの次元に制約されている場合、これほど洗練されたパッキングの概念があるとは思えません。おそらく私は何かを逃していますか？

*あなたの制約を正しく理解していれば、最小の高さは常に、塗りつぶされたセルの最大数を持つ列内の塗りつぶされたセルの数になります。これは、翻訳が上向きに適用されるか下向きに適用されるかによって変わりません。

于 2013-06-21T15:02:21.273 に答える