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

湊真一

～組合せ爆発にアルゴリズムで挑む！～
出来ることなら，すべての解が欲しい．でも，爆発的に増える組合せには手が出せない……．
そんな常識を覆す，新アルゴリズムが登場．今すぐ使えるpythonライブラリで，「列挙による問題解決」を体感しよう！

◆「超高速グラフ列挙アルゴリズム」とは？
鉄道の乗換案内，カーナビ，配電網などインフラのネットワーク設計，大規模システムの故障解析，災害時の避難所の割り当てなどにおいて，
共通して登場する「グラフ列挙問題」を高速で解くためのアルゴリズムです．
組合せ集合を効率よく表現するためのデータ構造であるZDD（Zero-suppressed Binary Decision Diagram)を使うことで，
従来とは比較にならないほど速い列挙が実現．望ましい性質をもつグラフを検索するなどの解析が可能となります．

◆ZDD初の解説書
本書は，ZDDを開発した研究グループによる初めての解説書です．
組合せ爆発の困難を分かりやすく表す「おねえさん問題」を切り口にZDDの威力を説明した後，パズル解き・配電網設計・鉄道の経路探索・選挙区割りのなどの事例を挙げて，
それらがいかにスピーディーに解けるかを紹介します．さらに，文字列集合や順序集合などを用いた高度なデータマイニングへの応用についても解説します．

◆公開ライブラリで今すぐ実践！
自由にダウンロード可能なpythonライブラリ“Graphillion”を使えば，本書で紹介する手法がすぐに体験できます．

★人気のWEB動画「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」の研究チームによる，初の解説書です．

内容紹介

組合せ爆発には、アルゴリズムで挑むのだ!出来ることなら、すべての解が欲しい。でも、爆発的に増える組合せには手が出せない…そんな常識をくつがえす、新アルゴリズムが登場!グラフを高速で列挙し、圧縮、索引化する手法とその応用を解説。今すぐ使えるPythonライブラリで、「列挙による問題解決」を体感しよう!

内容（「BOOK」データベースより）

湊真一 ： 北海道大学 教授 博（工）

著者について

湊/真一
北海道大学大学院情報科学研究科教授。1988年、京都大学工学部情報工学科卒業。博士(工学)。NTT研究所研究員、スタンフォード大学客員研究員などを経て、2010年より現職。2009年~2015年、科学技術振興機構(JST)ERATO湊離散構造処理系プロジェクト研究総括を兼務。大規模離散構造データの表現と演算処理アルゴリズムの研究教育に従事(本データはこの書籍が刊行された当時に掲載されていたものです)

著者：ERATO 湊離散構造処理系プロジェクトの検索結果

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