Algorítmica y complejidad computacional. Un caso de A5 (60 vértices) sin osbtrucciones pero con obstáculos.

1.Estoy poniendo a prueba el método de la escalera con este caso, que que me sirve para testar varios temas:

–una de ellas es que lo habíamos diseñado y aplicado siempre para casos con una involución y este no tiene involuciones.

–otra es que lo habíamos diseñado y aplicado para búsqueda de ciclos y este caso no tiene ciclos.

—otra es que lo hemos diseñado y aplicado a casos con obstrucciones y este solo tiene obstáculos en uno de los VFs.

–y finalmente quiero ver si hacer el método por los dos ciclos añade algo. Pienso que así es.

En las primeras pruebas ha funcionado bien (es decir se puede aplicar) con la salvedad que lo he aplicado para buscar ciclos cuando este caso no los tiene (x Rankin). Me he dado cuenta más tarde :-(.

Una conclusión es que el método, al margen del potencial problema de complejidad computacional que hemos señalado en anteriores entradas necesita ser pulido. Para aplicarlo de momento hay que invertir mucha inteligencia natural y hay que ir automatizando criterios de decisión. Esto no lo veo complicado,pero necesita un cierto tiempo.

The spiderweb

Como hemos explicado en múltiples entradas anteriores la base para el método de la escalera, es el conocimiento de como determinadas propiedades estructurales del dígrafo (básicamente retorcimiento y entrelazado; todavía no tengo claro si la propiedad de entrelazado de ciclos se puede incluir en este esquema ni como hacerlo) afectan a sus propiedades de hamiltonicidad. No se le podría haber ocurrido a nadie que no conozca los efectos de estas propiedades estructurales. El  método nos proporciona un test (pensamos  que rápido) para determinar si un caso tiene obstrucciones o no.

2.Es el caso que en su momento fue mi favorito. Aunque es entangled puede tener recorridos hamiltonianos (RHs, en este caso caminos) en los dos vértices finales posibles (VFs). Pero en uno de los VFs se encuentran fácilmente y en el otro (en aquel en el que el caso se muestra entangled) son escasos y se encuentran con dificultad. Por lo tanto el caso tiene obstáculos pero no obstrucciones. Es lo que lo hace interesante.

Nota. Hay un primer motivo por el que el encontrar un RH en un VF puede ser más complicado que en el otro, que no tiene nada que ver con la propiedad de entangled. En el complicado ya se han activado de partida más IASes por el generador de orden menor (C3), y esto hace que queden menos opciones de activación. En otras entradas con otros casos ya hemos  explicado claramente lo que añade el ser entangled.. Fin de nota.

Cuando digo que es complicado para un VF se de lo que hablo pues lo busqué  manualmente y me exigió un backtraking superprofundo. Retamos al lector a buscarlo manualmente. El backtraking se puede evitar, como hemos demostrado en anteriores entradas.

El caso es que hoy tenía que recuperar estos RHs que tanto me costó encontrar y pensaba que guardaba las copias de este trabajo manual pero las tiré, cosa que me sorprende, o no las encuentro, cosa que no me sorprende :-). Y lo he buscado con el programa que hice.

Con el programa en los dos VFs lo encuentra rápidamente (el tamaño de 60 vértices es pequeño) pero en el fácil lo encuentra directamente sin backtraking tras cuatro opciones en unos 25 segundos y en el complicado los encuentra tras 24 opciones y con un backtraking profundo (11 llamadas de backtraking) y tarda 1 minuto y 25 segundos.

Me gustaría ver como funcionan los algoritmos de las tesis sobre las que hemos comentado en las anteriores entradas para este caso, el VF complicado.

Realmente el backtraking, con este tamaño no puede ser demsiado profundo. En teoría es de 2^(|V|/|IAS|)= 2(5!/2/5)=2^(60/5)=2^12 = 4096, pero en realidad es menos, pues con el control de los ciclos al final el backtraking es bastante menor.

A continuación el RH fácil (VF=42563) y luego el complicado (VF=64352).

