#75「ルート探索アルゴリズムの話- 点と線が描くグラフ理論の世界-」
デデデータ!!〜“あきない”データの話〜第38回「ルート探索アルゴリズムの話- 点と線が描くグラフ理論の世界-」の台本・書き起こしをベースに、テキストのみで楽しめるようにnote用に再構成したものです。
これまで「ゲーム理論」や「ベイズ理論」「確率モデル」などの数理的テーマを取り上げてきた。今回はそれらと並ぶ重要な数学の一分野として、“グラフ理論”を中心に「ルート探索アルゴリズム」や「最適化問題」の話をしてみようと思う。
世の中の仕組みを見渡すと、じつは多くのものごとが「点と線」の構造で捉えられる。人間関係（SNSやコミュニティ）、交通網（鉄道や道路ネットワーク）、Webサイト間のリンク、物流のルートなど、ほぼ無数の事象が“ノード（頂点）”と“エッジ（辺）”で抽象化できるのだ。そして、この“点と線”を扱うグラフ理論こそ、いまのデータやDXの文脈では欠かせないツールになっている。
ここでは、グラフ理論の歴史から具体的な探索アルゴリズム、さらには実社会で頻出する「巡回セールスマン問題（TSP）」まで一気に駆け抜けてみたい。
ケーニヒスベルクの橋──グラフ理論の始まり
グラフ理論というと、とかく「抽象的で難しそう」という印象を抱くかもしれない。しかし、その起源は意外にも非常に身近な“橋めぐり”のエピソードだ。かの数学の巨匠、レオンハルト・オイラーが「ケーニヒスベルクの七つの橋を一度ずつ渡ってすべて踏破できるか」という町の疑問を解き明かそうとしたことから、この学問の扉が開かれたといわれている。
ケーニヒスベルクには川の上に7つの橋があり、「この橋を全部一度ずつ通る道を作れるか？」と昔から人々が不思議に思っていた。しかし誰もはっきり答えられない。そこで数学者のオイラーが、
陸地を「点」
橋を「線」
として地図をシンプルな図形に置きかえて考えた。
するとわかったことは、一筆書きで「すべての橋を一度ずつ」通るには、通過する頂点は“出入りの線が同じ数”でないといけないということ。つまり“頂点の次数”は偶数である必要があることに気づいた。
逆に「出発点」と「到着点」の2か所だけは、“出る線と入る線の数”が一致しない（つまり奇数の次数）でもよい。最大で2つまでならOKというルールになる。
ケーニヒスベルクの結果はどうなるか？
ケーニヒスベルクの地図を「4つの陸地＝4頂点」「7つの橋＝7線」で表すと、4つの頂点すべてが奇数の次数になっていた。
ところが、一筆書きを可能にするには「奇数の頂点が多くても2つまで」でなくてはならない。
実際は4つも奇数頂点があるので、この街で「7つの橋を一度ずつすべて渡る」道は作れない、と結論づけられたわけだ。
これが「グラフ理論」のはじまりだ。
この「陸地＝点、橋＝線」のように、現実の問題を“点と線”の関係として考えるのがグラフ理論。いまやインターネットのネットワークや交通網など、複雑なつながりを扱うときに欠かせない手法として使われている。
この一見“橋を渡るだけ”の話が、あらゆるネットワーク構造を数学的に表す「グラフ理論」の扉を開いたのだから歴史は面白い。
点と線で世界をモデル化する
では、グラフ理論はどんな分野なのか。ノード（点）とエッジ（線）を使い、世の中の「つながり」を表す手法だ。
SNSを例にすると、ユーザをノード、フォローや友達関係をエッジとして捉えられる。フェイスブックの友達関係は双方向なので「無向グラフ（Undirected Graph）」、Twitterのフォロー関係は片方向なので「有向グラフ（Directed Graph）」に分類できる。
道路網や鉄道網など、移動の距離やコスト（運賃・通行料金）が重要になる場合は、エッジに“重み”を付け加えた「重み付きグラフ（Weighted Graph）」として扱う。大まかに分けると、次の3タイプが代表的だ。
無向グラフ：友達関係など、AとBが常に対等な関係を示す
有向グラフ：A→BとB→Aが異なる非対称の関係を表す（フォローやリンク先など）
重み付きグラフ：エッジに距離や運賃、時間、親密度などの数値を付与して解析する
たとえば東京駅から神保町駅まで移動する場合、地下鉄に乗るか徒歩にするか、別ルートにするかなど、移動時間や運賃、快適さなどを比較検討するだろう。これらを“重み”として扱い、最適な移動手段を計算する仕組みが「グラフ理論＋探索アルゴリズム」だ。
幅優先探索からA*まで──ルート探索アルゴリズム
グラフ理論を学ぶ楽しさの一つに「さまざまな探索アルゴリズム」がある。ノードとエッジで世界を抽象化したら、どのルートが最短か、どうすれば目的地に一番速く到達できるか、といった問題を解くために、何種類かの手法が考案されている。ここでは代表的な4つを紹介する。
1. 幅優先探索（Breadth-First Search: BFS）
いわば「団体行動で宝探しをする」ような手法だ。
スタートから1ステップ進み、その地点に隣接するノードをすべてチェックし、次の1ステップへ進む──というように幅広く探索する方法だ。重み（移動コスト）が同じとみなす場合は、最短経路を見つけやすい。ただし実際に所要時間や距離が異なる場面には向かない。
2. 深さ優先探索（Depth-First Search: DFS）
「奥まで突き進んでダメだったら戻ってくる」ソロ冒険スタイル。行けるところまで一気に進み、行き止まりにぶつかったら折り返し、次の道を探る。こちらも重み付きの最短経路には不向きだが、“全ノードを巡回するには便利”な面がある。
3. ダイクストラ法（Dijkstra）
「重み付きグラフにおける最短経路探索の代表格」だ。BFSやDFSではコストを考慮しないが、ダイクストラは「どの道を選べば合計コストが最小になるか」を計画的に算出する。ノードをひとつずつ決め打ちするのではなく、周辺のルートの重みを都度更新しながら、最終的に“スタートからゴールまでの最短距離（あるいは時間）”を導き出す。乗換案内アプリや地図アプリなどが裏で活用している手法でもある。
4. A*（エースター）
ダイクストラ法に「推定値（ヒューリスティック）」を加えた進化版、ともいわれる。地図で目的地までの直線距離やおおまかな距離感を“予測”として利用し、探索の効率を上げるのだ。直感（推定距離）と実際の距離をうまく組み合わせ、最短経路をより高速に見つけるという特徴がある。
巡回セールスマン問題（TSP）の深淵
探索アルゴリズムの話をさらに発展させると、「巡回セールスマン問題（Traveling Salesman Problem: TSP）」という数理最適化の難題に行き着く。
これは「複数の都市（ノード）をできるだけ短いルートで巡回し、出発地点に戻る」ための最適解を求める問題だ。
たとえば5都市なら120通り、10都市なら362万8800通り、30都市ともなれば桁外れ（30!）の組み合わせ数が存在してしまう。コンピュータでも全探索は困難なうえ、これは「NP困難」な問題として有名だ。
しかし、実社会ではAmazonの配達やUberの配車など、まさに複数地点を効率的に回る状況が日常茶飯事だ。そこで活躍するのが「ヒューリスティック」や「近似アルゴリズム」である。
ヒューリスティックと近似アルゴリズム
1. ヒューリスティック
厳密最適解は得られなくても「そこそこ良い解」を素早く出す手法で、現場の問題をパパッと解決するのに向く。たとえば「貪欲法（Greedy Algorithm）」は、その時点でいちばん得をする選択を即断即決して進む。宅配ルートなら“いま最も近い地点に向かう”、クラウドストレージの容量整理なら“いちばん大きいファイルから削除していく”といった具合だ。
2. 焼きなまし法（Simulated Annealing）
最初はランダムに手を広げ、少しずつ「より良い解」へ収束させる。局所最適にハマらないよう、最初は意図的に“悪そうな手”も試す確率を高めるなど、物理学の焼きなましにヒントを得たアルゴリズムだ。
3. 近似アルゴリズム
数学的な保証をもった手法で、「最適解の何倍以内」といった明確な精度保証をつける場合がある。局所改善を何度も試す「2-Opt」なども、バカにできない力を発揮する。たとえば一度作ったルートをちょっと入れ替え（swap）て、距離が短くなればその変更を採用する──これを繰り返すだけでも、意外なほど優秀な解にたどり着くことがある。
ビジネスへの応用と“実用的な最適解”
こうしたグラフ理論と探索アルゴリズムは、単なる学問にとどまらず、すでに社会のありとあらゆるシーンに溶け込んでいる。Amazonの配達ルートやUberのドライバー配車、工場の部品搬送、観光プランの自動生成など、「点と線と重み」が絡む問題は尽きない。
しかし、理論的に完璧な“最適解”を求めようとすると、計算コストが膨大になりすぎて現実的でなくなる場合が多い。そこは「ヒューリスティック」や「近似アルゴリズム」でうまく落としどころを見つけ、“使えるレベルでそこそこ最適”を目指すのが常套手段だ。その意味で、完全無欠の最適解よりも「実務に活かせる解」が重要というわけである。
おわりに──数理モデルの活用を恐れない
グラフ理論や探索アルゴリズムを初めて学ぶと、「こんなところに数学が使われているのか」と驚くかもしれない。たとえば日常的に使う乗換案内アプリが、ダイクストラ法やA*などを裏で走らせている事実を知ると、それだけで世界の見え方が変わる。
かつて「モンティホール問題」や「ベイズ理論」の話題で“確率を更新してみると直感が覆される”という体験があったように、グラフ理論でも「点と線」で視点を切り替えると、複雑に見えた問題がスルッと整理されることがよくある。仮にロジックが直感に合わない場合でも、実験（たとえば簡単なコップ当てゲームを複数回やる）を通じて体で理解する、というのが私のおすすめのアプローチだ。
グラフ理論の可能性は無限大だ。人間同士のソーシャルグラフや、工場内の動線、さらには生成AIの検索経路など、これからもさまざまな形で応用が広がっていくだろう。どれも最適解を100％厳密に出すのは難しいが、そこに数学的なヒントが詰まっている。
ともあれ、ルート探索の裏側にある数理モデルに触れると、日々の生活でも視点が変わってくる。乗り換え案内が瞬時に最短ルートを弾き出すのは、単なる“魔法”ではない。人類が築いてきた数学の恩恵なのである。
専門用語解説
頂点（ノード／Vertex, Node）
グラフ理論で扱う「点」。SNSにおけるユーザや、地図上の駅・交差点などがノードとして例示される。辺（エッジ／Edge）
グラフ理論で扱う「線」。SNSでのフォロー関係、道路や鉄道など、ノード間を結ぶ関係を示す。有向グラフ（Directed Graph）：A→BとB→Aが区別される。
無向グラフ（Undirected Graph）：AとBは相互関係として同等に扱う。
重み（ウェイト／Weight）
距離・時間・コストなど数値化できる要素。道路網の移動距離、運賃、所要時間などの“重み付きグラフ”として扱う。次数（Degree）
頂点に接続しているエッジの本数。頂点の次数が「偶数」か「奇数」かが、一筆書き（オイラー路）の可否を左右する。NP困難問題（NP-hard problem）
計算理論で登場する分類。多くの組み合わせを総当たりで解くには、計算量が爆発的に増大する問題。巡回セールスマン問題（TSP）は代表例。ヒューリスティック（Heuristic）
完全解（最適解）を厳密に求めるのではなく、現実的な計算時間で「そこそこ良い解」を求める手法。貪欲法や焼きなまし法などが該当する。近似アルゴリズム（Approximation Algorithm）
「最適解の何倍以内」といった誤差保証がついているアルゴリズム。局所改善（2-Optなど）を繰り返し、解をアップデートしていく方法などがある。
歴史解説
ケーニヒスベルクの七つの橋問題
18世紀にレオンハルト・オイラーが解決した、一筆書き（オイラー路）にまつわる有名な逸話。
「どう頑張っても7つの橋をすべて一度ずつ渡ることはできない」理由を、陸地＝頂点、橋＝辺としてグラフ化し、頂点の次数で判定した。
この成果が「グラフ理論」の原点の一つとなった。
レオンハルト・オイラー（Leonhard Euler, 1707-1783）
スイス生まれで、当時のプロイセンをはじめ各地で活躍した数学者。解析学から幾何学、物理学など、多岐にわたる業績を残した。
ケーニヒスベルクの橋問題を解決し、“位相幾何学”や“グラフ理論”の基礎を築いた。
TSP（巡回セールスマン問題）の登場
19～20世紀にかけて「複数の都市を短いルートで巡回する問題」が研究されるようになった。
1960年代以降の計算機科学の発展とともに“計算困難問題”として認知され、アルゴリズム研究や組合せ最適化の分野で中心的な議題となっている。
アルゴリズム解説
1. 幅優先探索（Breadth-First Search: BFS）
特長
スタートからの「階層（距離）の浅いノード」から順に探索。
重みを考慮しない“最短手順”の発見に向いている（重み付きには不向き）。
主な利用場面
無重みグラフでの最短経路探索
SNSで「フォロー距離1のユーザを探す」などの単純階層検索
2. 深さ優先探索（Depth-First Search: DFS）
特長
行けるところまで一気に進んで行き止まりになったら戻る“バックトラッキング”手法。
全ノードを巡回・チェックしたいときにシンプルで使いやすい。
主な利用場面
組合せ探索（パズル、迷路）、木構造の処理
3. ダイクストラ法（Dijkstra’s Algorithm）
特長
重み付きグラフにおける代表的な最短経路探索。
各ノードまでの最短距離を段階的に更新しながら決定していく。
負の重みがない場合に有効。
主な利用場面
交通経路（運賃・距離・時間）の最短経路
地図アプリのルート検索
4. A*（エースター）
特長
ダイクストラに「ヒューリスティック（推定値）」を取り入れて探索効率を上げたアルゴリズム。
目的地までの直線距離などを見積もりに用いる。
主な利用場面
ゲームAIの道筋（ナビゲーションメッシュなど）
ロボットの最短経路探索
TSP（巡回セールスマン問題）と近似手法
TSPの概要
N都市を一度ずつ巡って始点に戻る最短ルートを探す。
Nの階乗（N!）という莫大な組合せを要するため、全探索が難しい（NP困難）。
代表的なヒューリスティック・近似アルゴリズム
貪欲法（Greedy Algorithm）
近い都市から順に回っていくなど、目先の利益を優先する。
実装が簡単で計算が速いが、必ずしも最適解を保証しない。
焼きなまし法（Simulated Annealing）
初期解からスタートし、ランダムな交換などで徐々に良い解に近づける。
“高温”期は悪い手も採用し、局所解からの脱却を狙う。
2-Opt, 3-Optなどの局所探索
ルートを一部入れ替えて距離が短縮すれば採用する、という操作を繰り返す。
単純ながら大幅改善に寄与するケースが多い。
ビジネス・実社会への応用
物流・宅配ルート最適化
Amazonや宅配各社が配達順序を計算し、燃料コストや人件費を削減。
リアルタイム交通情報（渋滞など）の考慮も含め、ほぼ間違いなくグラフ理論＋近似最適化が活躍。
タクシー・ライドシェアの配車管理
UberやLyftなどが、需要と供給（ドライバー位置・顧客リクエスト）を最適にマッチングして効率化。
「どのドライバーをどの乗客に向かわせるか」をグラフモデルで計算する。
工場内搬送、AGV（自動搬送車）の経路計画
生産ラインでの部品運搬、ロボットが走行する最適な経路を探索。
安全性と効率を両立させるためにヒューリスティックも併用。
まとめ
ケーニヒスベルクの橋問題を起点に、グラフ理論はSNS・地図アプリ・物流など日常生活のあらゆる場面で応用されている。
グラフ探索アルゴリズム（BFS、DFS、ダイクストラ、A*など）を適切に使い分けることで、最適経路や最短手順が導き出せる。
巡回セールスマン問題のように、理論的には計算が膨大になる問題でも、ヒューリスティックや近似アルゴリズムを使うことで「実務に使える最適解」に近づくことができる。