Location : Home > Languages > Perl > Package
Title : Algorithm::BinPack
 		Toolbox Logo

名称

　Algorithm::BinPack - 箱詰め問題

概要

　Algorithm::BinPack は箱にものを効果的に詰める。箱には最大値を与えられており、可能な限り空きがないように詰め込まれる。例えばディスクの枚数をできるだけ小さくしつつＣＤにファイルを格納するようなものである。

my $bp = Algorithm::BinPack->new(binsize => 4);

$bp->add_item(label => "one",   size => 1);
$bp->add_item(label => "two",   size => 2);
$bp->add_item(label => "three", size => 3);
$bp->add_item(label => "four",  size => 4);

for ($bp->pack_bins) {
   print "Bin size: ", $_->{size},  "\n";
   print "  Item: ",   $_->{label}, "\n" for @{ $_->{items} };
}

メソッド

new

　新しい Algorithm::BinPack オブジェクトを生成する。最大の箱の大きさは引数 'binsize' で指定され、必須である。誤差（fudge factor）を引数 'fudge' で指定することもできる。もし指定された場合には、充填するものの大きさは誤差で割ることのできる大きさに丸められる。これはよく似た大きさのものをラベル順に並べる際に有用である。

my $bp = Algorithm::BinPack->new(binsize => 4);
my $bp = Algorithm::BinPack->new(binsize => 100, fudge => 10);

add_item

　箱にものを追加して詰める。必要な引数は 'label' と'size' であるが、他のものも指定できる。オプションとして引数 'bin' を指定すると、指定した箱にものを詰めることができる。

$bp->add_item(label => 'one',  size => 1);
$bp->add_item(label => 'two',  size => 2, desc => 'The second numeral');
$bp->add_item(label => 'zero', size => 3, bin => 0);
$bp->add_item(qw(label three size 3));
$bp->add_item(qw(label four size 4 random key));

prefill_bin

　（削除される可能性のあるメソッド）
　add_item で 'bin' 引数を直接扱うことができるので本メソッドは冗長である。.

pack_bins

　箱にものを詰める。本メソッドは、各箱の余白ができるだけ小さくなるように詰めようとする。キーとして箱全体のサイズを含む 'size'、箱の中のものを保持する配列参照を含む 'items' のハッシュ参照のリストを返す。それぞれのものはキー 'label', 'size', その他追加されたものを含むハッシュ参照である。
　誤差が指定された場合にはキー 'fudgesize' を含むものを返す。

for my $bin ($bp->pack_bins) {
   print "Bin size: ", $bin->{size}, "\n";

   for my $item (@{ $bin->{items} }) {
      printf "  %-6s %-20s\n", $_, $item->{$_} for keys %{ $item };
      print  "  ---\n";
   }
}

参考資料

　本モジュールは Steven S. Skiena 著の 'The Algorithm Design Manual' に記されている箱詰めアルゴリズム（the bin packing algorithm）を実装している。

　本モジュールは Algorithm::Bucketizer と似ているがいくつか違いがある。Algorithm::Bucketizer のアルゴリズムは複数組み合わせの最適化に基づいているため、モジュールは別に構築される。これに対し Algorithm::BinPack におけるアルゴリズムは予見可能で、複数組み合わせを必要としない。
　またよく知られた問題の名前を反映している。"bin packing" のバリエーションについて調べてみれば "bucketizer" のバリエーションよりも極めて多いことがわかるだろう。

著者

　Carey Tilden, <revdiablo@wd39.com>

謝辞

　Andrew 'Terra' Gillespie, <algorithm_binpack@Tech.FutureQuest.net> - prefill_bin

著作権とライセンス

　Copyright (C) 2004-05 by Carey Tilden

　本コードは２つのライセンスに対応しており、ユーザはどちらかを選ぶことができる。

Toolbox Logo
 Updated : 2006/10/12