Utilize este identificador para referenciar este registo:
https://rinacional.tecnm.mx/jspui/handle/TecNM/3218| Título: | Estrategias de búsqueda local para el problema de SUMCUT |
| Autor: | Zamarron Escobar, Daniel Enrique. |
| Data: | 2013-06-01 |
| Editora: | Tecnológico Nacional de México |
| metadata.dc.publisher.tecnm: | Instituto Tecnológico de Ciudad Madero |
| Descrição: | En este trabajo de investigaci´on se aborda el problema de dise˜nar estrategias eficientes de b´usqueda local para el problema del SUMCUT. El SUMCUT es un problema NP-duro que consiste en minimizar la suma de los cortes de un grafo conexo; dicho problema tiene aplicaciones en la gen´etica, en la arqueolog´ıa y en la reducci´on de matrices dispersas. La contribuci´on m´as importante de este tra bajo consiste en cinco nuevas estrategias de b´usqueda local, la cuales incorporan mecanismos eficientes para la predicci´on del costo de una inserci´on consecutiva los cuales reducen la complejidad de las b´usquedas locales de O(n 3 ) a O(n 2 ). Para validar la eficiencia de las estrategias propuestas se desarroll´o una soluci´on metaheur´ıstica del problema SUMCUT, basada en una b´usqueda local iterada con procesamiento celular. Se realizaron pruebas experimentales con instancias est´andar, los cuales mostraron que para las instancias m´as grandes que las b´usque das locales propuestas, reducen el tiempo de ejecuci´on del algoritmo al menos un 90 % alcanzando el mismo nivel de calidad. Resultados parciales de este trabajo se incorporaron en el art´ıculo “Estrategias de b´usqueda local para el problema de SUMCUT”, el cual fue publicado en el VI Encuentro de Investigadores de Posgrado en el ´area de Ciencias Computacionales realizado en el Instituto Tecnol´ogico de Ciudad Madero los d´ıas del 10 al 14 de diciembre del 2012. |
| metadata.dc.type: | info:eu-repo/semantics/masterThesis |
| Aparece nas colecções: | Maestría en Ciencias de la Computación |
Ficheiros deste registo:
| Ficheiro | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| G11070004_donacion_tesis_bib.pdf | 820.92 kB | Adobe PDF | Ver/Abrir |
Este registo está protegido por copyright original. |
Este registo está protegido por Licença Creative Commons
