TSP => Traveling Salesman Problem 旅行商問題
1、旅行商問題
旅行商每個城市都經過一次,又回到出發地;搜尋出旅行商所經過的最短路徑;
6個城市将會有
5!/2=60
條路,因為經過城市1後有5個選擇,若選擇城市2,那麼經過城市2後有四個選擇,依次類推,經過第5個城市的時候隻有一種選擇,那就是最後一個城市,是以是
5*4*3=60
條路;
即n個城市有
(n-1)!/2
條路
TSP問題的原型即為哈密爾頓回路問題;
2、鑽孔規劃問題
決定在電路闆上鑽孔(為焊入部件)順序問題;鑽孔機總移動距離最小化機關時間内生産量最大化;
3、不對稱旅行商問題
每個城市都經過一次,又回到出發點,搜尋出經過的最短路徑;但是,城市間的行走時間各不相同(行走世間的非對稱性);
4、旅行商問題的變化
城市間距離:
非對稱TSP:城市間距離與方向有關
對稱TSP:城市間距離與方向無關
平面TSP:城市是平面上的點,城市間距離是2點間的直線距離
其他情況:
m人TSP: m人從出發點出發周遊所有城市
剛好通過各城市1次 -> 通過1次以上
通過各邊1次以上 = 中國郵差問題(Chinese Postman Problem)