Arte TSP

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.

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.

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.

http://www.cgl.uwaterloo.ca/~csk/projects/tsp/

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.

300x300_logo

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios .




UPV/EHU
ZTF-FCT

Q2006 A2016

facebook facebook

Premio a la Mejor Entrada de marzo del Carnaval de Física 2014: El lago elgygytgyn (por Marta Macho)
Premio Mejor Post en la VII Edición del Carnaval de Humanidades..Gracias a Marta Macho
Premio a la Mejor Entrada de la Edición 4.1231 del Carnaval de Matemáticas.

Egutegia | Calendario

octubre 2013
L M X J V S D
 123456
78910111213
14151617181920
21222324252627
28293031  

Artxiboak | Archivo

Estatistika | Estadística

  • 5.433.933 sarrerak | visitas

RSS Noticias UPV/EHU

  • Se ha producido un error; es probable que la fuente esté fuera de servicio. Vuelve a intentarlo más tarde.

RSS UPV/EHU Albisteak

  • Se ha producido un error; es probable que la fuente esté fuera de servicio. Vuelve a intentarlo más tarde.

RSS Eventos UPV/EHU

  • Se ha producido un error; es probable que la fuente esté fuera de servicio. Vuelve a intentarlo más tarde.

RSS UPV/EHU Ekitaldiak

  • Se ha producido un error; es probable que la fuente esté fuera de servicio. Vuelve a intentarlo más tarde.
Follow on WordPress.com

A %d blogueros les gusta esto: