3

編集：この問題は「切り株問題」と呼ばれているようです

ビン内のチャンクの (スペース) 最適な配置を提供するアルゴリズムが必要です。1 つの方法は、最初に大きなチャンクを配置することです。しかし、この例でそのアルゴリズムがどのように失敗するかを確認してください。

Chunks        Bins
-----------------------------
AAA BBB CC DD (       ) (   )

Algorithm     Result
-----------------------------
biggest first (AAABBB ) (CC )
optimal       (AAACCDD) (BBB)

「ビッグファースト」は DD には収まりません。次のような表を作成すると役立つ場合があります。

Size 1: ---
Size 2: CC, DD
Size 3: AAA, BBB

Size 4: CCDD
Size 5: AAACC, AAADD, BBBCC, BBBDD
Size 6: AAABBB

Size 7: AAACCDD, BBBCCDD
Size 8: AAABBBCC, AAABBBDD
Size 10: AAABBBCCDD
4

4 に答える 4

3

これは基本的に、ビンパッキング問題の変種です。この問題は NP 困難であることが知られているため、複雑なケース (つまり、多くのオブジェクトとビン) に対して効率的な最適アルゴリズムを見つけることを期待しないでください。

ただし、オブジェクト/ビンの数が比較的少ない場合は、可能性のあるすべての組み合わせを深さ優先検索で徹底的に検索するだけで問題ないでしょう。

これは非常に簡単に実装できます。最初のオブジェクトを取得し、最初のオブジェクトを各ビンに順番に配置してアルゴリズムを再帰的に再実行します (つまり、使用可能なビン スペースからオブジェクトのサイズを減算します)。最後に、これまでに見つかった最良の「解決策」を追跡し、すべての組み合わせを試したら、これを最終的な回答として返す必要があります。

次の方法で、このアルゴリズム アルゴリズムの実行を高速化することもできます。

  • 同じサイズのすべてのオブジェクトを同等と見なす
  • 現在の最適なソリューションを打ち負かすことができない場合、たとえば、完全に適合するソリューションを既に見つけている場合は、検索ツリーを剪定します (つまり、ブランチから早期に戻る)。

問題サイズに関するコメントに基づいて更新

処理するチャンクが非常に多いように見える場合は、次のことを試してください。

  • 上記のように徹底的な検索を使用して、最大の 10 ～ 20 個のチャンクを適合させます。
  • 最大適合アプローチを使用して残りを割り当てる
于 2010-12-23T18:45:08.137 に答える
2

Mikera の言うとおりです。この複数のナップザック問題 (ビン パッキング問題の変形) はNP 困難です。

ここにいくつかのオプションがあります（同様の質問に対する私の回答からコピーされました）：

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

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

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

于 2010-12-24T10:14:15.903 に答える
1

この問題に対する一般的な最適なアルゴリズムはまだ存在しません (ビン パッキング問題を参照してください)。ウィキペディアおよび/または「ビンパッキング問題」のグーグルでいくつかの異なるアプローチを見つけることができ、おそらく「ナップザック問題」もいくつかの助けになるでしょう。

于 2010-12-23T18:34:34.113 に答える
0

Donald Knuth のDancing Linksアルゴリズムは、「正確なカバー」問題の解決策をすばやく見つけます。

于 2010-12-23T18:44:41.680 に答える