フロンティア法 - 組合せ問題の解を列挙索引化するZDD構築アルゴリズム

Presentation on theme: "フロンティア法 - 組合せ問題の解を列挙索引化するZDD構築アルゴリズム"— Presentation transcript:

1 フロンティア法 - 組合せ問題の解を列挙索引化するZDD構築アルゴリズム
川原　純 科学技術振興機構　ERATO湊離散構造処理系プロジェクト 北海道大学　情報科学研究科

2 列挙問題 例：グラフ上の2点間のパスを列挙 s t 既存の 列挙Alg. 列挙結果は1つずつ出力

3 列挙結果を1つずつ出力すると… 保存ができない 欲しい解を検索、絞り込みが難しい 活用が難しい s … t 17×17 グリッドグラフ
= 6.3 × 1061 = 約 63 那由多 個 s t … 17 辺 p, q を使用、辺 r を使用していないパスをすべて列挙 長さ最小のものは？ 数え上げ、ランダムサンプリング等

4 列挙結果の保存・活用 ZDD: 集合の集合をDAGで表したデータ構造 s t 全 s-t パスを表す ZDD 展開
Alg. （一様）ランダムサンプリング … 数え上げ 重み最小の要素を計算 展開 検索、絞り込み 全 s-t パスを表す ZDD 6×1061個のパスが ノード数4×108 個の ZDDに圧縮

5 列挙結果の検索・絞り込み % e ∩ ZDDには様々な代数演算が用意されている ある辺 e を通らないパスの集合 圧縮したままの演算が可能
単に列挙だけでなく、列挙結果の活用が可能となる → 列挙索引化 % e 制約A： 例えば、要素数が 10個以下 ∩ 全s-t パスを 表すZDD 制約Aを 表すZDD 制約Aを満たす 全s-tパスを表すZDD

6 本発表の内容 パス列挙（ZDD構築）アルゴリズム [D.Knuth 08]
Tutte多項式計算アルゴリズム [K.Sekine, H.Imai 95] （見かけは異なるが、） 本質的に同じアルゴリズム → 様々な対象について、ZDDを構築可能 → フロンティア法として汎用化 本質的に何が必要かを抽出 フロンティア法によって ZDD構築可能な問題を整理

7 ZDD: 集合の集合を表現するデータ構造 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 e3 e4 e5 e3 e5
(Zero-suppressed Binary Decision Diagram) [S.Minato 93] 1 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 { { } { } { } , , e3 e4 e5 e3 e5 e5 { } { } { } } , , 集合の集合 ZDD

8 ZDD: 集合の集合を表現するデータ構造 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 e3 e4 e5 e3 e5
1 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 { { } { } { } , , e3 e4 e5 e3 e5 e5 { } { } { } } , , 集合の集合 : 0 終端 それぞれ1つずつもつ 1 : 1 終端 ZDD ei e1 e5 : ノード ～ いずれかのラベル e1 , e2 ,… , e5 の順序

9 ZDD: 集合の集合を表現するデータ構造 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 e3 e4 e5 e3 e5
ノードは0枝と1枝を1つずつもつ 1 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 { { } { } { } , , e3 e4 e5 e3 e5 e5 { } { } { } } , , 集合の集合 : 0 終端 それぞれ1つずつもつ 1 : 1 終端 ZDD ei e1 e5 : ノード ～ いずれかのラベル e1 , e2 ,… , e5 の順序

10 ZDD: 集合の集合を表現するデータ構造 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 e3 e4 e5 e3 e5
ノードは0枝と1枝を1つずつもつ 1 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 { { } { } { } , , e3 e4 e5 e3 e5 e5 { } { } { } } , , 集合の集合 1つの集合が、 top から までの1本のパスに対応 1 ZDD : 0 終端 それぞれ1つずつもつ 1 : 1 終端 ei e1 e5 : ノード ～ いずれかのラベル

