はじめに
小学生の子どもに巡回セールスマン問題を教えようと思ってWebサイトや書籍を探したのですが、なかなか適当な解説が見つからないので、自分で書いてみます。はじめに家庭訪問の順番の例について説明したうえで、組合せが爆発すること、コンピュータでもなかなか解けないことを説明します。
家庭訪問の順番を決めよう！
身近な問題の中には、いろんな選択肢の中から一番良い組み合わせを選ぶ、という問題が結構あります。こういう問題を「組合せ最適化問題」といいます。例として、家庭訪問の順番について考えます。
先生が、クラスの生徒の家庭訪問をするとします。先生は忙しいので、なるべく遠回りをしないで、生徒全員の家を回りたいと思っています。例えば、１丁目に行って、２丁目に行って、また１丁目に行くよりは、１丁目の２人の家に行ってから２丁目に行ったほうが行ったり来たりしなくて済みますよね。
このようにして、一番近道するにはどういう順番で回ればいいか？という問題を、「巡回セールスマン問題」と言います。セールスマンがお得意様全員のところにどうやって早く行くか？という話から、こういう名前がついています。
クラス全員の家庭訪問の順番を決めるには？
実は、クラスの生徒が増えれば増えるほど、この問題を解くのは大変です。
例えば、生徒が３人（Aさん、Bさん、Cさん）の場合を考えてみます。家庭訪問の順番は、次の６つが考えられます。
- スタート→Aさん→Bさん→Cさん→ゴール（80分）
- スタート→Aさん→Cさん→Bさん→ゴール（70分）
- スタート→Bさん→Aさん→Cさん→ゴール（60分）
- スタート→Bさん→Cさん→Aさん→ゴール（70分）
- スタート→Cさん→Aさん→Bさん→ゴール（60分）
- スタート→Cさん→Bさん→Aさん→ゴール（80分）
この場合は、Bさん→Aさん→Cさんの順番、または、逆の順番でCさん→Aさん→Bさんの順番で家庭訪問するのが一番早そうです。
生徒が３人の場合は、家庭訪問の順番は６通りでしたが、生徒の数が増えると家庭訪問の順番は何通りになるでしょうか？
- 生徒が３人の場合：6通り（3×2×1=6）
- 生徒が４人の場合：24通り（4×3×2×1=24）
- 生徒が５人の場合：120通り（5×4×3×2×1=120）
- 生徒が６人の場合：720通り（6×5×4×3×2×1=720）
- 生徒が７人の場合：5,040通り（7×6×5×4×3×2×1=5040）
・
・
・
- 生徒が30人の場合：約265,252,859,812,191,000,000,000,000,000,000通り（30×29×28×…×2×1）
とんでもない数になってしまいました。こうなると順番を考えるよりもさっさと行ったほうが早いですね。
コンピュータで計算すればいいじゃないか、と思われる方がいらっしゃるかもしれません。ちょっと考えてみましょう。
例えば、現在（2021年）日本で最高の性能を持つスーパーコンピュータは、毎秒44京2010兆回の計算ができるそうです。
TOP500は性能評価用プログラムの処理速度で性能を競う年2回のランキングで、今回は17日に発表された。富岳は毎秒44京2010兆回（京は1兆の1万倍）で、フルスペックまで整備を進めた結果、前回の41京5530兆回から向上。2位の米国「サミット」に約3倍の性能差をつけ圧勝となった。
https://scienceportal.jst.go.jp/newsflash/20201120_n01/
では仮に、1秒で44京2010兆通りの計算ができたとしましょう。生徒が30人の場合の順番を全部計算すると、600,106,015,276,105秒、つまり、約1900万年もかかります。やっぱり難しそうですね。
実際には、計算しなくていいところを計算しないようにして高速化する方法や、一番速い回り方じゃなくてもいいからそこそこ速ければいいという計算方法（近似解法）があり、現実的な時間で計算することができます。
そのほかの難しい問題
似たような問題の例として、「ナップザック問題」という問題があります。
例えば、遠足に持っていくおやつの合計金額が３００円までだったとします。家にいくつかの種類のおやつがあったとして、どのおやつを持っていけば好きなものを一番たくさん持っていけるかを考えます。
この問題も、家庭訪問と同じように、おやつの種類が増えれば増えるほど、持っていけるおやつの数が増えれば増えるほど、計算に時間がかかります。
ちなみに、出発地から目的地に行くのにどこを通っていくのが最短経路か？という問題は、家庭訪問に似ているような気がしますが、こちらは、コンピュータを使えば比較的速く解くことができます。この計算はカーナビなどで使われています。