荷作り問題 - 東京大学

荷作り問題
東京大学大学院
工学系研究科
伊庭斉志
荷作り問題



ベルトコンベアをいろいろな大きさ（Ｌ以下とする）
の荷物がN個流れてくる
最大でL単位分の荷物が入る大きな箱がある
使う箱の数が最小になるように詰めていくのにどう
すればよいか？
荷作り問題

荷物の例 N=25のとき、L=10とする
6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1

ベルトコンベアという点が注意


荷物をまとめて分類できない
荷物が来るたびに１つずつ箱に入れるしかない
ネクストフィット法




もっとも簡単だが、効率が悪い
箱に入れられる限り荷物を入れる
入らなくなったら次の箱に入れる
箱はどんどん運ばれてしまうので、前の箱に
入れなおすことはできない
ネクストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
まず6の荷物が来ると新しい箱に入れる

[6]
ネクストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
次の6の荷物はそこには入らないので新しい箱に
入れる

[6],[6]
ネクストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
次の5の荷物もそこには入らないので３番目の箱
に入れる

[6],[6],[5]
ネクストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
次の5の荷物は３番目の箱に入るのでそこに入れ
る

[6],[6],[5,5]
ネクストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
次とその次の５の荷物２つは新しい４番目の箱に
入れる

[6],[6],[5,5],[5,5]
ネクストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
以上の結果、次のように最終的な箱の入れ方が求
められる

[6],[6],[5,5],[5,5],[4,3,2],[2,3],[7],[6],[5,4],[3,2,2],
[4,4],[5],[8,2],[7,1]
ネクストフィット法

荷物の例 N=25のとき、L=10とする

[6],[6],[5,5],[5,5],[4,3,2],[2,3],[7],[6],[5,4],[3,2,2],
[4,4],[5],[8,2],[7,1]

箱は14個使い、そのうち3個だけが満杯である

無駄な（空き）スペースの合計は

4+4+1+5+3+4+1+3+2+5+2=34
ファーストフィット法



ネクストフィット法を少し改善する
前の方の箱の空きスペースに荷物が入れられない
のがネクストフィット法の欠点である
荷物がまだ入る箱のなかで最初に来ていたものに
荷物をいれてもいいとする
ファーストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
まず6の荷物が来ると新しい箱に入れる

[6]
ファーストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
次の6の荷物はそこには入らないので新しい箱に
入れる

[6],[6]
ファーストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
次の5の荷物もそこには入らないので３番目の箱
に入れる

[6],[6],[5]
ファーストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
次の5の荷物は３番目の箱に入るのでそこに入れ
る

[6],[6],[5,5]
ファーストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
次とその次の５の荷物２つは新しい４番目の箱に
入れる

[6],[6],[5,5],[5,5]
ここまではネクス
トフィット法と同じ
ファーストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
次にくる４の荷物は、６が入った最初の箱に入れら
れる

[6,4],[6],[5,5],[5,5]
ファーストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
次にくる3の荷物は、６が入った2番目の箱に入れ
られる

[6,4],[6,3],[5,5],[5,5]
ファーストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
次の２の荷物２つと３の荷物１つは5番目の箱をつ
くっていれる

[6,4],[6,3],[5,5],[5,5],[2,2,3]
ファーストフィット法

荷物の例 N=25のとき、L=10とする


6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
以上の結果、次のように最終的な箱の入れ方が求
められる

[6,4],[6,3,1],[5,5],[5,5],[2,2,3,3],[7,2],[6,4],[5,2,2],
[4,4],[5],[8],[7]
ファーストフィット法

荷物の例 N=25のとき、L=10とする

[6],[6],[5,5],[5,5],[4,3,2],[2,3],[7],[6],[5,4],[3,2,2],
[4,4],[5],[8,2],[7,1]

箱は12個使い、そのうち6個が満杯である

無駄な（空き）スペースの合計は


1+1+2+5+2+3=14
ネクストフィット法：4+4+1+5+3+4+1+3+2+5+2=34
ファーストフィット法

もっと改善できないか？




[6],[6],[5,5],[5,5],[4,3,2],[2,3],[7],[6],[5,4],[3,2,2],
[4,4],[5],[8,2],[7,1]
後ろの方に大きな荷物があると無駄なスペースが
生じやすい
前の方の箱に残っている空きスペースは後になる
と小さくなっているので新たな箱が必要である
サイズの大きいものから入れていく
並べ替えネクストフィット法

荷物の例 N=25のとき、L=10とする

6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
ソート


8,7,7,6,6,6,5,5,5,5,5,5,4,4,4,4,3,3,3,2,2,2,2,2,1
[8],[7],[7],[6],[6],[6],[5,5],[5,5],[5,5],[4,4],[4,4],[3,
3,3],[2,2,2,2,2],[1]
並べ替えネクストフィット法

荷物の例 N=25のとき、L=10とする

[8],[7],[7],[6],[6],[6],[5,5],[5,5],[5,5],[4,4],[4,4],[3,
3,3],[2,2,2,2,2],[1]

箱は14個使い、そのうち4個が満杯である

無駄な（空き）スペースの合計は

2+3+3+4+4+4+2+2+1+9=34
並べ替えファーストフィット法

荷物の例 N=25のとき、L=10とする

6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1
ソート


8,7,7,6,6,6,5,5,5,5,5,5,4,4,4,4,3,3,3,2,2,2,2,2,1
[8,2],[7,3],[7,3],[6,4],[6,4],[6,4],[5,5],[5,5],[5,5],[4
,3,2,1],[2,2,2]
並べ替えファーストフィット法

荷物の例 N=25のとき、L=10とする

[8,2],[7,3],[7,3],[6,4],[6,4],[6,4],[5,5],[5,5],[5,5],[4
,3,2,1],[2,2,2]

箱は11個使い、そのうち10個が満杯である

無駄な（空き）スペースの合計は

最後の箱の空き＝4
並べ替えファーストフィット法

荷物の例 N=25のとき、L=10とする

[8,2],[7,3],[7,3],[6,4],[6,4],[6,4],[5,5],[5,5],[5,5],[4
,3,2,1],[2,2,2]

箱は11個使い、そのうち10個が満杯である

無駄な（空き）スペースの合計は

最後の箱の空き＝4
これが最適か？
並べ替えファーストフィット法

荷物の例 N=25のとき、L=10とする

6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1

箱は11個使い、そのうち10個が満杯である
無駄な（空き）スペースの合計＝４

荷物の合計




6+6+5+…+=106
箱の容量は１０なので箱は11個少なくとも必要
無駄になるスペースは４以上 よって最適解
レポート課題の１つ

並べ替えファーストフィットは本当にいいのか？

他にいい方法がないのだろうか？


ヒューリスティック
どのようにして確かめたらいいだろうか？



ランダムに問題を生成していろいろな方法で試す
意地悪な問題をわざと作ってみる
ソートの分は損していないか？