Foro de elhacker.net

Buenas, hace un tiempo hice un programa para resolver el problema mencionado en el titulo.

Quisiera saber que tan eficaz es para lo cual necesito compararlo con el metodo de solucion Branch and Bound, por lo cual necesito por si alguno tiene, sabe o conoce un enlace donde este el codigo del metodo recien mencionado aplicado para este problema. Si esta escrito en C mejor, ya que es con el cual hice mi programa.

Gracias.

No estará lo que buscas en GitHub???...

Saludos.

 :rolleyes: :o :rolleyes:

Hola, buscando encontre un codigo en el siguiente enlace https://www.geeksforgeeks.org/traveling-salesman-problem-using-branch-and-bound-2/ (https://www.geeksforgeeks.org/traveling-salesman-problem-using-branch-and-bound-2/).

Es correcto el codigo ese?

Gracias.

Es muy difícil verificar "que tan eficaz es" tu algoritmo comparado con otro para un problema cuya resolución no existe salvo la fuerza bruta.

Si tu algoritmo también sigue el método de ramificación y poda, el rendimiento de tu algoritmo, va a depender casi exclusivamente de la profundidad de conocimiento en el lenguaje usado. En casos así elegir la estructura de datos adecuada, puede suponer una gran diferencia aun cuando otras partes del algoritmo, no sean igual de eficientes.

Considera la eficiacia (para este caso) como la mejor aproximación al resultado real y la eficiencia o rendimiento como el tiempo empleado. Ambos son igual de deseables...
La eficacia en estos casos están basado en heurísticas y ahí es muy dependiente de los ejemplos usados. Es perfectamente posible que un algoritmo arroje mejores resultados con ciertos ejemplos respecto de otro algoritmo y peores resultados con otros ejemplos.

Por otro lado el mayor limitante para verificar la eficacia es el tiempo preciso para encontrar resultados allí donde el tiempo es una premisa mayor... para acotaciones limitadas, siempre podrá modificarse un algoritmo para arrojar mejores resultados, más aproximados a la solución real.
Con la eficiencia, pasa lo mismo. Hay algoritmos que son muy rápidos para un cierto orden y a medida que aumenta el orden, disminuye su eficiencia y viceversa (por ejemplo la 'búsqueda por el método de burbuja' es más eficiente que quicksort, para (por ejemplo) 100 elementos, es comparativamente similar con 1000 elementos, pero es notablemente deficiente con 1.000.000 de elementos). Dado la explosión combinatoria del problema del agente viajero, la eficiacia y eficiencia de un algoritmo frente a otro exige pruebas exhaustivas, precisamente en diferentes órdenes de tamaño, y la que mayor determine la eficacia es prohibitiva en el tiempo, aunque si para pocas es menor y con cada aumento en la complejidad, sigue una curva de menor, parece que no vaya a cambiar la tendencia. Aún así es fácil demostrar esto para la eficiencia, pero no para la eficacia (exactitud en el resultado), ya que no hay forma de valorar una eficacia basada en los resultados que se arrojen.

Si tienes una soluciones (hipotéticas, pongamos) como en la siguiente tabla:

nº de prueba  items en juego   solucion real   tu solucion su solucion
-------------------------------------------------------------------------------
1                 5                   500          500          500     
2                 10                 1800         1800         1800
3                 20                 4723         4723         4723
4                 40                22000        22000        22000
5                 80               110000       109000       109600
6                 160              456000        44000       438000
7                 320             1380000      1350000      1360000
8                 640             9000000      8880000      8879000
9                 1280           25000000     24820000     24840000

Como ves, cuando la cantidad de items es poca, la solución puede ser real, o variar muy levemente, pero a medida que aumenten los valores, y sobretodo dependiente de cada ejemplo, un algoritmo podría arrojar una solución más cercana a la real en un problema concreto y más elejada en otro.. entonce no hay forma de valorarlo con precisión para decidir que uno es más eficaz que otro. Más bien en estos casos, lo que se valoran son las premisas requeridas, en resumen se adapta a las necesidades que la situación exija. Por ejemplo el factor tiempo puede dar más peso... así un sistema que solucione en pongamos 10 segundos aunque el valor real pudiera ser menos preciso, puede ser preferible a otro sistema que arroja una mejor precisión pero que demore 5 minutos en dar dicha solución.
En este problema la precisión (eficacia) y el tiempo (eificnecia) están en contraposición y debe valorarse un equilibrio entre ambos.

Entiendo lo que me decis; pero dejando un poco de lado la eficiencia, no existe ningun programa que lo resuelva de manera eficaz, ademas de la fuerza bruta?

Es decir que tarde lo que tarde no hay programa que siempre encuentre la solucion mas optima?

Mi programa lo comprobe tanto de manera practica como logica (teorica). Es decir que siempre encuentra el valor mas optimo. De ahi a que sea lo suficientemente eficiente es otro tema.

No. Es un problema no resuelto.
No existe ningún algoritmo conocido al margen de la fuerza bruta que garantice la solución correcta.
Nota que el diseño de un algoritmo que lo resuelva debe resolver todos los casos (para ser tenido como tal), y no uno que solo resuelva casos demasiado simples (para estos casos siempre podrá crearse un algoritmo eficaz y aceptable en tiempo).

Se recurre a heurísticas (aproximación a la solución, pero sin poder saber realmente si es la solución real), como te comentaba al señalarte:

Te agradezco la pronta respuesta.

Y con respecto al programa que hice resuelve cualquier caso de manera eficaz sin importar digamos las ciudades ni los costos de los trayectos. Lo que no se si es lo suficientemente eficiente.

Te doy un ejemplo: para 23 ciudades en una computadora con un CPU de 4 núcleos se resuelve en un par de minutos.

Con casos de menos ciudades, por ejemplo hasta 13 ciudades, lo compare con la fuerza bruta y me daba el mismo resultado. Ademas comprobé que la parte lógica funcionara correctamente para que siempre, como dije recién, me de el resultado mas óptimo.

