巡回セールスマン問題(traveling salesman problem, TSP)は、都市(頂点)を一回ずつ一筆書きのように通るとき、コスト(例えば経路長)を最小化する問題である。TSPの近似解を求める方法として2-optがある。競技プログラミングのマラソンマッチではた...