11 ZDD: 集合の集合を表現するデータ構造 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 e3 e4 e5 e3 e5
ノードは0枝と1枝を1つずつもつ 1 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 { { } { } { } , , e3 e4 e5 e3 e5 e5 { } { } { } } , , 集合の集合 1つの集合が、 top から までの1本のパスに対応 1 ZDD : 0 終端 それぞれ1つずつもつ 1 : 1 終端 ei e1 e5 : ノード ～ いずれかのラベル

12 ZDD: 集合の集合を表現するデータ構造 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 e3 e4 e5 e3 e5
ノードは0枝と1枝を1つずつもつ 1 e1 e2 e3 e4 e5 e1 e2 e5 e2 e4 e5 { { } { } { } , , e3 e4 e5 e3 e5 e5 { } { } { } } , , 集合の集合 1つの集合が、 top から までの1本のパスに対応 1 ZDD : 0 終端 それぞれ1つずつもつ 1 : 1 終端 ei e1 e5 : ノード ～ いずれかのラベル

13 ZDDの性質 e1 e1 1 1 e2 e2 e2 e3 e3 e4 e4 e5 e5 1 1 等価な2つのノードは必ず共有される

14 パスは辺の集合で表現できる e1 e4 s t e3 e2 e5 e1 e1 e4 e4 s t s t e3 e3 {e1, e4}

15 パスは辺の集合で表現できる e1 e4 全ての s-t パスを列挙して、 s t e3 辺集合の集合で表す e2 e5 e1 e1 e4

16 パスは辺の集合で表現できる e1 e4 s t 全ての s-t パスを列挙して、 e3 辺集合の集合で表す e2 e5
all s-t path = {{e1, e4}, {e2, e5}, {e1, e3 ,e5}, {e2, e3 ,e4}} e1 e4 e1 e4 s t s t e3 {e1, e4} e3 {e2, e5} e2 e5 e2 e5 e1 e1 e4 e4 s t s t e3 e3 {e2, e3 ,e4} {e1, e3 ,e5} e2 e2 e5 e5

17 Knuth のパス列挙アルゴリズム 全 s-t パスを表現する ZDD をトップダウン的に構築 ZDD

18 パス列挙（ZDD構築）アルゴリズム [Knuth 08]
e1 e4 e1 e1 = 1 e1 = 0 s t e3 e2 e2 e2 = 0 e2 = 1 e2 = 0 e2 = 1 e2 e5 e3 e3 e3 e3 1 1. 辺に順番を付ける （例えば、s から幅優先） e4 （もっと良い方法もあり） e5 2. ZDDを構築 辺 e1, e2,… の順に処理 s-t パスになっている 1 s e1 t e2 e3 e4 e5 各辺変数 ei に対し、 ei = 0 or 1 を決めていく ei = 1 である辺が s-t パスになっているか？

19 パス列挙（ZDD構築）アルゴリズム [Knuth 08]
e1 e4 e1 e1 = 1 e1 = 0 s t e3 e2 e2 e2 = 0 e2 = 1 e2 = 0 e2 = 1 e2 e5 e3 e3 e3 e3 1 1. 辺に順番を付ける （例えば、s から幅優先） e4 （もっと良い方法もあり） e5 2. ZDDを構築 s-t パスに なっていない s-t パス + 余分な辺 辺 e1, e2,… の順に処理 s e1 t e2 e3 e4 e5 s e1 t e2 e3 e4 e5 各辺変数 ei に対し、 ei = 0 or 1 を決めていく ei = 1 である辺が s-t パスになっているか？

20 パス列挙（ZDD構築）アルゴリズム [Knuth 08]
e1 e4 e1 e1 = 1 e1 = 0 s t e3 e2 e2 e2 = 0 e2 = 1 e2 = 0 e2 = 1 e2 e5 e3 e3 e3 e3 1 1. 辺に順番を付ける （例えば、s から幅優先） e4 （もっと良い方法もあり） e5 2. ZDDを構築 辺 e1, e2,… の順に処理 1 1 1 1 他は0 各辺変数 ei に対し、 ei = 0 or 1 を決めていく 1 が1つのパスに対応

