Implementación paralela de un algoritmo genético para resolver el problema del agente viajero
Date
2017-09
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
"El problema del agente viajero o TSP por sus siglas en inglés (Traveling Salesman Problem) es ampliamente estudiado en el área de las Ciencias de la Computación, ya que se considera como un problema difícil de resolver, denominándose en un lenguaje computacional como NP completo [1], es decir, es un problema para el que no se puede garantizar que se encontrará la solución en un tiempo de cómputo razonable. Entre mayor sea el tamaño del problema, en este caso, cuanto mayor sea la cantidad de ciudades mayor será el tiempo que tardará una computadora en calcular o encontrar la solución. Si bien el origen del problema no se conoce con exactitud, algunas versiones remontan su origen en el año de 1832. Surgiendo en una guía de agentes viajeros de recorridos a través de Alemania y Suiza, sin embargo, en un inicio el problema carecía de un análisis matemático como lo conocemos hoy en día. La primera ocasión que fue estudiado por matemáticos fue durante los años de 1930 en Viena y Harvard, destacándose Karl Menger, quien definió el problema mediante el algoritmo de fuerza bruta".
Description
Keywords
Citation
Collections
Document Viewer
Select a file to preview:
Can't see the file? Try reloading