最適解を出すのが困難な「巡回セールスマン問題」

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

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

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

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

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

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

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