21 パス列挙（ZDD構築）アルゴリズム [Knuth 08]
e1 e3 e1 e1 = 1 e1 = 0 s t e2 e2 e2 = 0 e2 = 1 e2 = 0 e2 = 1 e2 e4 e3 e3 e3 1 1

22 パス列挙（ZDD構築）アルゴリズム [Knuth 08]
e1 e3 e1 e1 = 1 e1 = 0 s t e2 e2 e2 = 0 e2 = 1 e2 = 0 e2 = 1 e2 e4 e3 e3 1 ノードを共有できるときは共有したい ただし、子DAGを作成せずに、共有可能か判定を行う

23 mate 配列 パス列挙（ZDD構築）アルゴリズム [Knuth 08] 接続情報の記憶法 2 e1 e4 i 1 2 3 4 1 4 e3
1 4 e3 mate[i] e2 e5 頂点がパスの端 逆端の番号 3 頂点がパスの途中 頂点がいずれの パスにも含まれない 自身の番号

24 mate 配列 パス列挙（ZDD構築）アルゴリズム [Knuth 08] e1 e4 接続情報の記憶法 2 1 4 i 1 2 3 4 e3
e3 mate[i] 3 e2 e5 頂点がパスの端 逆端の番号 頂点がパスの途中 [1, 2, 3, 4] 頂点がいずれの パスにも含まれない 自身の番号 e1 e1 = 1 e1 = 0 [1, 2, 3, 4] [2, 1, 3, 4] e2 [2, 1, 3, 4] e2 [1, 2, 3, 4] [3, 2, 1, 4] e3 e3 e3 … [4, 0, 0, 1] [4, 0, 0, 1] e4 e4 mate 配列が一致すれば共有可能

25 パス列挙（ZDD構築）アルゴリズム [Knuth 08] e1 e4 接続情報の記憶法 2 1 4 i 1 2 3 4 e3 mate[i]
e3 mate[i] 3 e2 e5 頂点がパスの端 逆端の番号 頂点がパスの途中 頂点がいずれの パスにも含まれない 自身の番号 一般に c d a b ex ex a b c d c d a b ex+1 a b c d d c 最大4か所書きかえれば更新できる

26 パス列挙（ZDD構築）アルゴリズム [Knuth 08]
未処理 処理済み 接続情報の記憶法 s t mate 配列はすべての頂点について 記憶する必要はない 5 5 s t s t 7 1 7 1 処理済みの辺と 未処理の辺の 両方が接続している 頂点集合を フロンティアという 6 6 e8 e8 等価 i i mate[i] mate[i] フロンティア上のmate値のみ記憶、比較

27 パス列挙（ZDD構築）アルゴリズム [Knuth 08]
i mate[i] s t 7 6 5 1 s-tパスが 完成 に接続 mate 配列を用いると、枝刈りも容易に可能 フロンティア 5 mateを見れば 分岐が生じることが 判定できる t s 1 7 に接続 6 i s t 7 6 5 1 s-tパス + 余計な辺 に接続 i mate[i] mate[i]

28 パス列挙アルゴリズム [Knuth 08] パス列挙の場合の 固有の処理

29 実験結果 日本地図グラフ 北海道から鹿児島までの全パス 日本地図 47 0.01秒 951 1.4 × 1010 2重化 94
頂点数 計算時間 ZDDノード数 パスの数 日本地図 47 0.01秒 951 1.4 × 1010 2重化 94 248.72秒 18,971,787 5.0 × 1044 本 本 （= 503正9760澗3851溝1518穣9594杼2145垓9492京6092兆3972億3861万6064）

