2dでn個の他のオブジェクトで形状をカバーするアルゴリズム

Question

こんにちは、他のn個のオブジェクトでカバーのアルゴリズムを探しています。私はいくつかのビンパッキングアルゴリズムを見ましたが、すべてのオブジェクトを指定されたコンテナの中に完全に収めるように試みます。私の場合は

誰かが私を助けたり、私を案内したりすることができれば、この問題に関する情報を得ることができます。

Answer 1

問題は部分的にはNP -completeです。これは、Partition問題の幾何学的一般化であるためです。リストを考えると、整数{a_1,...,a_n}とtaget和

S := (a_1 + ... + a_n)/2 

の 問題となっている問題のインスタンスがn次元の長方形{1,...,n}の各iため

1 * a_i 

とターゲットを用いて生成することができますサイズの領域

2 * S. 

小さい方の矩形はカバーできますPartitionのインスタンスが等しい総量の2つのサブセットに分割することを認めた場合に限り、より大きな四角形を作成することができます。

Answer 2

この問題は、セットカバーの問題を非常に簡単に減らすことができます。 link

これらの図が描かれている仮想のグリッド面を考えてみましょう。大きな図形から、宇宙集合Uをグリッドの正方形に構成します。

ここで、n個の小図形のそれぞれについて、Uのサブセットである同様のセットを構築します。 Uにないこれらのセットから余分な要素を削除します。

これで、作成したn個のサブセットを使用して、Uのためのセットカバーが必要になります。最小のセットカバーをお探しの場合は、NP完成です。

あなたは、カバーの問題を解決するためのおおよその解決策を選択することをお勧めします。形状やオブジェクトについて知られている何

Approximation algorithms for Set Cover

Approximating Set Cover