みなさんこんにちは！
自然科学研究科 M2 の S.K です．
この記事に興味を持ってくださりありがとうございます！
前回の記事では，数学における ”原理” について考えました．
今回の記事でも，抽象的な数学の世界を具体例と結びつけながら紹介していきたいと思います．
早速ですがみなさんは「巡回セールスマン問題」という言葉を聞いたことはないでしょうか？
あるセールスマンが，いくつかの都市を訪れて戻ってくる出張をしようとしています．各都市間の距離はわかっているとします．各都市に一回ずつ寄るとすると，この出張旅行の総移動距離を最小にするにはどのような順で都市をまわればよいでしょうか？
いくつかの都市をまわることを考えると，多くの人は所要時間という観点でも，交通費という観点でも，移動のコストを最小限に抑えたいと思うことでしょう．（観光目的ではなく，仕事ですからね）
5 つの都市を出張でまわることを考えてみましょう．
5 つの都市と、それらを結ぶ経路は以下のようなモデルで表すことができます．
A，B，C，D，E の 5 つの都市と，それらを結ぶ経路を簡潔に表した図になります．
過去に書いた私の記事を読んだことがある方は，ピンときたかもしれませんが，これはグラフと呼ばれる数学的な対象になっています．
各都市が頂点に対応していて，各都市を結ぶ経路が辺に対応しています．
詳しくはぜひこちらの記事をご参照ください．
これが本当に数学？ ～四色定理を通して～ - 図書館学習サポーターの学修サポートコンテンツ！ (hateblo.jp)
このようにして「出張のコストをなるべく抑えるにはどうしたら良いか」という問題は数学の問題，特にグラフ理論の問題として捉えることができるのです．
さて，各都市間の距離はわかっていることが前提なので，上で示した図に書き入れてみましょう．
あくまで一例ですが，各都市間の距離が上記の数値で表せたとしましょう．例えば都市 A と都市 B 間の距離は 7 です．
次に考えなければならないことは，各都市に一回ずつ寄ってスタートした都市に戻ってくる経路は何通りあるのかということです．
都市 A をスタートとして考えてみましょう．
スタートとゴールは都市 A になるので，残りの 4 つの都市をどうまわるかを考えれば良いわけです．
よって答えは 4! 通りです．（これはビックリマークではなく，階乗を表しています）
といいたいところですが，A→B→C→D→E→A と A→E→D→C→B→A のように，同じ並びを逆にたどると，移動距離の合計は等しくなります．よって実際は 4! = 24 の半分の 12 通りの経路があることがわかります．（高校での数学で数珠順列という言葉を聞いたことはありませんか？）
少し面倒かもしれませんが，全通り列挙してそれぞれの経路でかかるコストを計算してみましょう．
①（A-B-C-D-E-A）： 7 + 10 + 8 + 6 + 12 = 43
②（A-B-C-E-D-A）： 7 + 10 + 4 + 6 + 9 = 36
③（A-B-D-C-E-A）： 7 + 13 + 8 + 4 + 12 = 44
④（A-B-D-E-C-A）： 7 + 13 + 6 + 4 + 11 = 41
⑤（A-B-E-C-D-A）： 7 + 14 + 4 + 8 + 9 = 42
⑥（A-B-E-D-C-A）： 7 + 14 + 6 + 8 + 11 = 46
⑦（A-C-B-D-E-A）： 11 + 10 + 13 + 6 + 12 = 52
⑧（A-C-B-E-D-A）： 11 + 10 + 14 + 6 + 9 = 50
⑨（A-C-D-B-E-A）： 11 + 8 + 13 + 14 + 12 = 58
⑩（A-C-E-B-D-A）： 11 + 4 + 14 + 13 + 9 = 51
⑪（A-D-B-C-E-A）： 9 + 13 + 10 + 4 + 12 = 48
⑫（A-D-C-B-E-A）： 9 + 8 + 10 + 14 + 12 = 53
以上の計算から，A-B-C-E-D-A の順で都市をまわることで移動のコストを最小限に抑えることができます．（もちろんこの逆の A-D-E-C-B-A の順で都市をまわっても移動のコストは最小になります．）
この巡回セールスマン問題の考え方には，いくつか役に立つ応用もあります．
スクールバスが学校を出て，何カ所かの停留所をまわって生徒を乗せて学校へ戻ってくる．このときに所要時間が最小になる経路を求める．
これがわかれば時間だけでなく，ガソリン代の節約にもなります．（最近高いですからね．）
郵便局員が郵便局を出て，郵便ポストに投函された郵便を集めてまわる．このときに所要時間が最小になる経路を求める．
こちらも車でまわるならばガソリン代の節約になります．徒歩でまわるとしても，必要以上に遠回りすることは避けたいですよね．
今回は簡単な例を考えましたが，巡回セールスマン問題を実際の都市について解こうとすると，これはかなり複雑で難しい問題になります．
しかしすでに解かれている都市もあります．
例えば，アメリカ合衆国の1998年時点で人口が500人を超えていた13,509市町村については，巡回セールスマン問題がとかれています．
興味のある方はぜひ調べてみてください．
納得するには時間がかかる内容も含まれていたかもしれません．
ぜひゆっくりと考えてみてください．
最後まで読んでいただきありがとうございました！
【参考文献】
アーサー・ベンジャミン，ゲアリー・チャートランド，ピン・チャン 著．松浦俊輔 訳．グラフ理論の魅惑の世界．第１版，青土社，2015年，405p．
