admin

Categorías

Coobis

Algoritmos

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

 

Algoritmo aplicable al software actual que iguala en velocidad a la computación cuántica

¿Imposible? No tanto, al menos en teoría tal y como revela el siguiente estudio, liderado por John Watrous, en el Instituto de Computación Cuántica de Waterloo en Ontario, Canadá. Hasta ahora, todos entendíamos la computación cuántica como el siguiente nivel para la informática, aquella que ofrecería un rendimiento y velocidad duplicado al actual y que formaría parte del “día después” a la Ley Moore. Quizá este estudio nos viene a decir que no estaba todo dicho con respecto a lo que la informática “clásica”, actual, se refiere.

El estudio de los investigadores afirma que, al menos en ciertos problemas, la informática clásica puede igualar la velocidad final de una computadora cuántica de trabajo. Este curioso resultado surgió del propio estudio del rendimiento en la computación cuántica. Watrous y el resto de científicos encontraron que un algoritmo poco utilizado en el software de hoy podría proporcionar un nuevo nivel de rendimiento de resolución de problemas en los ordenadores tradicionales, que a la vez, podría coincidir, en teoría, a la velocidad obtenida por los ordenadores cuánticos. Watrous lo explicaba así:

Estamos poniendo mucho dinero en la construcción de ordenadores cuánticos, pero no debemos subestimar el poder de los algoritmos. Una consecuencia clara y notable de esta caracterización implica que la computación cuántica no proporciona ningún aumento de potencia de cálculo alguno sobre la informática clásica. Al menos en el contexto de sistemas de demostración interactiva

Una vez conformado el singular hallazgo y con el fin de establecer el estudio. Los investigadores utilizaron el algoritmo para evaluar el potencial de velocidad en computación clásica. En este caso se utilizó para el desarrollo dos tipos de investigación matemática: la optimización combinatoria y la teoría del aprendizaje. El resultado viene a decir que un algoritmo proporciona una forma de resolver un problema usando procesos paralelos. Para Watrous es sorprendente, ya que:

Nunca se ha considerado en un ambiente paralelo. Teníamos que demostrar que este método podría ser en paralelo, y hasta ahora jamás se había realizado. Podemos tratar de de construir ordenadores cuánticos para resolver problemas, pero también podríamos simplemente diseñar nuevos algoritmos para resolver problemas

Actualmente no existen ordenadores en el mercado comerciales, de computación cuántica. IBM y otras compañías sí están empezando a desarrollar las tecnologías de lo que será la informática del futuro, empezando por los elemento básicos. Para que os hagáis una idea del desarrollo de este descubrimiento, se podría emplear el algoritmo en la informática comercial, en programas de software o en el ámbito de la programación que busca resolver problemas de optimización.

Fuente:  Bitelia

Bajo una licencia Creative Commons

__________________________

Enlaces de interés:

Nuevo material que supone avance en la computación cuántica.

Actualidad informática: Científicos de Frontera. Cirac

¿Logaritmos, el nuevo punto flotante?

Related Posts with Thumbnails

Calendario

diciembre 2024
L M X J V S D
« Nov    
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

Spam

Otros enlaces

  • Enlaces

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


  • Paperblog

    autobus las palmas aeropuerto cetona de frambuesa