ビンパッキング問題

引っ越しで段ボール箱を次々に詰めながら、もっと賢い順番なら箱が少なくて済んだのでは、と思ったことはありませんか。それがビンパッキング問題で、難しいことで有名です。コンピュータでさえ、大きな入力で最少のビン数を見つけるには工夫した探索が必要です。それでも、単純なルールで驚くほど近づけます。

同じ高さのビンに、大きさの違う色とりどりのアイテムが積み重なり、その上でさらにアイテムが待っている様子
同じ高さのビンに、大きさの違う色とりどりのアイテムが積み重なり、その上でさらにアイテムが待っている様子

問題

サイズを持つアイテムと、どれも同じ量を収められるビンが与えられたとき、どのビンもあふれないように、できるだけ少ないビンですべてのアイテムをビンに入れます。サイズは重さ、長さ、時間、ファイルサイズなどを表せます。雨の日の午後のパズルのように聞こえますが、NP 困難です。どんな入力に対しても最少のビン数を速く求める方法は知られていません。

速いルール

ネクストフィットは、次のアイテムが入らなくなるまで1つのビンを詰め、それから新しいビンを始めて、二度と前を振り返りません。ファーストフィットはすべてのビンを開いたままにし、各アイテムを空きのある最初のビンに入れます。ベストフィットは各アイテムを、まだ空きのあるビンのうち最も詰まったビンに入れます。3つとも即座に決めるので、アイテムが1つずつ届き、すぐに置かなければならない場合に便利です。

先に並べ替える

難しいのは大きなアイテムです。広い空きが必要だからです。アイテムを大きい順に並べてからファーストフィットかベストフィットを使うと、ビンがまだ空いているうちに大きなアイテムが入り、すき間を小さなアイテムが埋めます。降順ファーストフィットが使うビンは、最少のビン数の 11/9 に定数を足した数を超えることはありません。並べ替えないファーストフィットでは 1.7 倍です。

例

サイズ 10 のビンと、合計 40 になるアイテム 2、3、2、1、3、4、5、6、7、7 を考えます。ファーストフィットは 2、3、2、1 を1つ目のビンに、3 と 4 を2つ目のビンに入れ、その後 5、6、7、7 はそれぞれ専用のビンが必要になります。合計 6 個のビンです。大きい順に並べると、降順ファーストフィットは 7 + 3、7 + 3、6 + 4、5 + 2 + 2 + 1 を作ります。満杯のビン 4 個で、下界 40 / 10 = 4 と一致します。

最少のビン数を求める

アイテムが少なければ、部分集合に対する動的計画法で厳密な答えを求められます。アイテムの各集合について、それを収める最少のビン数と最も空いた最後のビンを、アイテムが1つ少ない集合から組み立てます。n 個のアイテムで約 2ⁿ·n ステップかかります。より大きな問題は分枝限定法や整数計画法で解かれ、下界を使えば、詰め方が最善からどれだけ離れうるかがわかります。

使われる場面

トラックやコンテナへの積み込み、標準の長さのパイプや紙のロールをできるだけ無駄なく切り出すこと(カッティングストック問題)、仮想マシンのサーバーへの割り当て、ファイルのディスクへの格納は、どれもビンパッキング問題です。数の代わりに箱を扱う2次元や3次元では、問題はさらに難しくなります。

よくある質問

オンラインとオフラインのビンパッキングの違いは何ですか?

オンラインでは、残りのアイテムを知らないまま、各アイテムを届いたらすぐに置かなければなりません。ネクストフィット、ファーストフィット、ベストフィットはこの方式です。オフラインでは、すべてのアイテムが事前にわかっているので、降順ファーストフィットのように先に並べ替えられます。

降順ファーストフィットはどれくらい最適に近いですか?

使うビンは多くても最少のビン数の 11/9 にビン 6/9 個分を足した数で、この上界が改善できない厳密なものであることを György Dósa が 2007 年に証明しました。典型的な入力では、たいてい最適か、1個多いだけです。

ビンパッキングはナップサック問題と同じですか?

関連はありますが別の問題です。ナップサック問題は1つの袋を最も価値の高いアイテムで満たし、ビンパッキングはすべてのアイテムをできるだけ少ない袋に入れます。ビンパッキングの厳密なソルバーは、ナップサックに似た問題を何度も解くことで動くことがよくあります。

なぜアプリではアイテムが 12 個までなのですか?

厳密な答えはアイテムのすべての集合を調べるからです。12 個のアイテムで、すでに 4,096 個の集合になります。速いルールなら何千個ものアイテムを扱えますが、描画と厳密な答えとの比較は追いつきません。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

ビンパッキングを試す