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

講義の目標 パスの数え上げアルゴリズムを理解する 大規模データを扱うためのデータ構造の1つ 「ZDD」 についてより詳しく知る 大規模データの保存、活用 様々な対象を表現するZDDを高速に構築する手法 　 「フロンティア法」 アルゴリズムを理解する 適用事例について知る

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

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 の順序

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 の順序

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 : ノード ～ いずれかのラベル

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 : ノード ～ いずれかのラベル

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 : ノード ～ いずれかのラベル

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

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

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

パスは辺の集合で表現できる 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

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

パス列挙（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 パスになっているか？

パス列挙（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 パスになっているか？

パス列挙（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つのパスに対応

パス列挙（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

パス列挙（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 ノードを共有できるときは共有したい ただし、子DAGを作成せずに、共有可能か判定を行う

パス列挙（ZDD構築）アルゴリズム [Knuth 08] s t e1 e3 パス列挙（ZDD構築）アルゴリズム [Knuth 08] s t e2 e4 e1 = 0 e1 = 1 e2 = 0 e2 = 1 ? e1 = 0 e1 = 1 e2 = 1 e2 = 0 途中の経路は分からないが s につながっていることは分かっている

パス列挙（ZDD構築）アルゴリズム [Knuth 08] s t … … 未処理辺 処理済み辺 t フロンティア

… … パス列挙（ZDD構築）アルゴリズム [Knuth 08] d a t s f c b h g f f d d d d a s a s

… … パス列挙（ZDD構築）アルゴリズム [Knuth 08] d f a t s d f a c s b t h g c b h g f

mate 配列 … … パス列挙（ZDD構築）アルゴリズム [Knuth 08] 接続情報の記憶法 d 頂点がパスの端 a a t s 逆端の頂点 f c s b … b h 頂点がパスの途中 g 頂点がいずれの パスにも含まれない v d f g v a b 自身の頂点 mate[v] mate[v] f d s a 0 mate 配列

パス列挙（ZDD構築）アルゴリズム [Knuth 08] a e1 e5 s t e3 e2 a s b e6 e4 s a c mate 値 a s b e6 e4 s a c b a s a a b b s s a s b s s s a c s c s s

パス列挙（ZDD構築）アルゴリズム [Knuth 08] a e1 e5 s t e3 e2 a s b e6 e4 s a c mate 値 a s b e6 e4 s a c a a b s b a s s b s a s a b s s s c s

パス列挙（ZDD構築）アルゴリズム [Knuth 08] a e1 e5 s t e3 e2 b e6 e4 c s a s c s s a c t s

パス列挙（ZDD構築）アルゴリズム [Knuth 08] a e1 e5 s t e3 e2 b e6 e4 c s a s c s a t 1 s c s 1 1

パス列挙（ZDD構築）アルゴリズム [Knuth 08] a e1 e5 s t e3 e2 b e6 e4 c s a 根から　　までの 1つの経路が 1 つのs-t パスに 対応する 1 s c s a t 1 s c s 1 1

パス列挙（ZDD構築）アルゴリズム [Knuth 08] mate 配列の更新例 a a g g b b s c s c d d f f v a b c d f v a b c d f g mate[v] c 0 a d s mate[v] 0 0 g d s c

パス列挙（ZDD構築）アルゴリズム [Knuth 08] mate 配列の更新 一般に a b c d c d a b c d a b a b c d 0 0 d c 最大4か所書きかえれば更新できる

パス列挙アルゴリズム [Knuth 08]

枝刈り a a b c s g d f g b s c d f

枝刈り a a b c s g d f g b s c d f

枝刈り a a b c s g d f t g b s c d t f

枝刈り 1 a a b c s g d f t g b s c d t f

パス列挙アルゴリズム [Knuth 08]

