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

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

Благодарим вас в Advance

Ответы

Ответ 2

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

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

Ответ 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). Программа написана на С++, однопоточная и просто грубая - возможности. Для тестирования было бы более целесообразным удалить одно место, тогда требуется ~ 660 мс (0,7 с), которого все еще достаточно, чтобы увидеть, не изменились ли изменения кода.