algorithm - ブロックレイアウトアルゴリズム

Question

奇妙な形のブロックを配置するためのアルゴリズムを改善するための助けを探しています。私の問題領域は奇妙ですが、私のブロックの最も良い例えは、4つ以上のピースを持つことができることを除いて、テトリスのピースです。ブロックはまだ直角だけで構成されていますが、長くて曲がりくねっていたり、分岐したりすることができます。

最小限のスペースに複数の大きな任意の形状のブロックを配置しようとしていますが（ビンパッキング問題です）、現在の解決策は見苦しいです。基本的に1つを配置し、残りをブルートフォースしてグリッドの原点に配置し、衝突しなくなるまでゆっくりとさまざまな方向に押します。遅くはありませんが、ピースをうまくフィットさせようとはしないので、全体のスペースを無駄にしません。

私が試すことができる唯一のことは、ブロックをサイズ順に並べ、最初に最大のものを配置し、次に残りの穴に最後に最小のものをはめ込むことです。しかし、裏目に出ることができる方法は確かにあります。

ここで役立つヒューリスティックまたは近似アルゴリズムはありますか？

結果は次のようになります。

また、おそらく私のGravatarは、これがロックマンに関連していることを示しています...

Answer 1

これ（ポリオミノ形状パッキング）は、一般的に重要な数学の問題のようです。これに取り組んだ他の人の専門知識を紹介します。この男は、他の人が解決策を提出できる彼のウェブサイトにたくさんのポリオミノの例を持っています。彼はまた、Javaのソルバーソフトウェアを持っています。

http://gp.home.xs4all.nl/Site/Polyomino_Solver.html。

http://gp.home.xs4all.nl/PolyominoSolver/downloadsolver.htm

Stephen Montgomery-Smithによってこのために作成されたアルゴリズムもいくつかあります。これは、上記よりも包括的であるように見えます（これでは解決できなかったいくつかの問題を解決しました）が、最終的にxscreensaverになりました（リアルタイムでクールに解決します）。見る！）。次のスクリーンショットは、スクリーンセーバーからのもので、ペントミノまでの形状のみを示していますが、一般的なコンテナーを使用した一般的な形状で機能します。

http://www.math.missouri.edu/~stephen/software/

これらのソフトウェアのいずれかが、穴を許容するポリオミノの最適な適合に近いかどうかはわかりません。しかし、この方法は間違いなく「決定可能」です。つまり、ソリューションに1x1のポリオミノを追加して、適合する特定の結果が見つかるかどうかを確認し、1x1のピースを削除して結果を得ることができるという意味です。

アプリケーションの場合、逆方向に作業する方が効率的かもしれません。これらのアルゴリズムはすべて、各ブロックのユニットセルの数が複雑です。ブロックをレイアウトする良い方法は、ブロックをより大きなセルの「サブディビジョン」と見なすことです。これにより、ブロックの3x3の正方形は、再スケーリングされたバージョンの1x1の正方形に対応します。次に、ブロックを空のスペースで埋めて、すべてがより大きなブロックで構成されるようにし、アルゴリズムを実行して、余分なスペースを取り除きます。これは実行がはるかに高速になるだけでなく、必要なブロック間のスペースも生成します。