基于分形法和聚類相結合求解TSP問題.pdf

1、旅行商問題(Traveling Salesman Problem)，縮寫為TSP，TSP問題是一個難于解決的著名數(shù)學難題之一。這個問題的特點就是易于描述但是隨著樣本點數(shù)目的增加，計算復雜度呈指數(shù)增加。TSP問題已經(jīng)被應用到很多領域，進而引出了求解TSP問題的重要性。但是有關TSP問題的求解，到目前為止還沒有任何一種算法能夠確切的在有限時間內(nèi)求得最優(yōu)解。
　　 本文提出了一種分形法和ISODATA聚類相結合去求解TSP問題。借助分

2、形思想和“分而治之”的策略，即把原本很多的城市數(shù)，先用ISODATA聚類算法進行聚類，每個小的聚類就成了另一個小的TSP問題，這樣就把大的TSP問題分解成了多個小的TSP問題。這樣，就將高冪指數(shù)算法問題轉(zhuǎn)換為多個低冪的指數(shù)算法問題。
　　 此外，本文介紹了兩個小規(guī)模TSP問題的處理算法，一個是窮舉算法，另外一個是局部最優(yōu)交換法算法。在局部最優(yōu)交換法中，提供了幾個局部判斷優(yōu)的交換策略和原則，例如兩點交叉交換策略、單點最近原則、雙點

3、最近原則等，并且理論證明了這些策略和原則的正確性。采用上述算法，對諸多小類以及各類之間進行求解，獲得最優(yōu)TSP路徑后，將各個小類連接起來。這樣將難于計算的復雜大問題采用“分而治之”的策略，簡化為多個易于計算的簡單問題，進而找到近似最優(yōu)解。
　　 通過對網(wǎng)上公布的TSPLIB測試庫中的Berlin52、St70、Ch150和Bayg29問題的求解，應用該課題提出的算法求解了4個TSP問題，試驗結果說明，得出的解優(yōu)于或者接近于網(wǎng)上公