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

14 ~ 15 。プリムのアルゴリズムで最小全域木を求める。そしてその正しさの背理法を用いた証明。 自明は英語で trivial 、ラテン語の trivialis に由来する。名詞の trivium が取るに足りないもの、また中世ヨーロッパの身に付けうべき教養「三学(trivium)」からも来ている。 欲張りアルゴリズム(greedy algorithm)。クルスカルのアルゴリズム。マトロイド。 ネットワークのフェイルセーフのように二重連結のグラフの最小の部分集合を求める問題はシュタイナー木問題として知られる。

2026-07-20, read count: 1, page: 121 ~ 140, pages read: 20

16 ~ 19 。全域有効木。ケーニヒスベルクの橋。オイラーがこの問題を通じてグラフ理論の基礎を作った。 字数が奇数になるノードの数は偶数になる特性の完全帰納法(complete induction)または数学的帰納法(mathematical induction)で証明できる。 オイラー小路、オイラー閉路。オイラー閉路を含むグラフはオイラー的。 次数が奇数のノードは必ず辺が 1 つ残り、それはオイラー小路の開始ノードか目標ノードでなければならない。それ以外は偶数の次数。 経路の問題を一筆書きのルールに抽象化したんやな。華麗な抽象化。

2026-07-21, read count: 1, page: 141 ~ 171, pages read: 31

20 ~ 21。 サンタクロースの家の一筆書き。 オイラーの業績は多方面に及び、オイラーの定理・オイラーの式が様々な分野で知られる。数学記号の発明やオイラー数 e ・円周率 π ・虚数 i の定数記号の作成。 現実問題におけるグラフ理論の応用。としてゴミ収集車が市内を巡回する経路の最適化。オイラー閉路がない場合は奇数ノードの経路を「操業橋渡し運行」することで次数を偶数にして閉路を作る。 サンタクロースの家の一筆書き、確かにオイラーの定理だわ。奇数ノードが 2 つあるので、そこを開始ノードと目標ノードにすれば一筆書きできる。今まで知らずに生きてきた。

2026-07-22, read count: 1, page: 172 ~ 189, pages read: 18

20 ~ 23 。組み合わせ問題と組み合わせの爆発。オンライン問題。輸送問題。 二面的かどうかという組み合わせ問題をマッチング問題という。ブラッサムのアルゴリズム。O(n^3)。色彩輪法って言葉は何？ 中国の郵便配達員問題はごみ収集車のようなすべての経路をたどる必要がある問題。 プロッタの図をグラフと考える。強連結な有向グラフ。入次数と出次数が一致しないノードは次数が一致するよう調整する必要がある。 クリティカルなノードだけの補助グラフを作ってみるとマッチング問題の代わりに輸送問題に置き換えられる。 頭に入り切らなくてわかんなくなってしまったわ。調べたところオンライン問題が難しいのは全ての入力が一度に与えられず複雑になるためで、輸送問題もオンラインであれば難しくなる。 ここではオフラインだからオフライン割当問題同様に最適化できるという話みたい。これは読んでてわからんかった。

2026-07-23, read count: 1, page: 190 ~ 211, pages read: 22

24 ~ 25 。 ナイトのツアー。ウォーンスドルフの規則はヒューリスティックなものでマス目の数により必ず解決できるとは限らなくなる。 グラフの辺を一度だけ通るハミルトン路。その閉路がハミルトン閉路。 8x8 のチェス盤にオイラー閉路は存在しないが(奇数ノードが 4 つ)ハミルトン閉路はいくつか存在する。 20 ゲーム(icosian game)。プラトンの正多面体とグラフの関係は次の章っぽい。 ヒューリスティックはファスト&スローでもピックアプされてた。分野問わず、規則性のある環境では統計的に正しそうな解法を選ぶと大体あってるという普遍性があるんやな。

2026-07-24, read count: 1, page: 212 ~ 236, pages read: 25

26 。ハミルトン閉路は決定問題。決定問題で「はい」と答えれるかどうかは NP(Non-deterministic Polynomial)(非決定性多項式) 問題で、効率的な検証可能な証明が存在する。 1 つの問題に対する効率的なアルゴリズムで NP に属するすべての問題に対する効率的なアルゴリズムが得られることを NP 困難という。 NP 困難な最初の問題は充足可能性問題。 本書では NP 完全と出てこない。 NP に属して NP 困難な問題を指していて、ハミルトン閉路は NP 完全みたい。

2026-07-25, read count: 1, page: 237 ~ 249, pages read: 13

27 。最短のハミルトン経路を見つける問題は、巡回路問題または巡回セールスマン問題(Traveling Salesman Problem, TSP)。 実用例としては基盤の穴あけ加工の最適化。 w.l.o.g. without loss of generality。一般性を失うことなく。 ここまでで触れた「欲張り」な戦略は最隣接ヒューリスティック解法(Nearest-Neighbor Heuristic)。 これは構成的ヒューリスティック解法。改良的ヒューリスティック解法ではすで見つけたルートを更に短くするため辺の取り替えを試す。 品質を保証できないってのはヒューリスティックな解法だからって話なんやろな。このヒューリスティックの考え方はまだあんま頭に馴染んでない。

2026-07-26, read count: 1, page: 250 ~ 263, pages read: 14

28 ~ 29 。最適な範囲を絞るための下限と上限を求める。ヒューリスティックな解法で得た長さを最適な長さの上限とする。規則を緩める。数学では緩和法 relaxation。 1-木(名前が一般的すぎて全然検索に引っかからない)は 1 つのノードを除いて出来た全域木に、取り除いたノードにつながる 2 辺をつないだもの。ハミルトン路は全域木であり、ハミルトン閉路(準回路)は 1-木。 ヒューリスティックな方法では最適な回に全く近づけないことも起こりうるため、最適な解から遠ざかっていないことを保証できるならそれに越したことない。 グラフ理論の用語と TSP 上の文脈とが混ざってるっぽくて用語がいっぱいでややこしい。 クリストファイズのアルゴリズムでは最適解からたかだか 50% しか違わないツアーを作成できる。

2026-07-27, read count: 1, page: 264 ~ 278, pages read: 15

30 ~ 31。分枝。最小 1-木。最隣接ヒューリスティック解法のツアーを上限とする。各分枝で最小 1-木を下限にして超えた時点で探索を中断して、別の経路を探索する。分枝限定法。 多面的組み合わせ論。グラフから幾何学的な対象を作る。頂点の集合を多面体として扱う。頂点の数が増えるほど面の数も膨大になるが、すべての面を使わなくなくても巡回路の経路の数の適当な下限を得るのには十分役立つ。 ふーんという感じで頭に染み込んできてないなあ。

2026-07-28, read count: 1, page: 279 ~ 300, pages read: 22

32 。 1954 年のアメリカの 49 都市の準回路問題を解くのに組合せ最適化が使われた。分枝限定法の下限に多面的組み合わせ論が使われた。組合せ最適化の進歩について。 「プロテクター＆ギャンブル」って書いてるが「プロクター＆ギャンブル」の誤記やろな。 これで本書は終わり。後半つらかったけど全体的にわかりやすく示してくれてるしまた読んで理解を深めたい。もう絶版ぽいし大事に学ばせてもらおう。 一部の用語が検索しても一般的な日本語の用語と違ったみたいなので、その辺の照らし合わせもしたら読んだ内容をうまく定着できるんじゃないかなあ。

2026-07-29, read count: 1, page: 301 ~ 318, pages read: 18