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

電子版価格
¥3,520
  • 電書あり

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

  • ただいまウェブストアではご注文を受け付けておりません。
  • サイズ A5判/ページ数 177p/高さ 22cm
  • 商品コード 9784627852617
  • NDC分類 007.64
  • Cコード C3004

内容説明

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

目次

第1部 導入と準備(「フカシギの数え方」とグラフ列挙アルゴリズム;準備―グラフに関する基礎知識;ZDD:「組合せ集合」を表すデータ構造)
第2部 グラフ列挙アルゴリズムとその応用(ZDDを用いたグラフ列挙アルゴリズム;種々のリンクパズルへの応用;電力網解析への応用;鉄道経路探索への応用;社会のさまざまな問題への応用)
第3部 発展的な話題(「おねえさんの問題」の世界記録;BDD/ZDD―論理と集合に関する演算処理系の技法;さらに広がるBDD/ZDDの応用)
付録

著者等紹介

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

感想・レビュー

※以下の感想・レビューは、株式会社ブックウォーカーの提供する「読書メーター」によるものです。

しろっこー

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

mft

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

Tsukasa Fukunaga

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

外部のウェブサイトに移動します

よろしければ下記URLをクリックしてください。

https://bookmeter.com/books/9336824
  • ご注意事項