巡回セールスマン問題
Traveling Salesman Problem（TSP）とも呼ばれる。与えられたグラフのすべてのノードを1度ずつ通る最短経路を求める問題。多くの場合、ノードの2次元位置座標が与えられ、ノード間の距離はそのユークリッド距離で与えられる。 Nearest Neighbor (NN)法
初期経路を構築するのに用いられる。任意のノードから出発し、もっとも手近にある未訪問ノードを順に辿っていく。
2-opt
適当な2つの辺を選び、それらを入れ替えることで全体の経路長を短縮できるか試す改善手法。互いに交差する辺であれば、かならず経路長は改善するが、わざわざ交差を検出する必要はなく、すべてのノード対に対して交換を試して改善するかみればよい。
3-opt
2-optと同様の改善を3つの辺に対して行う手法。
参考文献