30 実験結果 n × n グリッド n n 構築時間（秒） 15 206.0 16 701.9 17 2326.0 18 7607.1 19
・・・ n 実験結果 n × n グリッド n 構築時間（秒） 15 206.0 16 701.9 17 2326.0 18 7607.1 19 20 21 Thanks to 岩下洋哲氏

31 ZDD と集合族 集合の集合（集合族）は ZDD で効率よく保持できる a 1 b b {{a, b, c, d}, {a, c}, {b, d}, {b, c}} c c c d d d 1 1 1 1 は省略

32 ZDD と集合族 集合族への操作例： a を含む集合だけを取り出し、a を消去する {{a, b, c, d}, {a, c}, {b, d}, {b, c}} {{b, c, d}, {c}} a を含まない集合だけ 取り出すなら、LO 枝側を もってこればよい a 1 b b b c c c c c d 1 d d d 1 1 1 1 1 トップの要素なら簡単にできる

33 ZDD と集合族 集合族への操作例： c を含む集合だけを取り出し、c を消去する {{a, b, c, d}, {a, c}, {b, d}, {b, c}} {{a, b, d}, {a}, {b, d}} a a 1 1 b b b b c c c c c c d d d d 1 d d 1 1 1 1 1 1 1 トップでなければ、その変数の深さまで潜って、 枝の付け替えを行う

34 ZDD と集合族 集合族への操作例： c を含む集合だけを取り出し、c を消去する {{a, b, c, d}, {a, c}, {b, d}, {b, c}} {{a, b, d}, {a}, {b, d}} c を含まない集合だけ 取り出すなら、LO 枝の 方に付け替えればよい a a 1 1 b b b b c c c c c c d d d 1 d d 1 d 1 1 1 1 1 1 トップでなければ、その変数の深さまで潜って、 枝の付け替えを行う

35 ZDD と集合族 集合族への操作例： e を各要素に追加する {{a, b, c, d}, {a, c}, {b, d}, {b, c}} {{a, b, c, d, e}, {a, c, e}, {b, d, e}, {b, c, e}} e a 1 a b b b b c c c c c c d d d 1 d d d 1 1 1 1 1 1 1 トップに加える場合

36 ZDD と集合族 集合族への操作例： e を各要素に追加する {{a, b, c, d}, {a, c}, {b, d}, {b, c}} {{a, b, c, d, e}, {a, c, e}, {b, d, e}, {b, c, e}} a a 1 b b b b c c c c c c e e e e d d d 1 d d d 1 1 1 1 1 1 1 間に加える場合

