TSP路線改善法
Tour
Improvement
| 啟發式解法必然有弱點，使用路線建構法所得到的路線可見到許多缺點有待改進。2-opt exchanges是常用的路線改善法，它先選擇兩段較長的路徑，從路線裡去除，然後設法以不同方式將殘缺的路線再接續起來。n取2的選擇非常多，因此改善的速度可能非常慢。下面的Java程式可以選擇兩種方式來建構路線：隨機插入(random insertion)與近鄰法(nearest neighbor)，然後再進行2-opt路線改善。 |
Epilogue
|
TSP由於問題定義明確易懂，可在短時間內上手並求得品質不錯的解答，但是要發展出品質極佳且速度合理的演算法相當困難，尤其是點的分佈型態千變萬化，能夠有效求解各種大型TSP問題(1000點以上)的演算法一直是研究者追求的目標。有意深造嗎？ |
本網頁參考自http://itp.nat.uni-magdeburg.de/~mertens/TSP/node3.html
原作者: Stephan Mertens