巡回セールスマン問題を解く「山登り法」と「焼きなまし法」

前回記事では、巡回セールスマン問題を解く簡単な方法として、一番近い点に移動し続ける方法を紹介しましたが、さらに良い答えを出せる方法はあるのでしょうか。今回は、「山登り法」と「焼きなまし法」を紹介します。

山登り法とは

山登り法は、答えを少しずつ改善していくことで良い解を出すアルゴリズムです。具体的には、次のような処理を行います。

• 手順1：適当な答えを生成する （例：A, B, C, D, E, F, A の順に巡る）
• 手順2：答えに “少しの変更” を加え、もし答えが良くなれば変更を採用するということを数万回繰り返す。

ここで、どのような“少しの変更”を加えるかは人それぞれですが、巡回セールスマン問題の場合、以下のように、ある部分の移動順序を逆順にするという変更を加えると、上手くいくことが知られています^※1。

• 例1：移動順序 A, B, C, D, E, F, A を A, B, E, D, C, F, A にする
• 例2：移動順序 A, B, C, D, E, F, A を A, C, B, D, E, F, A にする

※1：このような方法は「2-opt法」と呼ばれています。