{vi, {2, 3, 5, 6, 4}, {2, 3, 6, 4, 5}, {6, 4, 5, 2, 3}, {5, 2, 3, 6, 4}, {3,
6, 4, 5, 2}, {4, 5, 2, 3, 6}, {4, 5, 3, 6, 2}, {4, 5, 6, 2, 3}, {6,
2, 3, 4, 5}, {6, 2, 4, 5, 3}, {6, 2, 5, 3, 4}, {5, 3, 4, 6, 2}, {4,
6, 2, 5, 3}, {4, 6, 5, 3, 2}, {4, 6, 3, 2, 5}, {3, 2, 5, 4, 6}, {5,
4, 6, 3, 2}, {6, 3, 2, 5, 4}, {2, 5, 4, 6, 3}, {2, 5, 6, 3, 4}, {2,
5, 3, 4, 6}, {3, 4, 6, 2, 5}, {3, 4, 2, 5, 6}, {3, 4, 5, 6, 2}, {5,
6, 2, 3, 4}, {5, 6, 3, 4, 2}, {5, 6, 4, 2, 3}, {4, 2, 3, 5, 6}, {3,
5, 6, 4, 2}, {6, 4, 2, 3, 5}, {6, 4, 3, 5, 2}, {3, 5, 2, 6, 4}, {2,
6, 4, 3, 5}, {4, 3, 5, 2, 6}, {5, 2, 6, 4, 3}, {5, 2, 4, 3, 6}, {4,
3, 6, 5, 2}, {6, 5, 2, 4, 3}, {2, 4, 3, 6, 5}, {3, 6, 5, 2, 4}, {3,
6, 2, 4, 5}, {2, 4, 5, 3, 6}, {5, 3, 6, 2, 4}, {5, 3, 2, 4, 6}, {2,
4, 6, 5, 3}, {6, 5, 3, 2, 4}, {3, 2, 4, 6, 5}, {3, 2, 6, 5, 4}, {6,
5, 4, 3, 2}, {4, 3, 2, 6, 5}, {2, 6, 5, 4, 3}, {5, 4, 3, 2, 6}, {5,
4, 2, 6, 3}, {2, 6, 3, 5, 4}, {3, 5, 4, 2, 6}, {4, 2, 6, 3, 5}, {6,
3, 5, 4, 2}, {6, 3, 4, 2, 5}, vf}

{vi, {4, 5, 6, 2, 3}, {4, 5, 2, 3, 6}, {4, 5, 3, 6, 2}, {3, 6, 2, 4, 5}, {2,
4, 5, 3, 6}, {2, 4, 3, 6, 5}, {2, 4, 6, 5, 3}, {6, 5, 3, 2, 4}, {3,
2, 4, 6, 5}, {4, 6, 5, 3, 2}, {5, 3, 2, 4, 6}, {5, 3, 4, 6, 2}, {5,
3, 6, 2, 4}, {6, 2, 4, 5, 3}, {6, 2, 5, 3, 4}, {6, 2, 3, 4, 5}, {3,
4, 5, 6, 2}, {5, 6, 2, 3, 4}, {5, 6, 3, 4, 2}, {5, 6, 4, 2, 3}, {4,
2, 3, 5, 6}, {3, 5, 6, 4, 2}, {6, 4, 2, 3, 5}, {2, 3, 5, 6, 4}, {2,
3, 6, 4, 5}, {6, 4, 5, 2, 3}, {5, 2, 3, 6, 4}, {3, 6, 4, 5, 2}, {3,
6, 5, 2, 4}, {5, 2, 4, 3, 6}, {4, 3, 6, 5, 2}, {6, 5, 2, 4, 3}, {6,
5, 4, 3, 2}, {4, 3, 2, 6, 5}, {2, 6, 5, 4, 3}, {5, 4, 3, 2, 6}, {3,
2, 6, 5, 4}, {3, 2, 5, 4, 6}, {5, 4, 6, 3, 2}, {6, 3, 2, 5, 4}, {2,
5, 4, 6, 3}, {4, 6, 3, 2, 5}, {4, 6, 2, 5, 3}, {2, 5, 3, 4, 6}, {3,
4, 6, 2, 5}, {3, 4, 2, 5, 6}, {2, 5, 6, 3, 4}, {6, 3, 4, 2, 5}, {4,
2, 5, 6, 3}, {4, 2, 6, 3, 5}, {6, 3, 5, 4, 2}, {5, 4, 2, 6, 3}, {2,
6, 3, 5, 4}, {3, 5, 4, 2, 6}, {3, 5, 2, 6, 4}, {2, 6, 4, 3, 5}, {4,
3, 5, 2, 6}, {5, 2, 6, 4, 3}, vf}

P.s.1. Realmente no  me satisface el resultado, estos dos únicos RHs. Para lo que busco necesitaría conocer todos los que terminan en los dos VFs. Y el algoritmo no lo tengo programado para esto.

P.s.2. Extraigo de una presentación la siguiente diapositiva que me parece informativa sobre un tema sobre el que había oído hablar muy de pasada y que no visualizaba bien.

¿ Realmente se utiliza el TSP para resolver este tipo de problemas en la  práctica biológica ?. Lo  dudo…

Anuncios

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: