Решение задачи коммивояжера с помощью 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.