ZDD
を用いたグラフ列挙索引化における
頂点インデックスの追加
Adding the Vertex Indices
for Enumerating and Indexing the Graphs via ZDD
鈴木 浩史
1∗湊 真一
1Hirofumi Suzuki
1Shin-ichi Minato
11
北海道大学 大学院情報科学研究科
1
Graduate School of Information Science and Technology, Hokkaido University
Abstract: Enumerating all the subgraphs of a graph satisfying given constraints is one of the most fundamental problems in combinatorics and graph theory. Frontier-based search is known as a method of enumerating and indexing all the subgraphs satisfying several constraints. Operating the index constructed by the frontier-based search, we can extract the subgraphs with several conditions in the edges of the graph. On the other hand, it is difficult to extract with several conditions in the vertices of the graph. We propose the method for adding the vertex indices for the frontier-based search and resolve the problem. Via the theoretical analysis and the computational experiments, we investigate the difference of the performance between the frontier-based search and the our method.
1
はじめに
与えられたグラフから指定された制約条件を満たす ような部分グラフをすべて列挙することを，部分グラ フ列挙と呼ぶ. 列挙とは，考えうる選択肢をすべて掲示 することであり，状況に応じた適切な判断に繋がるた め，移動経路の選択や配電網の設計など実問題との関 連が深い. これまで，バックトラック法や逆探索法 [2] などの手法により，パスやサイクル，木などの様々な 条件に対して列挙アルゴリズムが考案されている. 本 研究では，ZDD (ゼロサプレス型二分決定グラフ) と 呼ばれるデータ構造を用いて膨大な数の解を圧縮して 列挙する手法である，フロンティア法 [5] に着目する. ZDD は，組合せ集合を圧縮保持する索引データ構造 であり，検索や絞り込みを索引のサイズに依存した計 算時間で処理できる. 部分グラフを元のグラフにおけ る辺や頂点の組合せと見做せば，列挙された部分グラ フの集合を ZDD で圧縮保持できる. フロンティア法 では，部分グラフを辺の組合せと見做して列挙を行い， 列挙結果の ZDD を構築する. このため，フロンティア 法が出力する ZDD では，辺で条件付けられた検索や絞 り込みが容易に実現できる. フロンティア法の応用は 多岐に渡り，パズルの求解 [7] やフロアプラン [1]，電 ∗連絡先： 北海道大学 大学院情報科学研究科 〒 060-0814 札幌市北区北 14 条西 9 丁目 E-mail: [email protected] 力網のロス最小化 [3] などに用いられている. 一方で，部分グラフを辺の組合せと見做すことは，頂 点で条件付けられた検索や絞り込みにおいて，ZDD の 処理性能を制限してしまう. 例えば，指定された頂点部 分集合をカバーするような部分グラフの抽出や，頂点 の重みを考慮した最適解探索などの実現が難しくなる. そこで我々は，フロンティア法に頂点インデックス を導入することで，部分グラフを辺と頂点の組合せと 見做して列挙を行い，列挙結果の ZDD を構築する手法 を提案する. これにより，頂点で条件付けられた検索 や絞り込みも容易に可能な ZDD を得られる. しかし， 提案手法が構築する ZDD は，フロンティア法が構築す る ZDD よりもサイズが大きくなるため，ZDD の構築， 検索や絞り込みの処理速度が遅くなりやすいと考えら れる. そこで，理論解析を行い ZDD のサイズに上界を 与える. また，実験的に上界よりも十分に小さな ZDD を得られる事例が存在することを示す. 本稿は次のように構成される. 2 章では，準備として 部分グラフ列挙とフロンティア法について述べる. 3 章 では，提案手法により解決しようとする課題を述べた 後で，提案アルゴリズムを説明し，理論解析を行う. 4 章では，実験結果を示す. 5 章で，本稿をまとめる. 人工知能学会研究会資料 SIG-FPAI-504-082
準備
2.1
部分グラフ列挙
頂点集合 V と辺集合 E ⊆ {{u, v}|u ∈ V, v ∈ V } か らなる組をグラフと呼び G = (V, E) と表記する．G の 部分グラフとは，頂点部分集合 V′ ⊆ V と辺部分集合 E′⊆ E からなるグラフ G′= (V′, E′) である．G′が G の部分グラフであることを G′⊆ G と表記する. グラフ H = (V, E) に対して，V [H] = V, E[H] = E とする. グラフ G と構造の制約に対して，制約を満たす G の 部分グラフとして考えうるものすべてを出力すること を、部分グラフ列挙と言う．制約としては，s-t パス， 木，クリークなどの具体的な構造をはじめ，辺の本数 や次数，連結成分の数などを制限する制約もある.2.2
ZDD
二分決定グラフ (Zero-suppressed Binary Deci-sion Diagram : ZDD) [6] は，出次数が 2 の非巡回 有向グラフであり，組合せ集合の完全二分木による表 現を圧縮したデータ構造である．完全二分木において， 内部節点のラベルとして組合せに出現しうるアイテム を持たせ，子節点へ伸びる 2 つの枝にアイテムの取捨 選択を対応付けると，根から葉への各パスはそれぞれ 異なる組合せに対応する．さらに，葉節点に論理値を 割当てることで，葉にたどり着いたパスに対応する組 合せが存在するか否かを表すと，組合せ集合を表現で きる．特に，アイテムの順序が決まっていればその表 現は一意となる．完全二分木の内部節点から張られる 枝を，取捨選択の割り当てに対応付けて 1-枝/0-枝と呼 び，葉節点を 1-終端/0-終端と呼ぶ． 完全二分木から ZDD を構築するためには，以下の 2 つの簡約化規則を可能な限り適用し続ければ良い． • 共有規則：ラベルおよび子節点が等しい 2 つの節 点をまとめる． • 削除規則：1-枝が 0-終端に接続する節点を削除 する． これらの簡約化規則により，ZDD は組合せ集合の一意 かつコンパクトな表現となり，これ以上簡約化規則を 適用できない形を，既約な ZDD と呼ぶ． ZDD は組合せ集合を圧縮して保持するだけでなく， 効率的な処理基盤を備えている．例えば，和集合・積集 合などの基本的な集合演算や，要素の検索の他，保持 する組合せの総数を数え上げたり，アイテムの重み総 和が最適となる組合せを求める操作などを行える．こ れらの処理は，多くの場合で ZDD の節点数に依存し た計算時間で実現され，ZDD がコンパクトであれば効 率的に動作する． x1 0 x2 x3 1 0 x3 0 0 x2 x3 1 0 x3 1 x1 x2 1 0 x3 a 0 b c 1 1 c 1 0 b c 1 0 c 0 a 0 b c 1 c x x x x x 共有 x 削除 x 削除 0 図 1: 組合せ集合{{a, c}, {b}, {b, c}, {c}} を表す完全二 分木とそれを圧縮してできた ZDD
2.3
フロンティア法による ZDD 構築
フロンティア法 (Frontier Based Search : FBS， 以 降 FBS と呼ぶ) [5] では，グラフ G = (V, E) と制約に対 して，G′⊆ G のうち制約を満たすものすべてを表現す る ZDD を構築する．このとき，部分グラフは辺をアイ テムとする組合せ E[G′]⊆ E で表現され，孤立点は無 視される. FBS は，辺に順序 (e1< e2<· · · < e|E|) が あるとして，辺 e1から順に使う (1-枝をたどる) また は使わない (0-枝をたどる) というニ分岐をすることで グラフ探索を行いつつ，処理した辺をラベルとして持 つ ZDD の節点を生成する．この際，等価な節点および 不要な節点の判定により, 節点の共有や枝刈りを行う. 2.3.1 フロンティアと mate 配列 i = 1, . . . , m に対して，Fi =∪ij=1ej∩ ∪mj=i+1ejを 定義し，これを i 番目のフロンティアと呼ぶ．これは， 探索過程における処理済み辺と未処理辺の境界である. フロンティアに着目することで，図 2 のような等価な 探索過程や，図 3 のような不要な探索過程を捉え，節 点の共有と枝刈りが可能となる. u x w v e1 e2 e3 e4 e3 e5 フロンティア: {} u x w v e1 e2 e3 e4 e3 e5 フロンティア: {u,v} u x w v e1 e2 e3 e4 e3 e5 フロンティア: {v,w} u x w v e1 e2 e3 e4 e3 e5 フロンティア: {v,w} u v w x s t u v w x s t u v w x s t u v w x s t p u v w x s t p 図 2: s-u パスと v-x パスおよび中間点 w からなる等価 な構造を持つ二つの探索過程 等価な節点および枝刈り判定のため，ZDD の各節点 にフロンティアに着目した構造を表現する配列を記憶す る．これは，mate 配列と呼ばれる. 2 つの節点の mate 配列が等価ならば，そられの節点は等価であると判定 できる．mate 配列は制約に応じて設計され，s-t パス
u x w v e1 e2 e3 e4 e3 e5 フロンティア: {} u x w v e1 e2 e3 e4 e3 e5 フロンティア: {u,v} u x w v e1 e2 e3 e4 e3 e5 フロンティア: {v,w} u x w v e1 e2 e3 e4 e3 e5 フロンティア: {v,w} u v w x s t u v w x s t u v w x s t u v w x s t p u v w x s t p 図 3: フロンティア外の頂点 p の存在により s-t パスを 構成不可能な構造を持つ探索過程 に対する mate 配列は式 (1) のように定義される [5]． mate[v] = 0 (v がパスの中間点である) u (v− u パスがある) v (v を含むパスがない) (1) 2.3.2 アルゴリズム ラベル eiを持つ ZDD の節点集合を Ni，終端節点の みからなる集合を N|E|+1と記述する．ZDD の構築は N1から開始し，N1, N2, . . . , N|E|と幅優先的に行う． まず，ZDD の根 r を生成し空の mate 配列を記憶させ N1← {r} とする．Niを構築した後は，各節点 n∈ Ni から x-枝 (x∈ {0, 1}) をたどった先にラベル ei+1を持 つ節点 nxを生成し，Ni+1 ← Ni+1∪ {nx} とする．た だし，N|E|の各節点に対しては nxが 0-終端/1-終端と なるようにする．n の mate 配列に対して eiに関する更 新を行い nxに記憶する．このとき，更新前の mate 配 列には∀v ∈ Fi\ Fi−1の項目を追加し，更新後の mate 配列からは∀v ∈ Fi\ Fi+1の項目を削除する．その後， 等価な mate 配列を持つ節点 n′′∈ Ni+1が存在するか を判定し，存在しないならば Ni+1 ← Ni+1∪ {n′} と し，存在するならば n′← n′′とする． FBS の擬似コードを Algorithm 1 に示す．mate 配 列を更新し新しい節点を生成する処理を関数 GetNode としているが，これは制約に応じた設計を行う．本稿 では，mate 配列の更新処理については割愛する.
3
頂点インデックスの導入
3.1
解決しようとする課題
フロンティア法で得られた ZDD では，辺で条件付け られた検索や絞り込み，辺の重み総和が最大 (最小) な 部分グラフの抽出が容易にできる. 一方で，頂点で条 件付けられた処理は容易にできるとは限らない. すな わち，部分グラフを辺のみの組合せとして表現するこ とが，部分グラフに対する ZDD の処理性能を制限し ていると言える．ここでは，その実例を二つ述べる.Algorithm 1Frontier Based Search
1: N1← {r} 2: Ni← ϕ for i = 2, . . . , |E| + 1 3: for i = 1 to|E| do 4: for each n∈ Nido 5: if nが0-終端でも1-終端でもないthen 6: n.mateに∀v ∈ Fi\ Fi−1の項目を追加 7: for each x∈ {0, 1} do 8: nx← GetNode(n.mate, ei, x) 9: nx.mateから∀v ∈ Fi\ Fi+1の項目を削除 10: if ∃n′ ∈ Ni+1, nx.mate = n ′ .mate then 11: nx← n ′ 12: else 13: Ni+1← Ni+1∪ {nx} 14: end if 15: nのx-枝の先にnxを接続する 16: end for 17: end if 18: end for 19: end for 1 つ目の例として，指定された頂点集合 S をカバー する部分グラフを取り出す操作を取り上げる. これは Steiner Tree 問題に出現する代表的な条件を用いた絞 り込みである. しかし，残念ながら辺の組合せを保持 する ZDD では，そのような操作を効率的に処理する 演算は存在しない (詳細は省略する) .
もうひとつの例として，Prize Collecting Steiner Tree 問題 (PCST) [4] を取り上げる. PCST は，辺および 頂点に重みのあるグラフ G = (V, E, c, p), c : E → R≥0, p : V → R≥0が与えられたとき，連結な部分グ ラフ T = (V′, E′), E′ ⊆ E の中で，式 (2) を最大化す る部分グラフを見つける問題である. prof it(T ) = ∑ v∈V′ p(v)− ∑ e∈E′ c(e) (2) この問題は Steiner Tree 問題の一般化として知られて おり，回路設計やネットワークデザインに応用を持つ， NP 困難な問題である. PCST の解候補は木となることが知られているため， フロンティア法を用いてすべての木を列挙すれば，結 果の ZDD から容易に解を得られるように思える. しか しながら，式 (2) を見ればわかるとおり，この問題で は頂点の重みの総和と辺の重みの総和によって全体の 重みが定まる. フロンティア法の出力 ZDD では辺の組 合せ集合を扱うため，頂点の重みを考慮した最適化は 容易にはできない (詳細は省略する) . 従って，フロン ティア法を用いて PCST を解くことは難しい.
3.2
提案手法とその性質
部分グラフを辺の組合せで表現することにより，ZDD の処理性能が制限されてしまうことを述べた．この制 限を取り払うために，FBS の出力 ZDD に頂点のラベルを持つ節点 (頂点インデックス) を追加し，部分グラ フ G′ ⊆ G を辺と頂点の組合せ E[G′]∪ V [G′]⊆ E ∪ V で表現する ZDD を構築することを考える．このよう な ZDD では，3.1 章に示した実例も容易に処理できる． 我々は，FBS に基づき頂点インデックスを持つ ZDD を構築するアルゴリズムを与える．このアルゴリズム が構築する ZDD は，FBS が構築する ZDD よりも大き くなる. そこで，理論解析によりその差異を示す. 3.2.1 辺と頂点の順序付け E∪ V の各要素をラベルとする ZDD を構築するた め，辺と頂点の間に順序関係を定める必要がある．今， 辺に関する順序関係 e1 < e2 <· · · < e|E|が定められ ているとする．また，V ={v1, v2, . . . , v|V |} のように 各頂点が番号付けられているとする．このとき，辺と 頂点の順序関係を次のように定める． 各頂点 v について，v∈ Fi\Fi+1となる i がただひと つだけ存在する．このことに基き ei< v < ei+1とする． 二つの頂点 vj, vk (j < k) について，ei < vj < ei+1 かつ ei < vk< ei+1である場合は ei < vj< vk < ei+1 とする．これにより，順序関係は一意に定まる． 3.2.2 FBS に基づくアルゴリズム I = E∪ V とし，辺と頂点に順序関係が定まってい るとき，j 番目にあたる辺または頂点を表すアイテムを Ijと記述する．Ijをラベルに持つ ZDD の節点集合を Nj′，終端節点のみからなる集合を N|I|+1′ と記述する． ZDD の構築は N1′, N2′, . . . , N|I|+1′ と幅優先的に行う． まず，ZDD の根 r を生成し空の mate 配列を記憶さ せ N′ 1← {r} とする．Nj′を構築した後について二つの 場合を考える． (i) Ij= eiである場合は，FBS と同様 に各節点 n′∈ N′ jについて x-枝をたどった先のラベル Ij+1を持つ節点 n′xの生成と，節点の共有判定をおこな い Nj+1′ を構築していく．ここで，mate 配列の更新の 際，∀v ∈ Fi\ Fi−1の項目を追加する．ただし，mate 配列の更新後に∀v ∈ Fi\ Fi+1の項目を削除する操作 は行わない． (ii) Ij= v である場合は，各節点 n′∈ Nj′ について v に関する分岐を考えることになるが，これ は n′.mate の表す構造が v を含むか否かを判定すれば 良い．v が含まれるならば，1-枝の先に節点 n′′を生成 し n′′.mate← n′.mate，N′ j+1← Nj+1′ ∪ {n′′} とし，0-枝の先に 0-終端を接続する．このとき，n′′.mate から v の項目を削除する．また，mate の一致による節点の 共有も行う．v が含まれないならば，各枝に対する操 作を逆にすればよい．v が n′.mate の表す構造に含ま れるか否かは，mate 配列を用いて容易に判定できる． 例えば、s-t パスを列挙する場合，mate 配列の定義か ら mate[v]̸= v である頂点は必ずパスに含まれる．既 存の種々の mate 配列では，いずれについても同様の 判定を行うことができる． 今後，提案アルゴリズムを EXT-FBS と呼ぶ．EXT-FBS の擬似コードを Algorithm 2 に示す．GetNode 関 数は，従来の設計を用いてよい．
Algorithm 2Extension Frontier Based Search
1: N1′ ← {r} 2: Ni′← ϕ for i = 2, . . . , |I| + 1 3: for j = 1 to|I| + 1 do 4: for each n′∈ Nj′ do 5: if n′が0-終端でも1-終端でもないthen 6: if Ij= eithen 7: n′.mateに∀v ∈ Fi\ Fi−1の項目を追加 8: for each x∈ {0, 1} do 9: n′x← GetNode(n′.mate, ei, x)
10: if ∃n′′ ∈ Ni+1′ , n′x.mate = n′′.mate then 11: n′x← n′′ 12: else 13: Nj+1′ ← Nj+1′ ∪ {n′x} 14: end if 15: n′のx-枝の先にn′xを接続する 16: end for 17: end if 18: if Ij= v then 19: x← n.mateの表す構造にvが含まれるなら ば1そうでなければ0 20: n′x← n′ 21: n′x.mateからvの項目を削除する
22: if ∃n′′∈ Ni+1′ , n′x.mate = n′′.mate then
23: n′x← n′′ 24: else 25: Nj+1′ ← Nj+1′ ∪ {n′x} 26: end if 27: n′のx-枝の先にn′xを接続する 28: n′の(1− x)-枝の先に0-終端を接続する 29: end if 30: end if 31: end for 32: end for 3.2.3 出力 ZDD の節点数 FBS の出力 ZDD の節点数を元に，EXT-FBS の出力 ZDD の節点数について議論する．ここで，ZDD Z の 終端を除く節点数を N (Z)，mate 配列に格納されうる 値の種類数を d，フロンティアに含まれる頂点の最大数 を fmax= maxi|Fi| とする．まず，FBS について，各 ラベルにおける節点数はそれぞれ出現しうる mate 配列 の数 dfmaxで抑えられる．よって，FBS の出力 ZDD Z について，以下の定理 1 が成り立つ [5]． 定理 1. N (Z)≤ |E|dfmaxである． これに対し，EXT-FBS の出力 ZDD を Z′とすると， 以下の定理が成り立つ．
定理 2. N (Z′)≤ (|E| + 2|V |)dfmaxである. 証明 EXT-FBS の動作から，辺をラベルに持つ節 点の数は FBS と変わらない. そこで，頂点をラベルと して持つ節点の数について考える. ei < v < ei+1であるとき，eiをラベルに持つ節点の 子として v をラベルに持つ節点が，最大で 2 個生成さ れる. v < w < ei+1であるとき，v をラベルに持つ節 点の子として w をラベルに持つ節点が生成される. v をラベルに持つ節点から伸びる枝の一方は必ず 0-終端 に接続されるから，w をラベルに持つ節点の数は v を ラベルに持つ節点の数以下である. よって，頂点をラ ベルに持つ節点の数は 2|V |dfmax以下となる.
以上から，N (Z′)≤ |E|dfmax+ 2|V |dfmax = (|E| + 2|V |)dfmaxである. 出力 ZDD を既約にした場合については，ZDD Z を 既約にした ZDD を ¯Z とすると，以下の定理が成り立つ. 定理 3. N ( ¯Z′)≤ (2fmax+ 3)2fmaxN ( ¯Z) である. 証明 Z を基に ¯¯ Z′と等価な ZDD Z を構築する過 程から導出する. ZDD Z において eiをラベルとして 持つ節点集合を Zi と記述する. 根を始点とする任意 のパス p に対し，p により表される部分グラフを G(p) と書く. 根から節点 n へのパスの集合を Pn として， G(n) = {G(p) | p ∈ Pn} とする. はじめに，Z ← ¯Z と し，以下の (i)，(ii) の操作を行う. (i) 今，1 つの頂点 v に着目すると，v ∈ Fi\ Fi−1 である i と v ∈ Fj \ Fj+1 である j が一意に定まる. k = i + 1, . . . , j の順に次の操作を行う. ∀n ∈ Zkにつ いて Pnを考える. ∃G0, G1 ∈ G(n), v /∈ V [G0], v ∈ V [G1] のとき，n と等価な二節点 n0, n1を生成しZk ← Zk∪ {n0, n1} \ {n} とする. このとき，G0= G(p0) で ある p0∈ Pnの終点を n0，G1= G(p1) である p1∈ Pn の終点を n1とする. この操作の後も，Z は ¯Z と等価 である. これを，各頂点に対して行うと，∀n ∈ Zi(i = 1, . . . ,|E|) について，v ∈ Fiに対して∀G′∈ G(n), v ∈ V [G′] または∀G′∈ G(n), v /∈ V [G′] が成り立つ. (ii) 今，Z の 1 つの節点 n に着目する. n のラベル を ei，n の x-枝側の子を nxとして，次の操作を行う. Fi = {v | v ∈ Fi, ∀G′ ∈ G(n), v ∈ V [G′]} とする. ∀v ∈ Fiに対してそのラベルを持つ節点を生成し， ¯Z′ 上の順序関係に従って 1-枝で連結したパスを構成する. その始点を n の 0-枝に接続し，終点から n0へ 1-枝を 伸ばす. Fi∪ eiでも同様にパスを構成し，始点を n の 1-枝に接続し，終点から n1へ 1-枝を伸ばす. このとき， 構成したパスの各節点の 0-枝には 0-終端を接続する. (i)，(ii) の結果，(a)Z の根から 1-終端へのすべての パス p は，v をラベルに持つ節点を v ∈ V [G(p)] なら ば通り，v /∈ V [G(p)] ならば通らない. このため，p は E′ = E[G(p)], V′ =∪e∈E′e として V′∪ E′を表現す る. (b) ¯Z′が V′∪ E′を持つならば ¯Z は必ず E′を持 ち，これは ¯Z′をZ に置き換えても成り立つ. (c) Z 上 の順序関係は ¯Z′上の順序関係と等しい. (a)，(b)，(c) より，Z は ¯Z′に等価である. (i) において，Z の各節点 n に対し，n と等価な二つ の節点 n0, n1に置き換える操作は，ラベル eiに対して 高々|Fi| 回である. よって，Z における辺をラベルに持 つ節点の数は高々2fmaxN ( ¯Z) 個となる. Z で頂点をラベルに持つ節点の数は，辺をラベルに 持つ各節点につきラベル eiとして高々|Fi| + |Fi∪ ei| 個存在するから，全体で高々(2fmax+ 2)2fmaxN ( ¯Z) 個 である. 以上から，N ( ¯Z′) ≤ 2fmaxN ( ¯Z) + (2f max+ 2)2fmaxN ( ¯Z) = (2f max+ 3)2fmaxN ( ¯Z) が示された. FBS の計算量は出力 ZDD の節点数に依存すること が知られており，定理 1 と定理 2 から，EXT-FBS は FBS と遜色ない計算効率であると推測できる. また，定 理 3 から，EXT-FBS の出力 ZDD を既約にした ZDD 節点数は，FBS の出力 ZDD に比べて，fmaxに対して 指数的に大きくなる可能性が示唆された. 次章で，ZDD サイズに関する実験により，EXT-FBS が FBS と遜色 ない計算効率であるという推測が実験的に正しいこと と，既約にした ZDD は定理 3 に示した上界よりも十 分に小さくなる事例が存在することを示す.
4
実験と考察
FBS と EXT-FBS の出力 ZDD と既約にした ZDD の 実際の節点数を調査する．列挙の制約には，s-t パス， 木，森の 3 つの構造を用いた．それぞれに対して，格 子グラフ (8× 8, 9 × 9, 10 × 10 の 3 種)，日本の都道 府県隣接関係グラフ (JP， 47 頂点 104 辺)，アメリカ の州隣接関係グラフ (US， 48 頂点 103 辺)，完全グラ フ (K8, K9, K10の 3 種) のグラフデータを用いた．辺 の順序付けには，グラフを幅優先探索でたどったとき の辺の通過順序を用いた．fmaxの値は，n× n の格子 グラフで n，JP で 8，US で 9，Knで n− 1 である. まず，出力 ZDD の節点数について，実験結果を表 1 に示す．すべてのグラフデータに対して，EXT-FBS は FBS に対して 2 倍未満の差しか出なかった．これは， EXT-FBS が FBS と比べて遜色ない計算効率で動作す ることを裏付けている． 次に，出力 ZDD それぞれを既約にした場合の節点数 について，実験結果を表 2 に示す．EXT-FBS は FBS に比べてすべてのグラフデータで，s-t パスに対しては 2 倍前後の差，木に対しては 2 倍未満の差であり，十 分にコンパクトであると言える．一方で，森に対して は多くのグラフデータで 5 倍以上の差がついた．特に， 格子グラフに対しては，グラフサイズが大きくなるにつれてその差が広がっている．これは，fmaxの増加に よるものと考えられる. この結果から，グラフの構造 によっては, 頂点インデックスを導入しても大きな影響 がない事例もあることが示された. 表 1: 出力 ZDD の節点数 構造 グラフ 節点数 FBS EXT-FBS 倍率 8× 8 132954 212892 1.60 9× 9 549905 877182 1.60 10× 10 2248587 3576356 1.59 JP 12345 17285 1.40 s-tパス US 23459 34703 1.48 K8 1706 2054 1.20 K9 5572 6458 1.16 K10 17904 20210 1.13 8× 8 696177 1313672 1.89 9× 9 4123169 7722761 1.87 10× 10 24822123 46199496 1.86 JP 57710 91387 1.58 木 US 101930 178051 1.75 K8 7411 9779 1.32 K9 31207 39837 1.28 K10 135403 168411 1.24 8× 8 873778 1592386 1.82 9× 9 5305534 9567236 1.80 10× 10 32631735 58327992 1.79 JP 63872 101451 1.59 森 US 123397 209594 1.70 K8 7807 10333 1.32 K9 32941 42113 1.28 K10 142872 177802 1.24
5
おわりに
本稿では，FBS による部分グラフ列挙の問題点とし て，特に頂点で条件付けられた検索や絞り込みに対す る処理性能が制限されてしまうことに言及し，これを 解決するために，頂点インデックスを導入し FBS を改 良した EXT-FBS を提案した. また理論解析と実験に より，EXT-FBS の計算効率が FBS と比べて遜色無い ことや，EXT-FBS が生成する ZDD が十分コンパクト になる事例があることを示した. 今後の課題は，Steiner Tree 問題やその派生問題を はじめとする実問題への適用や，頂点インデックスの 導入により可能となる，ZDD を用いた新たな部分グラ フ操作を考案することが考えられる. 本研究の一部は JSPS 科研費基盤 (S) 15H05711 の助 成による．参考文献
[1] Naoki Katoh Atsushi Takizawa, Yushi Miyata. Enu-meration of floor plans based on zero-suppressed
bi-表 2: 既約にした ZDD の節点数 構造 グラフ 節点数 FBS EXT-FBS 倍率 8× 8 57442 129536 2.26 9× 9 238656 537492 2.25 10× 10 980772 2204934 2.25 JP 2389 4957 2.07 s-tパス US 6665 14655 2.20 K8 577 816 1.41 K9 1812 2373 1.31 K10 5634 6985 1.24 8× 8 351603 556706 1.58 9× 9 1726107 2723412 1.58 10× 10 8454881 13304547 1.57 JP 30028 42218 1.41 木 US 59413 89805 1.51 K8 4077 4832 1.19 K9 15537 17879 1.15 K10 61294 69015 1.13 8× 8 43788 558679 12.76 9× 9 171540 2731283 15.92 10× 10 670824 13336886 19.88 JP 8432 46477 5.51 森 US 14706 94024 6.39 K8 2247 4845 2.16 K9 8525 17913 2.10 K10 33549 69106 2.06
nary decision diagram. In Proceedings of the 19th
In-ternational Conference on Computer-Aided Architec-tural Design Research in Asia (CAADRIA 2014), pp.
275–284, 2014.
[2] David Avis and Komei Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, Vol. 65, pp. 21–46, 1993.
[3] Takeru Inoue, Keiji Takano, Takayuki Watanabe, Jun Kawahara, Ryo Yoshinaka, Akihiro Kishimoto, Koji Tsuda, Shin ichi Minato, and Yasuhiro Hayashi. Loss minimization of power distribution networks with guaranteed error bound. IEEE Transactions on Smart
Grid, Vol. 5, pp. 102–111, January 2014.
[4] David S. Johnson, Maria Minkoff, and Steven Phillips. The prize collecting steiner tree problem: Theory and practice. In Proceedings of the Eleventh Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA ’00,
pp. 760–769, Philadelphia, PA, USA, 2000. Society for Industrial and Applied Mathematics.
[5] Jun Kawahara, Takeru Inoue, Hiroaki Iwashita, and Shin-ichi Minato. Frontier-based search for enumerating all constrained subgraphs with compressed representation. https://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/
tcstr 14 76/tcstr 14 76.pdf, September 2014.
[6] Shin-ichi Minato. Zero-suppressed BDDs for set ma-nipulation in combinatorial problems. Proc. of 30th
ACM/IEEE Design Automation Conf. (DAC 1993),
pp. 272–277, 1993.
[7] Ryo Yoshinaka, Toshiki Saitoh, Jun Kawahara, Koji Tsuruma, Hiroaki Iwashita, and Shin-ichi Minato. Finding all solutions and instances of numberlink and slitherlink by zdds. Algorithms, Vol. 5, No. 2, p. 176, 2012.
