こんにちは、他のn個のオブジェクトでカバーのアルゴリズムを探しています。私はいくつかのビンパッキングアルゴリズムを見ましたが、すべてのオブジェクトを指定されたコンテナの中に完全に収めるように試みます。私の場合は2dでn個の他のオブジェクトで形状をカバーするアルゴリズム
誰かが私を助けたり、私を案内したりすることができれば、この問題に関する情報を得ることができます。
こんにちは、他のn個のオブジェクトでカバーのアルゴリズムを探しています。私はいくつかのビンパッキングアルゴリズムを見ましたが、すべてのオブジェクトを指定されたコンテナの中に完全に収めるように試みます。私の場合は2dでn個の他のオブジェクトで形状をカバーするアルゴリズム
誰かが私を助けたり、私を案内したりすることができれば、この問題に関する情報を得ることができます。
問題は部分的には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つのサブセットに分割することを認めた場合に限り、より大きな四角形を作成することができます。
この問題は、セットカバーの問題を非常に簡単に減らすことができます。 link
これらの図が描かれている仮想のグリッド面を考えてみましょう。大きな図形から、宇宙集合Uをグリッドの正方形に構成します。
ここで、n個の小図形のそれぞれについて、Uのサブセットである同様のセットを構築します。 Uにないこれらのセットから余分な要素を削除します。
これで、作成したn個のサブセットを使用して、Uのためのセットカバーが必要になります。最小のセットカバーをお探しの場合は、NP完成です。
あなたは、カバーの問題を解決するためのおおよその解決策を選択することをお勧めします。形状やオブジェクトについて知られている何
?例えば。彼らはすべて凸ですか? – Henrik
申し訳ありませんが、私はあなたが凸であることを理解していません、申し訳ありませんが、私はこの問題ではあまりよくありません。形状はhtml5キャンバスで描画されるので、円、矩形などにすることができます。他のすべてのオブジェクトは長方形になります – Alex