超高速グラフ列挙アルゴリズム
超高速グラフ列挙アルゴリズム－〈フカシギの数え方〉が拓く，組合せ問題への新アプローチ－
森北出版
著者：ERATO 湊離散構造処理系プロジェクト
編集：湊真一
編集まえがき
目次
第1部 導入と準備
1.「フカシギの数え方」とグラフ列挙アルゴリズム
2.準備―グラフに関する基礎知識
2.1 グラフ
グラフとは
さまざまなタイプのグラフ
2.2 グラフの列挙
列挙問題とは
部分グラフの列挙
列挙法
3.ZDD：「組合せ集合」を表すデータ構造
3.1 ZDD(ゼロサプレス型二分決定グラフ)
3.2 ZDDの生成方法
3.3 ZDDによる列挙と索引化
第2部 グラフ列挙アルゴリズムとその応用
4.ZDDを用いたグラフ列挙アルゴリズム
4.1 グラフ列挙
4.2 Graphillionによる部分グラフ列挙
4.3 s-t経路集合を表す ZDDの構築アルゴリズム
4.4 ノードの共有とフロンティア
4.5 さまざまな部分グラフ列挙
4.6 その他のフロンティア法ライブラリ
5.種々のリンクパズルへの応用
5.1 ナンバーリンク
5.2 スリザーリンク
5.3 まとめ
6.電力網解析への応用
6.1 問題の概要
6.2 グラフ問題への対応づけ
6.3 Graphillionを用いた実践
6.4 まとめ
7.鉄道経路探索への応用
7.1 はじめに
7.2 大都市近郊区間とは
7.3 Graphillionを用いた経路探索
データとスクリプト
東京近郊区間路線図における経路探索
全国路線図における経路探索
7.4 実験：さまざまな「最高」を達成する経路を求める
7.5 Ekillion
7.6 まとめ
8.社会のさまざまな問題への応用
8.1 展開図の列挙
8.2 選挙区割りの列挙
8.3 避難所割り当ての列挙
8.4 住宅のフロアプランの列挙
8.5 まとめ
第3部 発展的な話題
9.「おねえさんの問題」の世界記録
9.1 記録への挑戦
9.2 骨格となるアルゴリズム
9.3 辺の省略
9.4 コンパクトな状態コード
9.5 最小完全ハッシュ関数
9.6 表引きによる高速化
9.7 その場でのデータ更新
9.8 共有メモリ並列処理
9.9 モジュラ計算
9.10 まとめ
10.BDD/ZDD―論理と集合に関する演算処理系の技法
10.1 BDD：論理関数の演算処理関係
10.2 BDDとZDD
10.3 入力変数の順序づけ
10.4 計算機内部でのBDD/ZDDのデータ構造
10.5 BDD/ZDDの基本演算とその処理アルゴリズム
11.さらに広がるBDD/ZDDの応用
11.1 ZDDを用いたデータベース解析
頻出アイテム集合マイニング
組合せ頻度表とZDDベクトル表現
組合せ頻度表の代数系
11.2 Sequence BDDを用いた文字列集合の処理
文字列集合の表現
Sequence BDD
トライとSequence BDD
11.3 πDDを用いた順列集合の処理
順列集合の表現
πDDのデータ構造
応用例 – あみだくじの解析
付録A Graphillionマニュアル
A.1 Graphillionインストール
MacOS,Linux
Windows
A.2 GraphSetクラス
GraphSetクラスにおけるグラフの表現
GraphSetオブジェクトの構築
GraphSetオブジェクトの操作
NetworkXとの連携
リファレンス
付録B Ruby版VSOP（ZDDライブラリ）マニュアル
B.1 概要
B.2 インストール
B.3 用語・表記
B.4 使用方法
B.5 Nクイーン問題の解法
B.6 演算子・関数一覧
索引