Trabajo Fin de Grado
Análisis experimental de heurísticas para el problema del viajante de comercio
Autor/es | Verde López, José María |
Director | Romero Jiménez, Álvaro |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2018-01 |
Fecha de depósito | 2018-07-25 |
Titulación | Universidad de Sevilla. Grado en Matemáticas |
Resumen | El Problema del Viajante de Comercio es un problema de optimización de tipo NP-duro cuyo objetivo es, dado un conjunto de puntos y la distancia entre cada par de ellos, encontrar el camino más corto que pase por todos ellos ... El Problema del Viajante de Comercio es un problema de optimización de tipo NP-duro cuyo objetivo es, dado un conjunto de puntos y la distancia entre cada par de ellos, encontrar el camino más corto que pase por todos ellos y empiece y acabe en el mismo punto. Este problema aparentemente tan sencillo esconde una gran complejidad a la hora de afrontarlo, pues a medida que va aumentando el número de puntos nos damos cuenta de que resolverlo por fuerza bruta es en vano. Debido a esto y a la importancia de sus aplicaciones se han realizado numerosos estudios acerca del problema, centrados normalmente en el diseño de heurísticas con el n de reducir el tiempo de cálculo de soluciones. En este Trabajo de Fin de Grado se ha llevado a cabo la implementación en el lenguaje de programación Haskell de varias de esas heurísticas y de un algoritmo de fuerza bruta con el objetivo de hacer al nal de la presente memoria un análisis experimental comparativo de la e ciencia de cada uno de estos algoritmos. |
Cita | Verde López, J.M. (2018). Análisis experimental de heurísticas para el problema del viajante de comercio. (Trabajo Fin de Grado Inédito). Universidad de Sevilla, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Verde López José María TFG.pdf | 486.1Kb | [PDF] | Ver/ | |