37 ∩ ZDD と集合族 {{a, b, c, d}, {{a, b, c, d}, {a, b},
{b, d}, {b, c}} {{a, b, c, d}, {a, b}, {b, d}, {c, d}} {{a, b, c, d}, {b, d}} 様々な集合演算が効率よく実行可能 （再帰を用いたアルゴリズム）

38 列挙結果の検索・絞り込み（再掲） % e ∩ ZDDには様々な代数演算が用意されている ある辺 e を通らないパスの集合
制約A： 例えば、要素数が 10個以下 ∩ 全s-t パスを 表すZDD 制約Aを 表すZDD 制約Aを満たす 全s-tパスを表すZDD

39 解の数え上げ a 1 {d}, {c}, {c, d}, {b}, {b, d}, {b, c, d},
13 a 1 6 7 {d}, {c}, {c, d}, {b}, {b, d}, {b, c, d}, {a}, {a, d}, {a, c, d}, {a, b}, {a, b, c}, {a, b, d}, {a, b, c, d} b b 3 4 3 c c c d d 1 2 1

40 一様ランダムサンプリング 確率 確率 a a 1 b b b b c c c d d {d}, {c}, {c, d},
13 7 13 13 6 13 a a 1 6 7 6 7 b b b b 3 4 3 c c c d d 1 2 {d}, {c}, {c, d}, {b}, {b, d}, {b, c, d}, {a}, {a, d}, {a, c, d}, {a, b}, {a, b, c}, {a, b, d}, {a, b, c, d} 1

41 一様ランダムサンプリング 確率 確率 a 1 b b b c c c c c d d {d}, {c}, {c, d},
13 確率 確率 a 1 6 3 6 3 6 b 6 7 b b 3 3 3 4 3 c c c c c d d 1 2 {d}, {c}, {c, d}, {b}, {b, d}, {b, c, d}, {a}, {a, d}, {a, c, d}, {a, b}, {a, b, c}, {a, b, d}, {a, b, c, d} 1

42 一様ランダムサンプリング {b, d} a 1 b b c c c d d {d}, {c}, {c, d},
13 a 1 6 7 b b 3 4 3 c c c d d 1 2 {d}, {c}, {c, d}, {b}, {b, d}, {b, c, d}, {a}, {a, d}, {a, c, d}, {a, b}, {a, b, c}, {a, b, d}, {a, b, c, d} 1

43 フロンティア法とは トップダウンにZDDを構築する技法 e1 e1 = 1 フロンティア e1 = 0 5 e2 e2 e2 = 0
t s 1 e3 e3 7 1 6 i ノードを共有できるときは共有したい mate[i] フロンティア上に 何らかの情報を持たせて、 共有可能性と枝刈りを判定 一般化して configuration と呼ぶ

44 辺変数型 パス型 森型 頂点変数型 グラフ ハイパー グラフ フラグ型 クリーク 頂点被覆 0-1 ナップザック 頂点彩色 マトロイド
[Knuth 2008] 森 全域木 一般化 ハミルトンパス カット（セット） 信頼性多項式 [Imai et al. 1997] 辺被覆 集合被覆 s-tカット オイラー路 シュタイナー木 k 終端カット サイクル 根付き森、木 完全 マッチング [Knuth 2008] 連結成分 集合分割 ハミルトンサイクル 信頼性多項式 複数終端対パス [Hardy et al. 2007] 集合 パッキング Tutte多項式 マッチング （ナンバーリンク） Jones多項式 　　（ひもの絡み目） [Yoshinaka et al. 2012] 　上記3つ [今井, 今井 1998] 複数サイクル 上記2つ[関根, 今井 1996] 有向グラフ 有向パス [Knuth 08] 頂点変数型 クリーク 頂点被覆 0-1 ナップザック 頂点彩色 マトロイド 独立集合 特殊 部分和 括弧列 Tutte 多項式 [Saitoh et al. 2009] [Imai et al. 1996] 支配集合 特殊 数分割 動的計画法的な見方も可能

45 全域木の列挙 （本質的には [K.Sekine, H.Imai 95]） configuration の設計 5 5 s t s t s t
未処理 処理済み 5 5 s t s t s t 7 7 1 1 1 1 6 6 2 2 e8 e8 フロンティアの 定義は同じ 等価 i i mate[i] mate[i] configuration として、各頂点が属する 連結成分の番号を記憶

46 全域木の列挙 （本質的には [K.Sekine, H.Imai 95]） 枝刈りの設計 5 5 t s t 7 1 s 1 7 1 1 6
同じ連結成分を 両端とする辺を加えるとき、 サイクルができる 5 t s 7 t 1 s 1 7 に接続 1 1 6 2 6 2 i 加えない mate[i] 5 t 孤立成分が 生じる s 7 1 1 最後の辺まで処理後、 0 に接続されないなら に接続 6 2 1 に接続

47 フロンティア法（再掲） 枝刈り の設計 configuration の設計

48 マッチングの列挙 configuration の設計 枝刈りの設計 5 5 t s t s 7 1 7 1 6 6 i 5 6 7 i
マッチングに 使われている 頂点に 辺を加える時 6 6 に接続 i i mate[i] mate[i] 既にマッチングに使われている頂点は 1 使われていない頂点は 0 と すればよい 最後の辺まで処理後、 0 に接続されないなら 1 に接続

49 辺変数型 パス型 森型 頂点変数型 グラフ ハイパー グラフ フラグ型 クリーク 頂点被覆 0-1 ナップザック 頂点彩色 マトロイド
[Knuth 2008] 森 全域木 一般化 ハミルトンパス カット（セット） 信頼性多項式 [Imai et al. 1997] 辺被覆 集合被覆 s-tカット オイラー路 シュタイナー木 k 終端カット サイクル 根付き森、木 完全 マッチング [Knuth 2008] 連結成分 集合分割 ハミルトンサイクル 信頼性多項式 複数終端対パス [Hardy et al. 2007] 集合 パッキング Tutte多項式 マッチング （ナンバーリンク） Jones多項式 　　（ひもの絡み目） [Yoshinaka et al. 2012] 　上記3つ [今井, 今井 1998] 複数サイクル 上記2つ[関根, 今井 1996] 有向グラフ 有向パス [Knuth 08] 頂点変数型 クリーク 頂点被覆 0-1 ナップザック 頂点彩色 マトロイド 独立集合 特殊 部分和 括弧列 Tutte 多項式 [Saitoh et al. 2009] [Imai et al. 1996] 支配集合 特殊 数分割 動的計画法的な見方も可能

50 支配集合の列挙 v1 v4 v7 v5 v8 v2 v9 v1 v3 v1 = 0 v1 = 1 v6 v2 v2 v2 = 0
頂点の取捨選択の情報を （フロンティア上の）頂点に記憶しているため、 効率が良いとは限らない v1 v4 v7 v5 v8 v2 ではない全ての頂点は v9 v1 v3 v1 = 0 v1 = 1 少なくとも1つの に隣接する v6 v2 v2 v2 = 0 v2 = 1 v2 = 0 v2 = 1 v1 v4 v7 頂点を変数とするZDDを構築 v5 v8 v2 i 頂点が支配されているなら1 支配されていないなら0 と すればよい mate[i] v3 v9 v6

51 0/1 ナップザック問題の列挙 x1 x2 xn x1 x1 = 1 x1 = 0 x1 x2 x2 x2 = 1 x2 = 0
重さ x1 各アイテムを 取るかとらないかを選択 重さが M 以下になるような取り方 50 x2 100 … … xn configuration = 重さの総和 210 x1 x1 = 1 x1 = 0 50 x1 x2 x2 x2 = 0 x2 = 1 x2 = 0 x2 = 1 x2 動的計画法のテーブルと見ることもできる … このグラフに対する フロンティア法と 見ることができる xn

52 辺変数型 パス型 森型 頂点変数型 グラフ ハイパー グラフ フラグ型 クリーク 頂点被覆 0-1 ナップザック 頂点彩色 マトロイド
[Knuth 2008] 森 全域木 一般化 ハミルトンパス カット（セット） 信頼性多項式 [Imai et al. 1997] 辺被覆 集合被覆 s-tカット オイラー路 シュタイナー木 k 終端カット サイクル 根付き森、木 完全 マッチング [Knuth 2008] 連結成分 集合分割 ハミルトンサイクル 信頼性多項式 複数終端対パス [Hardy et al. 2007] 集合 パッキング Tutte多項式 マッチング （ナンバーリンク） Jones多項式 　　（ひもの絡み目） [Yoshinaka et al. 2012] 　上記3つ [今井, 今井 1998] 複数サイクル 上記2つ[関根, 今井 1996] 有向グラフ まとめ　　・フロンティア法によって様々な対象を表現する 　　　　　　 ZDDを構築可能 → configuration と枝刈りの設計 有向パス [Knuth 08] 頂点変数型 クリーク 課題: 計算量評価等の理論的裏付け 頂点被覆 0-1 ナップザック 頂点彩色 マトロイド 独立集合 特殊 部分和 括弧列 Tutte 多項式 [Saitoh et al. 2009] [Imai et al. 1996] 支配集合 特殊 数分割 動的計画法的な見方も可能