Tesis "Caracterización del Problema de Minimización de Ancho de Banda"
Alumno: Nelson Rangel Valdéz
Asesor: Dr. José Torres Jiménez
El estudio de Fenómenos de Transición de Fase (FTF) en el área de Inteligencia Artificial (IA) comenzó aproximadamente hace 30 años, cuando el fenómeno descubierto en el problema de Satisfactibilidad fue relacionado con los FTF que ocurren con imanes, en materia condensada. Hoy en día, los trabajo de investigación hechos sobre FTF y problemas de IA encuentran aplicación en la caracterización de la dureza de las instancias de problemas, en la generación de casos de prueba que sirvan como punto de referencia para la comparación de algoritmos, y en el diseño de mejores resolvedores.
El trabajo de investigación que se desarrolló presenta una metodología general para la identificación del FTF en problemas en IA. Esta metodología sirvió como base para la identificación empírica del FTF en el problema de Minimización de Ancho de Banda en Grafos(MABG). El trabajo desarrollado muestra evidencia empírica de que las instancias generadas a partir del valor crítico del parámetro de control son en promedio las más difíciles, en comparación con instancias generadas para otros valores. La evidencia empírica se obtuvo a través de un algoritmo exacto y fue ratificada por medio de algoritmos aproximados. Finalmente, se llevó a cabo un análisis teórico sobre la existencia de otro FTF en MABG y que se relaciona con el fenómeno identificado de forma empírica.