用 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。