- 詰めているアイテム
- 入る
- 入らない
ビンパッキング問題
荷物をバンに、ファイルをディスクに、ジョブをマシンに。ビンパッキング問題は、アイテムの並びを同じ大きさのビンにできるだけ少ない数で収める方法を問います。最善の詰め方を必ず見つける速い方法は知られていませんが、単純なルールでもかなり近づけます。ルールを選び、1ステップずつ進めて、厳密な答えと比べてみましょう。 棚のアイテムをタップしてから、入れたいビンをタップします。緑のビンにはそのアイテムが入る空きがあり、「新しいビン」でビンをもう1つ開けます。ビンの中のアイテムをタップすると、また取り出せます。すべてのアイテムをできるだけ少ないビンに詰めてください。下界(合計の重さをビンのサイズで割って切り上げた数)と可能な最少数で、どこまで近づいたかがわかります。「最少のビン」は最善の詰め方を示します。パネルでアイテムの重さ(キログラム単位)とビンのサイズを変えられます。「ステップごと」の表示では、速いルール(ネクストフィット、ファーストフィット、ベストフィットを、入力順のアイテムまたは大きい順に並べたアイテムに適用)や、動的計画法で求めた厳密な答えがどう詰めるかを見られます。「再生」を押すとアイテムがビンに入っていく様子を見られ、「ステップ」と「戻る」で1ステップずつ進められます。ステップのスライダーをドラッグすると好きな位置に移動できます。ボードを選択しているときは、矢印キーで1ステップずつ移動し、スペースキーで再生・一時停止し、Home と End で最初と最後に移動します。
使い方
- 品物をタップし、空きのあるビンをタップして入れるか、「新しいビン」をタップしてビンを増やしましょう。
- できるだけ少ないビンを目指すか、「最少のビン」を押して一番よい詰め方を見てみましょう。
- 「ステップごと」表示を開き、ルールを選んで再生を押し、各品物がビンを順に試す様子を見ましょう。
ルール
ネクストフィットは最後のビンだけを開いておきます。そこに入らないアイテムは新しいビンを始めます。ファーストフィットは最初のビンから順に試し、空きのある最初のビンを選びます。ベストフィットはすべてのビンを試し、空きのあるビンのうち最も詰まったものを選んで、使われない空間を最小にします。ファーストフィットとベストフィットは、先にアイテムを大きい順に並べることもできます。それが降順ファーストフィットと降順ベストフィットです。
厳密な答え
最後のルールは経験則ではありません。アイテムの集合に対する動的計画法で最少のビン数を求めます。アイテムの各集合について、それを収める最少のビン数と、そのビン数での詰め方のうち最後のビンの最小の詰め込み量を記録します。集合はアイテムを1つずつ加えて大きくなり、加えたアイテムは最後のビンに追加されるか、新しいビンを開きます。n 個のアイテムでは集合が 2ⁿ 個あるため、このアプリではアイテムは最大 12 個までです。下界、つまり合計サイズをビンのサイズで割って切り上げた値は、詰め方がどれだけ最善に近いかを示します。
よくある質問
どのビンパッキングのルールが一番良いですか?
速いルールの中では、降順ファーストフィットと降順ベストフィットが最も強力です。使うビンが、最少のビン数の 11/9 に小さな定数を足した数を超えることはありません。並べ替えていないアイテムに対するファーストフィットとベストフィットは最少のビン数の 1.7 倍以内、ネクストフィットは 2 倍以内に収まります。
ビンパッキングはなぜ難しいのですか?
アイテムがビン2つに収まるかどうかを判定するだけで、すでに分割問題になり、これは NP 完全です。そのため P = NP でない限り、どんな入力に対しても最少のビン数を速く求める方法はなく、厳密な方法は最悪の場合に指数時間かかります。
下界とは何ですか?
アイテムの合計サイズをビンのサイズで割り、切り上げた値です。ビンはすべてのアイテムを収めなければならないので、これより少ないビンで済む詰め方はありません。最善の詰め方が下界と一致することは多いですが、いつもではありません。サイズ 6 のアイテム3つとサイズ 10 のビンでは、下界は 2 ですがビンは 3 個必要です。
これは動的計画法ですか?
厳密な答えはそうです。アイテムの各集合に対する最善の詰め方を、より小さな集合の最善の詰め方から組み立てます。速いルールは貪欲法で、一度決めたら二度と振り返りません。
どこかにデータが送られますか?
いいえ。すべての計算はブラウザの中で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