next up previous contenido
Next: Conclusiones Up: Presentación de los Previous: Resultados para los


Comparación de resultados con los otros métodos de cálculo de reversibles

El proceso aquí propuesto ha obtenido los mismos resultados comparado con el algoritmo de Hillman para los casos (3,h) y (4,h), en el caso del (5,h) Hillman obtuvo con su algoritmo de Hillman 385 clusters mínimos, sin embargo al parecer la forma de definir sus clusters fué diferente a la presentada en este escrito por lo que con una posterior revisión de los mismos que Hillman está haciendo actualmente se espera que concuerde con nuestros resultados.

Cabe señalar las grandes semejanzas que existen entre el algoritmo que Hillman desarrolló y el proceso que aquí se expone, ya que las tablas que Hillman produce en su proceso para los posibles ancestros de una cadena en realidad pueden ser vistas como las coordenadas donde aparecen en la matriz de conectividad de la misma y la concatenación que hace él de tablas para obtener los ancestros de cadenas de mayor longitud es similar a multiplicar matrices de conectividad para obtener otras matrices de cadenas de mayor longitud.

Sin embargo la implementación del algoritmo de Hillman debe tomar en cuenta almacenar todas las tablas que se vayan formando conforme crezca la longitud de las cadenas a revisar y realizar comparaciones entre el grupo de tablas de ancestros para las cadenas de longitud n con las tablas para cadenas de longitud menor.

En el proceso presentado en este trabajo la recursión nos permite no tener que guardar las matrices de conectividad conforme se vayan generando (esta tarea se deja al compilador) y no se tienen que realizar comparaciones de una matriz de conectividad con las demás de cadenas de longitud menor, sino que usamos el criterio de los índices de Welch para saber si las matrices de conectividad manifiestan un mapeo global reversible, de hecho la implementación de Hillman podría mejorarse agregando estas mismas condiciones y evitando hacer comparaciones entre tablas, por ejemplo, Hillman dice que cada tabla debe tener el mismo número de elementos que el resto, ésto no es más que aplicar el concepto de multiplicidad uniforme, la comparación que hace entre tablas podría evitarse si mejor en cada tabla checara que una columna tuviera L elementos distintos y en la otra R elementos distintos, la condición que establece que solo una pareja debe ser formada por elementos iguales es revisar que solo exista un único ciclo permitido para generar la cadena; así se tendría que para cada tabla , por lo que M=1.

De esta manera mientras que el algoritmo de Hillman tarda en calcular las reglas reversibles de un ACL(5,h) más de 13 horas, la implementación que se expone aquí con una programación muy simple tarda menos de 5 minutos, y se espera todavía mejorar este tiempo.

En el caso del algoritmo que usa índices de Welch, el tiempo de cálculo no es muy diferente, sin embargo este proceso solo contemplaba ACLR donde un renglón estuviera formada por elementos todos iguales entre sí, cosa que no siempre sucede para los reversibles.

 


next up previous contenido
Next: Conclusiones Up: Presentación de los Previous: Resultados para los


Seck Tuoh Mora Juan Carlos
E-mail:seck@delta.cs.cinvestav.mx