Coloquio de Matemáticas por: Pedro Lanzagorta

Resumen: En este coloquio se hablará sobre uno de los problemas más estudiados en el área de computación y matemáticas: el problema del agente viajero. Un problema NP-completo, cuya complejidad sobrepasa dramáticamente el poder de cualquier súper computadora creada por el hombre hasta la fecha. A lo largo de la sesión, se hablará sobre la historia de este problema, por qué es tan importante y qué herramientas se pueden emplear para resolver el problema en un contexto real.

Es un lunes a las 6 de la mañana en la caótica Ciudad de México. Eres el conductor de un autobús de transporte comunitario del ITAM. Tienes la ubicación de 40 alumnos que desean ser recogidos, todos ellos localizados en distintos puntos de la ciudad. Tu trabajo es pasar por cada uno de ellos y regresarlos a todos al ITAM antes de que el reloj marque las 7 y los profesores comiencen a tomar asistencia. Son casi las 6:30 y aún falta recoger a más de una decena de estudiantes. El tráfico está empeorando, parece que hubo un accidente. ¿Será está la mejor ruta? Miras el reloj y suspiras. Ojalá hayas elegido la mejor ruta de entre las 1.4x10^51 posibles.