2-optは、巡回セールスマン問題にて、nearest neighborルートを改善する方法である。
以下の動画を見ると、アルゴリズムの概要がわかる。
https://www.youtube.com/watch?v=UGGPZnAUjPU
もう少し具体的に説明すると、以下のようにA,B,C,D4点間のnearest neighborで作られたルート(AとB、CとDが繋がっている)の距離の総和に対して、AとD、BとCを繋げたルートの距離の総和の方が小さい場合、後者の新しいルートに置き換える。
・nearest neighborによるルート
・新しいルート
上記の例では、新しいルートのBC間の距離が短いため、距離の総和がnearest neibhorより小さい。そのためルートの置き換えをする。
このような4点間の距離の比較を繰り返すことにより、全体のルートを改善する。