Booklog - 最適経路の本 レナの不思議な数学の旅

コレも結構前に買って積まれたままだったので読む。最適経路問題を題材にしたグラフ理論に触れた小説って感じ。 まえがき、 1 ~ 2 。身近なテーマとしてルートプランを題材にして最短経路問題に触れはじめたところ。 ルートプランが現実に何に応用されてるか、プロジェクトプランをルートプランの一部として考えられるとか、現実に落とし込んで平易な説明が進められてるので優しい。

2026-07-15, read count: 1, page: 1 ~ 18, pages read: 18

3 ~ 6 。ルートプランはグラフとしてモデル化できる。 グラフはノードとノードをつなぐ辺あるいは弧の集合。ノードは複数の辺を持つことができ、辺には向きがあるものが有向グラフ(ダイグラフ)。 ノード自身に戻る辺はループ。辺(弧)は重みを持つ。重みを自然数だけに制約を課す事もできるし負数でもいい。 ノードが僅かに増えるだけでも組み合わせの爆発が起こる。 小気味良く話が進むので読みやすい。これまた子供に読ませたいなという感じを持ってる。けど本書を読みはじめてからあまり時間取れず思ったほど量を読めてない。

2026-07-16, read count: 1, page: 19 ~ 48, pages read: 30

7 ~ 9 。グラフの組み合わせの爆発はグローバルに解決した場合の話。ローカルに解決すればパターンは多くない。 ダイクストラのアルゴリズム。重みの正負の制約でアルゴリズムが変わる可能性がある。数学的なお作法の説明を絡めてアルゴリズムで最短経路を探るステップを読み解いてる。 弧ないし辺を複数回使わず出発ノードに戻ってっくるグラフを回路 or 閉路という。グラフに負の閉路があると最短経路の算出でいくらでも短い経路になる。ワーシャル-フロイドのアルゴリズムで調べられる。 載ってる URL がどう見ても Java Applet でびっくりした。章が短いし面白くサクッと読めるが時間があまり取れないので小刻みに読む。

2026-07-17, read count: 1, page: 49 ~ 76, pages read: 28

10 ~ 11 。 計算量理論。チューリングテスト。計算量を計算する際に演算の数を上に見積もる。 人間的な直感は直線的な最短距離は瞬時に判断できるが、重み付けされていると途端に役立たなくなる。 昔チームで働いてたときにお若いのにアルゴリズムの時間/空間計算量の話したな...あのときこの本を教えれたら良かったか。

2026-07-18, read count: 1, page: 77 ~ 102, pages read: 26

12 ~ 13 。前処理による計算の効率化。 取り除くことでグラフが分割されるクリティカルな辺を基点にグラフを分割。分割後のグラフの計算量が同程度であるほど効率がいい。 経路の選択に関わらない辺を重みに畳み込む。 非閉路的グラフを木と呼ぶ。スパニングツリー、全域木。 辺の重みが最小になるよう全域木を選ぶ。スパニングツリー問題、全域木問題。 ダイクストラのアルゴリズムではすべての開始ノードについて調べる必要があり、ワーシャル-フロイドののアルゴリズムの方が適する。

2026-07-19, read count: 1, page: 103 ~ 120, pages read: 18