Я написал простой генетический алгоритм, который может решить проблему коммивояжера с 5 городами. Я хочу посмотреть, как это происходит с проблемой с большим количеством городов, например, 10, 25, 50, 100, но я не могу найти образец даты для проблемы, чтобы попробовать. В принципе, я ищу 2D-списки или матрицы с расстояниями между городами. Было бы неплохо, если бы было решение. Где я должен смотреть?
Благодарим вас в Advance
Я не уверен, но, как кажется, на странице " "Чтение или запись сообщений о проблемах продавца (TSP)" есть некоторые файлы входных данных, например, этот.
Кроме того, "TSP Test Data" является хорошим источником.
Известная тестовая библиотека для TSP с экземплярами от 14 до почти 100 000 городов - это TSPLIB. Экземпляры были решены до оптимальности, в некоторых случаях также доступно оптимальное решение.
Многие из примеров имеют реальный фон, такой как путешествия в городах Германии, Швейцарии, США или во всем мире. Некоторые из примеров представляют проблемы с буровым раствором для раскладки компьютерной платы. Также есть экземпляр, который представляет собой рейс Ulysses.
Источники, которые я нашел в Интернете, довольно велики. Я мог бы делать что-то неправильно, но 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 с), которого все еще достаточно, чтобы увидеть, не изменились ли изменения кода.