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.htmlEl 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.
Mostrar Mensajes
