El problema del viajante de comercio –Traveling Salesman Problem o TSP– es un problema muy conocido en teoría de complejidad computacional:
Dado un conjunto de ciudades, un vendedor debe visitarlas todas pasando una sola vez por cada una de ellas y regresando al punto de partida. Se trata de encontrar la ruta óptima, la que minimiza el recorrido.
Figura 1: TSP Art por Craig S. Kaplan http://www.cgl.uwaterloo.ca/~csk/projects/tsp/images/zebra.pdf
El TSP está entre los problemas denominados NP-completos, es decir, es un problema que no se puede resolver en tiempo polinómico en función del número de ciudades que el viajante debe recorrer.
El TSP Art es la versión artística del TSP. ¿De qué se trata? Se selecciona una imagen, se eligen algunos puntos y se conectan entre ellos… pero se conectan teniendo en mente el TSP.
Figura 2: Smileyland
http://www.oberlin.edu/math/faculty/bosch/making-tspart-page.html
En el ejemplo de la figura 2, en la imagen del centro , hay 2006 puntos, y se puede pensar que marcan las 2006 ciudades del reino de Smileyland. Si se piensa en el TSP en este feliz país, hay 2005! –el factorial de 2005… no se trata de una exclamación– posibles recorridos a investigar, algo imposible de realizar…
En 2003, la artista Adrianne Herman y el matemático Robert Bosch iniciaron su incursión en el arte TSP usando un sistema de cuadrículas que precisaba la elección de muchos puntos para que se produjera una imagen final decente.
En 2004, el profesor Craig S. Kaplan tuvo la idea de utilizar un sistema denominado weighted Voronoi stippling, un sistema de punteado que precisa menor cantidad de puntos que el utilizado por Herman y Bosch, y con el que los paseos del viajante de comercio resultan ser más orgánicos. En la página de Kaplan dedicada al arte TSP podéis encontrar sorprendentes imágenes generadas paseando y buscando el recorrido más económico.
Figura 3: Pingüinos de Craig S. Kaplan
http://www.cgl.uwaterloo.ca/~csk/projects/tsp/
Tras fijar el punteado de partida, se utiliza el Concorde TSP Solver, un programa creado para resolver el TSP simétrico y otros problemas de optimización: aparece entonces una aproximación del recorrido óptimo del viajante (tercera imagen en la figura 2) por la ciudad de Smileyland…
Más información:
- Craig S. Kaplan y Robert Bosch, TSP Art, en Renaissance Banff: Bridges 2005: Mathematical Connections in Art, Music and Science, 301-308, 2005 [pdf].
- TPS Art de Robert Bosch
- TPS Art de Craig S. Kaplan
Visto en Le blog-notes mathématique du coyote
Esta entrada participa en la edición 4.1231056 del Carnaval de Matemáticas cuyo blog anfitrión es Scientia.
ztfnews.wordpress.com 
Reblogueó esto en Martams's Blogy comentado:
#HaceTresAños Arte TSP
Me gustaMe gusta