天天看點

TSP旅行商問題1

TSP => Traveling Salesman Problem 旅行商問題

1、旅行商問題

旅行商每個城市都經過一次,又回到出發地;搜尋出旅行商所經過的最短路徑;

TSP旅行商問題1

6個城市将會有

5!/2=60

條路,因為經過城市1後有5個選擇,若選擇城市2,那麼經過城市2後有四個選擇,依次類推,經過第5個城市的時候隻有一種選擇,那就是最後一個城市,是以是

5*4*3=60

條路;

即n個城市有

(n-1)!/2

條路

TSP問題的原型即為哈密爾頓回路問題;

2、鑽孔規劃問題

決定在電路闆上鑽孔(為焊入部件)順序問題;鑽孔機總移動距離最小化機關時間内生産量最大化;

TSP旅行商問題1

3、不對稱旅行商問題

每個城市都經過一次,又回到出發點,搜尋出經過的最短路徑;但是,城市間的行走時間各不相同(行走世間的非對稱性);

TSP旅行商問題1

4、旅行商問題的變化

城市間距離:

非對稱TSP:城市間距離與方向有關

對稱TSP:城市間距離與方向無關

平面TSP:城市是平面上的點,城市間距離是2點間的直線距離

其他情況:

m人TSP: m人從出發點出發周遊所有城市

剛好通過各城市1次 -> 通過1次以上

通過各邊1次以上 = 中國郵差問題(Chinese Postman Problem)

繼續閱讀