texto:   A-   A+
eliax

Proponen solución óptica al "Vendedor Viajante" en matemáticas
eliax id: 3646 josé elías en ago 10, 2007 a las 08:29 AM (08:29 horas)
Toda persona que haya tomado un curso en donde se toque el tema de combinaciones y permutaciones es posible que conozca el famoso problema matemático que en Inglés se bautizó como "The Traveling Salesman Problem" ("El Problema del Vendedor Viajante").

Este famoso problema postula que es extremadamente difícil calcular la ruta óptima para que un vendedor visite varias ciudades cuando estas ciudades están a distancias diferentes unas de otras. El problema, tan sencillo como parece, es en realidad extremadamente difícil (en términos matemáticos se le considera "NP-Complete / NP-Hard", o "NP-Difícil"), y cualquier solución aproximada que se utiliza hoy día es utilizada con mucho orgullo por sus creadores.

Lo interesante de este problema es que tiene implicaciones bien prácticas en la vida cotidiana, pues es el problema que a diario empresas como FedEx, UPS o DHL deben resolver para optimizar la ruta que sus camiones de entrega hacen entre los varios destinos que visitan a diario. Se estima que cualquier mejora en ese algoritmo significa millones de dólares en ahorros para tales empresas debido a que ahorran tiempo (lo que significa mas tiempo para poder entregar mas paquetes), así como ahorro de combustible.

Lo mismo aplica para lineas aéreas, que deben optimizar el uso de sus aviones para que estén en el aire lo mas tiempo posible, pues mientras mas vuelan mas dinero generan.

Pues ahora los científicos Tobias Haist y Wolfgang Osten acaban de proponer una solución al problema que puede resolver cualquier escenario en tiempo cuadrático (en vez en tiempo polinomial).

Lo interesante de su propuesta es que la hicieron totalmente como un "experimento mental" (al estilo como los que hacía Einstein y con el cual descubrió la Teoría de la Relatividad), y mas asombroso aun que lo resolvieron con un dispositivo óptico, en donde los patrones de los fotones de luz dan la respuesta al problema para cualquier pregunta que se le haga.

Según ellos, si tienes suficiente fotones como para que sean al menos NN fotones ( en donde N es la cantidad de ciudades), entonces el problema se puede resolver.

Enlace al abstracto su propuesta (incluyen un enlace a un PDF con su estudio mental detallado)

autor: josé elías

Comentarios

  • [c&p] Toda persona que haya tomado un curso en donde se toque el tema de combinaciones y permutaciones es posible que conozca el famoso problema matemático que se bautizó como "El Problema del Vendedor Viajante". Este famoso problema postula que es extremadamente difícil calcular la ruta óptima para que un vendedor visite varias ciudades cuando estas ciudades están a distancias diferentes unas de otras. En términos matemáticos se le considera "NP-Complete / NP-Hard", o "NP-Difícil".

Añadir Comentario

tu nombre
tu email
(opcional)
web personal
(opcional)
en respuesta a...
comentario de caracteres máximo
2 + 1 = requerido (control anti-SPAM)
¿De qué color es el cielo?: requerido (control anti-SPAM)
 

"1...0...0...1
No se si reír o llorar
"

por "yo mismo" en abr 2, 2014


en camino a la singularidad...

©2005-2019 josé c. elías
todos los derechos reservados
como compartir los artículos de eliax