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

山登り法とは

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

  • 手順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法」と呼ばれています。

山登り法を体験してみよう

それでは、実際に手を動かして山登り法を体験してみましょう。まず、最初に適当な答え （ここでは移動順序 A, B, C, D, E, F, A） をつくります。

次に、3～5 番目 （C, D, E の部分）※2 を逆順にすると、下図のようになります。合計距離は 21.53 から 20.13 に改善したので、変更を採用します。

続いて、5～6 番目 （C, F の部分） を逆順にすると下図のようになります。合計距離は 20.13 から 22.63 に悪化してしまうので、変更を採用せず、元の移動順序 A, B, E, D, C, F, A に戻します。

次に、4～5 番目 （D, C の部分） を逆順にすると、下図のようになります。合計距離は 20.13 から 18.24 に改善するので、変更を採用します。

次に、5～6 番目 （D, F の部分） を逆順にすると、下図のようになります。合計距離は 18.24 から 22.07 に悪化してしまうので、変更を採用せず、元の移動順序 A, B, E, C, D, F, A に戻します。

最後に、2～4 番目 （B, E, C の部分） を逆順にすると、下図のようになります。合計距離は 18.24 から 17.63 に改善されるので、変更を採用します。

以上の 5 回のステップを行うことで、合計距離を 17.63 まで改善することができました。前回記事で紹介した方法では合計距離 19.65 までしか行かなかったので、山登り法はかなり良いアルゴリズムであると言えます。

※2： 3～5 番目といった “変更する部分” は、適当に選んでかまいません。（必ずしも最初の変更が 3～5 番目である必要はありません。）

山登り法の問題点

しかし、山登り法にも問題があります。それは、まだ最適解ではないのにもかかわらず、どんな “小さな変更” を加えてもスコアが改善しない「ニセの最適解」にハマってしまうことです。

例えば、前項の最後の図 (合計距離 17.63) の場合、本当はこれよりもっと良い答えが存在するのにもかかわらず、どのような小さな変更を行っても (つまりどの部分を逆順にしても) 合計距離がむしろ長くなってしまいます。

焼きなまし法とは

そこでこの問題を解決する方法として、焼きなまし法があります。焼きなまし法は、もし答えが悪化しても、一定の確率で変更を採用するというアルゴリズムです。

しかし、大きく答えを悪化させる変更をするのは良くないので、距離が 1 長くなったら 30% の確率で変更を採用、距離が 2 長くなったら 10% の確率で採用、距離が 3 長くなったら 1% の確率で変更を採用といったように、悪化が小さいほど採用確率を上げるのが鉄則です。

焼きなまし法を使うと、点の数が 100 や 200 といった大規模な巡回セールスマン問題でも、合計距離が最適解よりたった数パーセントしか長くない、非常に良い答えを出すことができます。

*　*　*

ここまで長い道のりでしたが、以上の全 18 回の連載で、競技プログラミングをやる上で必須の基本的なアルゴリズムは全て紹介し終えました。これで競プロ入門の免許皆伝となります。お疲れ様でした。

残りの 6 回の記事では、いくつかの発展的なアルゴリズムや、筆者が競プロの大会で戦った体験などについて記します。ぜひお楽しみください。