最短距離ではない巡回セールスマン問題

巡回セールス問題というと、与えられた点の全てを通る巡回路で一番距離が短いものということであり、下図のようなものを思い浮かべるであろう。

今回は、こういう普通のまっとうな巡回セールス問題ではなく、次図のような巡回セールス問題を考えてみよう。

この結果も、巡回セールスマン問題を解くプログラムで巡回路を最適化したものである。
正確に言うと、ほんのちょっとだけプログラムを変更した。

与えられた全ての町(点)を一度だけ通過しているので、巡回しているが、どうみても、距離が最短ではない。最短距離なら、巡回路が重なる場合には、さらに短い巡回路を簡単に作れる。

何だが、ぐるぐる回る巡回路になっているようだが、何を最適化したのだろうか？

殆どの巡回セールスマン問題を取り扱っている本では、巡回セールスマン問題を深く説明することがあっても、巡回セールスマン問題を多様に拡張する、あるいは抽象化することで、非常に多様な問題を解く基本的なアルゴリズムとして使えることの説明がほとんど皆無であり、とても残念である。

…ということで、ぐるぐる回る巡回路について、何を最適化しようとしたか、考えてみよう。

説明は、次回に行う。

（つづく）