Arte TSP

#HaceTresAños 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.

http://www.cgl.uwaterloo.ca/~csk/projects/tsp/images/zebra.pdf 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.

Ver la entrada original 319 palabras más

Anuncios

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 )

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 )

Google+ photo

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

Conectando a %s


A %d blogueros les gusta esto: