Por @Alvy — 30 de Agosto de 2014

Tsp-Red

El problema matemático del viajante (en inglés: Travelling Salesman Problem, TSP) es un clásico en el mundo de los algoritmos: encontrar la ruta más corta posible que visite cada ciudad una sola vez en un mapa, regresando a la ciudad de origen.

Como es de suponer, esto tiene miles de aplicaciones prácticas, pues también es un ejemplo de optimización y muchos problemas de otros campos pueden considerarse –matemáticamente– equivalentes. Si existiera un algoritmo definitivo no solo se podría ahorrar combustible y tiempo en los viajes, también optimizar cómo colocar los libros en una gran biblioteca o recorrer una calle para dejar los sobres de correo.

Por desgracia no existe un algoritmo definitivo: aunque a veces se puede encontrar la mejor solución si aumenta el número de nodos (en este caso: «ciudades») la complejidad del problema crece sobremanera; al cabo de un tiempo es fácil ver que no hay forma de probar todas las posibles soluciones ni de demostrar que una sea mejor que otra. Y aunque existen algoritmos parciales o para casos concretos –que son los que se utilizan en la práctica– debido entre otras cosas a que se sabe que es un problema NP-difícil (NP-hard) encontrar una forma de hacerlo supondría un gran avance matemático.

En la imagen un programa llamado Parano utiliza un algoritmo genético para resolver el TSP, mostrando visualmente los avances a medida que se producen: una forma original de resolverlo aunque probablemente no la óptima.

Compartir en Flipboard Compartir en Facebook Tuitear

PUBLICIDAD

Microsiervos Selección


Cero. Biografía de una idea peligrosa

EUR 28,00 (Reseña en Microsiervos)

Comprar


El gen egoísta

EUR 14,15 (Reseña en Microsiervos)

Comprar


Gödel, Escher, Bach: Un Eterno y Grácil Bucle

EUR 15,15

Comprar


Amazon Associates

Los productos aquí enlazados están a la venta en Amazon. Incluyen un código de Afiliado Amazon Associates que nos cede un pequeño porcentaje de las ventas. Los productos están seleccionados por los autores del blog, pero ni Amazon ni los editores de los libros o fabricantes de los productos participan en dicha selección.

Más libros y productos en:

Microsiervos Selección