Escribí un algoritmo genético simple que puede resolver el problema del vendedor ambulante con 5 ciudades. Quiero ver cómo funciona en un problema con más ciudades, algo así como 10, 25, 50, 100, pero no puedo encontrar una fecha de muestra para probarlo. Básicamente, estoy buscando listas o matrices en 2D con distancias entre ciudades. Sería bueno si hay una solución. ¿Dónde debería mirar?Datos para TSP simple
gracias de antemano
No estoy seguro, pero como parece, la página "Read or Write Traveling Salesman Problem (TSP) Files" tener algunos archivos de datos de entrada, por ejemplo, this one.
Además, "TSP Test Data" es una buena fuente.
Gracias, sí, su primer enlace parece ser lo que estoy buscando. Vi cosas de "DATOS DE PRUEBA DE TSP", pero parecen contener demasiadas ciudades. – Akavall
Una conocida biblioteca de referencia para el TSP con instancias que van desde tan solo 14 a cerca de 100.000 ciudades es el TSPLIB. Las instancias se han resuelto de manera óptima; en algunos casos, la solución óptima también está disponible.
Muchas de las instancias tienen antecedentes del mundo real, como viajes, ciudades en Alemania, Suiza, EE. UU. O en todo el mundo. Algunas de las instancias representan problemas de perforación para el diseño de la placa de computadora. También hay una instancia que representa el viaje de Ulises.
Las fuentes que he encontrado en línea son bastante grandes. Podría estar haciendo algo mal, pero 10 lugares (ciudades) toman ~ 0.6s y 11 lugares toman ~ 7s. El conjunto de datos de soluciones conocidas más pequeño que pude encontrar fue de 15 lugares (y se consideró "pequeño", el "clásico" de 48 lugares), pero tal vez sean algoritmos optimizados (sin fuerza bruta). Al final hice mi propia mesa con las ciudades del mundo real:
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
El formato de datos legibles por el programa es una tabla parcial (porque es simétrica):
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
Para mí esto se lleva a ~ 6.7 segundos para procesar en una tercera generación i7 (i7-3630QM). El programa está escrito en C++, de un solo hilo y simplemente fuerza bruta las posibilidades. Para las pruebas puede ser más práctico eliminar un lugar, luego toma ~ 660ms (0.7s) que es suficiente para ver si los cambios en el código hacen una gran diferencia.
He probado mi solucionador de TSP y obtengo el mismo camino: D Estoy muy feliz :) – Kamil
Gracias :) Me ayudó y obtuve la misma respuesta :) –
¿Desea datos con soluciones exactas o solo datos? Siempre puedes construir tus propios conjuntos de datos si lo deseas. Además, ¿está buscando instancias Euclidean TSP o instancias de TSP arbitrarias? – templatetypedef
Si se incluyen soluciones, sería bueno. No sé qué son las instancias TSP euclidianas y arbitrarias. Estoy empezando. – Akavall
También puede crear conjuntos con soluciones conocidas para comenzar, por ejemplo, crear n puntos en un círculo. La mejor solución es atravesarlos en orden, y puede aproximar la longitud de camino ideal por la longitud del círculo. – Mathias