最適なビンパッキング

ベストフィットはビンパッキングのオンラインアルゴリズムです。入力は異なるサイズのアイテムのリストです。出力はパッキングです。パッキングとは、各ビンのアイテムのサイズの合計が最大で容量以下になるように、アイテムを固定容量のビンに分割することです。理想的には、ビンの数はできるだけ少なくしたいのですが、ビンの数を最小化することは NP 困難な問題です。ベストフィットアルゴリズムは、次のヒューリスティックを使用します。

• 最初は空である、開いているビンのリストを保持します。
• アイテムが到着すると、アイテムが収まる最大荷重のビンがあればそれを見つけます。ビンの 荷重は、新しいアイテムを配置する前のビン内の既存のアイテムのサイズの合計として定義されます。
  • そのようなビンが見つかった場合、新しいアイテムはその中に配置されます。
  • それ以外の場合は、新しいビンが開かれ、その中に新しいアイテムが配置されます。

Best-Fit で使用されるビンの数を BF(L) で表し、リスト L で可能な最適なビンの数を OPT(L) で表します。BF(L) の分析はいくつかのステップで実行されました。

• の最初の上限は1971年に ウルマン^[1]によって証明されました。${\displaystyle BF(L)\leq 1.7\mathrm {OPT} +3}$
• 改良された上限はGarey、Graham、Ullman、^[2] Johnson、Demersによって証明されました。^[3]${\displaystyle BF(L)\leq 1.7\mathrm {OPT} +2}$
• その後、Garey、Graham、Johnson、Ullman、Yao、Chi-Chih ^[4]によって改良されました 。${\displaystyle BF(L)\leq \lceil 1.7\mathrm {OPT} \rceil }$
• 最終的に、この境界はDósaとSgallによってに改良されました。 ^[5]彼らはまた、この境界に一致するの例としての入力リスト も提示しています。${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$${\displaystyle L}$${\displaystyle BF(L)}$

Worst-Fit は、Best-Fit の「デュアル」アルゴリズムです。つまり、最小の負荷で次のアイテムをビンに入れようとします。

このアルゴリズムはNext-Fitと同じくらい悪い動作をする可能性があり、その最悪のケースのリストに載るでしょう。^[6]さらに、それは成り立ちます。 ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$${\displaystyle R_{WF}^{\infty }({\text{size}}\leq \alpha )=R_{NF}^{\infty }({\text{size}}\leq \alpha )}$

Worst-FitはAnyFitアルゴリズムなので、次のようなAnyFitアルゴリズムが存在する。^[6]${\displaystyle R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )}$