Resumen
El presente trabajo incluye una introducción general que lo
enmarca dentro del contexto de la educación en matemáticas, basándose en
la consideración del derecho a la educación y la importancia de las
matemáticas como base del desarrollo de la humanidad. Ya entrando en el
tema principal se presentan los antecedentes del problema del viajante o
TSP. Se hace un recuento de la historia del problema, su importancia y su
formulación. Se relacionan algunas de sus muchísimas variaciones indicando
cómo afectan la formulación del problema y se enuncian varias de sus
aplicaciones en problemas de la vida cotidiana. Desde el punto de vista
matemático, se entra en el análisis de la complejidad del problema, sin
pretender realizar la prueba de que el TSP es NP-duro si se dan los
elementos para concluirlo y se presenta la descripción del proceso
realizado para su demostración en 1972. Finalmente se clasifican, explican
y comparan algunos de los algoritmos que han participado en la solución
del TSP, para terminar con las conclusiones.