Título :	Algoritmos de Ruteo en Superficies de Embaldosados Rectilíneos
Autor:	Fidel González Gutiérrez
Palabras clave :	Ingeniería y Tecnología Ciencias Tecnológicas Ciencia de los Ordenadores
Fecha de publicación :	31-ene-2023
Editorial :	Informática
Facultad:	Facultad de Informática
Prográma académico:	Doctorado en Ciencias de la Computación
Resumen:	Se estudia el problema de ruteo en superficies de embaldosados rectilíneos. Formalmente el problema consiste en, dado un rectángulo R dividido en rectángulos de tamaño 1 x 2 (dominós), encontrar un conjunto de aristas sobre la periferia de R y dominós, interconectadas y libres de ciclos (árbol o corredor) que conecten todos los dominós desde un punto de acceso sobre la periferia de R, y cuya longitud total sea la mínima. Así planteado, es un subproblema del problema del Corredor de Longitud Mínima (MLC), el cual es NP-completo, y en consecuencia no existe algoritmo eficiente que produzca soluciones óptimas. Por lo que el objetivo es diseñar algoritmos de ruteo en superficies de embaldosados rectilíneos utilizando una metodología basada en la técnica de diseño greedy que produzcan un corredor de longitud total mínima. Para ello, se diseñan familias de instancias de embaldosados para el análisis experimental de los algoritmos de ruteo. Se presentan varias técnicas para la enumeración de embaldosados en general, a la vez que se utiliza una metodología de acuerdo a la técnica de backtracking para la generación de familias de embaldosados con dóminos no isomorfos y libres de corte de tamaño 6 x 5, 6 x 7, 6 x 8, 6 x 9, 6 x 10 y 7 x 8. Sobre dichas familias, se lleva a cabo el análisis experimental de cuatro heurísticas, midiendo su rendimiento y la solución, bajo los criterios de conectar primero: dominós más cercanos, dominós más alejados, vértices compartidos (mejorado), vértices internos (usando reducción). Las heurísticas se implementan en ©Mathematica versión 11.3.0.0 en una computadora MacBook Pro con un CPU de 2.6 GHz Intel Core i7 con 6 núcleos y 16 GB de memoria RAM. Como resultado del análisis experimental se establece que existen cotas inferior y superior para la longitud total del corredor, entre las cuales se encuentra la solución óptima. Asimismo, se establece que la heurística basada en el criterio de conectar todos los vértices internos, de acuerdo a los algoritmos de Kruskal y Prim, y enseguida llevar a cabo un proceso de poda para eliminar conexiones redundantes de dominós, produce los corredores de menor longitud total dentro de las cotas inferior y superior en el menor tiempo de ejecución. Los resultados se encuentran publicados en las revistas indexadas Revista de la Ingeniería Industrial y Visum Mundi
URI :	https://ri-ng.uaq.mx/handle/123456789/8245
Aparece en las colecciones:	Doctorado en Ciencias de la Computación

Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.