Imagen de portada

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

Marco Antonio Cruz Chávez, Pedro Moreno Bernal, Jesús del Carmen Peralta Abarca

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. 


Texto completo:

PDF

Referencias


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.


Enlaces refback

  • No hay ningún enlace refback.


_________________

ISSN impresa: 2007-1760

ISSN digital: 2448-9026

Inventio, la génesis de la cultura universitaria en Morelos, año 14, número 34, noviembre 2018-febrero 2019, es una publicación cuatrimestral editada por la Universidad Autónoma del Estado de Morelos (UAEM), a través de la Dirección de Publicaciones y Divulgación, Edificio 59, Galería de la Facultad de Artes, Campus Norte. Avenida Universidad 1001, colonia Chamilpa, CP 62209, Cuernavaca, Morelos, México. Teléfono +52 777 329 7900, ext. 3815. Página web: http://inventio.uaem.mx Correo: inventio@uaem.mx Editora responsable: Lic. Ana Isabel Yarto Wong. Reserva de Derechos al Uso Exclusivo No. 04-2009-093012081100-102. ISSN impresa: 2007-1760. ISSN digital: 2448-9026, otorgados por el Instituto Nacional del Derecho de Autor (Indautor). Responsable de la última actualización de este número: Gerardo Ochoa, Avenida Universidad 1001, colonia Chamilpa, CP 62209. Fecha de la última modificación: 25 de febrero de 2019.

Inventio está incluida en el Índice de Revistas Mexicanas de Divulgación Científica y Tecnológica del Conseio Nacional de Ciencia y Tecnología (Conacyt), en el directorio de Latindex (UNAM), en el repositorio de Dialnet (Unirioja), en el PKP Index (Public Knowledge Project), en Latinoamericana. Asociación de Revistas Académicas de Humanidades y Ciencias Sociales y en la Red Latinoamericana de Revistas Académicas en Ciencias Sociales y Humanidades (LatinREV).

Inventio publica artículos de divulgación que sean resultados de investigaciones originales desarrolladas por investigadores mexicanos y del extranjero. El contenido de los artículos que publica muestra la diversidad del pensamiento universitario y es responsabilidad de cada autor.

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.

International License Creative Commons