超高速グラフ列挙アルゴリズム―"フカシギの数え方"が拓く、組合せ問題への新アプローチ POD版 [単行本]

超高速グラフ列挙アルゴリズム―"フカシギの数え方"が拓く、組合せ問題への新アプローチ POD版 の 商品概要

• 目次

  第1部　導入と準備
  1．「フカシギの数え方」とグラフ列挙アルゴリズム
  2．準備―グラフに関する基礎知識
  3．ZDD：「組合せ集合」を表すデータ構造
  
  第2部　グラフ列挙アルゴリズムとその応用
  4．ZDDを用いたグラフ列挙アルゴリズム
  5．種々のリンクパズルへの応用
  6．電力網解析への応用
  7．鉄道経路探索への応用
  8．社会のさまざまな問題への応用
  
  第3部　発展的な話題
  9．「おねえさんの問題」の世界記録
  10．BDD/ZDD―論理と集合に関する演算処理系の技法
  11．さらに広がるBDD/ZDDの応用
  
  付録A Graphillionマニュアル
  付録B Ruby版VSOP（ZDDライブラリ）マニュアル

• 出版社からのコメント

  超高速なグラフの列挙を可能にするアルゴリズムの原理と応用．

• 内容紹介

  （初版2015年4月10日刊行）
  ～組合せ爆発にアルゴリズムで挑む！～
  出来ることなら，すべての解が欲しい．でも，爆発的に増える組合せには手が出せない……．そんな常識を覆す，新アルゴリズムが登場．今すぐ使えるPythonライブラリで，「列挙による問題解決」を体感しよう！
  
  ◆「超高速グラフ列挙アルゴリズム」とは？
  鉄道の乗換案内，カーナビ，配電網などインフラのネットワーク設計，大規模システムの故障解析，災害時の避難所の割り当てなどにおいて，共通して登場する「グラフ列挙問題」を高速で解くためのアルゴリズムです．組合せ集合を効率よく表現するためのデータ構造であるZDD（Zero-suppressed Binary Decision Diagram)を使うことで，従来とは比較にならないほど速い列挙が実現．望ましい性質をもつグラフを検索するなどの解析が可能となります．
  
  ◆ZDD初の解説書
  本書は，ZDDを開発した研究グループによる初めての解説書です．組合せ爆発の困難をわかりやすく表す「おねえさん問題」を切り口にZDDの威力を説明した後，パズル解き・配電網設計・鉄道の経路探索・選挙区割りのなどの事例を挙げて，それらがいかにスピーディーに解けるかを紹介します．さらに，文字列集合や順序集合などを用いた高度なデータマイニングへの応用についても解説します．
  
  ◆公開ライブラリで今すぐ実践！
  自由にダウンロード可能なPythonライブラリ“Graphillion”を使えば，本書で紹介する手法がすぐに体験できます．
  
  ★人気のWeb動画「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」の研究チームによる，初の解説書です．

• 著者紹介（「BOOK著者紹介情報」より）（本データはこの書籍が刊行された当時に掲載されていたものです）

  湊 真一(ミナト シンイチ)
  北海道大学大学院情報科学研究科教授。１９８８年、京都大学工学部情報工学科卒業。博士（工学）。ＮＴＴ研究所研究員、スタンフォード大学客員研究員などを経て、２０１０年より現職。２００９年～２０１５年、科学技術振興機構（ＪＳＴ）ＥＲＡＴＯ湊離散構造処理系プロジェクト研究総括を兼務。大規模離散構造データの表現と演算処理アルゴリズムの研究教育に従事。著書に“Ｂｉｎａｒｙ　Ｄｅｃｉｓｉｏｎ　Ｄｉａｇｒａｍｓ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ　ｆｏｒ　ＶＬＳＩ　ＣＡＤ”（Ｋｌｉｗｅｒ，１９９５年）など

• 著者について

  湊真一 (ミナト シンイチ)
  京都大学教授 博（工）

超高速グラフ列挙アルゴリズム―"フカシギの数え方"が拓く、組合せ問題への新アプローチ POD版 の商品スペック