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.
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.
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
...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.
En esta sin recortar se muestra además los datos del resultado:
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.
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:
Código [Seleccionar]
suma = recorridoinicial
...
...
...
buleano = Funcion CompararBY(entero A, entero distancia, inout entero suma, inout entero B, inout entero Y)
suma1 = ABC + XYZ
suma2 = AYC + XBZ
Si (suma2 < suma1)
suma = (suma - suma1 + suma2) //actualizar suma
devolver TRUE //al retorno se hace el intercambio cuando devuelve true.
fin si
fin funcion
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:
Código [Seleccionar]
//Heuristica de Intercambios de dos nodos:
suma = recorridoinicial //ABCDEFGH...
Hacer
intercambios = false
bucle para distancia desde (numnodos/2) hasta 2 retrocediendo de 1 en 1
Hacer
cambios = false
bucle para k desde 0 a numNodos-1
Si CompararBY(k, distancia, suma, B, Y)= true
intercambiar B con Y
cambios = true
numIntercambios +=1
evento Reportar(ruta.tostring, suma, numIntercambios)
fin si
numVisitados +=1
siguiente
intercambios = (intercambios or cambios)
Repetir mientras cambios=True
siguiente
// aquí el bucle para distancia =1
Hacer
cambios = false
bucle para k desde 0 a numNodos-1
Si CompararBC(k, suma, B, C)= true
intercambiar B con C
cambios = true
numIntercambios +=1
evento Reportar(ruta.tostring, suma, numIntercambios)
fin si
numVisitados +=1
siguiente
intercambios = (intercambios or cambios)
Repetir mientras cambios=True
Repetir mientras intercambios=TRUE
La función CompararBY es ligeramente diferente de CompararBC, esta última impide solapes entre los nodos que falsifiquen la suma de las distancia.
Código [Seleccionar]
// Distancia=1, es preciso mantenerse aparte para evitar solapes en la suma de distancias (sin complicar el algoritmo y que ello redunde en lentitud).
buleano = Funcion CompararBC(entero A, inout entero suma, inout entero B, inout entero Y)
suma1 = AB + CD // BC = CB (si es el problema del TSP simétrico).
suma2 = AC + BD // luego, la suma de estos está retirado
Si (suma2 < suma1)
suma = (suma - suma1 + suma2) //actualizar suma
devolver TRUE //al retorno se hace el intercambio cuando devuelve true.
fin si
fin funcion
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.
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.
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.
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
...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.
En esta sin recortar se muestra además los datos del resultado:
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.