p q 終端判定条件 辺 e を処理する前の判定 if x = 1 if GetDegree(p) = 2 or GetDegree(q) = 2 終端 if (p = s or p = t) and GetDegree(p) = 1 終端 GetDegree(v) if (q = s or q = t) and GetDegree(q) = 1 if mate[v] == v 終端 return 0 if mate[p] = q and mate[q] = p if mate[v] == 0 終端 return 2 if mate[p] = s and mate[q] = t or else mate[p] = t and mate[q] = s return 1 for each vertex v in the frontier if v != s or v != t or v!= p or v!= q if GetDegree(v) = 1 終端 end for 1 終端 end if

a a g g b b s s c c d d f f 辺 e を処理した後の判定 for each v such that v がフロンティアから外れる if v = s or v = t if GetDegree(v) = 0 GetDegree(v) 終端 if mate[v] == v else return 0 if GetDegree(v) = 1 if mate[v] == 0 終端 return 2 else return 1 a a g g b b s c s c d d f f

e1 e3 s パスの数え上げ e2 e4 e5 e6 e8 e7 e9 e10 t e11 e12 12 6 6 6 6 2 4 3 3

実験結果 s n × n グリッド t 頂点の数 (n + 1) × (n + 1) ・・・ n × n グリッド t 頂点の数 (n + 1) × (n + 1) The On-Line Encyclopedia of Integer Sequence (OEIS) : 数列大辞典 http://oeis.org/A007764

実験結果 s n × n グリッド t 頂点の数 (n + 1) × (n + 1) ・・・ n × n グリッド t 頂点の数 (n + 1) × (n + 1) The On-Line Encyclopedia of Integer Sequence (OEIS) : 数列大辞典 http://oeis.org/A007764

実験結果 s n × n グリッド t 頂点の数 (n + 1) × (n + 1) n time（秒） 15 206.0 16 701.9 17 2326.0 18 7607.1 19 28279.2 20 91944.1 21 284117.0 実験結果 ・・・ n × n グリッド t 頂点の数 (n + 1) × (n + 1) Thanks to 岩下洋哲氏

実験結果 日本地図グラフ 北海道から鹿児島までの全パス 日本地図 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 14797272518 本 5039760385115189594214594926092397238616064 本 （= 503正9760澗3851溝1518穣9594杼2145垓9492京6092兆3972億3861万6064）

講義の目標 パスの数え上げアルゴリズムを理解する 大規模データを扱うためのデータ構造の1つ 「ZDD」 についてより詳しく知る 大規模データの保存、活用 様々な対象を表現するZDDを高速に構築する手法 　 「フロンティア法」 アルゴリズムを理解する 適用事例について知る

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

