極小集合被覆を列挙する 実用的高速アルゴリズム

Presentation on theme: "極小集合被覆を列挙する 実用的高速アルゴリズム"— Presentation transcript:

1 極小集合被覆を列挙する 実用的高速アルゴリズム
宇野 毅明 国立情報学研究所 2002年3月　アルゴリズム研究会

2 極小集合被覆とは ・ E ： 台集合 ・ F ⊆ 2E ： 集合族
・ 　C ⊆ F が F の集合被覆　　⇔ ∀e ∈ E , ∃S∈ C, e ∈ S 極小集合被覆 ： 　他の集合被覆を含まない集合被覆 E = {1,2,3,4,5,6} F = {{1,2,3} , {1,4,5,6}, {1,3,5}, {2,4}, {5,6}} 集合被覆： 　　　　　　　　極小集合被覆： {1,2, } , {1,2, } {1, 3, }, {1, 4,5,6} { 2, }, { ,6}

3 極小集合被覆列挙問題 今回の研究： ↑のアルゴリズムを高速化
問題： 与えられた E , F ⊆ 2E に対して, F の極小集合被覆を全て出力せよ ・ #P-complete である ・ 出力多項式のアルゴリズムがあるかどうか不明 ・ 他のいろいろな問題と等価 (hypergraph dualization, minimal hitting set の列挙) ・ いろいろな人がチャレンジしている ・ 現在, 計算量の意味での最速なものは O(出力数 log 出力数) ・ 実用上高速なアルゴリズムを作る研究も行われている （ Kavvadias & Stavropoulos ’99） 今回の研究： ↑のアルゴリズムを高速化

4 無駄な出力の回数を解析  現在の計算量最速アルゴリズム
どうやって列挙するか？ ・ 　一般に良く使われる列挙法 ： 分割法 　解集合を2分割し, 各々を子問題として再帰的に解く ただし　　 ・ 空集合と全体集合, という分割をしないこと （子問題の解の存在性をチェックできること） 　　 　　　　・ 再帰的に子問題が作成できること 簡単に, 「 ある S を含む極小集合被覆」 「 ある S を含まない極小集合被覆」 と分割すると, 前者が子問題として 表現できない（あるいは重なる） ． 無駄な出力の回数を解析　  現在の計算量最速アルゴリズム

5 他のアプローチ 台集合 E = {e1,…,en} を限定した問題を逐次解く方法 ・ 最初 E1 = {e1} として問題を解く
・ 逐次 E を大きくしていき, 解集合を更新し, En={e1,…,en} の解集合を得る … E1 ={e1} E2 ={e1,e2} ,…, En-1 ={e1,…,en-1} E ={e1,…,en} 問題点 ： メモリを沢山消費 Kavvadias & Stavropoulos はメモリを使わないように改良

6 逆探索 Kavvadias & Stavropoulos の方法は, 逆探索として捉えられる
・ （特別なある一つの要素以外の）任意の解に, 親（他の解)を定義 ・ ただし, 各解が自分自身の真の先祖にならないこと ・ 親子関係から木（列挙木）が得られる

7 列挙木を深さ優先探索 ・ 解を列挙するには, 列挙木を深さ優先探索すればよい
・ 列挙木全体を記憶しなくても, 現在の解の子供を列挙するアルゴリズムがあれば十分 ・ 入力多項式のメモリしかいらない（木の高さが入力多項式なら） （・ さらに, 子供に順序付けをして, 与えられた子供の次の子供を見つけるアルゴリズムがあると, 木の深さもメモリに影響しない）

8 極小集合被覆間の親子関係 E0 ,…, En のすべての極小集合被覆に定義 （ Ei の極小集合被覆 C を ( i ,C ) と表記する）
1. C がEi-1 の極小集合被覆ならば, ( i-1 ,C ) を親とする 2. そうでないなら, C から（ ei を含む集合） を取り除いたものを C’ として, ( i-1 ,C’ ) を親とする i=6　　　　{1, }, {1,2, } 　　　　　　{ , }, {1, 4,5 } 　　　　　　{ 2, 4, 6}, {1, 3, 5,6}

9 親子関係の妥当性 集合被覆 C がEi の極小集合被覆である ⇔ C の各集合 S に対して, Ei の要素で S にしか覆われていないものが存在する （S のクリティカル要素と呼ぶ） 極小集合被覆 ( i ,C ) に対して, C がEi-1 の極小集合被覆でない  C のある集合 S のクリティカル要素は ei のみであり, C の他の集合のクリティカル要素は eiではない  C から S を除くと極小集合被覆になる {1,2, } {1,2, } { , } {1, 4,5 } { 2, 4, 6} {1, 3, 5,6}

