Ya hablamos bastante al respecto... te presenté algunos algoritmos.
De cara a un algoritmo, no importa el tipo de programación empleado, uno siempre puede moverlo a 'su terreno'.
En general, muchos de los algoritmos dicen resolverlo en 'n * n^3'... se teoriza que podría ser resuelto satisfactoriamente en ese tiempo (aunque no pueda comprobarse ser exacto).
Yo los algoritmos que he desarollado lo resuelven en log(n) * n^2, pero para tanto como 10.000 puntos, puede tardar entre 30 y 60 minutos... para decenas de puntos, no llega a 1sg. para 100 de puntos tarda unos 5-15 segundos. psra unos 1.000 puntos entre 40-60 sg. (siempre sin compilar), el resultado final de dibujarlo nunca forma parte del tiempo, evidentemente.
Lógicamente no hay forma de saber si la solución es exacta. Ya que cuando encuentras una forma de demostrar que no es exacto, en realidad has encontrado un nuevo método que aplicar al algoritmo y mejorar la solución y así se entra en un bucle, donde los tiempos se incrementan a cambio de mejorar un porcentaje muy pequeño (razón por la que algunos van en n^3 y yo en n^2, probablemente se consiga algo mucho más exacto pero con un tiempo n^4, n^5... Yo soy de los que teoriza (y así me lo apunta también mi intuición), que existe solución en tiempo polinómico y por tanto P = NP.
- Fuerza bruta: En la otra conversación, como inicialmente interesa saber si la solución que dabas era exacta, la única forma de proceder era con fuerza bruta (también porque era un número limitado de puntos y accesible en cálculo de tiempo). El tiempo con fuerza bruta es altamente costoso, inasumible como sabes con solo unas pocas decenas de puntos, incluso para el supeordenador más potente del mundo.
- Vecino más cercano: Luego te explicaba que incluso la fuerza bruta podía ser mejorada siguiendo el algoritmo del 'vecino mas cercano no visitado aún', es decir en vez de empezar el recorrido con la ruta aleatoria (en el modo en que vengan ordenados los puntos), buscas el más cercano al primero, luego el más cercano a ese que encontraste para el primero, etc... esa primera ruta, ya delimita mucho las siuientes ciudades que se deben viisitar... Se estima que la trayectoria del vecino más cercano puede rondar en alrededor del 125% de la solución exacta.
A veces esta opción es utilizada con frecuencia, pués calcularla es muy rápido, lo que se hace es elegir varias veces (pongamos 6-12) un punto al azar y trazar así la trayectoria para cada caso, se toma luego aquella que arroje el menor resultado.
Hay varios algoritmos que encajan en la 'efinición' de 'vecino más cercano'... pero casi cualquiera para empezar puede ser lo suficientemente bueno.
https://en.wikipedia.org/wiki/Nearest_neighbour_algorithmhttps://en.wikipedia.org/wiki/Greedy_algorithm- También te comentaba una heurística que que divide en regiones el 'mapa':
Hay varios... pero siempre se trata de heurísticas, pués como te dije no hay solución conocida al margen de la fuerza bruta.
Uno bastante asequible de implementar es:
---------------------------------------------------------
1 - Dividir el área en sectores (3x3 típicamente).
2 - Mientras cada sector tenga más de x nodos (5 o 6 típicamente), subdividir el sector de nuevo en más sectores (es una función recursiva, como se desprende).
3 - Cada sector finalmente se resuelve por fuerza bruta (5 o 6 nodos es algo muy rápido de resolver por fuerza bruta).
4 - Finalmente se van uniendo los sectores entre sí (haciendo optimizaciones al tiempo)
Esta última parte es la más compleja pues permite cierto margen de maniobra. Si el número de sectores al hacer la división no queda claramente acotado (esto es si son demasiados), se complica tomar decisiones, por eso la limitación de 3 es considerada muy aceptable.
- Heurísticas de intercambio: Luego te expuse un ejemplo de intercambios... en realidad son toda una serie, aunque 3-4 son los mejores.
Se trata de analizar segementos comparando la distancia actual entre 2-3 de ellos e intercambiándolos, si la distancia resultante es menor, se acepta el cambio, si no se sigue buscando.
Estos derivan en varios modelos, como ya te sugerí en su momento, pero por si no los exploraste suelen llamarse 2opt y 3opt.
El 2opt es muy exhaustivo y consume más tiempo, pero resuelve lentamente hasta probablemente menor de un 105%. Para una cantidad pequeña de puntos (hasta unos cientos, puede incluso encontrar la solución óptima (pero sin modo de saberlo, claro). El problema d ela lentitud de 2opt, es que encontrado dicho intercambio, deben también intercambiarse todos los que median entre ambos del intercambio, si se opera con 100 puntos y pongamos que uno es el 30 y el otro el 80, hay que intercambiar entre el 30 y el 80 de orden... y así con cada intercambio, Pero si estás operando con uno de 1.000.000 de puntos, imgina uno el 300.000 y otro el 800.000 todos en medio deben intercambiarse.
El 3opt, es una mejorar pero también es más complejo de desarrollar (no mucho más para alguien que sepa programar, por supuesto).
https://en.wikipedia.org/wiki/2-opthttps://en.wikipedia.org/wiki/3-opt2opt y 3opt, son la base principal del algoritmo Concorde, que se ha utilizado ampliamente desde hace décadas ya (y que se ha ido mejorando), luego te busco algún enlace y lo pongo al final.
Yo he diseñado alguno más sobre intercambios, los aplico antes y así, el 2opt, no tiene que encontrarse tantos intercambios (que para él son más costosos), por ello como paso final el 2opt, es excelente.
- Algoritmo de Crhitofides: También en aquel hilo creo recordar haberte mencionado este algoritmo. Lo interesante de éste es que fue el primero en establecer la importancia de satisfacer la desigualdad triangular. Y durante mucho tiempo fue el único que estuvo 'reinando' en solitario, hasta que algunos autores (Dantzig) mencionaron precisamente que solo con 'intentos' de intercambio', resultaba fácil optimizar el resultado partiendo incluso de una solución previa. Es allí al fragor de todo esa emocionate historia, cuando empieza a fraguarse el algoritmo Concorde.
https://en.wikipedia.org/wiki/Christofides_algorithm- Heurística de Lin-Kernighan: (No confundir con el algoritmo del particionado de grafos, es fácil enrevesarse en ello).
https://en.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristicPor otro lado hay un montón de documentación de la que puedes empaparte, leer, implementar, experiementar, descubir... basta buscarlo. O quizás me anime un día y busque en alguno de mis discos y los suba el repositorio del foro...
Página del algortimo Concorde: Tienes las fuentes del algoritmo, y muchas explicaciones detalladas. Es una página imprescindible para todo forofo de estos temas.
https://www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htmEs necesario leerse siempre la historia, aunque sea repasarlo por encima para notar como ha ido evolucionando y no perderse detalles que pueden parecer insignificantes, pero que de repente te aparece la inspiración:
https://en.wikipedia.org/wiki/Travelling_salesman_problemEn youtube mismo tienes muy buenos vídeos que también pueden ayudarte:
https://www.youtube.com/watch?v=GiDsjIBOVoA&pp=ugMICgJlcxABGAHKBQQyb3B0https://www.youtube.com/watch?v=UAEjUk0Zf90&pp=ygUEMm9wdA%3D%3Dhttps://www.youtube.com/watch?v=-6pWTdkhOgg&pp=ygUEMm9wdA%3D%3Dhttps://www.youtube.com/watch?v=42edM3ZQigk&pp=ygUEMm9wdA%3D%3Dhttps://www.youtube.com/watch?v=GQQfihTNhso&pp=ygUEMm9wdA%3D%3Dhttps://www.youtube.com/watch?v=tI2YV7eRE9s&pp=ygUEMm9wdA%3D%3Dhttps://www.youtube.com/watch?v=STbkQbsIYVQ&pp=ygUSQ29uY29yZGUgQWxnb3JpdGhthttps://www.youtube.com/watch?v=9QxQW9ZfqNc&pp=ygUSQ29uY29yZGUgQWxnb3JpdGhtBill Cook, se explica muy bien, y se extiende:
https://www.youtube.com/watch?v=Q-BTOKr8t7Q&pp=ygUSQ29uY29yZGUgQWxnb3JpdGhthttps://www.youtube.com/watch?v=q8nQTNvCrjE&pp=ygUPVFNQIC0gQmlsbCBDb29rhttps://www.youtube.com/watch?v=tChnXG6ulyE&pp=ygUPVFNQIC0gQmlsbCBDb29rhttps://www.youtube.com/watch?v=kxvHXt7V4Jk&pp=ygUPVFNQIC0gQmlsbCBDb29rhttps://www.youtube.com/watch?v=-rtvsiPNYW0&pp=ygUPVFNQIC0gQmlsbCBDb29rhttps://www.youtube.com/watch?v=pyVvSwh6Nps&pp=ygUPVFNQIC0gQmlsbCBDb29rY para ir terminando te pongo algunas imágenes y comento por encima:
Como se ve, el resultado deja que desear, todas esas líneas que se cruzan, las resuelve el 2opt.
Un mapa con 10.000 puntos (al azar), el coste final dio: 37.020
Este mapa, es con el trazado del 'vecino más cercano'. Puede verse líneas largas que van lejos, lo que suele suceder cuando todos los más cercanos a uno dado ya están ocupados. Pero como punto de partida suele ser lo mejor.
Ejemplo del trance 2opt: Véase las líneas que secruzan. Siempre que se cruzan se puede saber que es optimizable. Se han trazado a mano 2 pares de líneas alternativas, si se elige el conjunto el conjunto d elas amarillas, se forman 2 rutas inconexas (el algoritmo Concorde hace esto y luego iterativamente lo va resolviendo), yo por ejemplo he preferido tomar el par de color azul, es fácil saber cuales son, pues en la actualidad una conecta con ella y todas las que median deben intercambiarse de orden.
Aquí y allá puedes encontrar variantes que vale explorar...
Un mapa con 100 puntos y un coste de 4034. No es la óptima... Mira la siguiente que es el mismo mapa.
El mismo mapa que el anterior, diferente ruta, el cosot es de 4035 solo 1 más que el anterior. Puede verse un cruce (no se había aplicado aún el 2opt), es asumible que es bastante mejorable.
3.000 puntos. Aqui cada punto traza a los 11 vecinos más cercanos. Mis ideas tiran por este lado, no veo la necesidad de tener que conectar puntos más lejanos que cierta cantidad de vecinos, lógicamente que sea un punto el 90 más cercano para uno dado, no quita que para uno aislado ese sea (por ejemplo) el 3º más cercano)...
...y finalmente para terminar, hablemos de distancias y cálculos.
Nota que para meterse de lleno con el problema, suele ser acertado considerar la distancia euclidiana, pero cuando se tierne que llevar a un extremo técnico, conviene también tener las soluciones para la distancia de Manhattan (sumar la distancia de ambos ejes), también muchos brazos robóticos, mueven un eje sobre el otro (al mismo tiempo), el resultasdo es que el costo es solo el costo de la distancia mayor de los 2 ejes (la distancia corta llegó antes). De igual modo debe asumirse casos para 3 dimensiones. Aunque en este caso, se provee también la distancia del 3 eje. Es acertado usar una interfaz 'medida' entre 2 puntos, tener implementaciones de cada caso y luego según el sistema como un parámetro de entrada se pasa el tipo de medida, instanciando la implementación a usar, no supone ningún costo en usar el agoritmo, ni supone tener que rehacer el algortimo con 20 versiones... una para cada caso.
Un simple consejo para acelerar aún más los cálculos. Cuando operas con distancias de Euclides, para descubir si una ruta es más corta que otra, no es preciso usar las matemáticas completas:
d = Sqr(X^2 + Y^2)
Cuando se pretende comparar si AB + CD es más corto o largo que AC + BD... puede ahorrarse la raiz cuadrada:
d = X^+ y^2
La distancia por tanto solo se precisa cuando necesitas saber la distancia del trayecto total, pero no para comparar. Hay tantos cálculos que ahorrarse raíces cuadradas, sí o sí mejora el tiempo.
Espero que te sea útil....
p.d.: Recuerda no usar un mapa de distancias, por mucho que se ahorre hacer cálculos, solo vale para pequeñas cantidades, cuando tengas que operar con algo como 1.000 millones no puedes tener en memoria la distancia de 1000 millones a 1000 millones. siempre calcula, salvo que pretendas conformarte con un pequeño programa para resolver pocas decenas.
Autor
En línea
