旅行商問題的兩種算法.pdf

1、旅行商(TSP)問題是組合優(yōu)化中最典型的NP-Hard問題之一，并且應用廣泛，如電路版印刷設計、交通調度等。目前關于該問題的啟發(fā)式算法主要分為兩類：環(huán)路構造算法和環(huán)路改進算法。 隨著現(xiàn)代科技的發(fā)展，旅行商問題的研究規(guī)模與難度越來越大，單一的算法已經(jīng)不能很好地解決問題。本文在參考大量關于啟發(fā)式算法論文的基礎上，給出了二種有效地改善啟發(fā)式算法解質量的算法，并闡述了它們的基本思想以及操作步驟，并用程序實現(xiàn)，最后指出了兩個算法的優(yōu)缺點和

2、今后的研究方向。 算法1 是在研究最近鄰算法、貪心算法、蟻群算法的基礎上，分析環(huán)路構造算法優(yōu)缺點和適用用范圍。針對環(huán)路改造算法針容易陷入局部最優(yōu)等缺陷，提出了先優(yōu)化距陣再進行計算的思路，可在提高解質量的同時降低各類環(huán)路構造算法的時間復雜度。 利用該思路設計的驗證算法，可徹解20個城市以內的旅行商問題，驗證算法雖然增加了歸零的矩陣等處理步驟，但計算用時更短，極大提高了程序效率。測試結果證明，歸零矩陣可以有效改善原始矩陣數(shù)據(jù)

3、的排序關系，使得最優(yōu)解的矩陣數(shù)值變小，有效改善矩陣陷阱，歸零矩陣啟發(fā)集規(guī)模得以減少。 算法2 是在討論環(huán)路改進算法中局部搜索、LK、LKH 等算法的基礎上，分析局部最優(yōu)解與全局最優(yōu)解之間關系，對局部最優(yōu)解進行了分類。設計一種可加入更多種局部最優(yōu)類型的算法：二點組合算法。對該算法程序進行了多角度測試，結果表明這個算法解決中小規(guī)模的旅行商問題是實用的。 本文從新的視角重新分析啟發(fā)式算法的基本原理和數(shù)學基礎，通過分析、研究環(huán)路