『最短経路の本 レナのふしぎな数学の旅』メモ

読んだ。軽めのストーリーを添えながら、グラフ理論について丁寧に説明してくれる。
おれのようなアホでも基本的には理解できるが、中盤の中国人郵便配達問題あたりからかなり難しくなる。
これから先、グラフアルゴリズム実装の際にネット上の解説でもわけがわからなくなったら、この本を読み返すことになるだろう。

以下には、節ごとのキーワードと雑なメモを記載。

登場人物

• ビム
  • レナが父親に買ってもらったパソコンに紛れ込んでいた得体のしれないソフトウェア
  • レナとヤンにグラフ理論を教授する
  • 名前の由来はVimかと思ったら違うようだ
• レナ
  • 主人公
  • 数学苦手だとかほざいてるわりには頭が良い(またこのパターンか)
  • グラフ理論にのめり込んでいく
• ヤン
  • レナのボーイフレンド
  • サッカー少年でSFオタク
  • 軽率
• パパ
  • レナの父親
  • 鬼畜メガネ

1 (最初のコンタクト)

• ストーリー導入部

2 - 4 (ルートプランって何？ ~ 重みは重し)

• アルゴリズムについて
• グラフ理論の用語
  • グラフ、ノード、辺、連結、フェールセーフ、多重辺、無向・有向、重みなど

5 (危なくない爆発)

• 組み合わせ爆発

6 - 9 (最短経路をとるか、いなか、それが問題だ！ ~ ダメなものはダメ)

• ダイクストラ法
  • O(V^2)
• ワーシャル・フロイド法
  • O(V^3)

10 (良い時間、悪い時間)

• 計算量、O記法

11 (女の直感)

• 最適解と近似解

12 (仕事の前に一仕事)

• データの前処理による計算量軽減

13 - 14 (木々の間で鬼ごっこ ~ 素数ではなくて…)

• 木
• 全域木
• プリム法

15 (手に入るだけもらおう)

• 貪欲法
• クルスカル法（クラスカル法）

16 (ゼンイキユーコーなんとかって？)

• 全域有向木

17 - 20 (町の散策も勉強 ~ オイラーとサンタクロース)

• 次数
• オイラー路
• オイラー閉路

21 - 23 (今日はごみ収集車が散策する ~ 中国からの手紙)

• 中国人郵便配達問題
  • O(V^3)
• 二部グラフの最大マッチング

24 - 25 (チェックメイト ~ プラトニックな愛？)

• ハミルトン路
  • グラフの各ノードを一度だけ通過する経路
• ハミルトン閉路
  • 最後に始点に戻ってくるハミルトン路

26 - 27 (表記上の問題 ~ 巡回セールスマンのためだけではなくて)

• P問題
  • 答えが「はい」か「いいえ」であるような問題
• NP問題
  • ある具体的な課題に対する答えとともに、それを効率的に検証可能な「証明」が常に存在する問題
• NP困難
  • 効率的な解法アルゴリズムが見つかっていないこと（？）
  • また、おそらくそうしたアルゴリズムが存在しない
• 巡回セールスマン問題

28 - 32 (少ないは多い ~ 巡回セールスマンの成功物語)

• 緩和法
• ヒューリスティック解法
  • 解の上限・下限を見積もって貪欲（？）
• クリストファイズ(クリストフィード)のアルゴリズム
• 分岐限定法
  • 深さ優先探索の枝刈り（？）
• 多面体組合せ論
  • グラフの冪集合から幾何学的な対象を作る
• 組み合わせ最適化