2-opt其實是2-optimization的縮寫，簡言之就是兩元素最佳化。也可以稱作2-exchange 。
2-opt algorithm最早是由 croes發表在Operations Research上的一篇名為A Method for Solving Traveling-Salesman Problems的論文（該論文可在OR資料庫付費下載）中提出的。最初是用於解決TSP問題的算法。
簡介,2-opt歸屬,2-opt舉例,2-opt的推廣,備註,
簡介
2-opt其實是2-optimization的縮寫，簡言之就是兩元素最佳化。也可以稱作2-exchange 。
2-opt algorithm最早是由 croes發表在Operations Research上的一篇名為A Method for Solving Traveling-Salesman Problems的論文（該論文可在OR資料庫付費下載）中提出的。最初是用於解決TSP問題的算法。
2-opt歸屬
2-opt屬於局部搜尋算法，局部搜尋算法（local search algorithm）是解決組合最佳化問題的有效工具。1986年，Glover對局部搜尋算法進行推廣衍生，提出了禁忌搜尋算法（tabu search algorithm），如今已經廣為人知並且在組合最佳化領域中得到了廣泛的套用。
2-opt舉例
這裡我們就舉一個2-opt算法最原始套用的例子——解決TSP問題：
假設有一個旅行商必須要從A城市出發經過BCDEFGH這幾個城市最後回到A城市(可以理解為約束條件)，目標函式是路程最短(更廣義的說是 費用最少)。
首先我們可以任選一個可行解s={A,B,C,D,E,F,G,H,A}，並假設s是最優解Smin。然後使用2-opt算法進行問題的求解：隨機選取兩點i和k，將i之前的路徑不變添加到新路徑中，將i到k之間的路徑翻轉其編號後添加到新路徑中，將k之後的路徑不變添加到新路徑中。
原路徑: A ==> B ==> C ==> D ==> E ==> F ==>G ==> H ==> A
i = 4, k =7
新路徑:
1. (A ==> B ==>C)
2. A ==> B ==> C==> (G ==> F ==> E ==> D)
3. A ==> B ==> C==> G ==> F ==> E ==> D (==> H ==> A)
從而獲得一個新的可行解。將可行解代入目標函式可得目標函式值，將其與Smin的目標函式值比較，取兩者目標函式值較小的可行解為Smin，直到找不到比Smin還小的函式值為止。至此，該TSP問題已用2-opt算法解決。
2-opt的推廣
很容易將2-opt算法推廣到k-opt算法，即將上例s中的k個元素進行調換，以更換可行解並檢驗其在目標函式中的優度。
2-opt也叫2-exchange方法。或者說k-exchange，其中k≥2 。
