TY - JOUR AU - Cruz Chávez, Marco Antonio AU - Moreno Bernal, Pedro AU - Peralta Abarca, Jesús del Carmen PY - 2021/09/07 Y2 - 2024/03/28 TI - Aplicación de la teoría de la complejidad en optimización combinatoria JF - Inventio JA - inventio VL - 10 IS - 20 SE - Narraciones de ciencia y tecnología DO - UR - https://inventio.uaem.mx/index.php/inventio/article/view/324 SP - 35-42 AB - <p>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.</p> ER -