こんにちは、お久しぶりです。ここまで全 16 回の連載では、主に一番良い答え （最適解と言います） を出すアルゴリズムについて紹介しました。例えば、第 15 回記事ではスタート地点からゴール地点まで移動する一番短い経路を求める「ダイクストラ法」というアルゴリズムを解説しました。

しかし世の中の問題の中には、最適解を出すのが極めて困難なものもあります。今回はその例として「巡回セールスマン問題」を紹介します。

巡回セールスマン問題とは

巡回セールスマン問題は、以下のような問題です。

いくつかの点があります。あなたは点 A から出発し、全ての点を通って点 A に戻らなければなりません。移動しなければならない合計距離は最小でいくつですか。（ただし、点と点の間の距離は直線距離※で計算するものとします）

下図の例の場合、答えは約 17.14 です。点 A→E→B→C→D→F→A の順に移動すると合計距離約 17.14 になり、それ以上短い経路は存在しません。

※2 点間の直線距離は次のように計算することができます。 上下方向の位置に a、左右方向の位置に b の違いがあった場合、距離は √(a2+b2)です。

巡回セールスマン問題の "問題点"

それでは、巡回セールスマン問題はどうやって解けば良いのでしょうか。一番簡単な方法は、あり得る経路を全て列挙することです。

しかし、この方法を使うと先程の例の場合でも、A→B→C→D→E→F→A、A→B→C→D→F→E→A、A→B→C→E→D→F→A などを含め、全部で 120 通りの経路を列挙する必要があります。コンピューターを使わなければ、かなり骨の折れる作業となるでしょう。

さらに、点の数が 10 になると調べなければならない経路の数は約 36 万通りになり、15 になると約 870 億通り、20 になると約 12 京通り (1 兆の 120,000 倍) にまで膨れ上がります。一般的な PC の計算速度は毎秒 10 億回程度なので、コンピューターをもってしても無理があるでしょう。

点の数 6 10 15 20
経路の数 120 362,880 87,178,291,200 121,645,100,408,832,000

巡回セールスマン問題の "さらなる問題点"

巡回セールスマン問題の厄介な点はこれだけではありません。他の問題では、もし全列挙では現実的な時間で答えを出せなくても、より良いアルゴリズムを使えば一瞬で答えを出せることも多いのですが、巡回セールスマン問題は残念ながら違います。

実際、この問題を解く最も効率的なアルゴリズムの1つとして「ビット DP」というものがあるのですが、これを使っても点の数が 40～50 程度になると、計算に膨大な時間がかかってしまうのです。

したがって、巡回セールスマン問題を解く際は、最適解 (一番良い経路) を求めるのを諦め、短時間でできるだけ良い経路を求めることを目指すアプローチがよく使われます。

できるだけ良い経路を求めるには

それでは、現実的な時間でできるだけ良い経路を求めるには一体どうすれば良いのでしょうか。一番簡単な方法は、「まだ訪れていない中で一番近い点に移動し続けること」です。以下に例を示します。

すると、合計距離約 19.65 で移動することができました。最適解の合計距離 17.14 に比べれば少し悪いですが、差が 15% 程度しかないことから、ある程度は良い経路が求められていると言えるでしょう。

*　*　*

今回は巡回セールスマン問題の解法として、一番近い点に移動し続けるという方法を紹介しました。しかし、さらに良い経路を求める方法もたくさんあります。次回の記事ではその方法として、「山登り法」と「焼きなまし法」を紹介します。ぜひ楽しみにしてください。