3

ゲームを開発していて、パッキングの問題に似たコンポーネントのレイアウトを処理するために解決しなければならない問題を見つけました。

何をする必要があるかを要約すると、次のようなスペースがあるとします。

+------------+---------+------------+
| 0          | 1       | 2          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 3          | 4       | 5          |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 6          | 7       | 8          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+

すべての角のセルは 4x4 で、中央のセルは 3x3 です (残りのセルは 3x4 と 4x3 です)。次に、1x1 から 3x3 まで変化するこれらのブロック内に配置する一連の要素があります (4x4 はまだ必要ないと思いますが、何も変更しないはずです)。もちろん、これらの要素は境界線を越えることはできず、完全に 1 つのブロック内に配置する必要があります。

それらを割り当てる最良の方法はどれですか? 必要がない場合は、それらをすべてくっつけたくない場合を想定します (たとえば、2 つの要素を離して配置するのに十分なスペースがある場合は、2 つの要素を一緒に配置しないでください)。状況がかなり限られているため、単純なアルゴリズムを探しています..

おまけの質問: これらの 9 個のブロック (おそらく他の 3 ～ 4 個) に加えて、他のブロックがあると仮定すると、新しいブロックと比較してこれらのブロックを優先するにはどうすればよいでしょうか? (つまり、塗りつぶしのしきい値に達するまで、追加のブロックを使用しないということです)。

もちろん、私は一般的なアイデアを探していますが、実装はありません:)

4

1 に答える 1

7

この 2D Bin Packing問題はNP hardのようです。

以下にいくつかのオプションを示します。

  • 力ずくで、あるいはより良いのは、分岐してバインドすることです。スケールしません (まったく!) が、最適なソリューションを見つけます (おそらく私たちの生涯ではありません)。

  • 決定論的アルゴリズム: ブロックを最大サイズまたは最大側でソートし、そのリストを 1 つずつ調べて、残りの最良のスポットを割り当てます。これは非常に迅速に終了しますが、ソリューションは最適 (または実行可能) とはほど遠いものになる可能性があります。これは、何がうまくいかないかの例を示す素敵な写真です。しかし、シンプルに保ちたい場合は、これが最適です。

  • 決定論的アルゴリズムの結果から始まるメタヒューリスティック。これにより、妥当な時間内に、人間が思いつくよりも優れた非常に優れた結果が得られます。与えた時間と問題の難しさによって、それが最適な解決策である場合とそうでない場合があります。Drools Planner (オープン ソース Java)などのライブラリがいくつかあります。

于 2010-12-23T16:10:11.273 に答える