使用 Mathematica 解決旅行推銷員問題

問題

電車でこんな広告を見かけました😁📸 pic.twitter.com/iXEgvtXrpL
— 早稲田大学早水桃子研究室 (@hayamizu_lab) October 11, 2022

解法

1
d=SparseArray[{{1,2}->10,{2,1}->10,{1,5}->15,{5,1}->15,{1,4}->12,{4,1}->12,{1,3}->20,{3,1}->20,{2,5}->10,{5,2}->10,{3,4}->10,{4,3}->10,{3,8}->30,{8,3}->30,{3,7}->20,{7,3}->20,{3,6}->25,{6,3}->25,{4,5}->15,{5,4}->15,{4,8}->20,{8,4}->20,{5,9}->18,{9,5}->18,{5,8}->15,{8,5}->15,{6,7}->5,{7,6}->5,{7,8}->35,{8,7}->35,{8,9}->12,{9,8}->12},{9,9},Infinity];

使用 SparseArray 函數建立矩陣。每個元素代表該元素的行與列對應城市之間的距離。例如，第一個元素 {1,2}->10 表示 1 和 2 之間的距離是 10。倒數第二個元素 {9,9} 表示矩陣的大小，最後一個元素 Infinity 表示未指定城市之間的道路長度無限大。也就是說，意味著沒有道路。

1
{len,tour}=FindShortestTour[{1,2,3,4,5,6,7,8,9},DistanceFunction->(d[[#1,#2]]&)]

透過 FindShortestTour 函數，可以輕鬆解決旅行推銷員問題。{1,2,3,4,5,6,7,8,9} 代表城市編號。DistanceFunction->(d[[#1,#2]]&) 傳遞了代表城市之間距離的矩陣 d。

輸出

1
{137, {1, 2, 5, 9, 8, 7, 6, 3, 4}}

輸出為最短距離及當時的巡迴路線。最短距離為 137，巡迴路線為 1→2→5→9→8→7→6→3→4→1。按照 ABC 順序轉換後，將變為 A, B, E, I, H, G, F, C, D。