グラフ集合処理ライブラリGraphillion のチュートリアルです.本チュートリアルを通じて,Graphillionを用いたグラフ集合処理の基本を学ぶことができます.
チュートリアル中のコードはすべてGoogle Colaboratory上で動かすことができます.Google Colaboratoryを利用するためにはGoogleアカウントが必要です.
以下のリンクから各コンテンツをGoogle Colaboratoryで開くことができます.
-
グラフ入門: 本チュートリアルを理解するために必要となるグラフ理論の基礎について説明します.グラフとは何か,なぜグラフ理論が有益なのかを簡単に説明します.既にグラフ理論に習熟されている方は次章に進んでください.
-
グラフと組合せ爆発: グラフの問題を解く際,しばしば指数的に存在する部分グラフを扱わなければならない場面がでてきます.この章ではそのような組合せ爆発について解説します.
-
Graphillionに触れてみよう: いよいよGraphillionの説明に入ります.有名な「数え上げお姉さん問題」を題材に,Graphillionを用いたグラフ集合処理の例を紹介します.
-
Graphillionの内部: Graphillionの内部ではZDDとよばれるデータ構造が利用されています.GraphillionはZDDを意識せずとも利用することができますが,Graphillionの挙動を理解するためにはZDDの理解が不可欠です.この章ではGraphillionにおいてZDDが果たす役割について説明します.
-
GraphSet: Graphillionではグラフの集合を表すGraphSetとよばれるオブジェクトを作成し,様々な操作を実行することができます.この章ではGraphSetに対して行える代表的な操作を紹介します.
-
Graphillionによる最適化: Graphillionを用いることで,グラフに関する最適化問題を解くことができます.この章ではGraphillionを用いて最適化問題を解く方法と,Graphillionが得意とする最適化問題の種類について説明します.
-
ネットワーク信頼性の計算: Graphillionの機能を活用することで,ネットワークの故障に対する強さを調べることができます.
-
Graphillion 実践ガイド Graphillionで効率的に問題を解くための指針をいくつか紹介します.