RT info:eu-repo/semantics/bachelorThesis
T1 El problema del viajante con grafos
A1 Crehuet Lucas, Ismael
A2 Universidad de Valladolid. Facultad de Ciencias
K1 Problema del viajante
K1 Algoritmo de Christofides
K1 Complejidad computacional
AB Este Trabajo Fin de Grado en Matemáticas aborda el problema del viajante, un problema clásico de optimización combinatoria que responde a la siguiente pregunta: dada una lista de posibles ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible para visitar cada ciudad exactamente una vez y al finalizar regresar a la ciudad origen? El problema es modelizado mediante grafos, cuya teoría se desarrolla a lo largo del trabajo. El problema del viajante es muy difícil de resolver en la práctica de forma efectiva y en un tiempo razonable, a pesar de la apariencia del mismo. Debido a ello, se desarrolla la teoría de la complejidad computacional y se utilizan algoritmos aproximados para su resolución, siendo el de Christofides el principal algoritmo de resolución empleado en elpresente trabajo.
YR 2022
FD 2022
LK https://uvadoc.uva.es/handle/10324/57985
UL https://uvadoc.uva.es/handle/10324/57985
LA spa
NO Departamento de Algebra, Geometría y Topología
DS UVaDOC
RD 06-jul-2024