4

私は昨夜アプリケーションに取り組んでいて、おそらくそれを解決するための効率的なアルゴリズムがあると確信している特定の問題に遭遇しました。誰でも提案できますか？

問題：

TL;DR: 写真が役立つかもしれません: http://www.custom-foam-inserts.com/ . さまざまなコンパートメントに収まるアイテムがたくさんありますが、必要なケースの数を最小限に抑えたいと考えています。

.

特別に設計された保護ボックスに梱包したい N 個の高価な電子機器のセットがあります。これらのボックスには、それぞれが 1 つのアイテムに適合する多くのコンパートメントがあります。特定のアイテムに適合するように特別に設計されたもの (カメラの形をした穴) もあれば、一般的なもの (長方形の穴) もあります。C個の異なるサイズのコンパートメントがあり、それらのサイズが何であるかを事前に知っています.

これらのボックスには L 個の異なるレイアウトがあり、それぞれに少なくとも 1 つのコンパートメントがあります。レイアウトは、「2 つの大きな長方形のコンパートメントと 4 つの小さな円形のコンパートメント」です。

各コンパートメント サイズは少なくとも 1 つのレイアウトに存在しますが、どのコンパートメント サイズにも適合しないアイテムがあります。各アイテムは、少なくとも 1 つのコンパートメントに収まり、複数の異なるコンパートメントに収まる場合があります。たとえば、私の DSLR カメラは、「中程度の長方形」のコンパートメントにぴったりと収まり、「大きな長方形」のコンパートメントにゆったりと収まり、「大きな長方形」のコンパートメントにぴったりと収まる場合があります。 DSLR カメラ コンパートメント」ですが、「小さな円」には収まりません。この目的のために、各アイテムに適したコンパートメントのリストを作成しました.

アイテムは適度に不均一です。たとえば、あるサイズのアイテムが 50 個あり、別のサイズのアイテムが 20 個ある場合があります。

各ボックスには、ボリュームとドルの 2 つのコストがあります (ただし、D ~ V に比例)。すべてのアイテムを箱に収めながら、これらのコストのいずれかまたは両方を最小限に抑える必要があります。ボックスのレイアウトにより、最適なソリューションには未使用のコンパートメントが含まれる場合があります。2 つの溶液の体積が等しい場合は、未使用のコンパートメントが最も多いものを選択します。各コンパートメントは少なくとも 1 つのレイアウトに存在し、各アイテムは少なくとも 1 つのコンパートメントに収まるため、すべてのアイテムに適合するソリューションが常に存在します。

アイテム数: <=2000、平均ケース 150。コンパートメント数: <= 1000。レイアウト数: <= 1000。

これに関するアイデアはありますか？Knapsack と Bin Packing のアルゴリズムを少し調べましたが、それらが正しい方法であるかどうかはわかりません。大変助かりました。

4

1 に答える 1

1

問題の説明から、これは確かにナップザックの問題のように見えます。オプションの重みを念頭に置きながら、利用可能なスペースを最大化する必要があるからです。

目的に応じて、遺伝的アルゴリズムの使用を検討することもできます。この問題は NP Complete であるため、さらにアイテムを追加する必要がある場合、実行時間は最終的に爆発します。そのため、時間に関係なく利用可能な最適なソリューションが必要な場合は、主にこれを使用します。

一方、遺伝的アルゴリズムは比較的短い期間で何らかの解決策を提供できるはずですが、それが提供する解決策は、ナップザック アルゴリズムによって提供されるものほど良くない可能性があるため、GA を選択します。時間に制限がある場合は、何らかの解決策を提供する必要があり、それが絶対的な最善でなくてもかまいません。

于 2012-05-03T12:10:22.090 に答える