すべての都市を回る「一番短い道」はどれ？
東京、横浜、名古屋、大阪、京都。
もし、これらの都市をすべて一度ずつ訪れ、最後に出発地点へ戻るとしたら、どの順番で回れば移動距離を最も短くできるでしょうか。
都市が5つ程度なら、いくつかのルートを試して比較できそうです。
ところが、都市が10、20、50と増えていくと、候補となるルートの数は急激に増えていきます。
この有名な問題が、
巡回セールスマン問題（Traveling Salesman Problem：TSP）
です。
前回紹介したハミルトン閉路とよく似ていますが、TSPにはさらに重要な条件があります。
それは、
すべての都市を回るだけでなく、その中で最も短いルートを探すこと
です。
今回は、このシンプルなのに非常に奥深い問題を、身近な例からわかりやすく紹介します。
巡回セールスマン問題とは？
複数の都市があり、それぞれの都市間に距離があるとします。
セールスマンは一つの都市から出発し、
- すべての都市を訪問する
- 各都市を一度ずつ訪れる
- 最後に出発都市へ戻る
- 総移動距離をできるだけ短くする
という条件を満たすルートを探します。
「すべてを一度ずつ回って戻る」だけなら、前回紹介したハミルトン閉路と似ています。
しかしTSPでは、
どのルートが最短なのか
まで考えなければなりません。
ここが大きな違いです。
5都市なら簡単？
5つの都市を訪問する順番を単純に並べると、
5! = 120通り
あります。
出発地点を固定したり、逆回りを同じルートと考えたりすれば、実際に比較する候補はさらに減らせます。
そのため、小さな問題なら人間でもすべての候補を調べることができます。
では10都市ならどうでしょう。
10! は、
3,628,800
です。
さらに20都市になると、
20! は約
2.43 × 10¹⁸
という巨大な数になります。
都市が少し増えるだけで、候補の数が爆発的に増えてしまうのです。
一番近い都市へ行けば正解？
ここで簡単な方法を考えてみましょう。
「現在地から一番近い都市へ順番に移動すればいいのでは？」
確かに、この方法なら素早くルートを作ることができます。
このような考え方は最近傍法と呼ばれる方法の一例です。
しかし、必ず最短ルートになるとは限りません。
最初は近い都市ばかり選べても、最後に遠く離れた都市が一つ残り、大きく遠回りすることがあります。
つまり、
目の前で一番良さそうな選択が、全体でも一番良いとは限らない
のです。
これはTSPの面白いところです。
全部調べれば必ず答えは出る
最も単純で確実な方法は、考えられるルートをすべて調べることです。
すべての候補について総距離を計算し、一番短いものを選べば、最適解を見つけることができます。
この方法を総当たりと考えることができます。
都市が少ない場合には有効です。
しかし、都市が増えると候補数があまりにも多くなり、計算量が急激に増えてしまいます。
そこで実際の問題では、
「必ず最適解を求める方法」
だけでなく、
「かなり良いルートを短時間で見つける方法」
も重要になります。
コンピューターはどうやって探す？
TSPを解くためには、さまざまな方法が研究されています。
例えば、
- 不要な候補を途中で除外する
- 良さそうなルートから優先して調べる
- 近い都市を利用して最初の候補を作る
- ルートの一部分を入れ替えて改善する
といった工夫があります。
問題の大きさや目的によって、正確な最適解を求める場合もあれば、短時間で十分良い近似解を探す場合もあります。
現実社会では、計算時間そのものも大切な条件だからです。
配送の世界ではもっと複雑
TSPはよく配送ルートの説明に使われます。
例えば、一台の配送車が複数の住所へ荷物を届け、最後に配送センターへ戻るとします。
しかし現実には、
- 車が何台もある
- 荷物の重さが違う
- 配達時間が指定されている
- 渋滞がある
- 一方通行がある
- 道路によって移動時間が違う
といった条件があります。
そのため、実際の物流問題は単純なTSPよりさらに複雑になります。
それでも「多くの場所を、できるだけ効率よく回る」という基本的な考え方は共通しています。
物流以外ではどこで使われる？
巡回セールスマン問題の考え方は、配送だけに限られません。
例えば、
旅行計画
複数の観光スポットを効率よく巡る順番を考える。
工場
機械が複数の作業場所を効率よく移動する順序を決める。
ロボット
複数の点を巡回しながら検査や作業を行う。
電子回路
多数の接続点を効率的につなぐ経路を考える。
研究・データ解析
「どの順番で処理すれば効率がよいか」という問題として応用されることがあります。
一見すると旅行や配送の問題ですが、その本質は「順番を最適化すること」にあります。
自分でも小さなTSPを作ってみよう
紙に5つの都市を表す点を描いてください。
A、B、C、D、Eと名前を付けます。
それぞれの都市を線で結び、適当な距離を書きます。
そして、
Aからスタートして、
B、C、D、Eを一度ずつ訪れ、
最後にAへ戻ります。
いくつかの順番について総距離を計算してみてください。
最も短いルートを見つけることができるでしょうか。
都市を6個、7個と増やしていくと、急に問題が難しくなることを実感できるはずです。
ハミルトン閉路との違いを整理
最後に前回との違いを整理しましょう。
ハミルトン閉路
すべての頂点を一度ずつ訪れ、出発点に戻れるルートを探す。
巡回セールスマン問題
すべての頂点を一度ずつ訪れ、出発点へ戻るルートの中から、
総距離やコストが最も小さいルート
を探す。
つまり、
ハミルトン閉路は「回れるか？」
TSPは「どの回り方が一番よいか？」
を考える問題です。
まとめ
巡回セールスマン問題は、すべての都市を一度ずつ訪れ、出発地点へ戻るルートの中から最短のものを探す問題です。
ルールそのものはとても簡単です。
しかし都市が増えると候補のルートが急激に増えるため、最適な答えを効率よく見つけることが難しくなります。
この問題は、配送、物流、旅行、工場、ロボット、電子回路など、さまざまな分野につながっています。
そして私たちに重要なことを教えてくれます。
「一つ一つの選択が良く見えても、全体として最適とは限らない。」
数学は答えを計算するだけでなく、数え切れない選択肢の中から「より良い方法」を探すための道具でもあるのです。
次回予告
「四色問題とは？どんな地図でも4色だけで塗り分けられる？」
次回は、地図を隣り合う地域が同じ色にならないように塗る、有名な数学問題を紹介します。
