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

Microsiervos Selección


Nuevo mundo: Luna Apogeo II

EUR 2,99 (Reseña en Microsiervos)

Comprar


JPod

EUR 6,80 (Reseña en Microsiervos)

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