Por favor, use este identificador para citar o enlazar este ítem: https://ri-ng.uaq.mx/handle/123456789/8245
Registro completo de metadatos
Campo DC Valor Lengua/Idioma
dc.rights.licensehttp://creativecommons.org/licenses/by-nc-nd/4.0es_ES
dc.contributorArturo González Gutiérrezes_ES
dc.creatorFidel González Gutiérrezes_ES
dc.date2023-01-31-
dc.date.accessioned2023-05-19T19:24:40Z-
dc.date.available2023-05-19T19:24:40Z-
dc.date.issued2023-01-31-
dc.identifier.urihttps://ri-ng.uaq.mx/handle/123456789/8245-
dc.descriptionSe 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 Mundies_ES
dc.formatAdobe PDFes_ES
dc.language.isospaes_ES
dc.publisherInformáticaes_ES
dc.relation.requiresSies_ES
dc.rightsAcceso Abiertoes_ES
dc.subjectIngeniería y Tecnologíaes_ES
dc.subjectCiencias Tecnológicases_ES
dc.subjectCiencia de los Ordenadoreses_ES
dc.titleAlgoritmos de Ruteo en Superficies de Embaldosados Rectilíneoses_ES
dc.typeTesis de doctoradoes_ES
dc.creator.tidcurpes_ES
dc.contributor.tidcurpes_ES
dc.creator.identificadorGOGF670818HMNNTD09es_ES
dc.contributor.identificadorGOGA690910HNLNTR09es_ES
dc.contributor.roleDirectores_ES
dc.degree.nameDoctorado en Ciencias de la Computaciónes_ES
dc.degree.departmentFacultad de Informáticaes_ES
dc.degree.levelDoctoradoes_ES
Aparece en las colecciones: Doctorado en Ciencias de la Computación

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
RI007397.pdf15.61 MBAdobe PDFVista previa
Visualizar/Abrir
Mostrar el registro sencillo del ítem


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