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가 됩니다.