この本について
「最短経路の本 レナのふしぎな数学の旅」 は、数学の苦手な高校生レナが、父親からパソコンを贈ってもらったことから始まる。日常生活のさまざまな場面に現れる「最短経路」を題材にとりあげ、その背景にある数学的理論、すなわちグラフ理論の基礎が、複雑な数式の展開なしに物語の中でわかりやすく解説されている。
なお、Googleのエンジニアたちが選ぶプログラミングに関する書籍10冊 の中にノミネートされている。
読書記録
1. 最初のコンタクト P.1
レナの家に届いたパソコンにしゃべるソフトウェア「ベン」がインストールされていた。
2. ルートプランって何? P.8
ルートプランの応用例として、(1)ある地点から別の地点までの最短ルートを求める最短経路問題や、(2)依存関係のある作業工程の順番を決定するプロジェクトプラン問題、などがある。
3. 突然ですが,グラフです P.19
地図は、グラフ(ノードの集合V とエッジの集合E)を使ってモデル化、つまり抽象化できる。
グラフは常に連結しているとは限らない。
フェールセーフなシステム(ネットワーク、携帯電話網、電力供給網、交通網など)は、エッジを一本切断してもまだグラフの連結が保たれる。
エッジに方向があるグラフを有向グラフと呼ぶ。
あるノードとあるノードを繋ぐ有向あるいは無向エッジが複数あるようなグラフを多重グラフと呼ぶ。
あるノードにそのノード自体を繋ぐ有向あるいは無向エッジのことを、ループと呼ぶ。*
4. 重みは重し P.32
エッジは重み付けをすることができる。
特定のアルゴリズムを解くために、重みを負にすることがある。
- (例1) ノードでの滞在時間が発生する場合の最短経路問題 (TODO: 本の例を理解できてない)
- (例2) 全てのエッジの重さに-1をかけることで、最長経路問題を解くことができる。これは閉路(cycle)がないことが前提。
5. 危なくない爆発 P.37
ノードの数の冪乗に比例して計算量が増加する「組み合わせの爆発」が発生しうる。
6. 最短経路をとるか,いなか.それが問題だ! P.43
具体例として路線図を使い、駅Aから駅Bまでの最小の移動数を考えた。
路線図を重みなしグラフとみなし、幅優先探索を利用した。
7. ローカルに決断して,グローバルに最適化 P.49
具体例を用いて、重みが正のグラフにおけるダイクストラ法のアルゴリズムが説明された。
自分の言葉でまとめると、「ノードの最短距離を、始点からの最短距離が小さい順に確定する。任意のステップにおいて、次に最短経路が決まるノードは、既に最短距離が確定したノードと隣接していることが証明できる。」
8. 始めにインプットがあった P.57
ダイクストラ法を数式で紹介された。
用語の説明:
-
distances(s) <- 0の矢印は、代入を表す -
V \ Sは、集合の引き算であり、集合V - 集合S を表す -
v*における*とは、何かの問題における「最良」の解を表す。今回だと、distances(v)が最小となるノードを表す
工夫としては、最短距離となる経路を求めるために、predecessor = {node -> prev_node} を用いて、惨憺経路においてそのノードの一つ前のノードを記録しているところ。ダイクストラ法完了後、これを使って終点ノードから始点ノードまで辿ることができる。shortest_paths = {node -> node[]} にしない理由は、O(N^2)の空間量を消費してしまうから。
最後に、"single source shortest path algorithm" で始点から全ての点への最短距離を計算することで、現実世界においてどう応用できるのかの説明があった:「単一始点で全ての終点ノードへ最短経路とは、単一終点への全ての始点ノードからの最短経路に他ならない。これをあらかじめ計算しておくと、カーナビで、目的地への最短ルートからドライバーが外れた場合に、最短経路を計算し直す必要がなくなる。」
9. ダメなものはダメ P.69
ダイクストラ法はオランダ計算機科学者ダイクストラによって1959年に発表された。
無向グラフにおける最短経路問題は、無向エッジをそれぞれ2本の有向エッジに置き換えたグラフでダイクストラ法を使うことで解ける。
負の重みのエッジを持つグラフにおける最短経路問題は、閉路(cycle)上に負のエッジがあると最短距離がマイナス無限大になってしまう。負閉路の検出は、ワーシャルフロイド法を用いることで可能。
負の重みのエッジを持つグラフにおける最短経路問題において、各ノードは一度しか通過できない、という条件をつけた場合、これを解く効率的なアルゴリズム (おそらく多項式時間という意味)のアルゴリズムは存在しない。
10. 良い時間,悪い時間 P.77
チューリングマシンにおける計算量の紹介と、§8のダイクストラ法が O(N^2) 時間かかることの説明。
Gemini によると、
チューリングマシンは、1936年に数学者のアラン・チューリングによって考案された「計算とは何か」を定義するための仮想的な機械モデルです。現在のコンピュータの動作原理の基礎となっており、「どんなアルゴリズムも、理論上はこのマシンで実行できる」と考えられています。
- 基本的な仕組み
チューリングマシンは、非常にシンプルな4つの要素で構成されています。
- 無限に長いテープ: マス目(セル)に区切られており、記号(0や1など)が書かれています。
- 読み書きヘッド: テープ上の1つのマス目を読み、書き換え、左右に移動します。
- 状態(ステート): 「今、マシンがどんなモードか」を記録するメモリです。
- 命令規則(テーブル): 「現在の状態がAで、読み取った記号が0なら、1を書いて右へ移動し、状態をBにする」といったルールのセットです
この結果として、あるアルゴリズムの処理時間をわずかな基本演算の数として見積もることを可能としている。基本演算とは、例えば、足し算, 引き算, 掛け算, 割り算, 代入、比較演算などである。
11. 女の直観 P.92
二次元の地図上で、 「出発地点ノード s から、与えられた中間ノードのいずれかのみを通り、到着地点ノード z までたどり着く経路」のうち距離が最短となるルート(最適解)を求めたいとする。
この際、手早く良い初期解が得られれば、グラフ上で検討すべき範囲を狭めることができる。つまり、「s, z を焦点とし、長軸の長さが初期解の距離である楕円」を考え、この楕円の中のノードのみを通る経路を考えればよくなる。
なお、この方法は重みつきグラフでは使用できない。
12. 仕事の前に一仕事 P.103
s -> tの最短経路問題について、以下のようなグラフの前処理が可能である。
- s, t に連結していないノードを無視する
- クリティカルエッジが存在する場合、それを消し去って考えることできる
- s と t が同じ部分グラフの中に存在する場合、その部分グラフのみを使って
s -> tの最短経路問題を解く - そうではなく、
s -- x === y -- zのように xy間にクリティカルエッジが存在する場合、(部分グラフ1における s -> x の最短距離) + (x == y の距離) + (部分グラフ2における y -> z の最短距離)を考えれば良い
- s と t が同じ部分グラフの中に存在する場合、その部分グラフのみを使って
- s, t, "交差点ノード" 以外は間引いてかまわない。連続する複数のエッジをまとめて一つのエッジに置き換えることができる
これらの前処理は、カーナビのように、(i)グラフが不変のため、事前に時間をかけて前処理を行うことができる (ii) 入力に応じて瞬時に結果を出す必要がある、ようなケースに適している。
なお、これらによって処理時間が O(N^2) 時間から改善されるわけではない。
13. 木々の合間で鬼ごっこ P.110
◉ 木の定義
木(tree) = 連結(connected)していて、非閉路的(acyclic)なグラフ
閉路(acyclic) = 無向(undirected)グラフが経路(cycle)を含まない
◉ 木の性質
-
#nodes = #edges + 1を満たす - 一本でもedgeを取り除くと、連結グラフではなくなる
- 一本でもedgeを加えると、閉路が生じるため、木ではなくなる
あるノードからの「最短経路グラフ」は、木である。
あるグラフにおいて、その全てのノードを含む木を、全域木と呼ぶ。さらに、ノードの重みの合計が最小となる全域木を最小全域木と呼ぶ。
14. 素数ではなくて… P.121
無向木(directed tree)における最小全域木を求めるプリム法の紹介とその証明。
◉ プリム法のアルゴリズム
ダイクストラ法に類似した考え方だが、「あるノードが決定された時点で、隣接するノードたちを(開始地点 s からではなく)その決定されたノードからの距離と紐付けてcandidatesの集合に追加する」という点が異なっている。
◉ 上記のアルゴリズムで最小全域木が求められることの背理法による証明
上記のアルゴリズムにおいて、ある時点までのエッジの選択は正しかったが、その次のエッジv-wの選択が誤っていれば、エッジの重み合計がより小さい真の最小全域木が見つかったと仮定する。
ここで、v-wの代わりに選択すべきだったエッジをx-yとする。また、この時点までに連結完了したノード群からなる部分グラフをV, それ以外のノード群の集合からなる部分グラフをWとすると以下が言える。
- ①
edge_weight(v, w) < edge_weight(x, y) - ②
v ∈ V,w ∈ W, エッジv-wはVとW間のクリティカルエッジである - ③
x ∈ V,y ∈ W, エッジx-yはVとW間のクリティカルエッジである
今、完成した全域木の重み合計は、②と③から、
-
v-wを選んだ場合、spanning_tree_weight_sum(V) + edge_weight(v, w) + spanning_tree_weight_sum(W) -
x-yを選んだ場合、spanning_tree_weight_sum(V) + edge_weight(x, y) + spanning_tree_weight_sum(W)
両者を比較すると、①より、v-wを選んだ際の全域木のエッジの重み合計は、x-yを選んだ際のそれより小さくなると言えるが、これは、仮定に矛盾する。よって、上記のアルゴリズムによって最小全域木が求められることが証明された。
15. 手に入るだけもらおう P.133
クルスカル法による、無向木(directed tree)における最小全域木を求めるアルゴリズムが紹介された。
ここから発展して、マトロイドの話に及んだ。
◉ マトロイドについて
以下にまとめた。
アルゴリズムは、ちょっとした制約を加えることで解くのが難しくなることがある。例えば、
- 二重連結な(= critical edgeを持たない)最小全域木
- シュタイナー問題
16. ゼンイキユーコーなんとかって? P.141
有向木(directed tree)における最小有向全域木を求める方法の紹介。
プリム法やクルスカル法は使用できない。エドモンズ法を使用する必要がある。




