アルゴリズム

超高速グラフ列挙アルゴリズム-〈フカシギの数え方〉が拓く,組合せ問題への新アプローチ-

湊離散構造処理系プロジェクト

森北出版

第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 演算子・関数一覧

索引