ZDD と集合族 集合族への操作例： a を含む集合だけを取り出し、a を消去する {{a, b, c, d}, {a, c}, {b, d}, {b, c, d}} {{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 トップの要素なら簡単にできる

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

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

ZDD と集合族 集合族への操作例： 集合族 F から要素 ｘ を含む集合だけを取り出し、x を消去する F / x 集合族 F から要素 ｘ を含まない集合だけを取り出し、x を消去する F % x {{a, b, c, d}, {a, c}, {b, d}, {b, c, d}} abcd + ac + bd + bcd = (abd + a + bd) c + bd c を含む集合だけを取り出し、c を消去する (abcd + ac + bd + bcd ) / c = abd + a + bd c を含む集合だけを取り出し、c を消去する (abcd + ac + bd + bcd ) % c = bd

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

ZDD と集合族 集合族への操作例： d を各要素に追加する {{a, b, c, d, e}, {a, c, d}, {{a, b, c, e}, {a, c}, {b, e}, {b, c}} {{a, b, c, d, e}, {a, c, d}, {b, d, e}, {b, c, d}} a d が1つも 含まれない場合 a 1 b b b b c c c c c c d d d d e e e 1 e e e 1 1 1 1 1 1 1 間に加える場合

ZDD と集合族 集合族への操作例： d を各要素に追加する {{a, b, c, e}, {a, d}, {b, e}, {b, d}} {{a, b, c, d, e}, {a, d}, {b, d, e}, {b, d}} d が含まれる場合 {d} ∪ {d} = {d} である それほど簡単ではない（省略）

ZDD と集合族 集合族への操作例： 集合族 F の各要素に ｘ を加える F * x {{a, b, c, e}, {a, d}, {b, e}, {b, d}} abce + ad + be + bd 各要素に d を加える (abce + ad + be + bd) * d = abcde + add + bde + bdd = abcde + ad + bde + bd

ZDD と集合族 集合族 F から要素 ｘ を含む集合だけを取り出す（x は消去しない） (F / x) * x {{a, b, c, d}, {a, c}, {b, d}, {b, c, d}} abcd + ac + bd + bcd = (abd + a + bd) c + bd c を含む集合だけを取り出す（c は消去しない） ((abcd + ac + bd + bcd ) / c) * c = (abd + a + bd) * c = abcd + ac + bcd

ZDD と集合族 F = { {c}, {b, c} , {a}, {a, b}, {a, b, c} } G = { {b}, {b, c}, {a, b} } c + bc + a + ab + abc b + bc + ab a a 1 1 b b b b c c c c 1 1 F ∪ G = { {c}, {b, c} , {a}, {a, b}, {a, b, c}, {b} }

F = { {c}, {b, c} , {a}, {a, b}, {a, b, c} } G = { {b}, {b, c}, {a, b} } c + bc + a + ab + abc b + bc + ab a a 1 1 b b b b c c c c 1 1 (c + bc) + a(ε + b + bc) (b + bc) + a(b) F ∪ G = (c + bc) ∪ (c + bc) + a((ε + b + bc) ∪(b))

F G a a 1 1 F0 F1 G0 G1 一般に F = F0 ∪ a * F1 G = G0 ∪ a * G1 のとき F ∪ G = (F0 ∪ G0) ∪ a * (F1 ∪ G1)

apply (F, G, ∪) = make_node(a, apply (F0, G0, ∪), apply (F1, G1, ∪)) 1 1 1 F0 F1 G0 G1 F0 ∪ G0 F1 ∪ G1 一般に F = F0 ∪ a * F1 G = G0 ∪ a * G1 のとき F ∪ G = (F0 ∪ G0) ∪ a * (F1 ∪ G1) （ノード飛び越しがあると もっと複雑） apply (F, G, ∪) = make_node(a, apply (F0, G0, ∪), apply (F1, G1, ∪)) apply (F, {}, ∪) = F など ∩ や Δ (対称差) なども同様

F G F ∪ G a a a 1 1 1 F0 F1 G0 G1 F0 ∪ G0 F1 ∪ G1 最悪計算量は (F のノード数) * (G のノード数) 演算をキャッシュすると高速化できる （実用的には出力ZDDのノード数に線形のことが多い）

e1 e3 s F: 全s-t パスを表すZDD e2 e4 e5 e6 e8 e7 e9 e10 t e11 e12 e9 を必ず通る s-t パスの集合は？ (F / e9) * e9 e9 を必ず通らない s-t パスの集合は？ (F % e9) * e9

a, b, c, d のうち、 ちょうど3個の要素からなる集合の集合　を表すZDD { {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d} } a 1 b b R(3, 4) と表記する c c c d d d d 1

e9 を必ず通る長さが 8 の s-t パスの集合は？ F: 全s-t パスを表すZDD e2 e4 e5 e6 e8 e7 e9 e10 t e11 e12 e9 を必ず通る長さが 8 の s-t パスの集合は？ ((F / e9) * e9) ∩ R(8, 12) （必ずしも効率的とは限らない。 フロンティア法で直接作る方が速いことも）

条件付きパス（サイクル）の列挙

1 条件付きパス（サイクル）の列挙 e2 e1 e3 e4 f = f + f / e4 % e3 % e2 % e1) * e4

一様ランダムサンプリング 確率 確率 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

一様ランダムサンプリング 確率 確率 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

一様ランダムサンプリング {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

講義の目標 パスの数え上げアルゴリズムを理解する 大規模データを扱うためのデータ構造の1つ 「ZDD」 についてより詳しく知る 大規模データの保存、活用 様々な対象を表現するZDDを高速に構築する手法 　 「フロンティア法」 アルゴリズムを理解する 適用事例について知る

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

パス列挙アルゴリズム [Knuth 08] (a), (b), (c) がs-tパスの場合の固有の処理

ハミルトンパス （全点を通る s-t パス） 辺 e を処理した後の判定 for each v such that v がフロンティアから外れる if v = s or v = t if GetDegree(v) = 0 終端 else if GetDegree(v) = 1 or GetDegree(v) = 0 終端

複数終端対パス s2 s1 - t1 パス s1 交差しない の組を全列挙 s2 - t2 パス t3 s3 - t3 パス si や ti をヒント頂点、 t2 s3 (si , ti) をヒントペアという t1

複数終端対パス p q 終端判定条件 辺 e を処理する前の判定 if x = 1 if GetDegree(p) = 2 or GetDegree(q) = 2 終端 GetDegree(v) if (p がヒント頂点) and GetDegree(p) = 1 if mate[v] == v 終端 return 0 if (q がヒント頂点) and GetDegree(q) = 1 if mate[v] == 0 終端 return 2 if mate[p] = q and mate[q] = p else 終端 return 1 if (mate[p] と mate[q] がともにヒント頂点) (mate[p], mate[q]) も (mate[q], mate[p]) もヒントペアではない 終端

最後の辺を処理し終えて、 終端でなければ 終端 複数終端対パス 終端判定条件 辺 e を処理した後の判定 for each v such that v がフロンティアから外れる if v がヒント頂点 GetDegree(v) if GetDegree(v) = 0 if mate[v] == v return 0 終端 if mate[v] == 0 else return 2 if GetDegree(v) = 1 else 終端 return 1 最後の辺を処理し終えて、　　　終端でなければ　　 終端 1

全域木 （本質的には [K.Sekine, H.Imai 95]） サイクルが生じてはいけない 連結成分が2つ以上 生じてはいけない

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

全域木 （本質的には [K.Sekine, H.Imai 95]） configuration の設計 a a b b A A c c B 等価 v a b c v a b c mate[v] A A B mate[v] A A B configuration として、各頂点が属する 連結成分のIDを記憶 同じ連結成分に属しているなら同じID 異なる連結成分に属しているなら異なるID

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

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

辺変数型 パス型 森型 頂点変数型 グラフ ハイパー グラフ フラグ型 クリーク 頂点被覆 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] 支配集合 特殊 数分割 動的計画法的な見方も可能

支配集合の列挙 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 4 5 6 頂点が支配されているなら1 支配されていないなら0 と すればよい mate[i] 0 1 0 v3 v9 v6

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

辺変数型 パス型 森型 頂点変数型 グラフ ハイパー グラフ フラグ型 クリーク 頂点被覆 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] 支配集合 特殊 数分割 動的計画法的な見方も可能

適用事例：配電網のスイッチ構成 配電網 すべての家は ちょうど1つの変電所に つながっている必要がある サイクルが生じてはいけない 変電所を根とする 根付き全域森 ∩ 根付き森 ZDD 電気制約 ZDD 条件を満たす ZDD 引用： http://www.jst.go.jp/pr/announce/20120223/index.html

適用事例：配電網のスイッチ構成 配電網 468個のスイッチ 制約条件を満たす解の個数は 通り （＝ 約1063） 2136820138348532911682612214804905609 817839244385235398189521540 通り （＝ 約1063） 約1時間15分　 ZDDノード数 約110万個 (779MB) すべての家は ちょうど1つの変電所に つながっている必要がある サイクルが生じてはいけない 変電所を根とする 根付き全域森 ∩ 根付き森 ZDD 電気制約 ZDD 条件を満たす ZDD 引用： http://www.jst.go.jp/pr/announce/20120223/index.html

まとめ パスの数え上げアルゴリズム ZDD について詳細 様々な対象を表現するZDDを高速に構築する手法 「フロンティア法」 アルゴリズム 　 「フロンティア法」 アルゴリズム ハミルトンパス 複数終端対パス 全域木 マッチング 適用事例 フロンティア法のソースコード http://www-erato.ist.hokudai.ac.jp/~jkawahara/frontier