Problema del viajante de comercio - Branch and Bound

[Serapis]

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

[jca1]

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.

[Serapis]

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.

...también incluye la necesidad o no de que sea completo el sistema; es decir que no haya conexiones entre ciudades que existan.

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.

[jca1]

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.

[Serapis]

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,

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

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

[jca1]

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.

[Serapis]

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

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.

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.

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.

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.

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.

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

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.

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.

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.

[Serapis]

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.

[jca1]

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.

[Serapis]

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.