Bin Packing 問題　　近似アルゴリズム

■　Bin Packing 問題は次のように定義される：

いろいろな大きさのコップに、その容積一杯に水が入っているとする。各コップ u の容積は正の整数 s(u) とするとき、コップの集合を U とする。

一方、容積がどれも正の整数 B であるビンが K 個あるとする。

各コップの水はどれか一つのビンに注ぐとするとき、各ビンがこぼれないように注ぐ方法はあるか？

このように、方法が存在するか否かを問う問題は、「決定問題」と呼ばれる。

■　一方、次の問題を「最適化問題」と呼ぶ。

コップの集合Uに対して、最小何個のビンがあれば、各ビンがこぼれないようにできるか？

最適化問題を解いて、最小のビンの数が OPT 個と分かったならば、決定問題は

OPT ≦ K ならば、方法が存在し、

K ＜ OPT ならば、方法は存在しない

というように簡単に解くことができる。

最適化問題の方が、決定問題より難しいといえる。

■　Bin Packing 問題の場合、決定問題も最適化問題を高速に解くことは非常に難しいと予想されている。

ただ、最小のビンの数 OPT にかなり近い数のビンを詰める方法をを、高速に計算することは可能である。

このような方法を「近似アルゴリズム」と呼ぶ。

近似アルゴリズム　First Fit Algorithm

容積の大きいコップの水から、ビンに注いでゆく戦略が直感的には良さそうである。

1. ビンに番号を振る。
2. 最も容積の大きく、水の入ったコップを選び、その水をいれてもこぼれないビンの中で最も番号が若いビンに入れる。
   

定理　First Fit Algorithm が必要とするビンの数を FF 個、最小のビンの数を OPT 個とするとき

FF ≦ 2 * OPT

つまり最適な個数の高々２倍ぐらいしか First Fit Algorithm はビンを消費しない。

証明

• 　First Fit アルゴリズムの場合
  
  (B × FF) / 2　≦　（コップの水の総和）
  
  背理法：　
  　(B × FF) / 2　＞　（コップの水の総和）　と仮定すると、水が半分未満のビン X が存在することになる。
  　水が半分未満のビン Y がもう一つ存在する場合、First Fit の戦略から、X もしくは Y の水は他のビンにすべて注がれていなければならないので、矛盾。
  　半分未満のビンが X だけなら、 あるビン Z が存在して、X と Z の水の合計が B 以下になるはずであるが、この場合も X の水がすべて他のビンに注がれているはずで矛盾。
  
  
• 　最適な戦略の場合
  
  　（コップの水の総和）　≦　B × OPT
  
  
• 　従って　FF ≦ 2 * OPT
  

もう少しよい結果があるが、証明は長く単純でない。

定理　First Fit Algorithm が必要とするビンの数を FF 個、最小のビンの数を OPT 個とするとき

FF ≦ (17 / 10) * OPT +2

しかも以下の関係を満たす例題をつくれるので (17/10) を改善できない。

(17 / 10) * OPT -1 ≦　FF

つまり 最適な個数の高々1.7 倍ぐらいしか First Fit Algorithm はビンを消費しない。

文献　David S. Johnson, A. Demers, Jeffrey D. Ullman, M. R. Garey, R. L. Graham: Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SIAM J. Comput. 3(4): 299-325 (1974)