Aplicación de la teoría de la complejidad en optimización combinatoria
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.
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial 4.0.
Esta revista proporciona acceso abierto inmediato a su contenido, con base en el principio de ofrecer al público un acceso libre a las investigaciones para contribuir a un mayor intercambio global de conocimientos. Se distribuye bajo una licencia Creative Commons Reconocimiento-NoComercial 4.0 Internacional License.
