Aplicación de la teoría de la complejidad en optimización combinatoria

Autores/as

  • Marco Antonio Cruz Chávez Profesor e investigador, Centro de Investigaciones en Ingeniería y Ciencias Aplicadas (Ciicap), UAEM
  • Pedro Moreno Bernal Doctorado en Ingeniería y Ciencias Aplicadas, Centro de Investigaciones en Ingeniería y Ciencias Aplicadas (Ciicap), UAEM
  • Jesús del Carmen Peralta Abarca Profesora e investigadora, Facultad de Ciencias Químicas e Ingeniería (FCQeI), UAEM

Resumen

Existen problemas cuya solución computarizada puede tardar años en obtenerse, como el problema del ‘agente viajero’. Éste tiene aplicación real en empresas que necesitan reducir costos de transporte o el problema de la mochila donde debe maximizarse la carga de objetos en ésta, sin exceder el peso permitido. Este problema se aplica, por ejemplo, en empresas que requieren almacenar una gran cantidad de productos. Para todos los problemas existe al menos un algoritmo de solución. El proceso de los programas de solución de problemas y las dos variables para medir el rendimiento de éstos –memoria ocupada y tiempo de ejecución–, son analizadas en este artículo . Por otro lado, se proporciona una descripción de la teoría de la complejidad de acuerdo con la máquina de Turing y su impacto en la investigación computacional. Finalmente, se destaca el caso de la uaem, donde se han diseñado y aplicado heurísticas computacionales, para obtener soluciones a problemas como el ruteo vehicular.

Citas

Augusto Cortez, “Teoría de la complejidad computacional y teoría de la computabilidad”, RISI. Revista de Investigación de Sistemas e Informática, vol. 1, núm. 1, 2004, pp. 102-105, http://bit.ly/1ol5a2N, consultado en marzo de 2014.

Christos H. Papadimitriou y Kenneth Steiglitz, Combinatorial optimization. Algorithms and complexity, Dover Publications, Nueva York, 1998, p. 351.

Enrique Alba, “Experiencias paralelas (en la solución de problemas complejos)”, 9º Congreso Internacional de Cómputo en Optimización y Software 2012, 27 al 30 de noviembre de 2012, Cuernavaca, http://bit.ly/1kUScsx, consultado en marzo de 2014.

Laureano Santamaría Arana y Alejandro Rabasa Dolado, Metodología de programación. Principios y aplicaciones, ECU, San Vicente, 2004, p. 8.

Luis Joyanes Aguilar e Ignacio Zahonero Martínez, Algoritmos y estructuras de datos. Una perspectiva en C, McGraw-Hill Interamericana, Madrid, 2004, pp. 33, 44.

Manuel Alfonseca Moreno, “La máquina de Turing”, Números, Las matemáticas del siglo XX: una mirada en 101 artículos, núms. 43-44, 2000, pp. 165-168, http://bit.ly/OX1cmP, consultado en marzo de 2014.

Michael R. Garey y David S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, Macmillan Higher Education, Nueva York, 1979, pp. 10, 13.

R. C. Y. Castañeda, Estudio comparativo de diversos métodos de solución al problema del agente viajero (PAV), tesis de maestría, Universidad de las Américas Puebla (UDLAP), Cholula, pp. 1-3, http://bit.ly/1fWgz8A, consultado en marzo de 2014.

Sanjeev Arora y Boaz Barak, Complexity theory. A modern approach, Cambridge University Press, Nueva York, 2009, pp. 40-41.

Aplicación de la teoría de la complejidad en optimización combinatoria

Descargas

Publicado

2021-09-07

Cómo citar

Cruz Chávez, M. A. ., Moreno Bernal, P., & Peralta Abarca, J. del C. (2021). Aplicación de la teoría de la complejidad en optimización combinatoria. Inventio, 10(20), 35–42. Recuperado a partir de http://inventio.uaem.mx/index.php/inventio/article/view/324

Número

Sección

Narraciones de ciencia y tecnología