Данные для простого TSP

Question

Я написал простой генетический алгоритм, который может решить проблему коммивояжера с 5 городами. Я хочу посмотреть, как это происходит с проблемой с большим количеством городов, например, 10, 25, 50, 100, но я не могу найти образец даты для проблемы, чтобы попробовать. В принципе, я ищу 2D-списки или матрицы с расстояниями между городами. Было бы неплохо, если бы было решение. Где я должен смотреть?

Спасибо заранее

Answer 1

Я не уверен, но, как кажется, на странице «Read or Write Traveling Salesman Problem (TSP) Files» есть некоторые файлы входных данных, например, this one.

Кроме того, «TSP Test Data» является хорошим источником.

Answer 2

Известная библиотека тестов для TSP с экземплярами от 14 до почти 100 000 городов - TSPLIB. Экземпляры были решены до оптимальности, в некоторых случаях также доступно оптимальное решение.

Многие из примеров имеют реальный фон, такой как путешествия в городах Германии, Швейцарии, США или во всем мире. Некоторые из примеров представляют проблемы бурения для раскладки компьютерной платы. Также есть экземпляр, который представляет собой рейс Ulysses.

Answer 3

Источники, которые я нашел в Интернете, довольно велики. Я мог бы делать что-то неправильно, но 10 мест (городов) занимают ~ 0,6 с и 11 мест занимают ~ 7 с. Самый маленький набор данных известного решения, который я мог найти, был 15 мест (и считался «маленьким», «классический» - 48 мест), но, возможно, это для оптимизированных (не грубой силы) алгоритмов. В конце концов, я сделал свой собственный стол с реальными городами:

  m 
      a 
      a       h 
      s  h s    u 
      t a e i g   l 
      r a e t e   s 
      i c r t l e b b a  e 
      c h l a e c o e n o p 
      h e e r e h n r n h e 
      t n n d n t n g e e n 
maastricht 0 29 20 21 16 31 100 12 4 31 18 
    aachen 29 0 15 29 28 40 72 21 29 41 12 
    heerlen 20 15 0 15 14 25 81 9 23 27 13 
    sittard 21 29 15 0 4 12 92 12 25 13 25 
    geleen 16 28 14 4 0 16 94 9 20 16 22 
     echt 31 40 25 12 16 0 95 24 36 3 37 
     bonn 100 72 81 92 94 95 0 90 101 99 84 
    hulsberg 12 21 9 12 9 24 90 0 15 25 13 
    kanne 4 29 23 25 20 36 101 15 0 35 18 
     ohe 31 41 27 13 16 3 99 25 35 0 38 
     epen 18 12 13 25 22 37 84 13 18 38 0 

Optimal (by program): cities 0-7-4-3-9-5-2-6-1-10-8-0 = 253km 
maastricht -> hulsberg -> geleen -> sittard -> ohe -> kanne -> echt 
-> heerlen -> bonn -> aachen -> epen -> kanne -> maastricht 

Форматом данных для чтения программы является частичной таблицей (потому что это симметричный):

29 20 21 16 31 100 12 4 31 18 
15 29 28 40 72 21 29 41 12 
15 14 25 81 9 23 27 13 
4 12 92 12 25 13 25 
16 94 9 20 16 22 
95 24 36 3 37 
90 101 99 84 
15 25 13 
35 18 
38 

Для меня это занимает ~ 6,7 секунды для обработки на третьем поколении i7 (i7-3630QM). Программа написана на C++, однопоточная и просто грубая - возможности. Для тестирования было бы более целесообразным удалить одно место, тогда требуется ~ 660 мс (0,7 с), которого все еще достаточно, чтобы увидеть, изменились ли изменения кода.