Problema del viajante de comercio - Branch and Bound

[jca1]

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)

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.

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

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.

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)

[Serapis]

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.

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)

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.

[Serapis]

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

[jca1]

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.

[Serapis]

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.

[jca1]

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.

[Serapis]

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.

[Serapis]

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:

Código [Seleccionar] Expandir


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] Expandir


//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] Expandir


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

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.