Francis (th)E mule Science's News

Dibujo20130325 travel salesman - 13509 cities with more than 500 people in USA 1998

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 [1]). 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% [2]. ¿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 [3]. ¿Por qué ha…

Ver la entrada original 125 palabras más

Acerca de albertoarceti
Administrador de sistemas informáticos, y erps en la industria farmacéutica.

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: