湊真一

人物・団体ページへ

本

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

湊真一

☆
☆
☆
☆
☆
レビューを書く 

基本情報

ジャンル
：
物理・科学・医学
ISBN/カタログNo
：
ISBN 13 : 9784627852617
ISBN 10 : 4627852614
フォーマット
：
本
出版社
：
森北出版
発行年月
：
2015年04月
発売国
：
日本
共著・訳者・掲載人物など
:
科学技術振興機構 ,  
追加情報
:
１７７ｐ；22

内容詳細

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

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

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

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

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

【著者紹介】
湊真一 : 北海道大学大学院情報科学研究科教授。１９８８年、京都大学工学部情報工学科卒業。博士（工学）。ＮＴＴ研究所研究員、スタンフォード大学客員研究員などを経て、２０１０年より現職。２００９年〜２０１５年、科学技術振興機構（ＪＳＴ）ＥＲＡＴＯ湊離散構造処理系プロジェクト研究総括を兼務。大規模離散構造データの表現と演算処理アルゴリズムの研究教育に従事（本データはこの書籍が刊行された当時に掲載されていたものです）

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

ユーザーレビュー

総合評価

☆
☆
☆
☆
☆

0.0

★
★
★
★
★
 
0
★
★
★
★
☆
 
0
★
★
★
☆
☆
 
0
★
★
☆
☆
☆
 
0
★
☆
☆
☆
☆
 
0
レビューを書く

読書メーターレビュー

こちらは読書メーターで書かれたレビューとなります。

powered by

  • しろっこー さん

    読了日：2023/11/13

    組合せ集合を表すデータ構造である二分決定木をDAGに圧縮したZDDと呼ばれるグラフおよびその構築法のフロンティア法に関する解説書である．ZDDを用いた高速なグラフ列挙アルゴリズムの基本的な説明の後，経路，閉路，全域木などへの応用例や関連する話題が解説されている．興味深かったのは9章の「おねえさんの問題」と呼ばれる格子上の経路全列挙問題を解いた際に行った定数倍高速化についての解説である．世界記録に挑戦するために様々な工夫が凝らされている． あとMotzkin数が出てきてテンション上がった．

  • mft さん

    読了日：2015/06/07

    斜め読みになってしまったが、けっこうワクワクする世界。自分でも応用が考えられたら面白そう

  • Tsukasa Fukunaga さん

    読了日：2015/04/30

    数え上げおねえさんとして一躍有名になった、｢経路列挙問題｣に対して、最先端のアルゴリズムではどう取り組んでいるか、という事について記された本。難しい所は適宜省略しながらも重要なポイントをしっかり抑えたわかりやすい解説は、読んでいて非常に面白かったし、実問題へのアプリケーションやライブラリであるgraphillionの使い方なども興味深かった。(私がニコリパズル作成者だったというのもあるが)　本当に最先端の部分や今後の展望についても最後の章でページをしっかり割いて説明しており、非常に良い教科書であると思う。

レビューをもっと見る

(外部サイト)に移動します

人物・団体紹介

人物・団体ページへ

湊真一

北海道大学大学院情報科学研究科教授。１９８８年、京都大学工学部情報工学科卒業。博士（工学）。ＮＴＴ研究所研究員、スタンフォード大学客員研究員などを経て、２０１０年より現職。２００９年〜２０１５年、科学技術振興機構（ＪＳＴ）ＥＲＡＴＯ湊離散構造処理系プロジェクト研究総括を兼務。大規模離散構造データの表

プロフィール詳細へ

物理・科学・医学 に関連する商品情報

おすすめの商品

CD・DVD・レコード・本・ゲームを売るなら
HMV宅配買取