一種改進的求解TSP算法

《一種改進的求解TSP算法》是劉新撰寫的一篇論文。

基本介紹

• 中文名：一種改進的求解TSP算法
• 論文來源：湘潭大學
• 發表時間：2005-04-01
• 作者：劉新
• 分類號：TP301.6

論文摘要

TSP 問題是一個典型的NP-難問題,具有重要的理論價值和實際套用價值,多年來一直是學者們研究的熱點。由於大多數學者認為NP 問題不存在多項式時間內的完全算法,所以設計它的近似算法就具有相當重要的意義,而TSP 問題也成為了衡量近似算法效率的主要的標準。作者在充分研究了前人的各種算法的基礎上,分析了構造算法和調整算法的優劣,綜合設計出一種全新的近似算法,命名為“整體優先算法”。該算法以邊構造邊調整為基本思路,通過“大取”(即求取最大多邊形迴路作為初始路徑)、“近歸”(即把全部待接散點歸入最近的邊)、“遠接”(即求取整體最遠點的同邊最遠點接入閉合路徑)、“小調”(即進行路徑最最佳化調整使新接閉合路徑總距離最小)四個環節,逐步構造出最終的巡迴路徑。該算法的時間複雜度為O(n~3)。作者根據該算法編制出程式,對TSPLIB 上的部分數據進行了運算,結果令人滿意。不僅運行速度快(遠超過一般算法,僅次於貪心法),尋優能力也與主流算法不相上下,完全達到了預期目標。

引文格式

劉新. 一種改進的求解TSP算法[D].湘潭大學,2005.