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

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.

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.

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.

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.