基于分形法和聚類(lèi)相結(jié)合求解TSP問(wèn)題.pdf

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

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

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