10 ・ 子供は最大 |F| 人. 必ずいるとは限らない
親から子供を得るには ・ 親の定義の逆をすればよい ・ 任意の ( i ,C ) に対して, 1. もし C がEi+1 の極小集合被覆ならば, ( i +1,C ) は子供 　 ⇔　（ C はEi の極小集合被覆なので ( i ,C ) は( i +1,C ) の親 ） 2. C がEi+1 の極小集合被覆でないときは, C ∪{ S’ ＝（ ei+１ を含む集合）} が Ei+1 の極小集合被覆ならば, 　 ( i +1, C ∪{ S’ } ) は子供 　 ⇔　（ C ∪{ S’ } はEi の極小集合被覆でないので 　　　　 S’ を取り除いて得られる ( i ,C ) が親 ） ・ 子供は最大 |F| 人. 必ずいるとは限らない　　

11 高速化をして、実際どの程度速くなるか検証する
計算量は押さえられない ・ 1反復は入力多項式時間. 反復の総数は, 　（全ての Ei 上の, 極小集合被覆数の総和） ・ 出力数多項式時間にはならない ・ En 上の解集合に比べて Ei 上の解集合が極端に大きくなるとは考えにくい  たぶん, 実際はかなり速い（出力数多項式）だろう 　高速化をして、実際どの程度速くなるか検証する　

12 反復の高速化（改良１） ・ C ∪ ｛S’｝ の極小性チェックに時間がかかっている ・ 各反復で, 極小集合被覆 C に対し,
各 S∈C に対し, S のクリティカル要素 （ S しか覆ってない要素の集合） c(S) を記憶 c(S) ⊆ S’ となる S ∈C が存在しなければ, C ∪ ｛S’｝ は極小 { 1, 2, 3,7 }, { 1, 2, 4 }, { 5,6 } ・ { 3,5,7,8 } は加えられない　　 ・{ 1,2,3,5,8 } は加えられる 普通にチェック　O(|E||F|)  この方法 O(|E|) （ 計算結果から推測するに, Kavvadias & Stavropoulos は普通にチェック、の方法を用いているようだ）

13 反復の高速化（改良2） c(S) ⊆ S’ となる S ∈C が存在しなければ, C ∪ ｛S’｝ は極小
各 S’ ∈C の要素で, いずれかの c(S), S ∈C に含まれるものを保持 （反復の操作ごとに変更, 更新する. O(|F|) 時間程度） ／

14 順番を入れ替えて高速化 ・ E = { e1,…, en } の添え字を各要素を含む集合の数でソートする 小さい順  反復数が減るだろう
小さい順　　  　　反復数が減るだろう 大きい順　　  　　各反復の計算時間が減るだろう さて, どっちが速い？

15 計算機実験 環境 ： Pentium Ⅲ 500MHz, linux, 普通の C でプログラムを作り, gcc でコンパイルした
問題生成法 ：　各要素が, 各集合に含まれる確率が3割として生成 ※ 解が100万以上のときは100万個出力したところで打ち切る

16 実験結果の概略 計算時間／出力数 改良１： O(|E|) より少々大きい 改良２： O(|E|) 程度
・ 集合族の大きさは少ししか計算時間に関係しないようだ ※ 各反復で, 子供候補のうち, だいたい一定割合が子供になっているのだろう ※ 深い反復での, 各集合が含むクリティカル要素数は, ほぼ定数であったので, 改良２が速いのだろう ・ ランダム：小さい順：大きい順　 ＝ 　（およそ） 1 ： 0.7 ： 2.0 ※ 各集合の大きさの偏りを増やすと, この比は大きくなる 　　　　  　反復数を減らしたほうが効果は高いようだ　

17 改良 1 と改良 1+2 の比較 前の論文： |E|=50, |F|=50 で 500秒 程度

18 添え字の順序を並び替えた場合

19 さらに大きな台集合で 前の論文：　|E| = 1000 で 20000秒くらい

20 まとめと今後の課題 ・ 極小集合被覆列挙問題に対して, 実験的に高速なアルゴリズムを提案した
・ ランダム問題に対する計算実験の結果, 入力 E , F ⊆ 2E に対する計算時間は, 1つあたりおよそ O(|E|) であった ・ 添え字の付け方を工夫すると, 出力数多項式オーダーになるかもしれない （ ・実は, もうひとつ改良を試してみたのだが, 速くならなかった） ・ 解１つあたり O(1) 程度の時間にできるかどうかが今後の課題