Bien...
Si crees haber creado un algoritmo que resuelva el problema, lo primero es asegurarte que es así.
Para ello genera muy diferentes ejemplos, calculas por fuerza bruta la solución y tiempo empleado y luego lo comparas con tu algoritmo (importa sobre todo que la solución sea correcta, pués el tiempo es de suponer que será más eficiente que la fuerza bruta, si esto último no fuere así, no solucionaría nada, obviamente).
Cuando lo anterior quede satisfecho, intenta ponerte en contacto con un centro que tenga un superordenador, pregúntales si tienen datos de algún problema del viajero cuya solución hayan calculado, pídeles los datos para algo como 1000, 100.000 y 10 millones (por ejemplo), cuando lo resuelvas con tu algoritmo, dales la solución para que la comparen con la que ellos obtuvieron, si no coincide, pide la solución donde no coincide (la comparación en primera instancia sería la medida total, fallando, conviene tener como solución la ruta seguida, de modo que tú mismo puedas comparar si la suma de ellos es errónea, aunque pudiera ser que el problema fuere debido a la precisión de los decimales (es habitual esta discrepancia cuando se usa un PC y se compara el resultado con los obtenidos en un superordenador cuya coma flotante es muy superior), es decir que quede claro si la discrepancia es debida a la cuestión de la precisión o a un error en tu algoritmo.

- Si la solución coincide perfectamente, plánteate primero registrar tu algoritmo (al menos la propiedad intelectual, que quede acreditada a tu nombre), luego según lo que quiesieres hacer debes operar, si quieres que quede libre, solicita ayuda técnica para publicar un paper a los que te ayudaron en el superordenador... y si quieres obtener beneficios, podrías ponerte en contacto con grandes empresas.
Es muy conveniente antes de esto, intentar optimizarlo, pues no faltará quien partiendo de tu algoritmo haga unos simples cambios (a veces obvios) y reclamar que hizo una mejora sustancial sobre tu algoritmo (en general suele pasar a la historia el autor del algortimo más óptimo, especialmente si los menos óptimos, son además muy engorrosos de implementar).
Al margen de ello, el instituto Clay ofrece una recompensa para los 'Problemas del Milenio', creo recordar que éste (no exactamente el problema, si no que su resolución demostraría que los problemas NP son equivalentes a los problemas P y que por tanto pueden ser resueltos en tiempo polinómico). Por supuesto ese 'paper' debieras crearlo antes, porque sería lo que al final entregarías para reclamar el premio. (prize.problems@claymath.org , admin@claymath.org Nota para Admins, no borrar emails, son públicos)

- Si la solución no coincide (y ya probaste que no fue debido a error en la precisión de decimales), intenta escrutar donde pudiera estar el problema y tratar de arreglarlo. Si lo consigues, considera el paso anterior.

Si la solución no coincide, y no consigues resolverlo, intenta al menos determinar hasta que tamaño tu algoritmo resulta válido, seguramente todavía tenga interés un algoritmo que resuelva eficientemente (la fuerza bruta es muy ineficiente), para un número medio de nodos (pongamos entre cientos y pocos miles, pues cosas como semáforos, paradas de buses, etc... andan en esos términos). Simplemente sería un 'algoritmo menor del agente viajero' y a buena fé podría dar pistas a otros para intentar partiendo del mismo una solución total.

Considera que aunque se diga 'fuerza bruta' a menudo es razonable no practicarla en su totalidad, si no que puede ser podada... por ejemplo mi intuición me dice que en la práctica si los nodos tienen una distribución uniforme, bastaría con considerar para cada nodo la raíz cuadrada de los nodos, luego estos se escogerían entre los x más cercanos al mismo.
Resulta obvio lo absurdo de considerar cualquier ruta cuyo tramo parcial consista en ir de un nodo al nodo más lejano a éste, lo cual se puede descartar para todos los nodos, igualmente podría decirse lo mismo para el penúiltimo más lejano, etc... no queda claro el punto donde esto deja de ser cierto (ya digo que mi intuición me señala que es la raíz cuadrada aprox. para una distribución más o menos uniforme, como regla general).

Eso sí... prueba también con nodos cuya posición sea elegida al azar dentro de un área dada, para garantizar que no hay cierto vicio en los mapas seleccionados.

Tengo por ahí un programa de grafos para resolver determinados problemas, creo que se podría ajustar perfectamente para hallar soluciones por fuerza bruta (en realidad cortocircuita una ruta cuando la suma de un nodo supera la longitud de un trayecto que previamente ha sido más corto). Quizás tuviera que reajustarlo, porque creo recordar que lo hice para operar con pesos de valor entero (no con decimales)... Además tampoco precisa recorrer todas las rutas, ya que A-B-C es equivalente a C-B-A, a lo sumo precisa explorar = (((n-1)*2)/2) rutas.
...para nodos de pocas decenas calcularía perfectamente la solución en un tiempo asumible, así que si precisas comparar tus resultados, basta que me pases un mapa (una tabla de los nodos con las distancias al resto de ellos). Así se podría comparar si efectivamente tu algoritmo genera la solución óptima.

Ese sistema es muy laaaaaargo de definir y sobretodo de interpretar al programarlo, pues va a requerir rellenar huecos...

No es necesario que me lo mandes por privado, son simplemente datos, cifras, nada que requiera discrección, de hecho si se deja público puede que alguien más se anime a hacer un cálculo por su cuenta... o pruebe con su propia solución... y te dé 'su solución'.

Una tabla es sencilla de hacer.... te paso un dibujo de ejemplo, pero tú debes anotarlo en un fichero de texto, que luego yo pueda leer desde el programa para cargar los datos... meterlo manualmente tiene el riesgo de error en la introducción de datos, aparte de lo tedioso de la introducción manual que supone cuando los datos son varios.

Un ejemplo y te comento brevemente:
(https://i.imgur.com/GtWNyp8.png)
Cada número supone el nodo enésimo representado por el número en su fila o columna. Nota que los números de fila y columna en la imagen están solo por claridad, en el fichero es preferible omitirlos, su orden de ubicación lo representa y es suficiente, si no, exige filtrarlo.

Cada fila representa un nodo (ciudad por ejemplo), y a su derecha se señala la distancia que hay de él a cada uno de los nodo bajo cuya columna se ubica.
En la imagen se observa que solo he rellenado las distancias que parten del nodo 4 al resto de nodos: Al nodo 1 hay una distancia de 15, al nodo 2 una distancia de 22, al nodo 3 una distancia de 36, al nodo 4 (a sí mismo), una distancia de 0 (pero que he marcado como 'x', todos los nodos a sí mismo tienen igual valor representan la violación de pasar 2 veces por él mismo...), al nodo 5 hay una distancia de 81, al nodo 6 de 54... ...y finalmente al nodo 13 de 61.

Como ves cada nodo ocupa una fila, lo que se traduce en el fichero de texto como una línea de texto, al final de la misma un salto de línea (no te preocupes si tu sistema exige salto de línea y avance de carro, o solo uno de dichos caracteres (diferencias entre win2, mac y Linux) ya lo determino yo mismo al cargar el fichero al programa).
Separa la distancia entre nodos en el fichero con un simple espacio (no te preocupes si en alguno pusiste 2 o más espacios, se filtrarán)...

Al final guarda el fichero, verifica que esté correctamente editado, lo comprimes en zip (para evitar que sea manipulado), lo subes a una página de descarga y publicas el enlace.

Si el texto fuera muy pequeño (pongamos 10-20 nodos), y las líneas no muy largas puedes copiar el texto una vez completo el fichero y pegarlo directamente aquí en el foro entre etiquetas code...
Si las líneas son muy largas, incluso las etiquetas code pueden forzar saltos de línea, cuando una línea exceda x tamaño de longitud, aunque supongo que con etiquetas code el tamaño de línea será más generoso (que con eqtiquetas quote o que sin etiquetas).
...si se cortan automáticamente las líneas, falsea la interpretación de los datos a la hora de leerlos con un programa que entiende que los datos de un nodo están en una línea.
Si a pesar de todo las líneas fueran tan largas, que quedaren cortadas, entonces es preferible subir el fichero a alguna página de descargas y poner enlace y listo.

Con el ejemplo de la imagen, el fichero se vería así (nota que como solo he rellenado la fila 4, debe suponerse 3 filas por delante, y muchas más por detrás).

Gracias por la explicacion, aca te envio de manera mas aceptable.

La solucion que encontre como optima fue de 7561324 como costo de trayecto, cual seria el siguiente: 1-12-2-19-7-9-20-14-6-18-4-10-16-3-17-8-13-11-5-15-1.

Hola.

Hice algunos cambios para adaptarlo y lo puse anoche antes de irme a dormir a calcular, sigue calculando...

Nota que el programa está diseñado para mostrar cada solución que supera el límite previo... de ahí la lista de soluciones, cada línea siguiente supera la anterior acortando la distancia.

Sin embargo al venir a poner este mensaje me doy cuenta que tu diseño es 'circular', es decir, exige que tras visitar todas las 'ciudades' vuelva al origen.
En este programa adaptado mínimamente, no está considerado dicha opción... en realidad aún siendo el mismo problema son casos distintos y es conveniente tener (en tu algoritmo), un parámetro para indicar el caso y por tanto poder solucionar ambos.
Ya sacó las soluciones (omito las previas), dando como origen el nodo 1. Introduje los datos para considerar la ruta más corta sin consierar cual es la ciudad de origen (aunque lógicamente empieza en la 1 (A) y sin considerar regreso al nodo de origen.

Aunque veas que las soluciones que presento, ofrecen una distancia menor, considera el caso donde no se exige volver al origen (pero sigue visitando todas las ciudades), tiene por lo general (sobretodo si los datos son al azar), una solución más corta y no solo por eliminar el trayecto entre la última ciudad visitada y la ciudad de origen. Ya que al exigir la vuelta, ciertos nodos en su camino son evitados para poder 'volver'... por tanto no consideres aún fallida tu solución.

Mira de ver si puedes crear otro algoritmo equivalente donde no precise volver al origen (desde tu implementación (asumo que) esto debería serte relativamente sencillo, además es algo que sí o sí debes tener igualmente resuelto).
Desde mi programa no es más complejo si me hubiera percatado de ello al inicio... pues tira de grafos y el diseño está orientado a consideraciones generales aunque luego pueda especificar ciertos detalles... que deben darse como parametro en la entrada de datos.



Nota que el número asignado a cada nodo (1-20) ha sido remplazado por una etiqueta en el rango (A-T), pues de ese modo es más cómodo representarlo al ocupar cada uno un solo carácter (dígito) y también es más fácil de una simple ojeada distinguir letras de números (de los pesos)...


01-02-03-04-05-06-07-08-09-10-11-12-13-14-15-16-17-18-19-20
 A- B- C- D- E- F- G- H- I- J- K- L- M- N- O- P- Q- R- S- T

Si damos por hecho que se exige que la ciudad inicial sea la 1 (A), entonces los datos siguientes ofrencen la solución final. En realidad los datos de entrada están expuestos de tal manera, para continuar hasta que la última ciudad (nodo 20 (T)), fuere la ciudad de origen.
Soluciones (cada entrada (temporalmente la solución) supera la previa, se omiten las primeras (habría unas 50-100 soluciones temporales previas desde ABCDE...T con una distancia inicial de unos 22 millones):
...
1 ---> ABLHQCPJDRFNTIGSMKEO   8045241
1 ---> ABLKEOMHQCPJDRFNTIGS   8029724
1 ---> ABLMHQCDJPRFNTIGSKEO   7944387
1 ---> ABLMHQCPJDRFNTIGSKEO   7909997
1 ---> ABLOEKMHQCDJPRFNTIGS   7842256
1 ---> ABLOEKMHQCPJDRFNTIGS   7807866
1 ---> ABLSGITNFDJPRCQHMKEO   7771109
1 ---> ABLSGITNFRDJPCQHMKEO   7631457
1 ---> ABSGITNFDJPRCQHMLKEO   7573052
1 ---> ABSGITNFRDJPCQHMLEKO   7534083
1 ---> ABSGITNFRDJPCQHMLKEO   7433400
1 ---> AEKMHQCDJPRFNTIGSBLO   7397106
1 ---> AEKMHQCPJDRFNTIGSBLO   7362716
1 ---> AEKOLMBSGITNHQCFRDPJ   7359071
1 ---> AKEOLMBSGITNHQCFRDPJ   7346176
1 ---> ALBSGITNFRDJPCQHMKEO   7264340 <--- esta solución es la MISMA que la tuya (sin vuelta al origen):
1 ---> AOEKBLMHQCPJDRFNTIGS   7240895
1 ---> AOEKCHQMLBSGITNFRDPJ   7201363
1 ---> AOEKCQHMLBSGITNFRDJP   7150228
1 ---> AOEKCQHMLBSGITNFRDPJ   7028573
1 ---> AOEKLMBSGITNHQCFRDPJ   6991267
1 ---> AOEKMLBSGINTHQCFRDPJ   6963299
1 ---> AOEKMLBSGITNHQCFRDJP   6924025
1 ---> AOEKMLBSGITNHQCFRDPJ   6802370  <---- solución final: La ruta más corta partiendo del nodo 1, sin regreso al origen y sin especificar tampoco el nodo destino.




1 ---> ALBSGITNFRDJPCQHMKEO   7264340 <--- esta solución es la MISMA que la tuya (sin vuelta al origen): 1-12-2-19-7-9-20-14-6-18-4-10-16-3-17-8-13-11-5-15
Si a tu solución le quitamos la distancia entre las ciudades 15-1 (que es el caso que yo calculo), debería resulta lo mismo que lo que aquí aparece: 7561324 - 296984 = 7264340

Considera además que en una solución circular (como la que presentas), puedes cortar por el par de ciudades cuya distancia es mayor, al caso en tu solución circular esto sucede en los los nodos 7-9 y cuya distancia es 628171, y por tanto incluso así tendrías una solución más óptima con distancia de: 7561324 - 628171 = 6933153 ...pero como digo, sin considerar el regreso al origen hay soluciones más óptimas aún (salvo (generalmente) casos simétricos y otros que se diseñhacen al efecto), que considerando el caso circular y retirar la distancia entre los nodos que determinen el origen y el final.
Si necesitas alguna demostración que lo aclare, avisas y en cuanto saque un tiempo te hago algún boceto sencillo que lo refleje y demuestre...



También nota que el algoritmo aún no ha terminado. Terminaría cuando el nodo 20 (T), fuera la ciudad de origen...
Empezando por el nodo 4 (D), aún se localizan soluciones más cortas que empezando por A.
1 ---> DJPRFCQHMKEOALBSGITN   6769839
1 ---> DJPRFCQHNTIGSBLMKEAO   6745798
...dejarlo corriendo hasta Z llevaría muchas horas más, aunque como cada vez la solución temporal es más corta, se cortocircuita antes (cuando la suma parcial de nodos visitados superan ya esa distancia temporal), por lo que a medida que se encuentran soluciones corre más deprisa y necesita visitar menos nodos... el programa cuando lo pare (o a petición), muestra la cantidad de nodos recorridos (no cuenta los no visitados si los cortocircuita).
Lo dejaré funcionando unas horas más a ver que sale...



Por último, te recomiendo que hagas también las siguientes variaciones a tu algoritmo (pongo las más genéricas que podrían pedirte):
Y exponlas como parámetro, así una función general pública recibe los parámetros de entrada y una vez claro que se quiere hacer llama a una de las siguientes funciones privadas:
* Dado un nodo de origen, visitar todos los nodos y vuelta al origen      <---- esto es lo que tienes hecho.
- Dado un nodo de origen, visitar todos los nodos, pero sin requerir vuelta al origen.  <----- esta es la solución que yo te he presentado.
- Dado un nodo de origen y otro de destino visitar todos los nodos intermedios. <--- esta opción suele arrojar presumiblemente (obvio), una solución con mayor distancia que la previa, pero a menudo el origen y el destino están prefijados, luego debe considerarse).
- Hallar la distancia menor sin considerar un nodo de origen ni de destino <---- Esto es lo que está haciendo mi programa (mientras no lo pare). Esto suele requerirse cuando una operación ha de repetirse millones de veces, y entonces poder elegir la ruta más corta es lo óptimo cuando el acceso a un nodo de origen y de destino es indiferente... (suele ser el caso por ejemplo de muchas máquinas CNC, para dibujado, corte, soldadura, fabricación de microchips, etc...).

Hola es bastante interesante tu programa y el resultado que arroja.

El mio aplica al problema del viajante que incluye volver donde empezó y también incluye la necesidad o no de que sea completo el sistema; es decir que no haya conexiones entre ciudades que existan. Por ejemplo en un sistema de 10, llamemosle, ciudades, si todas se conectan entre si van a haber 45 trayectos; pero en mi programa no es necesario ese requisito.

Al final lo dejé corriendo hasta el final...

Cuando me fuí a dormir llevaba calculando alrededor de 24 horas y cuando me levanté (unas 6 horas después ya había terminado), con lo que ha tardado entre 24 y 30 horas (1 sólo núcleo 1'5Gh. el programa está en vb6, programado en NET sería bastante más rápido), pero vamos la idea de este programa no es la velocidad, si no la versatilidad de soluciones que puedo aplicarle y que cada cierto tiempo suelo ampliar.

El número de nodos visitados ha sido: 954.207.241.839 (casi 1 billón). En realidad aunque sea un número muy grande es mucho menor que todas las posibilidades que para 20 nodos (1*2*3*4*5*6*7*8*9... *19*20=  2.432.902.008.176.640.000 2'43Trillones ) .

Hay que añadir que usando fuerza bruta, todavía es posible evitar recorrer ciertos nodos por cortocircuito... para ello basta reordenar los pesos de mayor a menor... así cuanto antes una suma alcance y supere el valor menor actual, antes cortocircuita todas las derivaciones tras ese nodo. Es suficiente por tanto (para mi programa) con preparar los datos de entrada sin tocar nada del código... la desventaja en este caso es que las soluciones aparecerían 'desordenadas', aunque para lo que se pretende carece de importancia.

He aquí el resto de soluciones hasta el final...
1 ---> JDPFRCQHNTIGSBLMKEAO   6743168
1 ---> JDPRFCQHMKEAOLBSGITN   6736689
1 ---> JDPRFCQHMKEOALBSGITN   6638313
1 ---> JDPRFCQHNTIGSBLMKEAO   6614272
1 ---> JPDRFCQHNTIGSBLMKEAO   6611159 <--- Solución final mínima
1 ---> OAEKMLBSGITNHQCFRDPJ   6611159 <--- Solución final mínima
(estas dos últimas son iguales, porque el requisito era '< ó =' (interesa tener soluciones que sean iguales especialmente cuando sean la solución definitiva, si bien como se ve es el recorrido inverso... los recorridos inversos de las solucuones previas no aparecen porque antes de su tratamiento se alcanzó una solución menor).

- Revisando las soluciones se puede ver ciertas 'aglomeraciones' 'KEAO', 'GITN', 'LMBSG', etc... que van apareciendo contínuamente en cada solución con ligeras diferencias de orden. Lo que sugiere 'barriadas' de ciudades...
- Otra curiosidad es que todas las soluciones acaban (o empiezan si se considera las soluciones del revés), en unos pocos nodos específicos: O, S, J y N.

Sí, mi programa al operar con grafos, puedes evitar tmbiñén eso, sin tocar el código, si no solamente los datos de entrada. De hecho, 'codificar' correctamente los datos de entrada con los parámetros debidos es parte del problema, que uno debe saber resolver.

Si consideramos nodos a un ciruito completo (en mi caso  circuito cerrado), es decir cuando es una posible solucion siendo si es mayor o menor al costo encontrado hasta el momento, mi programa lo resuelve ese problema en 155 segundos aprox. analizando 12984 nodos, sobre un totoal de 19!/2, ya contempla la no repeticion de circuitos. es decir con la misma solucion podes empezar por cualquier ciudad.

Para las soluciones "mejores" q la mia y tu solucion optima, si le agregamos el trayecto para que sea circular, como resuelve mi programa, los resultados serian los siguientes:
8233366
8914050
8744122
8741260
8703954
8675986
8517919
8515057
8595825

Fijate que es mucho mayor que mi solucion, o sea que teniendo en cuenta un trayecto que no termine en el origen optimo (tu programa), y le sumamos el trayecto para que vuelva al origen supera por mucho a mi solucion, dejando la posibilidad a que si sea la mas optima mi solucion al problema planteado.

Sí. Por eso me pareció importante darte una cifra aunque sea aproximada del tiempo  empleado incluso aún siendo efectivo en no usar una 'fuerza bruta a ciegas' (que revisa todos los nodos sin ninguna optimización), Considera que a medida que aumente el número de nodos, el tiempo crece exponencialmente, de ahí el interés incluso por algoritmos heurísticos que aún no facilitando la solución óptima sea una aproximada, ya que el tiempo en tales casos se convierte en un requisito...

Sí y no...

Como ya te dije son dos problemas distintos, sus soluciones difieren (peneralmente) de modo considreable. Lo que difiere no es tanto el algoritmo, como la solución hallada. Me he tropezado con profesionales que interpretaron (y no solo por la mera conveniencia de la aproximación, como es el caso presente) que eran el mismo problema y que bastaba con romper o unir por el punto deseado ...tuve que demostrarles su error, pues insiitían en ello empecinadamente.
Es decir vale para decir 'la solución puede parecerse mucho a esto', dentro de cierta tolerancia, pero no para tomarla como solución.

Dado que ya me percarté de tu solución circular cuando llevaba varias horas en marcha, no quería retrasarlo más parando y volviendo a componer los datos. A ver si saco el fin de semana algo de tiempo libre y abordo el problema desde el caso circular comenzando desde el nodo A.

En realidad no es más complejo, para que mi programa lo trate circular, pues basta con añadir un nuevo nodo reetiqeutado como otro distinto pero con los mismos pesos que el nodo inicial y  añadirlo al final de todos, y exigirle que este sea además el último en la secuencia (como también lo es el primero), lo que consigue que sea circular... Aunque en tal caso, debe hacerse lo mismo para tratar cada nodo como el inicial (debe marcarse igulmente como el final), lo que fuerza a tratar los datos específicamente a cada caso... se puede automatizar por supuesto, pero dado que  solo son 20, se puede hacer manualmente, por otro lado dado que tu lo tienes empezando por el primer nodo (A), considerar de momento solo ese caso, resultará interesante. Es más que probable que tu solución sea la óptima, si no lo fuera, podrías revisar algún simple error, sino contuviere errores en el código pero no sacare la solución óptima, sería una heurística más, uy en ese caso habría que ver de entrar en competencia con las heurísticas actuales (nota que muchos lo mantienen en secreto, pensando que la solución final debe estar compuesto con parte de algoritmo que han creado y que solo les falta algún detalle que esperan encontrar en algún momento).

Nota que el hecho de sumar un tramo más, no solo incrementa el valor de ese tramo, sino que por lo general la solución suele ser menos óptima, ya que por 'fuerza' el último nodo que vuelve al origen está tan cerca del origen como los más próximos a él... En el caso que has presentado sumando (forzando la circulación uniendo el nodo final al inicial), no puede ser óptima, porque ese nodo final no garantiza que sea uno de los más próximos al inicial... para la solución más óptima de los casos no circulares, esto será (salvo casualidades y casos de simetría), casi siempre cierto.
 
Insisito por eso en que si tienes alguna intención de explotación o de propiedad intelectual debes acometer al menos esos casos que te comentaba, que son el mismo problema con ligeras perspectivas particulares, so pena de que cuando publiques, alguien los aborde y se apropie de dichos casos (porque tú no lo cubres). Nada más triste que alguien mueva cielo y tierra y luego otro que se limite a pegar una patada a una piedra (basándose en lo hecho: 'el estado actual del arte') y solo por ello sea quien se lleve la gloria.

Tenes razon que lo importante es ver el aumento de tiempo entre cantidad de "ciudades", es para definir que tan eficiente es. Es algo que tengo que comprobar bien.

Estoy pensando todavia como adaptar el programa como solucion al problema sin volver al origen. En este momento estoy teniendo tiempo libre, asi que voy a ver si puedo readaptarlo y cuando lo haga te muestro el resultado, que estimo sera el mismo que con tu programa, y el tiempo de ejecucion con la cantidad de nodos visitados.

Es totalmente cierto que ya 4 ojos ven mas que dos y este proyecto lo estoy haciendo solo. Segun toda la logica que utilice, para mi (de manera objetiva), resuelvo el problema de un circuito cerrado de manera eficaz.

Entre el tiempo de analisis de la solucion, pseudocodigos, codigo y pruebas llevo 5 años. En los cuales lo fui haciendo mientras tenia tiempo libre. Estimo que luego de hacer codigos, analizarlos y probarlos por el equivalente de un mes de trabajo 24/7, consegui que sea eficaz.

Espero que puedas adaptarlo al problema con vuelta al origen y ahi poder comparar de manera efectiva los resultados.

Ahora adapte el programa para tu caso. Como resultado fue el mismo, 6611159.
Tardo casi 12 minutos y analizo 15470 nodos.

Te agradezco mucho la colaboracion que estas haciendo y que me haces porque pude descubrir un par de falencias que tenia mi programa original y comparar mi programa modificado con el tuyo.

De forma absoluta será imposible establecerlo, pero interesará conocer tiempos para 10, 20, 30, 40, 50 ciudades y ver como evoluciona entre ellos. Por fuerza bruta en un pc llegado cierto número es inabordable.
 
Al margen de todo esto, cuando termines las adaptaciones a los diferentes problemas, deben también considerar la misma funcionalidad desde la perspectiva del paralaje, es decir ver de facilitar en pseudocódigo u diseño dle algoritmo para su tratamiendo en procesado paralelo. Los superordenadores, suelen agradecerlo... Aunque no es algo obligatorio, si conviene ver que tareas puedan ser concurrentes, pués eso facilitaría a los superordenadores hacer asumible millones de nodos, en un tiempo aceptable.


Cuando temrines de ampliar su funcionalidad y probar su eficacia, será el momento de intentar hacerlo más óptimo de cara a la velocidad, rediseñando cada parte.

Acabo de hacer los cambios al código y ya lo he puesto a calcular, para recorrido circular... cuando termine se podrá comparar los resultados.
He aprovechado para reordenar los nodos por pesos, así se cortocircuita antes, muchos pesos sobrepasan el valor de 1millon, y sabiendo que el recorrido mínimo ronda los 7 millones, supone que incluso se cortocircuitarán rutas con pocos nodos (lo que evita el recorrido que de ellos desciende hasta llegar a los 20 nodos con todas sus combinaciones). De hecho hay algunos pesos de incluso 2 millones.


Es normal. A cualquiera que le apasionen estas cosas, le dedica su tiempo... (a éste y otros problemas) yo suelo dedicarle cada año, 2 o 3 semanas de mi tiempo libre.
Creo en la posiblidad de la compresión infinita y también le suelo dedicar 2 o 3 semanas, también a los primos, etc...

---

p.d.: Acabo de pararlo, descubrí que al editar el orden de los nodos, me comí un dígito en uno de los pesos y un peso pasaba de 1.800.000 a solo 180.000, que muy probablemente podría falsificar la solución final...
Corregido vuelvo a ponerlo a funcionar.

Cuando es circular, no importa que nodo se ponga como el inicio, pues empezando por cualquier otro el recorrido sería el mismo. Es decir basta calcular como inicio un solo nodo, cuando finalice la solución es la que haya, aún así como no estaba presente cuando saltó al siguiente y no marqué el parámetro de finalizar al término del primer nodo, siguió calculando repitiendo la misma solución...


1 ---> AOELBSGITNFRCQHMKPDJA   9615287
1 ---> AOELBSGITNFRCQHMKJDPA   9611402
1 ---> AOELBSGITNFRCQHMPDJKA   9102210
1 ---> AOELBSGITNFRCPDJQHMKA   8587674
1 ---> AOELBSGITNFRCPJDQHMKA   8561109
1 ---> AOELBSGITNFRCDJPQHMKA   8551237
1 ---> AOELBSGITNFRDPJCQHMKA   8053919
1 ---> AOELBSGITNFRDJPCQHMKA   7983226
1 ---> AOEKLBSGITNFRDPJCQHMA   7846717
1 ---> AOEKLBSGITNFRDJPCQHMA   7776024
1 ---> AOEKLMHQCPJDRFNTIGSBA   7730384
1 ---> AOEKMHQCRDJPFNTIGSBLA   7708270
1 ---> AOEKMHQCRPJDFNTIGSBLA   7700976
1 ---> AOEKMHQCPDJRFNTIGSBLA   7611071
---------------------------------------------------------- Desde aquí son la misma solución en distinto orden (incluso al revés).
1 ---> AOEKMHQCPJDRFNTIGSBLA   7561324
1 ---> ALBSGITNFRDJPCQHMKEOA   7561324
1 ---> BLAOEKMHQCPJDRFNTIGSB   7561324
1 ---> BSGITNFRDJPCQHMKEOALB   7561324

La solución que ofreces queda constatado que es la solución real.

Mención aparte es que deberías hacer tu algoritmo más rápido.
Nota que mi programa aún teniendo utilidad diversa calcula unos 9-10 millones de nodos por segundo (y es un núcleo funcionando a 1'5Ghz). Aún suponiendo que el trabajo que tuviera que hacer por cada nodo fuera 100 veces mayor, seguirían siendo 90.000-100.000 nodos por segundo.
Tu dices que la solución la encuentras visitando unos 15.000-16.000 nodos, pero tarda unos 2 minutos, luego te sale que recorre 125-135 nodos por segundo, lo que es una velocidad muy baja. Por supuesto falta saber qué trabajo hay que hacer con cada nodo, pero estoy convencido que debe ser muy mejorable...

De las soluciones puestas arriba hasta la que suma: 7983226, fueron arrojadas apenas solté el botón de puesta en marcha, el resto ha ido apareciendo con las horas... Para según que cosas y casos (básicamente que precisen funcionar en tiempo real), una heurística con un valor de 7983226, que tarda menos de 1 sg en salir puede ser preferible a una solución exacta de 7561324, que tarde 2 minutos. Pero esto es solo cuando el tiempo de respuesta sea una premisa indispensable.
Aún así debes tratar de mejorar tiempos, entre x10 - x100.

Solo queria decirte que mi manera de resolverlo es diferente, pero eso visita pocas soluciones (mejores o no) en tanto tiempo.

Me interesaria saber si tu programa utiliza bastante memoria o no. Ya que por ejemplo las solucion con programacion dinamica si es necesario mucha memoria.

Estoy pensando como plantear una mejora en la eficiencia pero hasta ahora no lo logro.

Por lo menos mi programa es un paso mas para la eficacia y un paso menos para la posibilidad de demotrar P=NP, si asi lo fuera.

Mi programa usa muy poca memoria... apenas 2-6Mb. Depende de la cantidad de datos a introducir.
Aumenta poco más cuando pretendo que la salida vaya a fichero, y en ese caso mantengo en un buffer X entradas... (escribir a fichero las salidas una a una es costoso en tiempo, es preferible almacenarlas en un buffer y cuando se llene volcarlo de una tacada...)... al tiempo se van mostrando en un listado y cuando alcanza cierta cantidad se borran (excepto las últimas n entradas, y si se exige, antes de borrar se guardan a fichero).  Por eso fluctúa entre 2 y 6Mb. y puede que puntualmente en algún momento suba muy poco más.

Los datos (nodos) los almaceno simplemente en un array de estructura. En esa estructura un campo es Hijos() que es un array de otra estructura con el costo y un indice absoluto.
Adicionalmente la salida (temporal) se va guardando en una pila (guarda el indice absoluto del nodo, dicho índice es el que lo localiza en el array).

Los únicos datos intermedios que guarda es a través de la recursividad, de la función que ejecuta el cálculo, pero que como se operan con pocos nodos (20 en este ejemplo), el nivel de recursividad es muy limitado y tampoco se dispara el uso de la memoria.




Olvidaba decirte que si quieres probarlo bien deberás verificarlo con una buena cantidad de ejemplos y al caso hay una página buena con soluciones resueltas... los datos los dan en formato 'cordenadas 2D' (se suele indicar en cada fichero), es decir posición X e Y, por lo que requiere calcular distancias (euclídeas si fuera el caso de distancias Manhattan el mismo fichero debería señalarlo) y obliga a trabajar en algunos casos con coma flotante (en otros se trunca a enteros, lo que resulta más cómodo para deshacerse de los decimales)...

http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html
El caso que estamos tratando (en el hilo) es el que en esta página aparece el primero, el simétrico (A...Z = Z...A  .La distancia de un nodo a otro es igual a la distancia inversa del otro al uno).
Cada apartado suele terner 2 enlaces:
- El primer enlace te lleva a la página que hace de índice, donde constan enlaces a cada fichero con los datos de cada uno.
- El segundo enlace llerva a una página que contiene todas las soluciones para dichos problemas (puede que no todas sean correctas y sean solo las más próximas).
Los ejemplos los hay desde pocos nodos hasta miles de nodos, lo que da para poner a prueba prácticamente cualquier algoritmo.




Eso sí, si necesitas verificar 2 o 3 ejemplos más, pongamos de 10, 15 y 25 nodos avisa... te irá bien además de para verificar la solución como se comporta tu algoritmo en tiempos con la variación de nodos.
Más allá de 25 nodos, es muy probable que en un PC se eternice lo suficiente (con fuerza bruta, incluso cortocircuitando), como para desistir del intento... Aunque dando por entrada como valor un peso total superior en un 10-20% al valor que a ti te resulte, podría acotarlo todavía más, ya desde el principio, sin siquiera esperar a que se vaya optimizando la poda a medida que arroja resultados más cortos. ...Mientras no pase de 2 o 3 días de cálculo, por problema, no me importará echarte un cable.

Si por otro lado quieres ensayar muchas soluciones, y no depender de la lenta espera de respuestas por fuerza bruta, ni de copiar datos de aquí o de allá (sino generarlos rápidamente al azar) mira de implementar el algoritmo de Christofides, que es una heurística que se estima ofrece soluciones de alrededor de 3/2 de separación de la solución óptima.

p.d.: Añadidas algunas aclaraciones para evitar dudas.

Pude mejorar algo el programa para rendir mejor. Con el primer caso baje los 150 segundos a 50 segundos, visitando 26(en realidad son las mismas que antes, cerca de 13000. Pasa que puse una comprobacion previa a la final entonces ya me filtraban las que superaban a la que tenia guardada como mejor) soluciones (de las cuales se va quedando con la mejor hasta llegar a la mas optima)

Mi programa tambien se acorta si les pasas una solucion aproximada a la optima desde el principio.

Dale gracias, voy a probar con casos reales de 25 nodos (ahi te paso algun caso para ver como se comporta el algoritmo frente a otra cantidad de entradas).

Voy a empezar a probar con casos reales de n=30 tambien para ver como se comporta el programa.

Queria agregar que mientras busca el programa la mejor opcion va mostrando la mejor encontrada hasta el momento. por ej. si lo comparamos con una heuristica, mi programa encuentra la solucion de 7611071 en menos de dos segundos, antes de encontrar la optima (7561324)

Vaya, no me había dado cuenta... Al editarte en el mismo mensaje, no aparece como nuevo contenido pues no cambia la fecha de creación y la de edición no comporta su actualización en el hilo.

Como hace el mío... bien.
Pero ten en cuenta de procurar que el primer cálculo sea ya un valor no subóptimo. Imagina que fuera la ruta más larga, esto podría suponer una larga enumeración.

Yo por ejemplo, para obtener sobre ese de 20 nodos de forma rápida si ordenos los nodos (la adyacencia para cada nodo) de menor a mayor, me devuelve ya media docena de soluciones muy próximas, antes siquiera de soltar el botón del ratón, luego para llegar a la solución dada tarda algo menos de 5 minutos, si bien como es fuerza bruta (con poda), no tiene forma de saber si hay o no una solución más óptima por lo que hasta que no complete la búsqueda no puede garantizarse la solución (lógicamente si ya se conoce...).
En cambio si la entrada de datos se ofrece tal y como me la entregaste, entonces tarda todo el tiempo que te dije y la solución final aparecía alrededor de 18 horas tras su puesta en marcha (este equipo no es muy potente en comparación a los actuales, pero aú así el número de horas es significativo).

Te pongo los datos tal cual los envío como parámetro (para claridad de presentación aquí añado un '0' a la derecha para valores de 2 dígitos).

Nota que cada nodo queda así numerado alfanuméricamente:

A= B:064|C:041|D:082|E:099|F:093|G:161|H:099|I:116|J:060
B= A:064|C:069|D:044|E:105|F:130|G:200|H:150|I:174|J:122
C= A:041|B:069|D:062|E:058|F:062|G:133|H:081|I:108|J:066
D= A:082|B:044|C:062|E:071|F:111|G:177|H:139|I:169|J:127
E= A:099|B:105|C:058|D:071|F:055|G:110|H:091|I:125|J:108
F= A:093|B:130|C:062|D:111|E:055|G:071|H:036|I:071|J:070
G= A:161|B:200|C:133|D:177|E:110|F:071|H:067|I:081|J:121
H= A:099|B:150|C:081|D:139|E:091|F:036|G:067|I:035|J:054
I= A:116|B:174|C:108|D:169|E:125|F:071|G:081|H:035|J:059
J= A:060|B:122|C:066|D:127|E:108|F:070|G:121|H:054|I:059

Ahí el orden es el de los nodos: A,B,C,D...J y de esa forma tarda como dije más de 1 día...

En cambio reordenando los pesos para cada nodo y los propios nodos (según la suma d epesos que lo componen) y pasando esto como parámetro:

C= A:041|E:058|D:062|F:062|J:066|B:069|H:081|I:108|G:133
F= H:036|E:055|C:062|J:070|G:071|I:071|A:093|D:111|B:130
H= I:035|F:036|J:054|G:067|C:081|E:091|A:099|D:139|B:150
J= H:054|I:059|A:060|C:066|F:070|E:108|G:121|B:122|D:127
A= C:041|J:060|B:064|D:082|F:093|E:099|H:099|I:116|G:161
E= F:055|C:058|D:071|H:091|A:099|B:105|J:108|G:110|I:125
I= H:035|J:059|F:071|G:081|C:108|A:116|E:125|D:169|B:174
D= B:044|C:062|E:071|A:082|F:111|J:127|H:139|I:169|G:177
B= D:044|A:064|C:069|E:105|J:122|F:130|H:150|I:174|G:200
G= H:067|F:071|I:081|E:110|J:121|C:133|A:161|D:177|B:200
Nota que para cada fila los nodos están ordenados por pesos... y además las filas están ordenadas según la suma de los pesos de sus nodos, en ambos casos de menor a mayor, así la primera combinación hallada, se forma prácticamente con pesos muy bajos y por tanto poda exageradamente la cantidad de nodos a visitar... el comportamiento de la búsqueda de este modo, al final viene a ser muy equivalente a ciertas características (pero mucho menos compleja) que ofrece el algoritmo de Steinhaus.
...y de esta forma la solución aparece en menos de 5 minutos y la verificación completa en algo menos de 1 hora (creo recordar)...

Mira de aprovechar a introducir los datos siguiendo el mismo esquema de orden explicado (no hay necesidad de que identifiques los nodos a mi manera (id ':' peso'|'... etc), con tal que tras marcar el orden sigas pudiendo identificarlos correctamente), si ahora tienes podado cuando el peso acumulado supera el total menor hallado hasta el momento, esto acotará aún más con lo que ganarás muchísimo en tiempo (probablemente lo dividas entre 10 o más, y tanto más cuanto más nodos tenga).
Obviamente que sea así, va a depender del tipo ramificación y poda que esté efectuando tu algoritmo.

Olvidé señalar que los datos de los nodos y pesos que puse de ejemplo, no corresponden con los que me pasaste que con cifras tan grandes ocupa mucho ancho... pero que igualmente cualquier otra tabla de datos (como la presente más breve) cumple el cometido se servir de ejemplo por igual y con algo más de claridad si cabe...

---

Curioso... mi primer doble post forzado por la imposibilidad de editar el mensaje...  :laugh: :laugh: :laugh:

Te paso a comentar que basicamente mi algoritmo no se basa en ramificacion y poda. ademas lo puedo aplicar, con algunas variantes al codigo, a otros problemas del tipo np, cuales tambien resuelve, no tan eficientemente.

Por eso me es dificil encontrar una mejora en el tiempo de ejecucion aunque visite pocas soluciones.

Ok... Como el título del hilo lo lleva... pero he vuelto a releer tu primer mensaje y en efecto, la razón de ramificación y poda era que preguntabas para establecer diferencias y nada más.

Exactamente amigo, esa era mi intencion. Comparar un metodo conocido con el mio para ver si era "mejor" o no.

Por eso estaba averiguando los metodos conocidos que resuelven el problema y comprarlo con el mio. Pero ademas de los basados en ramificacion y poda no pude encontrar ningun otro.

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í.

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.

Ordenando carpetas, me encontré otra carpeta mal renombrada (y por tanto fuera de orden) donde tengo otro algoritmo que hice a comienzo de los 90, emplea una heurística muy diferente pero muy simple del que tiene como virtud los pocos nodos que precisa visitar. Es decir consigue un resultado muy rápidamente, por ejemplo para 20 nodos, apenas tarda 0'05-0'09sg. y visita solo unos cientos de nodos. Para 100 nodos apenas 0'3sg. y para 1000nodos solo 45sg. (en mi equipo que es viejo y no muy potente).

Ayer me puse a repasarlo para asegurarme que lo tenía completo y funcionaba bien, pues no dejé comentarios al respecto, y mientras lo migraba NET  (lo tenía en un viejo lenguaje) y para hacerlo más útil, lo fijé para usar un mapa finito (un área de 512x512), para crear los puntos aleatoriamente y poder dibujarlos (opcionalmente) en el mismo mapa sobre la marcha, a medida que encuentra rutas más óptimas.

Lo interesante de este algoritmo, es que puede ser usado como un primer paso para obtener una respuesta rápida, desde la cual partir con otro algoritmo más 'sesudo' (y más lento o consumidor de recursos), que es más adecuado para alcanzar un valor mucho más óptimo (repito cuando el número de nodos es mayor de unas pocas decenas).

La descripción de esta heurística es muy simple, se trata de ver si el intercambio entre dos nodos genera una ruta más óptima, en tal caso, se realiza el cambio.
Hay que proceder sistemáticamente no al azar, para que alcance en algún momento un punto de 'bloqueo' donde ya no se localizan mejoras con intercambios, momento en que  el algoritmo finaliza.
Un medio de optimizar las comparaciones es precalcular la ruta inicial (en general si no se ordenan 'geográficamente', el orden es el que subyace en el listado.
Así la idea de comparar el intercambio entre dos nodos asume la siguiente noción:

Nota que los nodos que se comparan son B e Y, así ABC es la ruta 'A a B' + 'B a C'.
Nota también que los intercambis, para ser exhaustivos, deben empezar a una distancia (entre B e Y) de numnodos/2, cuando a esa distancia no haya intercambios, se reduce la distancia hasta 2.

El intercambio de distancia 1, es muy similar, pero requiere aplicarse aparte, ya que si XYZ solapan en parte ABC (lo que sucede con distancia 1) BC y XY están tomando una distancia que ahora existe pero que de intercambiarse se rompe... luego no es adecuado hacer una comparación de sumas con solape de nodos. Puede resolverse a base de complicar el algoritmo con cada nodo a visitar, que lo hace subóptimo, en cambio si tratamos la distancia 1 en un bucle aparte, no hay esa pérdida de rendimiento en lógica extra ni hay que complicarse en resolver esa lógica extra.
El algoritmo principal sería:
La función CompararBY es ligeramente diferente de CompararBC, esta última impide solapes entre los nodos que falsifiquen la suma de las distancia.


Las variables, A,B,C, X, Y, Z,  K,D refieren al indice que ocupan en un array, y dichos índices son el indice del array de nodos. Yo uso una (clase) pila (más que nada porque se comparte entre todos los otros algoritmos), para éste, al caso se le ha añadido una propiedad Test (además de Push y Pop), para lectura y escritura no secuencial (algo como Peek y Poke) y con ello permitir el intercambio de índices cuando es aceptado. Ese array contiene pues los índices de la ruta a seguir, luego 'ruta.ToString' es tomar cada indice en el array separado por lo que prefieras una coma, un guión, etc... Si se busca más velocidad, el evento no es requerido, basta enviarlo cuando salga del bucle principal. Igualmente cuando se qiere revisar tiempos, se desactiva el dibujado, aunque el inicial y el final corren dentro del crono (al gusto pueden dejarse fuera).

Dos cuestiones a tener en cuenta son:
- Que el recorrido en el bucle debe ser circular, ya que si hay 20 nodos y A es el 19ª, B tendrá que ser el 0º y C el 1º, y si hay una distancia a aplicar de 8, entonces X será el 7º, Y el 8º y Z el 9º. Es decir el cálculo de índices debe recurrir al módulo de forma constante.
- Que puede hacerse un cálculo mucho más veloz si se mantiene en memoria una tabla con el mapa de las distancias, pero que solo es asequible cuando el número de nodos es tolerable.
Si se operara por ejemplo con 1 millón de nodos, entonces dicha tabla ocuparía en memoria los bytes que ocupen los datos de 1 billón. En tal caso en vez de mantener dicha tabla en memoria es preferible calcular cada vez la distancia ABC y XYZ, que al requerir potencias y raíz cuadrada (operando con la distancia de Euler), contínuamente hacen decaer la velocidad del algoritmo notablemente pero a cambio pueden abordarse problemas de varios miles de nodos (al pasarlo a NET sigue este modelo, en tanto que la versión que tenía en origen mantenía la tabla, pués lo tenía limitado a 100 nodos máximo).

Cuando se opera con una cantidad media de nodos (pongamos 100), lo que se observa es que opera bastante bien todos los nodos que están en el 'extraradio' del mapa, cometiendo en cambio 'torpezas' severas con nodos internos. La razón de esto es que solo ataca el intercambio de 2 nodos (esto es, la ruta de un nodo con sus 2 adyacentes), si el intercambio fuera comparando la distancia de 2 o más nodos (comparar dos nodos serían ABCD y WXYZ), se seguirían consiguiendo mejores resultados, tanto más necesario, cuando el número de nodos es mayor.
Se desprende (observando el mapa con los resultados) que este algoritmo apoyado por otro (tras éste) que operara mejor los nodos próximos entre sí lograría resultados muy óptimos en un tiempo muy rápido.

Es decir, lo más interesante de este algoritmo es que al ser tan rápido, puede ser la primera fase de otro más eficaz en el resultado. Llegar a cierto resultado óptimo, prontamente satisface la posibilidad para otro algoritmo más lento que opere a partir de donde éste lo deja.
De hecho es intuitivo que la programación dinámica puede asumirse como un intento de optimizar este tipo de situaciones.
Tu que sigues el esquema de programación dimámica ya te habrá quedado claro que si para algo como 20 nodos empleas (pongamos por ejemplo), 1-4Gb. de RAM, para uno de 30 nodos, seguramente te subas a 15 o 30Gb. y probablemente no puedas asumir problemas con más de 50 nodos sin sacrificar por algún lado, porque la RAM precisa será inasumible....
Este algoritmo al ser tan simple, el costo en RAM es pecata minuta, básicamente son unos pocos MB. que dependen de la cantidad de nodos y las estructuras asociadas, pués la parte principal como ya te de dicho es un simple array que mantiene los indices de los nodos que amntienen la ruta vigente.

A la noche me edito repaso el escrito y pongo imágenes...

Con pocos nodos (incluso con 20), suele encontrar la solución óptima o muy próxima, cuanto mayor es el número de nodos esa tendencia se pierde.
A la vista (tras dibujar el mapa), es observable que (cuando no consigue la ruta óptima), puede mejorarse fácilmente. Los humanos somos buenos visualmente para lograr heurísticas (difíciles de programar), pero con resultados muy cercanos al óptimo.
(https://ibb.co/kcbr7RT)
En la imagen adjunta, se observa como es mejorable la ruta si fuera del nodo 12 al nodo 2 y del nodo 13 al nodo 16.

El algoritmo de intercambio, se presta a muchas variaciones una que haré el próximo fin de semana, se explica muy bien justamente en la imagen de este ejemplo.
Se tendrá en cuenta para el intercambio, solo la distancia del segmento entre 2 nodos (en vez de los dos segmentos entre 3 nodos. Esto hace que la cantidad de cálculos sea menor, si bien la cantidad de nodos a visitar seguramente sea mucho más numeroso. Es importante implementarlo bien de otro modo se estaría operando con un algoritmo de fuerza bruta.
Al término incluso podría hacerse operar un algoritmo al término del otro, para determinar eficiencia y eficacia.

Cuando el número de nodos crece (por ejemplo, 100), es prácticamente imposible que arroje el resultado óptimo, como puede verse en esta imagen.
(https://i.ibb.co/JRrN05H/TSP-Itc-05-100.png)

Aquí un ejemplo para 1000 nodos, la imagen inicial con un costo total de 261.867, es reducida al final a solo 35.909, y para ello necesita visitar 9.105.000 nodos y realiza 5.506 intercambios.
La ruta inicial: 0,1,2,3,4,5,6 ... 997,998,999,0
(https://i.ibb.co/FK8mYkF/TSP-Itc-01.png)

...y el resultado al finalizar el algoritmo. Se ve como hay cruces largos entre puntos distantes, cruzando líneas, pero ha logrado reducirse notablemente de una forma muy simple y veloz.
(https://i.ibb.co/nntQFkK/TSP-Itc-02.png)

En esta sin recortar se muestra además los datos del resultado:
(https://i.ibb.co/s99CfXF/TSP-Itc-04.png)
Para 1000 nodos todavía es asequible usar una tabla de distancias (1 millón de elementos * 4 bytes = aprox. 4Mb.), así cada distancia se calcula una sola vez y se almacena, en un array bidimensional, con ello el algoritmo sería aún mucho más rápido que esos 45 segundos.
En cambio para 1 millon de nodos, requeriría aprox. 4Gb. y exigiría un PC con buena cantidad de memoria para encontrar ese espacio disponible contiguo (o ceñirse a otra estructura de datos no contigua).

Dibujando cada una d elas 5506 soluciones + la 'ruta.ToString', correspondientes, el tiempo se dispara a 458segundos. 10 veces más, es decir el tiempo se consume en el trazado más que en el cálculo, aunque es interesante verlo trabajar.
(https://i.ibb.co/pR2xXCB/TSP-Itc.png)

hola, hace tiempo que no me conecto por eso respondo ahora.


Mi algoritmo no sigue el esquema de programacion dinamica, uso el esquema de programacion lineal. por ende es practicamente nulo el uso de RAM.

Creo recordar que te había leído así, y... luego no me has corregido en ningún momento.

Haciendo uso del buscador, veo un hilo... aunque ahí claramente preguntas.
Supongo que al pasar el tiempo olvidé el detalle de que era una pregunta y asumí que era tu modelo.

Mi malentendido fue que utilizas heurística y por ende no siempre necesariamente puede dar el resultado optimo.

Como corrección a la cantidad de ciudades que recorre en el caso de las 20 ciudades son 100 millones, 10^8 (2500000 por segundo aproximadamente).
Usando Code Blocks y con 4 núcleos de 3.0 GHz.
Usa la fuerza bruta para hacer cortocircuito, por eso visita bastante menos ciudades.

Como use programación lineal puedo comprobar que, sea cual sea el caso, obtiene el resultado optimo.
Aunque para determinar O(n) dependeria de los casos, por ende necesitaria probar con casos representativos para obtenerlo.
Sea cual sea O(n) al ser obtenido por casos representativos no seria exacto, por ende no define la relacion entre P y NP