Hoy estudiaremos en clase el problema del viajante de comercio (TSP, Travelling Salesman Problem), un conocidísimo problema NP-difícil, y veremos una solución de programación dinámica.

Hay una página web del Georgia Tech (Georgia Institute of Technology) dedicada a este problema (ver este enlace) que contiene mucho material útil e interesante. Aunque también contiene cosas inútiles… por ejemplo, podéis encontrar una aplicación para iPhone/iPad que sirve para generar un recorrido del viajante de comercio a partir de una foto (generando primero un conjunto de puntos en la foto que servirán como vértices del grafo a visitar por el viajante). La foto de arriba es un ejemplo del resultado.