Решение задачи коммивояжера в R

Для решения задачи коммивояжера в R-project можно использовать пакет TSP:

> library("TSP")
# Заполним матрицу расстояний между городами…
> m <- matrix(c(0,   222, 652, 52,  447, 160, 445, 134, 380, 112, 536, 
+               222, 0,   594, 170, 565, 278, 223, 252, 322, 230, 654,
+               652, 594, 0,   600, 995, 708, 817, 682, 272, 660, 1084,
+               52,  170, 600, 0,   395, 108, 393, 82,  328, 60,  484,
+               447, 565, 995, 395, 0,   503, 340, 313, 723, 455, 519,
+               160, 278, 708, 108, 503, 0,   501, 190, 436, 48,  592,
+               445, 223, 817, 393, 340, 501, 0,   475, 545, 453, 877,
+               134, 252, 682, 82,  313, 190, 475, 0,   410, 142, 402,
+               380, 322, 272, 328, 723, 436, 545, 410, 0,   388, 812,
+               112, 230, 660, 60,  455, 48,  453, 142, 388, 0,   544,
+               536, 654, 1084, 484, 519, 592, 877, 402, 812, 544, 0),
+             nrow=11, byrow=TRUE)
> colnames(m) <- c("Воткинск", "Глазов", "Екатеринбург", "Ижевск", "Казань",
+                  "Камбарка", "Киров", "Можга", "Пермь", "Сарапул", "Уфа")
> rownames(m) <- colnames(m)
> m
             Воткинск Глазов Екатеринбург Ижевск Казань Камбарка Киров Можга Пермь Сарапул  Уфа
Воткинск            0    222          652     52    447      160   445   134   380     112  536
Глазов            222      0          594    170    565      278   223   252   322     230  654
Екатеринбург      652    594            0    600    995      708   817   682   272     660 1084
Ижевск             52    170          600      0    395      108   393    82   328      60  484
Казань            447    565          995    395      0      503   340   313   723     455  519
Камбарка          160    278          708    108    503        0   501   190   436      48  592
Киров             445    223          817    393    340      501     0   475   545     453  877
Можга             134    252          682     82    313      190   475     0   410     142  402
Пермь             380    322          272    328    723      436   545   410     0     388  812
Сарапул           112    230          660     60    455       48   453   142   388       0  544
Уфа               536    654         1084    484    519      592   877   402   812     544    0
# … создадим TSP-объект…
> tsp <- TSP(m)
# … и найдем решение методом "2-opt":
> tour <- solve_TSP(tsp, method="2-opt")
> tour
object of class ‘TOUR’ 
result of method ‘2-opt’ for 11 cities
tour length: 3080
# Получаем замкнутый маршрут, заданный списком городов по порядку обхода.
> labels(tour)
 [1] "Камбарка"     "Сарапул"      "Ижевск"       "Екатеринбург" "Пермь"        "Глазов"      
 [7] "Киров"        "Казань"       "Уфа"          "Можга"        "Воткинск"
> 48+60+600+272+322+223+340+519+402+134+160
[1] 3080

Существует альтернативный способ создания таблицы расстояний, с заполнением только нижней ее половины:

> m <- structure(c(222, 652, 52,  447, 160, 445, 134, 380, 112, 536,
+                  594, 170, 565, 278, 223, 252, 322, 230, 654,
+                  600, 995, 708, 817, 682, 272, 660, 1084,
+                  395, 108, 393, 82,  328, 60,  484,
+                  503, 340, 313, 723, 455, 519,
+                  501, 190, 436, 48,  592,
+                  475, 545, 453, 877,
+                  410, 142, 402,
+                  388, 812,
+                  544), 
+                Labels = c("Воткинск", "Глазов", "Екатеринбург", "Ижевск", "Казань",
+                           "Камбарка", "Киров", "Можга", "Пермь", "Сарапул", "Уфа"), 
+                 Size = 11L, class = "dist", Diag = FALSE, Upper = FALSE)
# Результат:
> m
             Воткинск Глазов Екатеринбург Ижевск Казань Камбарка Киров Можга Пермь Сарапул
Глазов            222                                                                     
Екатеринбург      652    594                                                              
Ижевск             52    170          600                                                 
Казань            447    565          995    395                                          
Камбарка          160    278          708    108    503                                   
Киров             445    223          817    393    340      501                          
Можга             134    252          682     82    313      190   475                    
Пермь             380    322          272    328    723      436   545   410              
Сарапул           112    230          660     60    455       48   453   142   388        
Уфа               536    654         1084    484    519      592   877   402   812     544

Отличий в использовании такой таблицы нет.