admin
EnglishFrenchGermanItalianPortugueseRussianSpanish

Categorías

Coobis

problema del viajante

Algoritmo genético para resolver el problema del viajante

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.

Ampliar en:  microsiervos





Algoritmo genético





your browser sucks

 

El problema del viajante

Actualidad Informática. El problema del viajante. Rafael Barzanallana. UMU

El problema del viajante consiste en encontrar el camino más corto que permite visitar una serie de ciudades conectadas por carreteras volviendo al punto de partida y visitando cada ciudad una sola vez. No hay ningún algoritmo eficiente para resolver este problema (que es NP-duro) . En 1950 los ordenadores permitían resolver un problema con 50 ciudades, en 1980 con unas 2300 ciudades y en 2006 se alcanzó el récord actual, 85900 ciudades (en la figura aparecen 13509 ciudades de EEUU). Los informáticos han tratado de descubrir algoritmos eficientes que aproximen la solución del problema. En 1976, Nicos Christofides (Imperial College, Londres) desarrolló un algoritmo eficiente que produce caminos cuyo coste excede al óptimo en menos del 50%. ¿Se puede mejorar? En 2011, se logró mejorar el algoritmo de Christofides con un nuevo algoritmo eficiente que excede del óptimo en menos del 49,99999999999999999999999999999999999999999999999996 por ciento. ¿Por qué ha costado tanto obtener una ventaja tan pequeña? Nadie lo sabe, pero resulta muy sugerente. Nos lo cuenta Erica Klarreich, “Computer Scientists Take Road Less Traveled. After decades without progress, new shortcuts are discovered in the traveling salesman problem,” Simons Foundation, Jan 29, 2013.

Fuente:  Francis (th)E mule Science’s News

Related Posts with Thumbnails

Calendario

agosto 2019
L M X J V S D
« Nov    
 1234
567891011
12131415161718
19202122232425
262728293031  

Lo más visto

  • Infografía: espectro electromagnético y sus aplicaciones - 12.205 views
  • Las ecuaciones de la física en la vida cotidiana - 9.136 views
  • Evolución del logo de Windows - 7.935 views
  • Versiones de éxito y fracaso de Windows - 7.221 views
  • Transistor óptico - 7.174 views
  • Evolución de los microprocesadores Intel - 6.942 views
  • El método científico, ejemplo con plantas - 6.823 views
  • Cómo pueden las ondas de radio atravesar las paredes - 6.619 views
  • Historia gráfica del universo desde el Big Bang - 6.597 views
  • Comparación humorística de navegadores de internet - 6.451 views

Spam

Otros enlaces

  • Enlaces

    Este blog no tiene ninguna relación con ellos, ni los recomienda.


  • Paperblog

    autobus las palmas aeropuerto cetona de frambuesa