無向グラフのパス列挙
部分グラフ 与えられたグラフの一部分からなるグラフ 与えられたグラフ 経路 ( パス ) や全域木などは部分グラフ 部分グラフの例 部分グラフ列挙 与えられた条件を満たす部分グラフをすべて求める 例 : から までの 同じ頂点を通らない経路は? - 経路 (- パス ) 全域木 5 6 部分グラフ列
... 謝辞 本スライドで使用している図の一部と全適用事例は発売予定の書籍 「超高速グラフ列挙アルゴリズム」（仮題） のドラフト版から引用しています。図の引用は「ZDD書籍から引用」と明示しています。 graphillion ライブラリの作者 井上 武 さん，岩下 洋哲 さん ...
18
疑似頻出アイテム集合の多項式遅延列挙アルゴリズム
... 単調性を持たず、完全に列挙することは簡単でない。そ のため、これらの問題に対するアルゴリズムは、ヒュー リスティックを用いて探索を行う、列挙の完全性を保 証しないものが多い。一方，系列パターンマイニング， 文字列マイニングの分野では，あいまい検索の技術を 用いて，エラーを許したマッチングでパターンの出現 ...
7
ZDDを用いたグラフ列挙索引化における頂点インデックスの追加
... e i < v < e i+1 であるとき，e i をラベルに持つ節点の 子として v をラベルに持つ節点が，最大で 2 個生成さ れる. v < w < e i+1 であるとき，v をラベルに持つ節 点の子として w をラベルに持つ節点が生成される. v をラベルに持つ節点から伸びる枝の一方は必ず 0-終端 に接続されるから，w をラベルに持つ節点の数は ...
6
ZDD によるパスの列挙 (計算機科学とアルゴリズムの数理的基礎とその応用)
... 近年 Knuth は， ZDD (Zero-suppressed Binary ZDD は膨大な集合族を効率よく圧縮できるのみな Decision Diagram) を用いた任意のグラフのある 2 らず，集合データに対する多様な演算もまた効率よ 点間を端点とするパスを列挙するアルゴリズムを提く実行可能であるという特長があり， VLSI 設計や 案した． ZDD ...
7
局所的な次数情報を用いた無向グラフの探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)
... いて. $P(d)\propto d^{-\gamma}$ と書ける. このようなネットワー クはスケールフリーネットワークとも呼ばれる . 筆者 らは以前 , 探索の対象をスケールフリーなグラフに 限定することでグラフの規模が非常に大きい場合で も効率の良い探索を行うアルゴリズム forest search ...
6
量子Bruhatグラフを用いたレベル・ゼロLSパスの表示 (組合せ論的表現論とその周辺)
... $0=\sigma_{0}<\sigma_{1}<\cdots<\sigma_{s}=1$ の組 $\eta=(\underline{x};\underline{a})$ で次の条件を満たすも ののことである : 各 $1\leq u\leq s-1$ について， $x_{u}\neq x_{u+1}$ であり，かつ， ...
10
ヒトゲノムからの有意な散在反復配列の列挙
... k の文 字列) の切り出し，不一致やギャップを考慮しつなぎ合 わせたものを反復配列候補とし，それらをクラスタリ ングすることで類似する反復配列候補をまとめて，そ のクラスタ中心を反復配列とする手法が提案されてい る [3]．この手法では，k 長の切り出しをつなぎ合わせ る際に経験的な知見を利用した手法を使用することや， 発見される反復配列がクラスタリング性能に依存する ...
6
各種の疑似クリーク列挙アルゴリズムの実験的性能比較
... k-plex の列挙器を主として解 の総数の観点から比較し，接続欠損数である ｋ の値 が大となるにつれ，総数において顕著な違いが現れる ことが明らかになった．これは列挙される解のチェック の手間を大幅に軽減させると同時に，探索時のオーバ ヘッドをかけたとしても，ターゲットを絞り込んだピ ...
8
時空間ネットワークを用いたフライトパターンの列挙について
... • 不定期便に対応したパイロット乗務スケジューリング [4] これらの研究の伝統的なアプローチには，集合被覆問題 (Set Covering Problem, SCP) もしくは集合分割問題 (Set Partitioning Problem, SPP) などが一般的である．しか し，これらの解法では最適解を求められなかったり，計算 に時間がかかってしまう場合がある．そこで，スケジュー ...
6
パス トレースの実行
... トレース結果のグラフィカル表示 コントローラは、送信元（ホスト A）と宛先（ホスト B）間のパス上のパス方向、ホストとデバ イス（IP アドレスを含む）をグラフィカル表示します。パス トレースの個々のデバイスをクリッ クすると、[トレース結果のデバイス詳細（Trace Results Device ...
28
4E1-1 オイラー路の高速な列挙索引化アルゴリズム
... 以上で，無向グラフに存在する全てのオイラー路 ( 又は閉 路 ) を列挙索引するアルゴリズムを説明した．この問題は #P- complete であることが知られているので [4] ，最悪の場合は， 本手法でも指数的な時間がかかる．しかし，本論文で示したよ うに， DAG がメモリに納まる範囲で小さく圧縮されるような ...
4
二分タングルグラムの描き方 (列挙問題に対する計算の高速化と可視化)
... $T$ の木間辺は $S$ から $T$ に向かって有 向化する . $T$ の辺は葉から根に向かって有向化する ...$D$ の upward-planarity と $\langle S,$ $T\rangle$ が木間辺の交差なく描けることが同値であること が分かる ...
8
アイテム集合列挙に基づく最適な順序付き決定木の高速発見
... 最近の大規模データからの知識発見では，データから 半自動的に発見されたパターンを複合特徴として用い た機械学習手法がふつうになってきた．例えば，バギン グやブースティング等の集団学習（ensemble learning） では，このような複合特徴として，決定株（decision stump）や，アイテム集合（itemset），系列パターン， ...
8
二分決定グラフを用いた帰納論理プログラミングの解の列挙
... j の命 題変数 x j に対応するノードを ⃝ j と表す. 各内部ノー ドは, 点線と実線でそれぞれ表される 2 つの枝をもち, それぞれ 0–枝 (low-branch), 1–枝 (high-branch) とい ...う. グラフの終端には, f alse を表す終端ノード 0 と, true を表す終端ノード 1 ...
6
グラフ同型に関する代表元のグラフを列挙するZDDの構築について
... では，節点に対応する変数は代表元 グラフにおける辺の有無を表しており，この変数の順 序は辺に対応する頂点番号の組の辞書順により定めて いる．ただし各グラフにおける辺の有無は完全グラフ を基準として考える．これにより，頂点番号の置換に ...
6
フロンティア法による強連結な部分グラフの列挙
... 9 の場合を，グリッ ドグラフは w = h で，それぞれ 2, 4, 6, 8, 10 の場合を 用いた．完全グラフは，各頂点対に双方向の辺を張り， 多重辺と自己ループがないように作成した．グリッド グラフは，偶数行と奇数行，および偶数列と奇数列に あたる辺でそれぞれ向きを変えており，多重辺と自己 ループはない．実験結果を表 2 と表 3 ...
6
グラフ系列からの頻出変化パターンの高速列挙法
... 人間関係ネットワーク，ホームページのネットワーク， 遺伝子ネットワークなどの対象では，我々がそれらの 時間変化を観測する時間分解能が高い．従って，隣接 するグラフ と でその構造が大きく変化する ことはなく，ごく一部の構造が変化すると考える．ま た，データから人にとって有用な知識を発見するデー タマイニングの立場からは，計算機の出力が人にとっ て理解可能であることが[r] ...
8
列挙木とMCMCを組み合わせた部分グラフサンプリングアルゴリズムの構築
... 4 計算機実験 本稿では，真の期待値 E[f |p] と，前節で与えたグラ フを基にしたサンプル近似との間に，どの程度の誤差 があるかを評価するための実験を行った．また，実行時 間の比較も行った．実験に用いた計算機の CPU は Intel Core i7，メモリは 16GB，OS は OS X10.11.5，使用し た言語は C++，コンパイラは ...
6
ZDDを用いた組合せテストケースの列挙索引化に関する実験と考察
... 2 の場合に，テスト 0,3,5,6 を選んだものである．この例において， どの 2 変数の ペアを取り出しても，00,01,10,11 の 4 通りの値の組み 合わせたものが出現している．このようなテスト集合 のことをペアワイズテスト集合と呼ぶ．更に 2 変数で はなく 3 変数の組み合わせを取り出したときに，000, 001, 010, ...
5
SATソルバーを用いたMCS列挙の実装とその評価
... 表 2 より，ほとんどのソフト節が単位節である PMS で，USoft により MCS 総列挙数が倍増しており，この 効果が大きいことが分かる．一方，多くのソフト節が非 単位節である MS では，Inc の効果が現れている．Basic， USoft 共に３∼４割ほど総列挙数が増えている．結果と して，提案手法については，MS に対しては Basic+Inc が，PMS ...
4