Title : Algorithm::SetCovering
|
Location : Home > Languages > Perl > Package Title : Algorithm::SetCovering |
|
Algorithm::SetCovering - 集合被覆問題
use Algorithm::SetCovering;
my $alg = Algorithm::SetCovering->new(
columns => 4,
mode => "greedy");
$alg->add_row(1, 0, 1, 0);
$alg->add_row(1, 1, 0, 0);
$alg->add_row(1, 1, 1, 0);
$alg->add_row(0, 1, 0, 1);
$alg->add_row(0, 0, 1, 1);
my @to_be_opened = (@ARGV || (1, 1, 1, 1));
my @set = $alg->min_row_set(@to_be_opened);
print "To open (@to_be_opened), we need ",
scalar @set, " keys:\n";
for(@set) {
print "$_: ", join('-', $alg->row($_)), "\n";
}
M 個の鍵と N 個の錠があったとし、１つの鍵は複数の錠をあけることができるものとする。
| lock1 lock2 lock3 lock4
-----+------------------------
key1 | x x
key2 | x x
key3 | x x x
key4 | x x
key5 | x x
開けるべき任意の錠の集合が与えられたとして（例えば 2,3,4）、これを達成する最小の鍵の集合を探索する。
上の例では [key4, key5] がこの条件を満たす。この背景にあるのは集合被覆問題（set covering problem）と呼ばれる問題であり、NP-完全（NP-complete）である。
$alg = Algorithm::SetCovering->new(columns => $cols, [mode => $mode]);
新たに Algorithm::SetCovering オブジェクトを生成する。必須のパラメータは columns で、行列で設定すべき列の数（錠の数）を指定する。
mode はオプションのパラメータで、探索アルゴリズムを指定する。mode には以下の値が指定できる。
brute_force
あらゆる鍵の組み合わせを実行する。鍵の数が小さいときのみ推奨される。
greedy
いわゆる「欲張り法（Greedy algorithm）である。 O(mn^2) の次数である。NP-困難な問題には不適である。デフォルトの mode はこの greedy である。
$alg->add_row(@columns)
行列に新たな行を足す。上の例では鍵を追加することに対応する。
$alg->add_row(1,0,0,1);
新しい鍵は錠 #1 及び #4 を開けることができる。
@columns の中の要素数はそれまでに定義されている要素の数と一致している必要がある。
$alg->min_row_set(@columns_to_cover)
所与の錠の集合に対し、これを開けるために必要な最小の鍵の集合を決定し、このかぎのインデクスを配列で返す。
被覆される必要がある要素位置を true 値で配列を通過することで列が被覆されているかを決定する。
例えば
my @idx_set = $alg->min_row_set(1,1,0,1);
は３項目以外の全部の列が被覆されていることを示し、そのインデクス番号を配列として返し、前もって（かつ黙示的に）後続の add_row() コマンドを用いて決定する。
もし条件を満たす鍵の集合が見つからなければ空のリストを返す。
どの錠があるインデクス番号で参照されているか忘れた場合には rows() メソッドを用いて探索することができる。
my(@opens_locks) = $alg->rows($idx_set[0]);
は前もって theadd_row() コマンドを通過したパラメータを返す 0 及び 1 の配列を返す。
現時点では、モジュールは implements 欲張り法と（科学的な目的で）総当り法を実装している。鍵のあらゆる組み合わせと生成し、使用した鍵の数によりソートして（より鍵の数が小さい組み合わせを優先して）初期の錠の数を開けるに必要な条件を満たすかを確認する。
これは明らかに鍵の数が小さい場合でないと奏功しない。鍵の数を N として 2**N-2 の組み合わせを実行することになるからだ。
一方、欲張り法では、鍵の数を m 、錠の数を n として O(mn^2) の計算量で済む。
Julien Gervais-Bird <j.bird@usherbrooke.ca> が指摘してくれた。
欲張り法が常に最小の鍵の組み合わせを返すわけではない。以下の例を見よ。
| lock1 lock2 lock3 lock4 lock5 lock6
-----+------------------------------------
key1 | x x x
key2 | x x
key3 | x x
key4 | x x
全ての鍵を開ける最小の鍵の集合は (key2, key3, key4) であるが、欲張り法の結果は key1 が他の鍵より多くの錠をあけることができるので (key1,key2,key3,key4) となる。
Mike Schilli, 2003, <m@perlmeister.com>
問題の解析のための入力と、アルゴリズムの説明をしてくれた rec.puzzles の以下の人たちに感謝。
Craig <c_quest000@yahoo.com>
Robert Israel <israel@math.ubc.ca>
Patrick Hamlyn <path@multipro.n_ocomsp_am.au>
Copyright 2003 by Mike Schilli
本ライブラリはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してもよい。
|
|
Updated : 2007/03/05 |